.. _solvers: ======= Solvers ======= .. _supported-solvers: Supported solvers ----------------- This version of CVX supports four solvers, each with different capabilities: ============================================================= ==== ==== ====== ===== ==== ========= Solver name LP QP SOCP SDP GP Integer ============================================================= ==== ==== ====== ===== ==== ========= `SeDuMi `_ Y Y Y Y E N `SDPT3 `_ Y Y Y Y E N `Gurobi `_ Y Y Y N N Y `MOSEK `_ Y Y Y Y Y Y `GLPK `_ Y N N N N Y ============================================================= ==== ==== ====== ===== ==== ========= (key: Y = Yes, N = No, E = Experimental) Each solver has different capabilities and different levels of performance. For instance, SeDuMi [Stu99]_, SDPT3 [TTT03]_, and MOSEK support all of the continuous (non-integer) models that CVX itself supports, while Gurobi is more limited, in that it does not support semidefinite constraints; and GLPK is limited even further. On the other hand, Gurobi, GLPK, and MOSEK support integer consraints, while SeDuMi and SDPT3 do not. SeDuMi and SDPT3 are included with the standard CVX distribution, so you do not need to download an additional solver to start using CVX. We have also entered into contractual arrangements with the developers of Gurobi and MOSEK that allow us to ship their binaries with CVX as well, but using those solvers requires a CVX Professional license. Due to license differences, we are *not* able to supply GLPK with CVX. However, If you are having difficulty with one solver, *please try another*. No one solver performs better than the others on *every* model CVX can generate---including commercial solvers. That said, if you encounter a problem that one solver can handle well and another cannot, please send us a bug report (see :ref:`support`) and we will forward the results to the solver's authors. We have created special sections in this user guide for using Gurobi and MOSEK with CVX: * Gurobi: :ref:`gurobi` * Mosek: :ref:`mosek` Support for GLPK should be considered experimental. .. _solver-selection: Selecting a solver ------------------ The default solver is currently SDPT3. We have found that SeDuMi is faster for most problems, but unfortunately not as reliable. None of the solvers are perfect, however, and you may find for your application that another solver is preferred. To see which solver is currently selected, simply type :: cvx_solver To change the current solver, simply follow the ``cvx_solver`` with the name of your chosen solver. For example, to select SeDuMi, type :: cvx_solver sedumi The ``cvx_solver`` command is case insensitive, so ``cvx_solver SeDuMi`` will work just fine as well. If you issue this command inside a model---that is, between ``cvx_begin`` and ``cvx_end`` it will change the solver *only* for that model; the next model will use the previous choice. If, only the other hand, you issue a ``cvx_solver`` command *outside* of a model, it will change the solver used for the remainder of your Matlab session (or until you change it again). If you would like to change the default solver *permanently*---that is, so that it remains the default even if you quit and re-start Matlab---then make sure it is set properly, and then issue the command :: cvx_save_prefs This command saves not only your solver choice, but also your settings for ``cvx_expert``, ``cvx_power_warning``, and ``cvx_precision`` as well. .. _solver-output: Controlling screen output ------------------------- Once you gain confidence in using CVX and start incorporating it into your larger algorithms and programs, you are likely going to want to silence the messages it delivers to the screen. To do so, simply add the ``quiet`` keyword to the ``cvx_begin`` command; that is, :: cvx_begin quiet ... cvx_end Previous versions of CVX utilized a separate ``cvx_quiet`` command and that command is still available in this version as well, if you prefer it. Entering ``cvx_quiet true`` suppresses screen output from the solver, while entering ``cvx_quiet false`` restores the screen output. If you enter these commands within a model---that is, between ``cvx_begin`` and ``cvx_end``---it will affect only that model. If you enter it *outside* of a model, it will affect all subsequent models. Entering cvx_quiet with no arguments returns the current setting. .. _interpreting: Interpreting the results ------------------------ After a complete CVX specification has been entered and the cvx_end command issued, the solver is called to generate a numerical result. It proceeds to replace the variables in your model with the computed numerical values, and creates the variable cvx_optval containing the value of the objective function. It also summarizes the result of its efforts in the form of a string named ``cvx_status``. The possible values of ``cvx_status`` are as follows: ``Solved`` A complementary (primal and dual) solution has been found. The primal and dual variables are replaced with their computed values, and the the optimal value of the problem is placed in cvx_optval (which, by convention, is :math:`0` for feasibility problems). ``Unbounded`` The solver has determined that the problem is unbounded. The value of ``cvx_optval`` is set to ``-Inf`` for minimizations, and ``+Inf`` for maximizations. (Feasibility problems, by construction, never produce an ``Unbounded`` status.) The values of any dual variables are replaced with ``NaN``, as the dual problem is in fact infeasible. For unbounded problems, CVX stores an *unbounded direction* into the problem variables. This is is a *direction* along which the feasible set is unbounded, and the optimal value approaches :math:`\pm\infty`. It is important to understand that this value is very likely *not* a feasible point. If a feasible point is required, the problem should be re-solved as a feasibility problem by omitting the objective. Mathematically speaking, given an unbounded direction :math:`v` and a feasible point :math:`x`, :math:`x+tv` is feasible for all :math:`t\geq0`, and the objective tends to :math:`-\infty` (for minimizations; :math:`+\infty` for maximizations) as :math:`t\rightarrow+\infty` itself. ``Infeasible`` The problem has been proven to be infeasible through the discovery of an unbounded direction. The values of the variables are filled with ``NaN``, and the value of ``cvx_optval`` is set to ``+Inf`` for minimizations and feasibility problems, and ``-Inf`` for maximizations. Associated with a provably infeasible problem is an *unbounded dual direction*. Appropriate components of this direction are stored in the dual variables. Similarly to the ``Unbounded`` case, it is important to understand that the unbounded dual direction is very likely not a feasible dual point. ``Inaccurate/Solved``, ``Inaccurate/Unbounded``, ``Inaccurate/Infeasible`` These three status values indicate that the solver was unable to make a determination to within the default numerical tolerance. However, it determined that the results obtained satisfied a "relaxed" tolerance leve and therefore may still be suitable for further use. If this occurs, you should test the validity of the computed solution before using it in further calculations. See :ref:`solver-precision` for a more advanced discussion of solver tolerances and how to make adjustments. ``Suboptimal`` This status is possible only for *mixed-integer* problems. It is returned when the branching algorithm has discovered at least one feasible integer solution, but it was unable to continue the search process to global optimality. This will occur if the solver is required to terminate due to a time limit or a forced interruption (for example, if the user types `Ctrl-C`.) ``Failed`` The solver failed to make sufficient progress towards a solution, even to within the "relaxed" tolerance setting. The values of cvx_optval and primal and dual variables are filled with ``NaN``. This result can occur because of numerical problems within SeDuMi, often because the problem is particularly "nasty" in some way (*e.g.*, a non-zero duality gap). ``Overdetermined`` The presolver has determined that the problem has more equality constraints than variables, which means that the coefficient matrix of the equality constraints is singular. In practice, such problems are often, but not always, infeasible. Unfortunately, solvers typically cannot handle such problems, so a precise conclusion cannot be reached. The situations that most commonly produce an Overdetermined result are discussed in :ref:`overdetermined`. .. _solver-precision: Controlling precision ---------------------- .. note:: We consider the modification of solver precision to be an advanced feature, to be used sparingly, if at all---and only after you have become comfortable building models in CVX. Numerical methods for convex optimization are not exact; they compute their results to within a predefined numerical precision or tolerance. Upon solution of your model, the tolerance level the solver has achieved is returned in the ``cvx_slvtol`` variable. Attempts to interpret this tolerance level in any absolute sense are not recommended. For one thing, each solver computes it differently. For another, it depends heavily on the considerable transformations that CVX applies to your model before delivering it to the solver. So while you may find its value interesting we strongly discourage dependence upon it within your applications. The tolerance levels that CVX selects by default have been inherited from some of the underlying solvers being used, with minor modifications. CVX actually considers *three* different tolerance levels :math:`\epsilon_{\text{solver}}\leq\epsilon_{\text{standard}}\leq\epsilon_{\text{reduced}}` when solving a model: - The *solver tolerance* :math:`\epsilon_{\text{solver}}` is the level requested of the solver. The solver will stop as soon as it achieves this level, or until no further progress is possible. - The *standard tolerance* :math:`\epsilon_{\text{standard}}` is the level at which CVX considers the model solved to full precision. - The *reduced tolerance* :math:`\epsilon_{\text{reduced}}` is the level at which CVX considers the model "inaccurately" sovled, returning a status with the ``Inaccurate/`` prefix. If this tolerance cannot be achieved, CVX returns a status of ``Failed``, and the values of the variables should not be considered reliable. (See :ref:`interpreting` for more information about the status messages.) Typically, :math:`\epsilon_{\text{solver}}=\epsilon_{\text{standard}}`, but setting :math:`\epsilon_{\text{standard}}<\epsilon_{\text{solver}}` has a useful interpretation: it allows the solver to search for more accurate solutions without causing an ``Inaccurate/`` or ``Failed`` condition if it cannot do so. The default values of :math:`[\epsilon_{\text{solver}},\epsilon_{\text{standard}},\epsilon_{\text{reduced}}]` are set to :math:`[ \epsilon^{1/2}, \epsilon^{1/2}, \epsilon^{1/4} ]`, where :math:`\epsilon=2.22\times10^{-16}` is the machine precision. This should be quite sufficient for most applications. If you wish to modify the tolerances, you may do so using the ``cvx_precision`` command. There are three ways to invoke this command. Called with no arguments, it will print the current tolerance levels to the screen; or if called as a function, it will return those levels in a 3-element row vector. Calling ``cvx_precision`` with a string argument allows you to select from a set of predefined precision modes: - ``cvx_precision low``: :math:`[ \epsilon^{3/8}, \epsilon^{1/4}, \epsilon^{1/4} ]` - ``cvx_precision medium``: :math:`[ \epsilon^{1/2}, \epsilon^{3/8}, \epsilon^{1/4} ]` - ``cvx_precision default``: :math:`[ \epsilon^{1/2}, \epsilon^{1/2}, \epsilon^{1/4} ]` - ``cvx_precision high``: :math:`[ \epsilon^{3/4}, \epsilon^{3/4}, \epsilon^{3/8} ]` - ``cvx_precision best``: :math:`[ 0, \epsilon^{1/2}, \epsilon^{1/4} ]` In function mode, these calls look like ``cvx_precision('low')``, etc. Note that the ``best`` precision settings sets the solver target to zero, which means that the solver continues as long as it can make progress. It will often be slower than ``default``, but it is just as reliable, and sometimes produces more accurate solutions. Finally, the ``cvx_precision`` command can be called with a scalar, a length-2 vector, or a length-3 vector. If you pass it a scalar, it will set the solver and standard tolerances to that value, and it will compute a default reduced precision value for you. Roughly speaking, that reduced precision will be the square root of the standard precision, with some bounds imposed to make sure that it stays reasonable. If you supply two values, the smaller will be used for the solver and standard tolerances, and the larger for the reduced tolerance. If you supply three values, their values will be sorted, and each tolerance will be set separately. The ``cvx_precision`` command can be used either *within* a CVX model or *outside* of it; and its behavior differs in each case. If you call it from within a model, *e.g.*, :: cvx_begin cvx_precision high ... cvx_end then the setting you choose will apply only until ``cvx_end`` is reached. If you call it outside a model, *e.g.*, :: cvx_precision high cvx_begin ... cvx_end then the setting you choose will apply *globally*; that is, to any subsequent models that are created and solved. The local approach should be preferred in an application where multiple models are constructed and solved at different levels of precision. If you call ``cvx_precision`` in function mode, either with a string or a numeric value, it will return as its output the *previous* precision vector---the same result you would obtain if you called it with no arguments. This may seem confusing at first, but this is done so that you can save the previous value in a variable, and restore it at the end of your calculations; e.g., :: cvxp = cvx_precision( 'high' ); cvx_begin ... cvx_end cvx_precision( cvxp ); This is considered good coding etiquette in a larger application where multiple CVX models at multiple precision levels may be employed. Of course, a simpler but equally courteous approach is to call ``cvx_precision`` within the CVX model, as described above, so that its effect lasts only for that model. .. _solver-settings: Advanced solver settings ------------------------ .. warning:: This is an **advanced topic** for users who have a deep understanding of the underlying solver they are using, or who have received specific advice from the solver's developer for improving performance. Improper use of the ``cvx_solver_settings`` command can cause unpredictable results. Solvers can be tuned and adjusted in a variety of ways. Solver vendors attempt to select default settings that will provide good performance across a broad range of problems. But no solver, and no choice of settings, will perform well for every possible model. On occasion, it may be worthwhile to give a particular special instructions to improve its performance for a specific application. Unfortunately, such settings differ from solver to solver, so there is no way for CVX to provide this ability in a verifiable, reliable, global fashion. Nevertheless, using the new ``cvx_solver_settings`` command, you can customize a solver's settings when a specific model demands it. We cannot emphasize enough that this is an *expert* feature to be employed by experienced modelers only. Indeed, if you are an expert, you understand that these warnings are essential: - CVX does not check the correctness of the settings you supply. If the solver rejects the settings, CVX will fail until you change or remove those settings. - There is no guarantee that altering the settings will improve performance in any way; indeed, it can make the performance worse. - CVX Research provides *no* documentation on the specific settings available for each solver; you will have to consult the solver's own documentation for this. - The settings set here *override* any default values CVX may have chosen for each solver. Thus in certain cases, using this feature this may actually confuse CVX and cause it to misinterpret the results. For this reason, we cannot support all possible combinations of custom settings. - Unless you have turned off solver output completely, CVX will warn you if any custom settings are in effect every time you solve model. With this warning out of the way, let us introduce ``cvx_solver_settings``. Typing :: cvx_solver_settings at the command prompt provides a listing of the custom settings that have been provided for the active solver. Custom settings are *specific to each solver*. Typing :: cvx_solver_settings -all will provide a full list of the custom settings provided for *all* solvers. To create a new custom setting for the current solver, use this syntax: :: cvx_solver_settings( '{name}', {value} ) ``{name}`` must be a valid MATLAB variable/field name. ``{value}`` can be *any* valid Matlab object; CVX does not check its value in any way. To clear all custom settings for the active solver, type :: cvx_solver_settings -clear To clear just a single setting, type :: cvx_solver_settings -clear {} To clear all settings for all solvers, type :: cvx_solver_settings -clearall The settings created by the ``cvx_solver_settings`` command enjoy the same scope as ``cvx_solver``, ``cvx_precision``, and so forth. For instance, if you use this command *within* a model---between ``cvx_begin`` and ``cvx_end``---the changes will apply only to that particular model. If you issue the command *outside* of a particular model, the change will persist through the end of the MATLAB session (or until you change it again). Finally, if you use the ``cvx_save_prefs`` command, any custom settings you have added will be saved and restored the next time you start Matlab.