In our last post we described the new API of Solver Foundation 3.0 for non-linear models. In particular we described the new API for the Compact Quasi Newton (CQN) solver. We also showed how to model and solve non-linear models using the solver interface. To do this it is necessary to introduce a delegate for getting the value of your goal function and a delegate for setting the gradient to your function. In today’s post we will see how to use Solver Foundation Services to model your problem, without needing to specify derivatives. Solver Foundation Services uses Automatic Differentiation to specify gradient information, so you don’t have to.
Just like in our last post, we consider the Rosenbrock optimization problem. We will again use a multi-dimensional variant where each variable is coupled just with one other variable.
The steps for modeling and solving non-linear models with Solver Foundation Services are exactly the same as those for any other model type. The model abstraction provided by Solver Foundation Services works just as well. The basic steps are:
1. Create a SolverContext and a model.
2. Define your model. This includes the Decisions and the Goal, which is a function of those Decisions. Note that only unconstrained, unbounded models can be solved with CQN, so no constraints are specified.
3. Solve the model and optionally report the solution.
Let’s see how those steps are carried out with Solver Foundation Services:
1. Create a Solver context and a model.
SolverContext context = SolverContext.GetContext();
Model model = context.CreateModel();
2. Next, you need to define your model. The model always includes definitions for Decision/s and a Goal. In this example it makes sense to use an indexed decision, as the Goal term involves some pattern over some index. We will define a Set, a Decision which is indexed by the Set, and a Goal which will be defined with our function to minimize.
const int dimensions = 100;
const int alpha = 100;
// Create a Set which the decision will be indexed with
Set dimensionsSet = new Set(Domain.IntegerRange(1, dimensions), "set");
// Create just one decision, indexed by dimensionsSet
Decision decision = new Decision(Domain.Real, "x", dimensionsSet);
// Add the decision to the model
model.AddDecision(decision);
// Define the goal. Note that we use ForEachWhere operator, as we only want to go throgh half of the indexes
model.AddGoal("theGoal", GoalKind.Minimize, Model.Sum(Model.ForEachWhere(
dimensionsSet, /* the set */
(index) => alpha * (Model.Power((decision[2 * index] - decision[2 * index - 1] * decision[2 * index - 1]), 2)) +
(Model.Power(1 - decision[2 * index - 1], 2)), /* the math expression */
(index) => index <= dimensions / 2 /* the condition */
)));
3. Solve the model with the appropriate directive (for this problem the default call will use the CQN solver as well) and optionally report the solution.
var directive = new CompactQuasiNewtonDirective();
var sol = context.Solve(directive);
var report = sol.GetReport() as CompactQuasiNewtonReport;
// From the report you can get details of the solution such as:
// report.TotalTime;
// report.IterationCount
// Print out all solution information
Console.WriteLine(report);
Running the code, the output is :
===Solver Foundation Service Report===
Date: 12/3/2010 2:40:51 PM
Version: Microsoft Solver Foundation 3.0.1.0 Enterprise Edition
Model Name: DefaultModel
Capabilities Applied: NLP
Solve Time (ms): 39
Total Time (ms): 243
Solve Completion Status: LocalOptimal
Solver Selected: Microsoft.SolverFoundation.Solvers.CompactQuasiNewtonSolver
Directives:
CQN(TimeLimit = -1, Tolerance = 1E-07, IterationsToRemember = 17, IterationLimit = 2147483647)
Solver solution quality: LocalOptima.
Iteration count: 22.
Evaluation call count: 28.
Tolerance difference: -2.63557088810946E-08.
===Solution Details===
Goals:
theGoal: 4.72745153676104E-21
Decisions:
x(2): 1.00000000001197
x(1): 1.00000000000559
x(4): 1.00000000001197
x(3): 1.00000000000559
x(6): 1.00000000001197
x(5): 1.00000000000559
.
Well, that’s it! All you need to do is define your goal in an abstract, mathematical way, and the rest (including automatic differentiation for the solver) is done by the Solver Foundation Services.
So, it is very easy and more mathematically descriptive to model your non-linear model with Solver Foundation Services. Also, it is easier to use a third party solver if for example you do need to add constraints to your model. What are the disadvantages? In which cases you would better off using the solver API? You should consider using the solver API in one of the following cases:
- Your goal function needs a math operator that is not currently supported in Solver Foundation Services.
- Your model’s dimension (number of Decisions) is very high. Mostly because of the automatic differentiation takes place, using Solver Foundation Services has larger memory footprint, so huge models might benefit from modeling directly against the solver. It depends heavily in the function itself, but around 100,000 Decisions you may consider switching to solver API.
- High dimensionality also effect the time performance, mainly as for the automatic differentiation. If time measure is highly important to you, and your problem is not small, you should at least experiment with the solver API to see if it helps.
-Solver Foundation Team