How to Reduce the overhead cost when solving a large number of optimization problems

How to reduce the overhead cost when solving a large number of optimization problems which only differ through some changing parameter in the model.

I know that there is a command called optimizer in YALMIP. Is there a similar command in CVX?

I did this manually for our application. CVX was great for prototyping our code, but once we settled on a problem formulation we were interested in removing CVX and feeding the solver directly. Using the Matlab debugger it was fairly straightforward to see what inputs CVX was sending into SeDuMi. For our problem, the transformation from our input data to the SeDuMi input (At, b, c, K) was not too difficult to understand (although not trivial).

Looking at the K structure can be a good first step to understanding what CVX has done; it will give you a sense for cone constraints and slack variables that have been added. The At equality constraint matrix tends to come out fairly sparse assuming you have a lot of added variables, so spy(At) was quite useful for a high-level understanding of the structure. CVX may also dualize your problem depending on the dimensions. For our case, we didn’t think dualizing was saving us much time, so as a first pass solution I just set up the non-dualized format, which was simpler.

Also note that there are several rounds of formulation; first the extract function gives the most straightforward thing CVX can offer; then eliminate may shrink or dualize that; finally there is reformulation specific to the particular solver, for example SeDuMi wants its cone constraints in a conventional order, so all the variables get rearranged to match that convention right before they go in. As a first pass, I chose to hardcode the formulation up to the point of specializing for particular solvers, as this was simpler and I thought that way it is easier to try different solvers.

Since our problem was an SOCP, I also switched the solver from SeDuMi to ECOS. Thanks Eric Chu for the suggestion. Between switching to ECOS and feeding the solver directly, our code got about 25x faster, and there is further speedup to be had if I go back and hardcode (in C) feeding the ECOS solver specifically instead of hardcoding the solver-agnostic format (in Matlab).

If your problem can be reduced to a QP without quadratic constraints, you might look into CVXGEN. I haven’t tried it but sounds promising.

I believe some of the CVX Python tools are starting to have more code-generation capabilities, which might also allow cutting out overhead. But I think these tools are not so mature.

For example, an in-progress Python tool for generating code to feed solvers based on a specific problem structure:

Also, once you have fed your inputs to the solver, you also still have to deal with converting the outputs back into your problem variables. The first step is processing with the reorder matrixto reverse solver-specific reorderings. Then the variables are processed by Q and P matrices.

Hi, I have a SOCP problem and I want to use ECOS as my CVX solver but there is no ECOS package in CVX, version 2.0 (beta) shim that I use now. Any idea how can I use ECOS with cvx?

@seyran, ECOS should have a “matlab” directory. If you run the cvx_install_ecos function it will try to mex ECOS for you and install the binary and shim into your CVX folder. Has to be CVX >= 2.0.

@seyran, in my experience ECOS is faster than SeDuMi for moderate problem size (100s of variables) but not sure for bigger problems. If you’re running many smaller problems though, CVX itself is likely the real bottleneck.

Thanks for your reply! @Chinasaur