MATLAB implementation of a primal-dual interior-point solver for convex programs with constraintsby Peter Carbonetto
Dept. of Computer Science
University of British Columbia
There are some very excellent software packages for solving constrained optimization problems (such as IPOPT). My code is not as efficient or as robust or as flexible as others, but it has the virtue of being simple (the solver is only 150 lines long!) and (relatively) easy to understand and use, and still works pretty well. It should also be reasonably fast for optimization problems that aren't too demanding.
My MATLAB code is based on the recent work in interior-point methods, specifically those methods that keep track of both the primal and dual optimization variables (hence primal-dual methods). These methods are special because they are numerically stable under a wide range of conditions, so they should work well for many different types of constrained optimization problems. That being said, you can always find a constrained optimization problem that is difficult enough to break these methods, so be careful! See below for a brief list of references that lay the foundation for this code.
I use a merit function which ensures global convergence (see the references below). What this means for you is that you don't have to use the Newton step (and compute the Hessian of the objective, which might be expensive to compute) to be guaranteed to converge to the optimal solution. For instance, you could use a quasi-Newton approximation to the Hessian instead, which is computed using the gradient information.
If you have any questions, praise, or comments, or would like to report a bug, do not hesitate to contact me. I've tested this software in MATLAB version 7.5.
LicenseThis work is licensed under the GNU Public license. Please cite the source as Peter Carbonetto, Department of Computer Science, University of British Columbia.
Installation and use
Click here to download a compressed
TAR archive containing six MATLAB files. The interior-point solver is
If you type
Some introductory references on interior-point methods and logistic regression
Stephen Boyd and Lieven Vandenberghe (2004). Convex Optimization. Cambridge University Press.
Jorge Nocedal and Stephen J. Wright (2006) Numerical Optimization, 2nd edition. Springer.
Margaret H. Wright (1991). Interior methods for constrained optimization. Acta Numerica, pp. 341--407.
Paul Armand, Jean C. Gilbert, and Sophie Jan-Jégou (2000). A Feasible BFGS Interior Point Algorithm for Solving Convex Minimization Problems. SIAM Journal on Optimization, Vol. 11, No. 1, pp. 199-222.
Trevor Hastie, Robert Tibshirani and Jerome Friedman (2001). The Elements of Statistical Learning. Springer.
May 21, 2008