CVXGEN: Code Generation for Convex Optimization

Increasing solve speed

CVXGEN is designed to let you solve convex optimization problems particularly fast. Here are some tips that may help you improve performance if solve time is critical.

  • Reduce the size of your problem. Where possible, reduce the number of variables, constraints or objective terms. With model predictive control problems, for example, see the paper by Wang and Boyd for suggestions. Reducing the time horizon will provide an approximately linear improvement in performance.

  • Use the most recent compiler for your platform, with appropriate compiler optimizations. We recommend gcc-4.4, with the -Os option. This can make a surprising difference. (A typical improvement with good optimization settings is 3times.) Using -Os is appropriate, since it aims to reduce code size, and CVXGEN problems often have relatively large code.

  • Relax constraint satisfaction and duality gap specifications. (See the settings section below.) This is particularly important if average solve times are more important than maximum solve times, as it lets CVXGEN return quickly if a good solution is found. Often a near-optimal point is found early, with subsequent iterations merely confirming the point's quality.

  • Lower the fixed iteration limit. (Again, see the settings.) This is particularly important if the maximum solve time is more important than the average solve time. It may lead to a reduced-quality (or even infeasible) solution, and should be used with care.

  • Adjust the initial values for the slack and dual variables. This advanced option is detailed in the settings, below.

Settings

The C code generated by CVXGEN allows several customizations. These can be made by changing the settings structure defined in solver.h. When using the Matlab interface, they may also be modified via the settings structure in Matlab. Here is an explanation of the various available options.

Primary settings

  • settings.eps Default: 10^{-6}. CVXGEN will not declare a problem converged until the duality gap is known to be bounded by eps.

  • settings.resid_tol. Default: 10^{-4}. CVXGEN will not declare a problem converged until the norm of the equality and inequality residuals are both less than resid_tol.

  • settings.max_iters. Default: 25. CVXGEN will exit early if eps and resid_tol are satisfied. It will also exit when it has performed max_iters iterations, regardless of the quality of the point it finds. Most problems should require fewer than 20 iterations.

  • settings.verbose. Default: 1. When set to 0, CVXGEN will output information about each iteration, including residual norms, duality gap bounds and step sizes.

Additional settings related to numerical performance

These advanced settings are recommended only for experienced users. More details will be provided in a later paper.

  • settings.kkt_reg. Default: 10^{-7}. Rather than solve the exact KKT system to find the search direction, CVXGEN regularizes the KKT matrix with a small positive or negative term on each part of the diagonal. Increasing kkt_reg yields more stable numerical characteristics, at the possible cost of more iterations. Increase if some valid problem instances fail to converge; decrease cautiously to potentially improve performance.

  • settings.refine_steps. Default: 1. To compensate for the KKT regularization, and further improve numerical characteristics, CVXGEN performs refine_steps of iterative refinement. Usually 1 step is sufficient. Increase for potentially improved reliability and fewer outer iterations, at a 10–20% cost per extra refine step; decrease to 0 for a risky solver that may not work, but may be significantly faster if it does.

  • settings.verbose_refinement. Default: 1. Provides more information about the iterative refinement. For debugging only.