Hey, did you know that Solver Foundation can solve unconstrained nonlinear optimization problems? Yep, it's true. Few people know about it because 1) we haven't talked about it too much and 2) it is not accessible from the SFS (which means you can't use OML or the Excel add-in to solve such problems). To use the solver you need to work with a solver object directly. The Samples directory contains a simple example, but since there has been a couple of requests I thought I would give a slighly more involved example.
The CompactQuasiNewtonSolver class solves unconstrained optimization problems: it finds the minimum (or maximum) of an unbound objective function f(x). x is an array of doubles, and f needs to be twice differentiable. The CQN solver uses the L-BFGS algorithm. Like other implementations, you need to provide a function that will serve up the function value and gradient on demand, given the variables x. To do that, set the GradientAndValueAtPoint property to a delegate that fills in the gradient, and returns the function value. You'll also need to specify a starting point.
The CompactQuasiNewtonSolver has a Solve method that takes a solver parameters object. It has a few interesting properties, including the solver tolerance and maximum iteration count. On construction you can also pass in an "abort" delegate. This function will be called periodically during the course of execution - if you return true then the solver will return. In my sample below, I abuse it to print out the progress of the solver as it proceeds. Note that I would have liked to have used solver.NumberOfIterations rather than keeping track of the number of calls myself. That's a bug, and it will get fixed in our 2.1 release.
The function can have as many variables as you like. In my example I am minimizing a multidimensional variant of the Rosenbrock function, a standard test problem. You can modify the code to use your own objective function by modifying the ValueAndGradient method. You can also learn more about the solver by consulting the Solver Programming Primer (page 24 or so).
using System; using Microsoft.SolverFoundation.Solvers; namespace Microsoft.SolverFoundation.Samples { /// <summary> Minimizes the generalized Rosenbrock function, a standard test case /// in nonlinear optimization. You can read more about the Rosenbrock /// function here: /// http://en.wikipedia.org/wiki/Rosenbrock_function /// </summary> public class Rosenbrock { public static void Main(string[] args) { int n = 4; // make sure I'm even, see below. double[] x = new double[n]; for (int i = 0; i < x.Length; i++) { x[i] = -1; } CompactQuasiNewtonSolver solver = new CompactQuasiNewtonSolver(n); int iterationCount = 0; CompactQuasiNewtonSolverParams param = new CompactQuasiNewtonSolverParams(() => { Console.WriteLine("{0} | {1:e6}", /*solver.NumberOfIterations*/ iterationCount++, solver.ToleranceDifference); return false; } ); solver.SetStartingPoint(x); solver.GradientAndValueAtPoint = (GetGradientAndValueAtPoint)ValueAndGradient; solver.Minimize = true; var solutionQuality = solver.Solve(param); Console.WriteLine(); Console.WriteLine("Solution quality = " + solutionQuality); Console.WriteLine("f(x) = " + solver.SolutionValue); solver.GetSolutionPoint(x); for (int i = 0; i < x.Length; i++) { Console.WriteLine("x[{0}] = {1}", i, x[i]); } } /// <summary>Get the function value and gradient for the specified point. /// </summary> /// <param name="x">The point at which the value and gradient should be computed.</param> /// <param name="gradient">The gradient vector, the same size as x.</param> /// <returns>The function value.</returns> private static double ValueAndGradient(double[] x, double[] gradient) { // The gradient and value are both computed inside the method for efficiency. // It's also possible to refactor value and gradient calculation into submethods. double value = 0; for (int j = 0; j < x.Length; j += 2) { double t1 = 1.0 - x[j]; double t2 = 10.0 * (x[j + 1] - x[j] * x[j]); gradient[j + 1] = 20.0 * t2; gradient[j] = -2.0 * (x[j] * gradient[j + 1] + t1); value += t1 * t1 + t2 * t2; } return value; } } }
My wife gave birth to a healthy baby daugther last night! Mom, baby, (and dad) are all doing well. I will be spending some time at home with the newest addition to our family, so I will go easy on the blog posts for awhile. When I come back I will do one on our nonlinear solver, more about Solver Foundation 2.0, and finish up my QAP series.
I'm pleased to announce the release of Solver Foundation 2.0, available at solverfoundation.com. We've added capabilities that allow Solver Foundation to solve important categories of optimization problems, improved the performance and stability our existing solvers, and improved our Visual Studio and Office tools to make model building and analysis easier. Here are a few of the highlights:
Excel 2007 add-in. We have completely overhauled the Excel 2007 add-in to make it easier to build, debug, and deploy models. Here is a screenshot from the new add-in:
As you can see, the building blocks of a model (Parameters, Decisions, Goals, Constraints) are built through a more task-centered user-interface, reducing the need for hand-coding OML. Data binding has been simplified, and decision (output) data binding is now supported. Models can include random parameters and recourse decisions to build stochastic models. Finally, the add-in now features the ability to deploy models directly to C# (for use within a Visual Studio project) or to OMLX (for use within SharePoint for server-side calculation). We're trying to simplify the modeling process and bridge the gap between modelers, developers, and business decision makers. Export to C# is this easy:
Simulation and stochastic programming. I previewed our stochastic modeling and solving features in a previous post. It is now possible to include random parameters in OML or SFS code to build stochastic models. Solver Foundation includes powerful sampling engines and decomposition techniques to solve large stochastic models quickly, and provides reporting information that tells you how the uncertainty affects the model.
MIP performance improvements. The new Gurobi 2.0 solver is included as the default MIP solver in Solver Foundation. The Gurobi solver's performance and functionality has been improved in a number of important ways, as described here. The combination of Solver Foundation Services' clean, powerful managed code API and Gurobi's world-class MIP solver gets even better in our 2.0. Our own in-house, purely managed MIP solver has been greatly improved as well.
Second Order Conic Programming. As I mentioned in this post, Solver Foundation 2.0's interior-point solver is now capable of solving large-scale second order conic programming models. SOCP models contain nonlinear conic constraints and are often countered in robust optimization and financial models.
Constraint Solver improvements. We have developed new metaheuristics and global constraints for our CP solver in conjunction with the gang in MSR Cambridge. Watch Lengning's blog for more details.
F# integration. We've heard a lot of positive noises about our F# integration - it's better in 2.0. Our F# optimization DSL has been improved and now incorporates units-of-measure as described in this post. Special thanks to the F# team for their help on this important piece of the puzzle.
And more. Submodel support, better SOS1/SOS2 support, improved reporting, improved model analysis and error messages, more solver plug-ins, better performance and memory usage across the board.
The release of Solver Foundation 2.0 is the culmination of one year of hard work by the team. I hope you will give it a try (the Express version is freely available) and provide your feedback either through the blog or through our MSDN forum. Getting this stuff right - and covering the scenarios that people care about - is hard work and it takes time. We've come a long way in a year, but there's so much more we want to do. As always, the team appreciates honest feedback, good and bad. We're serious about listening to that feedback to make Solver Foundation better.
A couple of weeks ago I wrote about one of our big features for Solver Foundation 2.0: stochastic programming. In this post I want to talk about a new solver for 2.0: an interior-point solver for Second Order Conic Programming (SOCP). Second Order Conic Programming is the problem of minimizing a linear function where there are linear terms constrained to be inside a second order cone. Also called conic quadratic programming, SOCP is important because it can be used to model many real-world robust optimization, engineering, and finance problems. You can even model certain types of chance constraints using SOCP. Here are a few favorite SOCP links:
An SOCP can contain conventional linear constraints Ax >= b as well as second-order cone constraints. Some solvers define SOCP in terms of conic variables rather than conic constraints. Solver Foundation’s interior point solver uses conic constraints rather than conic variables because (IMHO) it leads to a more flexible, easy-to-program solver API. A second-order cone is a pointed cone where the norm of n - 1 variables t_i is less than the other variable t_0 (so that a cross-section is a circle): t_0 >= || t_i ||, t_0 >= 0. A second-order cone in three dimensions looks like an ice cream cone. A second-order conic constraint is similar, except that each t can be a linear term that may combine several variables. The first term t_0 is called the "primary row".
What this means is that if you know how to build linear programming problems using the ILinearModel API I described last time, then you pretty much know how to build SOCP problems. You need to build a row that represents the conic constraint using AddRow, then you need to call AddRow once for each term in the conic constraint. That's it.
Here's a short code sample: given an InteriorPointSolver, pass in a list of matrices F and a corresponding list of matrices g. We want to find a vector x that minimizes the sum of ||Fx + g|| over all entries in F and g. The steps are as follows:
/// <summary> Create a simple sum-of-norms problem from F and g. /// </summary> /// <remarks>Returns the variable vids so the solution vector x can be /// retrieved after Solve().</remarks> private static int[] BuildSumOfNorms(InteriorPointSolver solver, List<double[][]> F, List<double[]> g) { int[] x = new int[F[0][0].Length]; for (int i = 0; i < x.Length; i++) { solver.AddVariable("x" + i, out x[i]); } // Add the goal. int goal; solver.AddRow("goal", out goal); solver.AddGoal(goal, 1, true); for (int k = 0; k < F.Count; k++) { int cone, t; // Add variable t_k, which is the upper bound on the kth norm. solver.AddVariable("t_" + k, out t); solver.SetCoefficient(goal, t, Rational.One); solver.SetBounds(t, Rational.Zero, Rational.PositiveInfinity); // Add a quadratic cone. solver.AddRow("cone_" + k, SecondOrderConeType.Quadratic, out cone); solver.SetBounds(cone, 0, Rational.PositiveInfinity); // Add the conic constraint int conicRow1; solver.AddRow("cr1_" + k, cone, SecondOrderConeRowType.PrimaryConic, out conicRow1); solver.SetCoefficient(conicRow1, t, Rational.One); solver.SetLowerBound(conicRow1, Rational.Zero); for (int i = 0; i < F[k].Length; i++) { int conicRow2; solver.AddRow("cr2_" + k + "_" + i, cone, SecondOrderConeRowType.Conic, out conicRow2); for (int j = 0; j < F[k][i].Length; j++) { if (F[k][i][j] != 0) { solver.SetCoefficient(conicRow2, x[j], F[k][i][j]); } } solver.SetLowerBound(conicRow2, -g[k][i]); } } return x; }
Those are the basics. We will have SOCP analogues of the LinearModel APIs, as well as APIs that let you look at the details of the conic constraints. In Version 2.0 we will support creation and solution of SOCP only using the InteriorPointSolver API. We will not have SFS or OML support for this release.