## MATLAB implementation of a primal-dual interior-point solver for convex programs with constraintsby Peter CarbonettoDept. 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 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 useClick 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 regressionStephen 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 |