transitioning from canned quasi-newton solvers to cvxopt

[Paul]

I just started using cvxopt. It is quite amazing. Thanks for the
excellent documentation.

I use canned conjugate gradient and quasi-newton code to do convex
optimizations. In a particular convex problem with 8000 parameters, I
use l-BFGS with a modification to allow for a strict L1 penalty on the
parameters. I am wondering if I can reformulate the optimization to
use cvxopt.solvers.cp so I can start using the power of cvxopt to add
inequality constraints, do convex relaxations, and so forth.

I had two general questions for which rough pointers or references
would be great:

1. What's a good strategy for transitioning from CG and BFGS to using
cvxopt? BFGS's steps are pretty efficient as it only makes low rank
updates to the inverse Hessian and stores only the projected gradient.
cvxopt.solvers.cp requires (?) a full Hessian that is possibly
expensive to compute and large. My Hessian is sparse so it's not so
bad in this case so I will try it anyway.

2. For objectives that are not differentiable like the L1 penalty,
what's a good way to go about including it in my optimization? Is such
a penalty builtin to cvxopt (I noticed something in cvxmod) or do I
need to implement it myself. The way Chen, Saunders, Donoho solve BPDN
seems pretty expensive and I was wondering if there are better ways to
do this. Unfortunately, my objective is different than BPDN so all the
specialized new solvers wont work.

Thanks,
Paul.

[Joachim Dahl]

Hi Paul.

> 1. What's a good strategy for transitioning from CG and BFGS to using
> cvxopt? BFGS's steps are pretty efficient as it only makes low rank
> updates to the inverse Hessian and stores only the projected gradient.
> cvxopt.solvers.cp requires (?) a full Hessian that is possibly
> expensive to compute and large. My Hessian is sparse so it's not so
> bad in this case so I will try it anyway.

CVXOPT only implements primal-dual interior point methods involving
the full Hessian.
You can still use iterative methods for solving the KKT equations and
you can
write customized KKT solvers for taking advantage of special structure
in the KKT
system - this post by Jeffery Klein is an excellent reference:

http://groups.google.com/group/cvxopt/browse_thread/thread/5bc91ddcb1cfc300/f71982d421490d72?q=#f71982d421490d72

>
> 2. For objectives that are not differentiable like the L1 penalty,
> what's a good way to go about including it in my optimization? Is such
> a penalty builtin to cvxopt (I noticed something in cvxmod) or do I
> need to implement it myself. The way Chen, Saunders, Donoho solve BPDN
> seems pretty expensive and I was wondering if there are better ways to
> do this. Unfortunately, my objective is different than BPDN so all the
> specialized new solvers wont work.
>

To use CVXOPT, your problem must be differentiable. L1 penalties are
normally
formulated as linear or second-order cone programs, for example

min. ||x||_1 s.t. Ax = b

would be rewritten as

min. sum(ti) s.t. -ti < xi < ti, Ax = b.

CVXMOD does these kinds of reformulations for you automatically.