<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Cone Programming — CVXOPT User's Guide</title>
<link rel="stylesheet" href="_static/cvxopt.css" type="text/css" />
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: '#',
VERSION: '1.1.1',
COLLAPSE_MODINDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: false
};
</script>
<script type="text/javascript" src="_static/jquery.js"></script>
<script type="text/javascript" src="_static/doctools.js"></script>
<link rel="copyright" title="Copyright" href="copyright.html" />
<link rel="top" title="CVXOPT User's Guide" href="index.html" />
<link rel="next" title="Nonlinear Convex Optimization" href="solvers.html" />
<link rel="prev" title="Sparse Linear Equations" href="spsolvers.html" />
</head>
<body>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="solvers.html" title="Nonlinear Convex Optimization"
accesskey="N">next</a></li>
<li class="right" >
<a href="spsolvers.html" title="Sparse Linear Equations"
accesskey="P">previous</a> |</li>
<li><a href="http://abel.ee.ucla.edu/cvxopt">CVXOPT home</a> |</li>
<li><a href="index.html">user's guide</a> </li>
</ul>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body">
<div class="section" id="cone-programming">
<span id="c-coneprog"></span><h1>Cone Programming<a class="headerlink" href="#cone-programming" title="Permalink to this headline">¶</a></h1>
<p>In this chapter we consider convex optimization problems of the form</p>
<div class="math">
<p><img src="_images/math/77b87703b14d3f1b59ac092865ee19b0f85cf188.png" alt="\begin{array}{ll}
\mbox{minimize} & (1/2) x^TPx + q^T x \\
\mbox{subject to} & G x \preceq h \\
& Ax = b.
\end{array}" /></p>
</div><p>The linear inequality is a generalized inequality with respect to a
proper convex cone. It may include componentwise vector inequalities,
second-order cone inequalities, and linear matrix inequalities.</p>
<p>The main solvers are <a title="cvxopt.solvers.conelp" class="reference internal" href="#cvxopt.solvers.conelp"><tt class="xref docutils literal"><span class="pre">conelp</span></tt></a> and
<a title="cvxopt.solvers.coneqp" class="reference internal" href="#cvxopt.solvers.coneqp"><tt class="xref docutils literal"><span class="pre">coneqp</span></tt></a>, described in the
sections <a class="reference internal" href="#s-conelp"><em>Linear Cone Programs</em></a> and <a class="reference internal" href="#s-coneqp"><em>Quadratic Cone Programs</em></a>. The function
<tt class="xref docutils literal"><span class="pre">conelp</span></tt> is restricted to problems with linear cost functions, and
can detect primal and dual infeasibility. The function <tt class="xref docutils literal"><span class="pre">coneqp</span></tt>
solves the general quadratic problem, but requires the problem to be
strictly primal and dual feasible. For convenience (and backward
compatibility), simpler interfaces to these function are also provided
that handle pure linear programs, quadratic programs, second-order cone
programs, and semidefinite programs. These are described in the sections
<a class="reference internal" href="#s-lpsolver"><em>Linear Programming</em></a>, <a class="reference internal" href="#s-qp"><em>Quadratic Programming</em></a>, <a class="reference internal" href="#s-socpsolver"><em>Second-Order Cone Programming</em></a>, <a class="reference internal" href="#s-sdpsolver"><em>Semidefinite Programming</em></a>.
In the section <a class="reference internal" href="#s-conelp-struct"><em>Exploiting Structure</em></a> we explain how custom solvers can
be implemented that exploit structure in cone programs. The last two
sections describe optional interfaces to external solvers, and the
algorithm parameters that control the cone programming solvers.</p>
<div class="section" id="linear-cone-programs">
<span id="s-conelp"></span><h2>Linear Cone Programs<a class="headerlink" href="#linear-cone-programs" title="Permalink to this headline">¶</a></h2>
<dl class="function">
<dt id="cvxopt.solvers.conelp">
<tt class="descclassname">cvxopt.solvers.</tt><tt class="descname">conelp</tt><big>(</big><em>c</em>, <em>G</em>, <em>h</em><span class="optional">[</span>, <em>dims</em><span class="optional">[</span>, <em>A</em>, <em>b</em><span class="optional">[</span>, <em>primalstart</em><span class="optional">[</span>, <em>dualstart</em><span class="optional">[</span>, <em>kktsolver</em><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.solvers.conelp" title="Permalink to this definition">¶</a></dt>
<dd><p>Solves a pair of primal and dual cone programs</p>
<div class="math">
<p><img src="_images/math/1a8d47fe4c6b9295f4c73ecb0181d7cdc2f265bd.png" alt="\begin{array}[t]{ll}
\mbox{minimize} & c^T x \\
\mbox{subject to} & G x + s = h \\
& Ax = b \\
& s \succeq 0
\end{array}
\qquad\qquad
\begin{array}[t]{ll}
\mbox{maximize} & -h^T z - b^T y \\
\mbox{subject to} & G^T z + A^T y + c = 0 \\
& z \succeq 0.
\end{array}" /></p>
</div><p>The primal variables are <img class="math" src="_images/math/26eeb5258ca5099acf8fe96b2a1049c48c89a5e6.png" alt="x"/> and <img class="math" src="_images/math/f37bba504894945c07a32f5496d74299a37aa51c.png" alt="s"/>. The dual variables
are <img class="math" src="_images/math/092e364e1d9d19ad5fffb0b46ef4cc7f2da02c1c.png" alt="y"/>, <img class="math" src="_images/math/b13f21416d84e13708696f34dea81026cda583c9.png" alt="z"/>. The inequalities are interpreted as
<img class="math" src="_images/math/a0bfc2010a37ca5ee8d8553f74881b8e12ea4bfd.png" alt="s \in C"/>, <img class="math" src="_images/math/d22f3a5882fad95b5a9af193c57e3db91989d676.png" alt="z\in C"/>, where <img class="math" src="_images/math/c3355896da590fc491a10150a50416687626d7cc.png" alt="C"/> is a cone defined as
a Cartesian product of a nonnegative orthant, a number of second-order
cones, and a number of positive semidefinite cones:</p>
<div class="math">
<p><img src="_images/math/975932e25b8d20b8ef19bccfe15bfc80e9960ca2.png" alt="C = C_0 \times C_1 \times \cdots \times C_M \times C_{M+1} \times
\cdots \times C_{M+N}" /></p>
</div><p>with</p>
<div class="math">
<p><img src="_images/math/a34d96670035ec4b9d538485aca155388900d586.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
\newcommand{\svec}{\mathop{\mathbf{vec}}}
\newcommand{\symm}{{\mbox{\bf S}}}
\begin{split}
C_0 & =
\{ u \in \reals^l \;| \; u_k \geq 0, \; k=1, \ldots,l\}, \\
C_{k+1} & = \{ (u_0, u_1) \in \reals \times \reals^{r_{k}-1}
\; | \; u_0 \geq \|u_1\|_2 \}, \quad k=0,\ldots, M-1, \\
C_{k+M+1} &= \left\{ \svec(u) \; | \; u \in \symm^{t_k}_+
\right\}, \quad k=0,\ldots,N-1.
\end{split}" /></p>
</div><p>In this definition, <img class="math" src="_images/math/1caa3e3ac8919174afb2c7d55599b897ea724bd1.png" alt="\mathbf{vec}(u)"/> denotes a symmetric matrix
<img class="math" src="_images/math/9ad99798ec4c38e165cf517cb9e02b1c9e824103.png" alt="u"/> stored as a vector in column major order. The structure of
<img class="math" src="_images/math/c3355896da590fc491a10150a50416687626d7cc.png" alt="C"/> is specified by <tt class="docutils literal"><span class="pre">dims</span></tt>. This argument is a dictionary with
three fields.</p>
<dl class="docutils">
<dt><tt class="docutils literal"><span class="pre">dims['l']</span></tt>:</dt>
<dd><img class="math" src="_images/math/9b25f8e64b484493fda944d25cad453423041fe6.png" alt="l"/>, the dimension of the nonnegative orthant (a nonnegative
integer).</dd>
<dt><tt class="docutils literal"><span class="pre">dims['q']</span></tt>:</dt>
<dd><img class="math" src="_images/math/f9408643dfec56ef1bdd651b0858bed3b41a899b.png" alt="[r_0, \ldots, r_{M-1}]"/>, a list with the dimensions of the
second-order cones (positive integers).</dd>
<dt><tt class="docutils literal"><span class="pre">dims['s']</span></tt>:</dt>
<dd><img class="math" src="_images/math/15c9e0d5b18ecfcec0dc5faf60950122d134d40e.png" alt="[t_0, \ldots, t_{N-1}]"/>, a list with the dimensions of the
positive semidefinite cones (nonnegative integers).</dd>
</dl>
<p>The default value of <tt class="docutils literal"><span class="pre">dims</span></tt> is
<tt class="docutils literal"><span class="pre">{'l':</span> <span class="pre">G.size[0],</span> <span class="pre">'q':</span> <span class="pre">[],</span> <span class="pre">'s':</span> <span class="pre">[]}</span></tt>,
i.e., by default the
inequality is interpreted as a componentwise vector inequality.</p>
<p>The arguments <tt class="docutils literal"><span class="pre">c</span></tt>, <tt class="docutils literal"><span class="pre">h</span></tt>, and <tt class="docutils literal"><span class="pre">b</span></tt> are real single-column dense
matrices. <tt class="docutils literal"><span class="pre">G</span></tt> and <tt class="docutils literal"><span class="pre">A</span></tt> are real dense or sparse matrices. The
number of rows of <tt class="docutils literal"><span class="pre">G</span></tt> and <tt class="docutils literal"><span class="pre">h</span></tt> is equal to</p>
<div class="math">
<p><img src="_images/math/0fb35d76d5ee3a9cea74866affcb223883174be3.png" alt="K = l + \sum_{k=0}^{M-1} r_k + \sum_{k=0}^{N-1} t_k^2." /></p>
</div><p>The columns of <tt class="docutils literal"><span class="pre">G</span></tt> and <tt class="docutils literal"><span class="pre">h</span></tt> are vectors in</p>
<div class="math">
<p><img src="_images/math/c620bdffc558c7c84614e360601c181863f7860c.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
\reals^l \times \reals^{r_0} \times \cdots \times
\reals^{r_{M-1}} \times \reals^{t_0^2} \times \cdots \times
\reals^{t_{N-1}^2}," /></p>
</div><p>where the last <img class="math" src="_images/math/fc97ef67268cd4e91bacdf12b8901d7036c9a056.png" alt="N"/> components represent symmetric matrices
stored in column major order. The strictly upper triangular entries
of these matrices are not accessed (i.e., the symmetric matrices are
stored in the <tt class="xref docutils literal"><span class="pre">'L'</span></tt>-type column major order used in the
<tt class="xref docutils literal"><span class="pre">blas</span></tt> and <tt class="xref docutils literal"><span class="pre">lapack</span></tt> modules). The default values for <tt class="docutils literal"><span class="pre">A</span></tt>
and <tt class="docutils literal"><span class="pre">b</span></tt> are matrices with zero rows, meaning that there are no
equality constraints.</p>
<p><tt class="docutils literal"><span class="pre">primalstart</span></tt> is a dictionary with keys <tt class="xref docutils literal"><span class="pre">'x'</span></tt> and
<tt class="xref docutils literal"><span class="pre">'s'</span></tt>, used as an optional primal starting point.
<tt class="docutils literal"><span class="pre">primalstart['x']</span></tt> and <tt class="docutils literal"><span class="pre">primalstart['s']</span></tt> are real dense
matrices of size (<img class="math" src="_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n"/>, 1) and (<img class="math" src="_images/math/dfb064112b6c94470339f6571f69d07afc1c024c.png" alt="K"/>, 1), respectively,
where <img class="math" src="_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n"/> is the length of <tt class="docutils literal"><span class="pre">c</span></tt>. The vector
<tt class="docutils literal"><span class="pre">primalstart['s']</span></tt> must be strictly positive with respect
to the cone <img class="math" src="_images/math/c3355896da590fc491a10150a50416687626d7cc.png" alt="C"/>.</p>
<p><tt class="docutils literal"><span class="pre">dualstart</span></tt> is a dictionary with keys <tt class="xref docutils literal"><span class="pre">'y'</span></tt> and <tt class="xref docutils literal"><span class="pre">'z'</span></tt>,
used as an optional dual starting point. <tt class="docutils literal"><span class="pre">dualstart['y']</span></tt> and
<tt class="docutils literal"><span class="pre">dualstart['z']</span></tt> are real dense matrices of size (<img class="math" src="_images/math/36f73fc1312ee0349b3f3a0f3bd9eb5504339011.png" alt="p"/>, 1)
and (<img class="math" src="_images/math/dfb064112b6c94470339f6571f69d07afc1c024c.png" alt="K"/>, 1), respectively, where <img class="math" src="_images/math/36f73fc1312ee0349b3f3a0f3bd9eb5504339011.png" alt="p"/> is the number of
rows in <tt class="docutils literal"><span class="pre">A</span></tt>. The vector <tt class="docutils literal"><span class="pre">dualstart['s']</span></tt> must be strictly
positive with respect to the cone <img class="math" src="_images/math/c3355896da590fc491a10150a50416687626d7cc.png" alt="C"/>.</p>
<p>The role of the optional argument <tt class="docutils literal"><span class="pre">kktsolver</span></tt> is explained in
the section <a class="reference internal" href="#s-conelp-struct"><em>Exploiting Structure</em></a>.</p>
<p><tt class="xref docutils literal"><span class="pre">conelp</span></tt> returns a dictionary that contains the result and
information about the accuracy of the solution. The most important
fields have keys <tt class="xref docutils literal"><span class="pre">'status'</span></tt>, <tt class="xref docutils literal"><span class="pre">'x'</span></tt>, <tt class="xref docutils literal"><span class="pre">'s'</span></tt>,
<tt class="xref docutils literal"><span class="pre">'y'</span></tt>, <tt class="xref docutils literal"><span class="pre">'z'</span></tt>. The <tt class="xref docutils literal"><span class="pre">'status'</span></tt> field is a string
with possible values <tt class="xref docutils literal"><span class="pre">'optimal'</span></tt>, <tt class="xref docutils literal"><span class="pre">'primal</span> <span class="pre">infeasible'</span></tt>,
<tt class="xref docutils literal"><span class="pre">'dual</span> <span class="pre">infeasible'</span></tt>, and <tt class="xref docutils literal"><span class="pre">'unknown'</span></tt>. The meaning of
the <tt class="xref docutils literal"><span class="pre">'x'</span></tt>, <tt class="xref docutils literal"><span class="pre">'s'</span></tt>, <tt class="xref docutils literal"><span class="pre">'y'</span></tt>, <tt class="xref docutils literal"><span class="pre">'z'</span></tt> fields
depends on the value of <tt class="xref docutils literal"><span class="pre">'status'</span></tt>.</p>
<dl class="docutils">
<dt><tt class="xref docutils literal"><span class="pre">'optimal'</span></tt></dt>
<dd><p class="first">In this case the <tt class="xref docutils literal"><span class="pre">'x'</span></tt>, <tt class="xref docutils literal"><span class="pre">'s'</span></tt>, <tt class="xref docutils literal"><span class="pre">'y'</span></tt>, and
<tt class="xref docutils literal"><span class="pre">'z'</span></tt> entries contain the primal and dual solutions, which
approximately satisfy</p>
<div class="math">
<p><img src="_images/math/b7416ae850a4be262250cf738c69746b8c161976.png" alt="Gx + s = h, \qquad Ax = b, \qquad G^T z + A^T y + c = 0,
s \succeq 0, \qquad z \succeq 0, \qquad s^T z = 0." /></p>
</div><p>The other entries in the output dictionary summarize the accuracy
with which these optimality conditions are satisfied. The fields
<tt class="xref docutils literal"><span class="pre">'primal</span> <span class="pre">objective'</span></tt>, <tt class="xref docutils literal"><span class="pre">'dual</span> <span class="pre">objective'</span></tt>, and
<tt class="xref docutils literal"><span class="pre">'gap'</span></tt> give the primal objective <img class="math" src="_images/math/343d0b1bdf0a89348e54e78243206b00921891fa.png" alt="c^Tx"/>, dual
objective <img class="math" src="_images/math/e3a39e1f9f23b6b48180b47a6941803e150acf02.png" alt="-h^Tz - b^Ty"/>, and the gap <img class="math" src="_images/math/2bd21984207bb64a4af86d045947fdb01d050f8f.png" alt="s^Tz"/>. The
field <tt class="xref docutils literal"><span class="pre">'relative</span> <span class="pre">gap'</span></tt> is the relative gap, defined as</p>
<div class="math">
<p><img src="_images/math/e227404751bdf9353900cfa8acb3db338ffb45bd.png" alt="\frac{ s^Tz }{ \max\{ -c^Tx, -h^Tz-b^Ty \} }
\quad \mbox{if} \quad \max\{ -c^Tx, -h^Tz-b^Ty \} > 0" /></p>
</div><p>and <tt class="xref xref docutils literal"><span class="pre">None</span></tt> otherwise. The fields
<tt class="xref docutils literal"><span class="pre">'primal</span> <span class="pre">infeasibility'</span></tt> and <tt class="xref docutils literal"><span class="pre">'dual</span> <span class="pre">infeasibility'</span></tt>
are the residuals in the primal and dual equality constraints,
defined as</p>
<div class="math">
<p><img src="_images/math/4d98c2c2a240fd3ece215d33344d6861c464542a.png" alt="\max\{ \frac{ \|Gx+s-h\|_2 }{ \max\{1, \|h\|_2\} },
\frac{ \|Ax-b\|_2 }{ \max\{1,\|b\|_2\} } \}, \qquad
\frac{ \|G^Tz + A^Ty + c\|_2 }{ \max\{1, \|c\|_2\} }," /></p>
</div><p class="last">respectively.</p>
</dd>
<dt><tt class="xref docutils literal"><span class="pre">'primal</span> <span class="pre">infeasible'</span></tt></dt>
<dd><p class="first">The <tt class="xref docutils literal"><span class="pre">'x'</span></tt> and <tt class="xref docutils literal"><span class="pre">'s'</span></tt> entries are <tt class="xref xref docutils literal"><span class="pre">None</span></tt>, and
the <tt class="xref docutils literal"><span class="pre">'y'</span></tt>, <tt class="xref docutils literal"><span class="pre">'z'</span></tt> entries provide an approximate
certificate of infeasibility, i.e., vectors that approximately
satisfy</p>
<div class="math">
<p><img src="_images/math/b57720e648d18f104bebca376094c72e087519ca.png" alt="G^T z + A^T y = 0, \qquad h^T z + b^T y = -1, \qquad
z \succeq 0." /></p>
</div><p>The field <tt class="xref docutils literal"><span class="pre">'residual</span> <span class="pre">as</span> <span class="pre">primal</span> <span class="pre">infeasibility</span> <span class="pre">certificate'</span></tt>
gives the residual</p>
<div class="last math">
<p><img src="_images/math/c917b15b2cdc303898562683b1ac6a34297c70df.png" alt="\frac{ \|G^Tz + A^Ty\|_2 }{ \max\{1, \|c\|_2\} }." /></p>
</div></dd>
<dt><tt class="xref docutils literal"><span class="pre">'dual</span> <span class="pre">infeasible'</span></tt></dt>
<dd><p class="first">The <tt class="xref docutils literal"><span class="pre">'y'</span></tt> and <tt class="xref docutils literal"><span class="pre">'z'</span></tt> entries are <tt class="xref xref docutils literal"><span class="pre">None</span></tt>, and
the <tt class="xref docutils literal"><span class="pre">'x'</span></tt> and <tt class="xref docutils literal"><span class="pre">'s'</span></tt> entries contain an approximate
certificate of dual infeasibility</p>
<div class="math">
<p><img src="_images/math/6489ee228737f4d9d3366e3a7432230c580b2266.png" alt="Gx + s = 0, \qquad Ax=0, \qquad c^T x = -1, \qquad
s \succeq 0." /></p>
</div><p>The field <tt class="xref docutils literal"><span class="pre">'residual</span> <span class="pre">as</span> <span class="pre">dual</span> <span class="pre">infeasibility</span> <span class="pre">certificate'</span></tt>
gives the residual</p>
<div class="last math">
<p><img src="_images/math/723b55830eebda94339bddfe5032d381c449a3fd.png" alt="\max\{ \frac{ \|Gx + s\|_2 }{ \max\{1, \|h\|_2\} },
\frac{ \|Ax\|_2 }{ \max\{1, \|b\|_2\} } \}." /></p>
</div></dd>
<dt><tt class="xref docutils literal"><span class="pre">'unknown'</span></tt></dt>
<dd><p class="first">This indicates that the algorithm terminated early due to
numerical difficulties or because the maximum number of iterations
was reached. The <tt class="xref docutils literal"><span class="pre">'x'</span></tt>, <tt class="xref docutils literal"><span class="pre">'s'</span></tt>, <tt class="xref docutils literal"><span class="pre">'y'</span></tt>,
<tt class="xref docutils literal"><span class="pre">'z'</span></tt> entries contain the iterates when the algorithm
terminated. Whether these entries are useful, as approximate
solutions or certificates of primal and dual infeasibility, can be
determined from the other fields in the dictionary.</p>
<p>The fields <tt class="xref docutils literal"><span class="pre">'primal</span> <span class="pre">objective'</span></tt>, <tt class="xref docutils literal"><span class="pre">'dual</span> <span class="pre">objective'</span></tt>,
<tt class="xref docutils literal"><span class="pre">'gap'</span></tt>, <tt class="xref docutils literal"><span class="pre">'relative</span> <span class="pre">gap'</span></tt>,
<tt class="xref docutils literal"><span class="pre">'primal</span> <span class="pre">infeasibility'</span></tt>,
<tt class="xref docutils literal"><span class="pre">'dual</span> <span class="pre">infeasibility'</span></tt> are defined as when <tt class="xref docutils literal"><span class="pre">'status'</span></tt>
is <tt class="xref docutils literal"><span class="pre">'optimal'</span></tt>. The field
<tt class="xref docutils literal"><span class="pre">'residual</span> <span class="pre">as</span> <span class="pre">primal</span> <span class="pre">infeasibility</span> <span class="pre">certificate'</span></tt> is defined
as</p>
<div class="math">
<p><img src="_images/math/373f482f73854e03e6ed7bd3e56010dedac0a40f.png" alt="\frac{ \|G^Tz+A^Ty\|_2 }{ -(h^Tz + b^Ty) \max\{1, \|h\|_2 \} }." /></p>
</div><p>if <img class="math" src="_images/math/ae2badac9a46b59f50871f2bb8d27dbc0e781580.png" alt="h^Tz+b^Ty < 0"/>, and <tt class="xref xref docutils literal"><span class="pre">None</span></tt> otherwise. A small
value of this residual indicates that <img class="math" src="_images/math/092e364e1d9d19ad5fffb0b46ef4cc7f2da02c1c.png" alt="y"/> and <img class="math" src="_images/math/b13f21416d84e13708696f34dea81026cda583c9.png" alt="z"/>,
divided by <img class="math" src="_images/math/eb1d31d3ef53ada239a7c1ebcfc362b3739e5fb5.png" alt="-h^Tz-b^Ty"/>, are an approximate proof of primal
infeasibility. The field
<tt class="xref docutils literal"><span class="pre">'residual</span> <span class="pre">as</span> <span class="pre">dual</span> <span class="pre">infeasibility</span> <span class="pre">certificate'</span></tt> is defined as</p>
<div class="math">
<p><img src="_images/math/7c7417a29910bcf840b52428dbb9ec70f1d85cd9.png" alt="\max\{ \frac{ \|Gx+s\|_2 }{ -c^Tx \max\{ 1, \|h\|_2 \} },
\frac{ \|Ax\|_2 }{ -c^Tx \max\{1,\|b\|_2\} }\}" /></p>
</div><p class="last">if <img class="math" src="_images/math/3d5748e90487d80ee689dc7c8ea13ef316542389.png" alt="c^Tx < 0"/>, and as <tt class="xref xref docutils literal"><span class="pre">None</span></tt> otherwise. A small value
indicates that <img class="math" src="_images/math/26eeb5258ca5099acf8fe96b2a1049c48c89a5e6.png" alt="x"/> and <img class="math" src="_images/math/f37bba504894945c07a32f5496d74299a37aa51c.png" alt="s"/>, divided by <img class="math" src="_images/math/2f2c7e1863869b3b250c3397ca8146a4d4863f1b.png" alt="-c^Tx"/>
are an approximate proof of dual infeasibility.</p>
</dd>
</dl>
<p>It is required that</p>
<div class="math">
<p><img src="_images/math/eebbe23287e11c882a2db71db881db3bb8dc23c4.png" alt="\newcommand{\Rank}{\mathop{\bf rank}}
\Rank(A) = p, \qquad
\Rank(\left[\begin{array}{c} G \\ A \end{array}\right]) = n," /></p>
</div><p>where <img class="math" src="_images/math/36f73fc1312ee0349b3f3a0f3bd9eb5504339011.png" alt="p"/> is the number or rows of <img class="math" src="_images/math/019e9892786e493964e145e7c5cf7b700314e53b.png" alt="A"/> and <img class="math" src="_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n"/> is
the number of columns of <img class="math" src="_images/math/6e28ce12d49d39f160d5a0ef54077fc98e4b9d2b.png" alt="G"/> and <img class="math" src="_images/math/019e9892786e493964e145e7c5cf7b700314e53b.png" alt="A"/>.</p>
</dd></dl>
<p>As an example we solve the problem</p>
<div class="math">
<p><img src="_images/math/ec3d0c1e0e6c4dc7823c2bdefd3004179a4338c3.png" alt="\begin{array}{ll}
\mbox{minimize} & -6x_1 - 4x_2 - 5x_3 \\*[1ex]
\mbox{subject to}
& 16x_1 - 14x_2 + 5x_3 \leq -3 \\*[1ex]
& 7x_1 + 2x_2 \leq 5 \\*[1ex]
& \left\| \left[ \begin{array}{c}
8x_1 + 13x_2 - 12x_3 - 2 \\
-8x_1 + 18x_2 + 6x_3 - 14 \\
x_1 - 3x_2 - 17x_3 - 13 \end{array}\right] \right\|_2
\leq -24x_1 - 7x_2 + 15x_3 + 12 \\*[3ex]
& \left\| \left[
\begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array}
\right] \right\|_2 \leq 10 \\*[3ex]
& \left[\begin{array}{ccc}
7x_1 + 3x_2 + 9x_3 & -5x_1 + 13x_2 + 6x_3 &
x_1 - 6x_2 - 6x_3\\
-5x_1 + 13x_2 + 6x_3 & x_1 + 12x_2 - 7x_3 &
-7x_1 -10x_2 - 7x_3\\
x_1 - 6x_2 -6x_3 & -7x_1 -10x_2 -7 x_3 &
-4x_1 -28 x_2 -11x_3
\end{array}\right]
\preceq \left[\begin{array}{ccc}
68 & -30 & -19 \\
-30 & 99 & 23 \\
-19 & 23 & 10 \end{array}\right].
\end{array}" /></p>
</div><div class="highlight-python"><div class="highlight"><pre><span class="gp">>>> </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">solvers</span>
<span class="gp">>>> </span><span class="n">c</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="o">-</span><span class="mf">6.</span><span class="p">,</span> <span class="o">-</span><span class="mf">4.</span><span class="p">,</span> <span class="o">-</span><span class="mf">5.</span><span class="p">])</span>
<span class="gp">>>> </span><span class="n">G</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([[</span> <span class="mf">16.</span><span class="p">,</span> <span class="mf">7.</span><span class="p">,</span> <span class="mf">24.</span><span class="p">,</span> <span class="o">-</span><span class="mf">8.</span><span class="p">,</span> <span class="mf">8.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span>
<span class="go"> 7., -5., 1., -5., 1., -7., 1., -7., -4.],</span>
<span class="go"> [-14., 2., 7., -13., -18., 3., 0., 0., -1., 0.,</span>
<span class="go"> 3., 13., -6., 13., 12., -10., -6., -10., -28.],</span>
<span class="go"> [ 5., 0., -15., 12., -6., 17., 0., 0., 0., -1.,</span>
<span class="go"> 9., 6., -6., 6., -7., -7., -6., -7., -11.]])</span>
<span class="gp">>>> </span><span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span> <span class="p">[</span> <span class="o">-</span><span class="mf">3.</span><span class="p">,</span> <span class="mf">5.</span><span class="p">,</span> <span class="mf">12.</span><span class="p">,</span> <span class="o">-</span><span class="mf">2.</span><span class="p">,</span> <span class="o">-</span><span class="mf">14.</span><span class="p">,</span> <span class="o">-</span><span class="mf">13.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span>
<span class="go"> 68., -30., -19., -30., 99., 23., -19., 23., 10.] )</span>
<span class="gp">>>> </span><span class="n">dims</span> <span class="o">=</span> <span class="p">{</span><span class="s">'l'</span><span class="p">:</span> <span class="mi">2</span><span class="p">,</span> <span class="s">'q'</span><span class="p">:</span> <span class="p">[</span><span class="mi">4</span><span class="p">,</span> <span class="mi">4</span><span class="p">],</span> <span class="s">'s'</span><span class="p">:</span> <span class="p">[</span><span class="mi">3</span><span class="p">]}</span>
<span class="gp">>>> </span><span class="n">sol</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">conelp</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">,</span> <span class="n">dims</span><span class="p">)</span>
<span class="gp">>>> </span><span class="n">sol</span><span class="p">[</span><span class="s">'status'</span><span class="p">]</span>
<span class="go">'optimal'</span>
<span class="gp">>>> </span><span class="k">print</span> <span class="n">sol</span><span class="p">[</span><span class="s">'x'</span><span class="p">]</span>
<span class="go">[-1.22e+00]</span>
<span class="go">[ 9.66e-02]</span>
<span class="go">[ 3.58e+00]</span>
<span class="gp">>>> </span><span class="k">print</span> <span class="n">sol</span><span class="p">[</span><span class="s">'z'</span><span class="p">]</span>
<span class="go">[ 9.30e-02]</span>
<span class="go">[ 2.04e-08]</span>
<span class="go">[ 2.35e-01]</span>
<span class="go">[ 1.33e-01]</span>
<span class="go">[-4.74e-02]</span>
<span class="go">[ 1.88e-01]</span>
<span class="go">[ 2.79e-08]</span>
<span class="go">[ 1.85e-09]</span>
<span class="go">[-6.32e-10]</span>
<span class="go">[-7.59e-09]</span>
<span class="go">[ 1.26e-01]</span>
<span class="go">[ 8.78e-02]</span>
<span class="go">[-8.67e-02]</span>
<span class="go">[ 8.78e-02]</span>
<span class="go">[ 6.13e-02]</span>
<span class="go">[-6.06e-02]</span>
<span class="go">[-8.67e-02]</span>
<span class="go">[-6.06e-02]</span>
<span class="go">[ 5.98e-02]</span>
</pre></div>
</div>
<p>Only the entries of <tt class="docutils literal"><span class="pre">G</span></tt> and <tt class="docutils literal"><span class="pre">h</span></tt> defining the lower triangular portions
of the coefficients in the linear matrix inequalities are accessed. We
obtain the same result if we define <tt class="docutils literal"><span class="pre">G</span></tt> and <tt class="docutils literal"><span class="pre">h</span></tt> as below.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="gp">>>> </span><span class="n">G</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([[</span> <span class="mf">16.</span><span class="p">,</span> <span class="mf">7.</span><span class="p">,</span> <span class="mf">24.</span><span class="p">,</span> <span class="o">-</span><span class="mf">8.</span><span class="p">,</span> <span class="mf">8.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span>
<span class="go"> 7., -5., 1., 0., 1., -7., 0., 0., -4.],</span>
<span class="go"> [-14., 2., 7., -13., -18., 3., 0., 0., -1., 0.,</span>
<span class="go"> 3., 13., -6., 0., 12., -10., 0., 0., -28.],</span>
<span class="go"> [ 5., 0., -15., 12., -6., 17., 0., 0., 0., -1.,</span>
<span class="go"> 9., 6., -6., 0., -7., -7., 0., 0., -11.]])</span>
<span class="gp">>>> </span><span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span> <span class="p">[</span> <span class="o">-</span><span class="mf">3.</span><span class="p">,</span> <span class="mf">5.</span><span class="p">,</span> <span class="mf">12.</span><span class="p">,</span> <span class="o">-</span><span class="mf">2.</span><span class="p">,</span> <span class="o">-</span><span class="mf">14.</span><span class="p">,</span> <span class="o">-</span><span class="mf">13.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span>
<span class="go"> 68., -30., -19., 0., 99., 23., 0., 0., 10.] )</span>
</pre></div>
</div>
</div>
<div class="section" id="quadratic-cone-programs">
<span id="s-coneqp"></span><h2>Quadratic Cone Programs<a class="headerlink" href="#quadratic-cone-programs" title="Permalink to this headline">¶</a></h2>
<dl class="function">
<dt id="cvxopt.solvers.coneqp">
<tt class="descclassname">cvxopt.solvers.</tt><tt class="descname">coneqp</tt><big>(</big><em>P</em>, <em>q</em><span class="optional">[</span>, <em>G</em>, <em>h</em><span class="optional">[</span>, <em>dims</em><span class="optional">[</span>, <em>A</em>, <em>b</em><span class="optional">[</span>, <em>initvals</em><span class="optional">[</span>, <em>kktsolver</em><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.solvers.coneqp" title="Permalink to this definition">¶</a></dt>
<dd><p>Solves a pair of primal and dual quadratic cone programs</p>
<div class="math">
<p><img src="_images/math/e91b9a70b0279938a93a0ec387ee7359ddb67098.png" alt="\begin{array}[t]{ll}
\mbox{minimize} & (1/2) x^T Px + q^T x \\
\mbox{subject to} & G x + s = h \\
& Ax = b \\
& s \succeq 0
\end{array}" /></p>
</div><p>and</p>
<div class="math">
<p><img src="_images/math/35cf8b0b6e5f53cc10c6ef43b8bc6fc921888521.png" alt="\newcommand{\Range}{\mbox{\textrm{range}}}
\begin{array}[t]{ll}
\mbox{maximize} & -(1/2) (q+G^Tz+A^Ty)^T P^\dagger
(q+G^Tz+A^Ty) -h^T z - b^T y \\
\mbox{subject to} & q + G^T z + A^T y \in \Range(P) \\
& z \succeq 0.
\end{array}" /></p>
</div><p>The primal variables are <img class="math" src="_images/math/26eeb5258ca5099acf8fe96b2a1049c48c89a5e6.png" alt="x"/> and the slack variable <img class="math" src="_images/math/f37bba504894945c07a32f5496d74299a37aa51c.png" alt="s"/>.
The dual variables are <img class="math" src="_images/math/092e364e1d9d19ad5fffb0b46ef4cc7f2da02c1c.png" alt="y"/> and <img class="math" src="_images/math/b13f21416d84e13708696f34dea81026cda583c9.png" alt="z"/>. The inequalities are
interpreted as <img class="math" src="_images/math/a0bfc2010a37ca5ee8d8553f74881b8e12ea4bfd.png" alt="s \in C"/>, <img class="math" src="_images/math/d22f3a5882fad95b5a9af193c57e3db91989d676.png" alt="z\in C"/>, where <img class="math" src="_images/math/c3355896da590fc491a10150a50416687626d7cc.png" alt="C"/> is a
cone defined as a Cartesian product of a nonnegative orthant, a number
of second-order cones, and a number of positive semidefinite cones:</p>
<div class="math">
<p><img src="_images/math/975932e25b8d20b8ef19bccfe15bfc80e9960ca2.png" alt="C = C_0 \times C_1 \times \cdots \times C_M \times C_{M+1} \times
\cdots \times C_{M+N}" /></p>
</div><p>with</p>
<div class="math">
<p><img src="_images/math/a34d96670035ec4b9d538485aca155388900d586.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
\newcommand{\svec}{\mathop{\mathbf{vec}}}
\newcommand{\symm}{{\mbox{\bf S}}}
\begin{split}
C_0 & =
\{ u \in \reals^l \;| \; u_k \geq 0, \; k=1, \ldots,l\}, \\
C_{k+1} & = \{ (u_0, u_1) \in \reals \times \reals^{r_{k}-1}
\; | \; u_0 \geq \|u_1\|_2 \}, \quad k=0,\ldots, M-1, \\
C_{k+M+1} &= \left\{ \svec(u) \; | \; u \in \symm^{t_k}_+
\right\}, \quad k=0,\ldots,N-1.
\end{split}" /></p>
</div><p>In this definition, <img class="math" src="_images/math/1caa3e3ac8919174afb2c7d55599b897ea724bd1.png" alt="\mathbf{vec}(u)"/> denotes a symmetric matrix
<img class="math" src="_images/math/9ad99798ec4c38e165cf517cb9e02b1c9e824103.png" alt="u"/> stored as a vector in column major order. The structure of
<img class="math" src="_images/math/c3355896da590fc491a10150a50416687626d7cc.png" alt="C"/> is specified by <tt class="docutils literal"><span class="pre">dims</span></tt>. This argument is a dictionary with
three fields.</p>
<dl class="docutils">
<dt><tt class="docutils literal"><span class="pre">dims['l']</span></tt>:</dt>
<dd><img class="math" src="_images/math/9b25f8e64b484493fda944d25cad453423041fe6.png" alt="l"/>, the dimension of the nonnegative orthant (a nonnegative
integer).</dd>
<dt><tt class="docutils literal"><span class="pre">dims['q']</span></tt>:</dt>
<dd><img class="math" src="_images/math/f9408643dfec56ef1bdd651b0858bed3b41a899b.png" alt="[r_0, \ldots, r_{M-1}]"/>, a list with the dimensions of the
second-order cones (positive integers).</dd>
<dt><tt class="docutils literal"><span class="pre">dims['s']</span></tt>:</dt>
<dd><img class="math" src="_images/math/15c9e0d5b18ecfcec0dc5faf60950122d134d40e.png" alt="[t_0, \ldots, t_{N-1}]"/>, a list with the dimensions of the
positive semidefinite cones (nonnegative integers).</dd>
</dl>
<p>The default value of <tt class="docutils literal"><span class="pre">dims</span></tt> is <tt class="docutils literal"><span class="pre">{'l':</span> <span class="pre">G.size[0],</span> <span class="pre">'q':</span> <span class="pre">[],</span>
<span class="pre">'s':</span> <span class="pre">[]}</span></tt>, i.e., by default the inequality is interpreted as a
componentwise vector inequality.</p>
<p><tt class="docutils literal"><span class="pre">P</span></tt> is a square dense or sparse real matrix, representing a positive
semidefinite symmetric matrix in <tt class="xref docutils literal"><span class="pre">'L'</span></tt> storage, i.e., only the
lower triangular part of <tt class="docutils literal"><span class="pre">P</span></tt> is referenced. <tt class="docutils literal"><span class="pre">q</span></tt> is a real
single-column dense matrix.</p>
<p>The arguments <tt class="docutils literal"><span class="pre">h</span></tt> and <tt class="docutils literal"><span class="pre">b</span></tt> are real single-column dense matrices.
<tt class="docutils literal"><span class="pre">G</span></tt> and <tt class="docutils literal"><span class="pre">A</span></tt> are real dense or sparse matrices. The number of rows
of <tt class="docutils literal"><span class="pre">G</span></tt> and <tt class="docutils literal"><span class="pre">h</span></tt> is equal to</p>
<div class="math">
<p><img src="_images/math/0fb35d76d5ee3a9cea74866affcb223883174be3.png" alt="K = l + \sum_{k=0}^{M-1} r_k + \sum_{k=0}^{N-1} t_k^2." /></p>
</div><p>The columns of <tt class="docutils literal"><span class="pre">G</span></tt> and <tt class="docutils literal"><span class="pre">h</span></tt> are vectors in</p>
<div class="math">
<p><img src="_images/math/c620bdffc558c7c84614e360601c181863f7860c.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
\reals^l \times \reals^{r_0} \times \cdots \times
\reals^{r_{M-1}} \times \reals^{t_0^2} \times \cdots \times
\reals^{t_{N-1}^2}," /></p>
</div><p>where the last <img class="math" src="_images/math/fc97ef67268cd4e91bacdf12b8901d7036c9a056.png" alt="N"/> components represent symmetric matrices stored
in column major order. The strictly upper triangular entries of these
matrices are not accessed (i.e., the symmetric matrices are stored
in the <tt class="xref docutils literal"><span class="pre">'L'</span></tt>-type column major order used in the <tt class="xref docutils literal"><span class="pre">blas</span></tt> and
<tt class="xref docutils literal"><span class="pre">lapack</span></tt> modules). The default values for <tt class="docutils literal"><span class="pre">G</span></tt>, <tt class="docutils literal"><span class="pre">h</span></tt>, <tt class="docutils literal"><span class="pre">A</span></tt>,
and <tt class="docutils literal"><span class="pre">b</span></tt> are matrices with zero rows, meaning that there are no
inequality or equality constraints.</p>
<p><tt class="docutils literal"><span class="pre">initvals</span></tt> is a dictionary with keys <tt class="xref docutils literal"><span class="pre">'x'</span></tt>, <tt class="xref docutils literal"><span class="pre">'s'</span></tt>,
<tt class="xref docutils literal"><span class="pre">'y'</span></tt>, <tt class="xref docutils literal"><span class="pre">'z'</span></tt> used as an optional starting point. The
vectors <tt class="docutils literal"><span class="pre">initvals['s']</span></tt> and <tt class="docutils literal"><span class="pre">initvals['z']</span></tt> must be
strictly positive with respect to the cone <img class="math" src="_images/math/c3355896da590fc491a10150a50416687626d7cc.png" alt="C"/>. If the argument
<tt class="docutils literal"><span class="pre">initvals</span></tt> or any the four entries in it are missing, default
starting points are used for the corresponding variables.</p>
<p>The role of the optional argument <tt class="docutils literal"><span class="pre">kktsolver</span></tt> is explained in the
section <a class="reference internal" href="#s-conelp-struct"><em>Exploiting Structure</em></a>.</p>
<p><tt class="xref docutils literal"><span class="pre">coneqp</span></tt> returns a dictionary that contains the result and
information about the accuracy of the solution. The most important
fields have keys <tt class="xref docutils literal"><span class="pre">'status'</span></tt>, <tt class="xref docutils literal"><span class="pre">'x'</span></tt>, <tt class="xref docutils literal"><span class="pre">'s'</span></tt>,
<tt class="xref docutils literal"><span class="pre">'y'</span></tt>, <tt class="xref docutils literal"><span class="pre">'z'</span></tt>. The <tt class="xref docutils literal"><span class="pre">'status'</span></tt> field is a string
with possible values <tt class="xref docutils literal"><span class="pre">'optimal'</span></tt> and <tt class="xref docutils literal"><span class="pre">'unknown'</span></tt>.</p>
<dl class="docutils">
<dt><tt class="xref docutils literal"><span class="pre">'optimal'</span></tt></dt>
<dd><p class="first">In this case the <tt class="xref docutils literal"><span class="pre">'x'</span></tt>, <tt class="xref docutils literal"><span class="pre">'s'</span></tt>, <tt class="xref docutils literal"><span class="pre">'y'</span></tt>, and
<tt class="xref docutils literal"><span class="pre">'z'</span></tt> entries contain primal and dual solutions, which
approximately satisfy</p>
<div class="last math">
<p><img src="_images/math/1d4aced4ae73a5ea1cc432d2029b806421524722.png" alt="Gx+s = h, \qquad Ax = b, \qquad Px + G^Tz + A^T y + c = 0,
s \succeq 0, \qquad z \succeq 0, \qquad s^T z = 0." /></p>
</div></dd>
<dt><tt class="xref docutils literal"><span class="pre">'unknown'</span></tt></dt>
<dd>This indicates that the algorithm terminated early due to numerical
difficulties or because the maximum number of iterations was
reached. The <tt class="xref docutils literal"><span class="pre">'x'</span></tt>, <tt class="xref docutils literal"><span class="pre">'s'</span></tt>, <tt class="xref docutils literal"><span class="pre">'y'</span></tt>,
<tt class="xref docutils literal"><span class="pre">'z'</span></tt> entries contain the iterates when the algorithm
terminated.</dd>
</dl>
<p>The other entries in the output dictionary summarize the accuracy
with which the optimality conditions are satisfied. The fields
<tt class="xref docutils literal"><span class="pre">'primal</span> <span class="pre">objective'</span></tt>, <tt class="xref docutils literal"><span class="pre">'dual</span> <span class="pre">objective'</span></tt>, and
<tt class="xref docutils literal"><span class="pre">'gap'</span></tt> give the primal objective <img class="math" src="_images/math/343d0b1bdf0a89348e54e78243206b00921891fa.png" alt="c^Tx"/>, the dual
objective calculated as</p>
<div class="math">
<p><img src="_images/math/29324e89cd738bc7e99f3eee77329a7a044b9454.png" alt="(1/2) x^TPx + q^T x + z^T(Gx-h) + y^T(Ax-b)" /></p>
</div><p>and the gap <img class="math" src="_images/math/2bd21984207bb64a4af86d045947fdb01d050f8f.png" alt="s^Tz"/>. The field <tt class="xref docutils literal"><span class="pre">'relative</span> <span class="pre">gap'</span></tt> is the
relative gap, defined as</p>
<div class="math">
<p><img src="_images/math/53e61f3814931a26816d64670ceadf602354dd4b.png" alt="\frac{s^Tz}{-\mbox{primal objective}}
\quad \mbox{if\ } \mbox{primal objective} < 0, \qquad
\frac{s^Tz}{\mbox{dual objective}}
\quad \mbox{if\ } \mbox{dual objective} > 0, \qquad" /></p>
</div><p>and <tt class="xref xref docutils literal"><span class="pre">None</span></tt> otherwise. The fields
<tt class="xref docutils literal"><span class="pre">'primal</span> <span class="pre">infeasibility'</span></tt> and <tt class="xref docutils literal"><span class="pre">'dual</span> <span class="pre">infeasibility'</span></tt> are
the residuals in the primal and dual equality constraints, defined as</p>
<div class="math">
<p><img src="_images/math/6bd8152c9dce040652f4d9e2725ff6a2522621ff.png" alt="\max\{ \frac{\|Gx+s-h\|_2}{\max\{1, \|h\|_2\}},
\frac{\|Ax-b\|_2}{\max\{1,\|b\|_2\}} \}, \qquad
\frac{\|Px + G^Tz + A^Ty + q\|_2}{\max\{1, \|q\|_2\}}," /></p>
</div><p>respectively.</p>
<p>It is required that the problem is solvable and that</p>
<div class="math">
<p><img src="_images/math/50b918c649afff9a6fe0b5f81d4e02355ff5ee65.png" alt="\newcommand{\Rank}{\mathop{\bf rank}}
\Rank(A) = p, \qquad
\Rank(\left[\begin{array}{c} P \\ G \\ A \end{array}\right]) = n," /></p>
</div><p>where <img class="math" src="_images/math/36f73fc1312ee0349b3f3a0f3bd9eb5504339011.png" alt="p"/> is the number or rows of <img class="math" src="_images/math/019e9892786e493964e145e7c5cf7b700314e53b.png" alt="A"/> and <img class="math" src="_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n"/> is the
number of columns of <img class="math" src="_images/math/6e28ce12d49d39f160d5a0ef54077fc98e4b9d2b.png" alt="G"/> and <img class="math" src="_images/math/019e9892786e493964e145e7c5cf7b700314e53b.png" alt="A"/>.</p>
</dd></dl>
<p>As an example, we solve a constrained least-squares problem</p>
<div class="math">
<p><img src="_images/math/d5a265356676b2bb4fbe1c50e2007bfd318074d8.png" alt="\begin{array}{ll}
\mbox{minimize} & \|Ax - b\|_2^2 \\
\mbox{subject to} & x \succeq 0 \\
& \|x\|_2 \leq 1
\end{array}" /></p>
</div><p>with</p>
<div class="math">
<p><img src="_images/math/6453fe08f902148e82972f42be74529a8c609deb.png" alt="A = \left[ \begin{array}{rrr}
0.3 & 0.6 & -0.3 \\
-0.4 & 1.2 & 0.0 \\
-0.2 & -1.7 & 0.6 \\
-0.4 & 0.3 & -1.2 \\
1.3 & -0.3 & -2.0
\end{array} \right], \qquad
b = \left[ \begin{array}{r} 1.5 \\ 0.0 \\ -1.2 \\ -0.7 \\ 0.0
\end{array} \right]." /></p>
</div><div class="highlight-python"><div class="highlight"><pre><span class="gp">>>> </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">solvers</span>
<span class="gp">>>> </span><span class="n">A</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span> <span class="p">[</span> <span class="o">.</span><span class="mi">3</span><span class="p">,</span> <span class="o">-.</span><span class="mi">4</span><span class="p">,</span> <span class="o">-.</span><span class="mi">2</span><span class="p">,</span> <span class="o">-.</span><span class="mi">4</span><span class="p">,</span> <span class="mf">1.3</span> <span class="p">],</span>
<span class="go"> [ .6, 1.2, -1.7, .3, -.3 ],</span>
<span class="go"> [-.3, .0, .6, -1.2, -2.0 ] ])</span>
<span class="gp">>>> </span><span class="n">b</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span> <span class="mf">1.5</span><span class="p">,</span> <span class="o">.</span><span class="mi">0</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.2</span><span class="p">,</span> <span class="o">-.</span><span class="mi">7</span><span class="p">,</span> <span class="o">.</span><span class="mi">0</span><span class="p">])</span>
<span class="gp">>>> </span><span class="n">m</span><span class="p">,</span> <span class="n">n</span> <span class="o">=</span> <span class="n">A</span><span class="o">.</span><span class="n">size</span>
<span class="gp">>>> </span><span class="n">I</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>
<span class="gp">>>> </span><span class="n">I</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="mf">1.0</span>
<span class="gp">>>> </span><span class="n">G</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="o">-</span><span class="n">I</span><span class="p">,</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="n">n</span><span class="p">)),</span> <span class="n">I</span><span class="p">])</span>
<span class="gp">>>> </span><span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="n">n</span><span class="o">*</span><span class="p">[</span><span class="mf">0.0</span><span class="p">]</span> <span class="o">+</span> <span class="p">[</span><span class="mf">1.0</span><span class="p">]</span> <span class="o">+</span> <span class="n">n</span><span class="o">*</span><span class="p">[</span><span class="mf">0.0</span><span class="p">])</span>
<span class="gp">>>> </span><span class="n">dims</span> <span class="o">=</span> <span class="p">{</span><span class="s">'l'</span><span class="p">:</span> <span class="n">n</span><span class="p">,</span> <span class="s">'q'</span><span class="p">:</span> <span class="p">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">],</span> <span class="s">'s'</span><span class="p">:</span> <span class="p">[]}</span>
<span class="gp">>>> </span><span class="n">x</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">coneqp</span><span class="p">(</span><span class="n">A</span><span class="o">.</span><span class="n">T</span><span class="o">*</span><span class="n">A</span><span class="p">,</span> <span class="o">-</span><span class="n">A</span><span class="o">.</span><span class="n">T</span><span class="o">*</span><span class="n">b</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">,</span> <span class="n">dims</span><span class="p">)[</span><span class="s">'x'</span><span class="p">]</span>
<span class="gp">>>> </span><span class="k">print</span> <span class="n">x</span>
<span class="go">[ 7.26e-01]</span>
<span class="go">[ 6.18e-01]</span>
<span class="go">[ 3.03e-01]</span>
</pre></div>
</div>
</div>
<div class="section" id="linear-programming">
<span id="s-lpsolver"></span><h2>Linear Programming<a class="headerlink" href="#linear-programming" title="Permalink to this headline">¶</a></h2>
<p>The function <a title="cvxopt.solvers.lp" class="reference internal" href="#cvxopt.solvers.lp"><tt class="xref docutils literal"><span class="pre">lp</span></tt></a> is an interface to
<a title="cvxopt.solvers.conelp" class="reference internal" href="#cvxopt.solvers.conelp"><tt class="xref docutils literal"><span class="pre">conelp</span></tt></a> for linear
programs. It also provides the option of using the linear programming
solvers from GLPK or MOSEK.</p>
<dl class="function">
<dt id="cvxopt.solvers.lp">
<tt class="descclassname">cvxopt.solvers.</tt><tt class="descname">lp</tt><big>(</big><em>c</em>, <em>G</em>, <em>h</em><span class="optional">[</span>, <em>A</em>, <em>b</em><span class="optional">[</span>, <em>solver</em><span class="optional">[</span>, <em>primalstart</em><span class="optional">[</span>, <em>dualstart</em><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.solvers.lp" title="Permalink to this definition">¶</a></dt>
<dd><p>Solves the pair of primal and dual linear programs</p>
<div class="math">
<p><img src="_images/math/1a8d47fe4c6b9295f4c73ecb0181d7cdc2f265bd.png" alt="\begin{array}[t]{ll}
\mbox{minimize} & c^T x \\
\mbox{subject to} & G x + s = h \\
& Ax = b \\
& s \succeq 0
\end{array}
\qquad\qquad
\begin{array}[t]{ll}
\mbox{maximize} & -h^T z - b^T y \\
\mbox{subject to} & G^T z + A^T y + c = 0 \\
& z \succeq 0.
\end{array}" /></p>
</div><p>The inequalities are componentwise vector inequalities.</p>
<p>The <tt class="docutils literal"><span class="pre">solver</span></tt> argument is used to choose among three solvers. When
it is omitted or <tt class="xref xref docutils literal"><span class="pre">None</span></tt>, the CVXOPT function
<a title="cvxopt.solvers.conelp" class="reference internal" href="#cvxopt.solvers.conelp"><tt class="xref docutils literal"><span class="pre">conelp</span></tt></a> is
used. The external solvers GLPK and MOSEK (if installed) can be
selected by setting <tt class="docutils literal"><span class="pre">solver</span></tt> to <tt class="xref docutils literal"><span class="pre">'glpk'</span></tt> or <tt class="xref docutils literal"><span class="pre">'mosek'</span></tt>;
see the section <a class="reference internal" href="#s-external"><em>Optional Solvers</em></a>. The meaning of the other
arguments and the return value are the same as for
<tt class="xref docutils literal"><span class="pre">conelp</span></tt> called with
<tt class="docutils literal"><span class="pre">dims</span></tt> equal to <tt class="docutils literal"><span class="pre">{'l':</span> <span class="pre">G.size[0],</span> <span class="pre">'q':</span> <span class="pre">[],</span> <span class="pre">'s':</span> <span class="pre">[]}</span></tt>.</p>
<p>The initial values are ignored when <tt class="docutils literal"><span class="pre">solver</span></tt> is <tt class="xref docutils literal"><span class="pre">'mosek'</span></tt> or
<tt class="xref docutils literal"><span class="pre">'glpk'</span></tt>. With the GLPK option, the solver does not return
certificates of primal or dual infeasibility: if the status is
<tt class="xref docutils literal"><span class="pre">'primal</span> <span class="pre">infeasible'</span></tt> or <tt class="xref docutils literal"><span class="pre">'dual</span> <span class="pre">infeasible'</span></tt>, all entries
of the output dictionary are <tt class="xref xref docutils literal"><span class="pre">None</span></tt>. If the GLPK or MOSEK
solvers are used, and the code returns with status <tt class="xref docutils literal"><span class="pre">'unknown'</span></tt>,
all the other fields in the output dictionary are <tt class="xref xref docutils literal"><span class="pre">None</span></tt>.</p>
</dd></dl>
<p>As a simple example we solve the LP</p>
<div class="math">
<p><img src="_images/math/20b4c4466ff23a0c6d3864f869c1c4a80c0fd408.png" alt="\begin{array}[t]{ll}
\mbox{minimize} & -4x_1 - 5x_2 \\
\mbox{subject to} & 2x_1 + x_2 \leq 3 \\
& x_1 + 2x_2 \leq 3 \\
& x_1 \geq 0, \quad x_2 \geq 0.
\end{array}" /></p>
</div><div class="highlight-python"><div class="highlight"><pre><span class="gp">>>> </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">solvers</span>
<span class="gp">>>> </span><span class="n">c</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="o">-</span><span class="mf">4.</span><span class="p">,</span> <span class="o">-</span><span class="mf">5.</span><span class="p">])</span>
<span class="gp">>>> </span><span class="n">G</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([[</span><span class="mf">2.</span><span class="p">,</span> <span class="mf">1.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">],</span> <span class="p">[</span><span class="mf">1.</span><span class="p">,</span> <span class="mf">2.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">]])</span>
<span class="gp">>>> </span><span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="mf">3.</span><span class="p">,</span> <span class="mf">3.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">])</span>
<span class="gp">>>> </span><span class="n">sol</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">lp</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">)</span>
<span class="gp">>>> </span><span class="k">print</span> <span class="n">sol</span><span class="p">[</span><span class="s">'x'</span><span class="p">]</span>
<span class="go">[ 1.00e+00]</span>
<span class="go">[ 1.00e+00]</span>
</pre></div>
</div>
</div>
<div class="section" id="quadratic-programming">
<span id="s-qp"></span><h2>Quadratic Programming<a class="headerlink" href="#quadratic-programming" title="Permalink to this headline">¶</a></h2>
<p>The function <a title="cvxopt.solvers.qp" class="reference internal" href="#cvxopt.solvers.qp"><tt class="xref docutils literal"><span class="pre">qp</span></tt></a> is an interface to
<a title="cvxopt.solvers.coneqp" class="reference internal" href="#cvxopt.solvers.coneqp"><tt class="xref docutils literal"><span class="pre">coneqp</span></tt></a> for quadratic
programs. It also provides the option of using the quadratic programming
solver from MOSEK.</p>
<dl class="function">
<dt id="cvxopt.solvers.qp">
<tt class="descclassname">cvxopt.solvers.</tt><tt class="descname">qp</tt><big>(</big><em>P</em>, <em>q</em><span class="optional">[</span>, <em>G</em>, <em>h</em><span class="optional">[</span>, <em>A</em>, <em>b</em><span class="optional">[</span>, <em>solver</em><span class="optional">[</span>, <em>initvals</em><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.solvers.qp" title="Permalink to this definition">¶</a></dt>
<dd><p>Solves the pair of primal and dual convex quadratic programs</p>
<div class="math">
<p><img src="_images/math/0a37188505ca27207357560da7b13319912482a8.png" alt="\begin{array}[t]{ll}
\mbox{minimize} & (1/2) x^TPx + q^T x \\
\mbox{subject to} & Gx \preceq h \\ & Ax = b
\end{array}" /></p>
</div><p>and</p>
<div class="math">
<p><img src="_images/math/05f225c5fa71605f1d627bf6731b4b5d7020a83d.png" alt="\newcommand{\Range}{\mbox{\textrm{range}}}
\begin{array}[t]{ll}
\mbox{maximize} & -(1/2) (q+G^Tz+A^Ty)^T P^\dagger
(q+G^Tz+A^Ty) -h^T z - b^T y \\
\mbox{subject to} & q + G^T z + A^T y \in \Range(P) \\
& z \succeq 0.
\end{array}" /></p>
</div><p>The inequalities are componentwise vector inequalities.</p>
<p>The default CVXOPT solver is used when the <tt class="docutils literal"><span class="pre">solver</span></tt> argument is
absent or <tt class="xref xref docutils literal"><span class="pre">None</span></tt>. The MOSEK solver (if installed) can be
selected by setting <tt class="docutils literal"><span class="pre">solver</span></tt> to <tt class="xref docutils literal"><span class="pre">'mosek'</span></tt>; see the
section <a class="reference internal" href="#s-external"><em>Optional Solvers</em></a>. The meaning of the other arguments and the
return value is the same as for
<a title="cvxopt.solvers.coneqp" class="reference internal" href="#cvxopt.solvers.coneqp"><tt class="xref docutils literal"><span class="pre">coneqp</span></tt></a> called with <cite>dims</cite>
equal to <tt class="docutils literal"><span class="pre">{'l':</span> <span class="pre">G.size[0],</span> <span class="pre">'q':</span> <span class="pre">[],</span> <span class="pre">'s':</span> <span class="pre">[]}</span></tt>.</p>
<p>When <tt class="docutils literal"><span class="pre">solver</span></tt> is <tt class="xref docutils literal"><span class="pre">'mosek'</span></tt>, the initial values are ignored,
and the <tt class="xref docutils literal"><span class="pre">'status'</span></tt> string in the solution dictionary can take
four possible values: <tt class="xref docutils literal"><span class="pre">'optimal'</span></tt>, <tt class="xref docutils literal"><span class="pre">'unknown'</span></tt>.
<tt class="xref docutils literal"><span class="pre">'primal</span> <span class="pre">infeasible'</span></tt>, <tt class="xref docutils literal"><span class="pre">'dual</span> <span class="pre">infeasible'</span></tt>.</p>
<dl class="docutils">
<dt><tt class="xref docutils literal"><span class="pre">'primal</span> <span class="pre">infeasible'</span></tt></dt>
<dd><p class="first">This means that a certificate of primal infeasibility has been
found. The <tt class="xref docutils literal"><span class="pre">'x'</span></tt> and <tt class="xref docutils literal"><span class="pre">'s'</span></tt> entries are
<tt class="xref xref docutils literal"><span class="pre">None</span></tt>, and the <tt class="xref docutils literal"><span class="pre">'z'</span></tt> and <tt class="xref docutils literal"><span class="pre">'y'</span></tt> entries are
vectors that approximately satisfy</p>
<div class="last math">
<p><img src="_images/math/e5dd15b60906f6540af7dbca5853d6a37a7f06b8.png" alt="G^Tz + A^T y = 0, \qquad h^Tz + b^Ty = -1, \qquad z \succeq 0." /></p>
</div></dd>
<dt><tt class="xref docutils literal"><span class="pre">'dual</span> <span class="pre">infeasible'</span></tt></dt>
<dd><p class="first">This means that a certificate of dual infeasibility has been found.
The <tt class="xref docutils literal"><span class="pre">'z'</span></tt> and <tt class="xref docutils literal"><span class="pre">'y'</span></tt> entries are <tt class="xref xref docutils literal"><span class="pre">None</span></tt>, and
the <tt class="xref docutils literal"><span class="pre">'x'</span></tt> and <tt class="xref docutils literal"><span class="pre">'s'</span></tt> entries are vectors that
approximately satisfy</p>
<div class="last math">
<p><img src="_images/math/d115e96624cc837dba5b4dda34873b8da01f8061.png" alt="Px = 0, \qquad q^Tx = -1, \qquad Gx + s = 0, \qquad Ax=0,
\qquad s \succeq 0." /></p>
</div></dd>
</dl>
</dd></dl>
<p>As an example we compute the trade-off curve on page 187 of the book
<a class="reference external" href="http://www.stanford.edu/~boyd/cvxbook">Convex Optimization</a>,
by solving the quadratic program</p>
<div class="math">
<p><img src="_images/math/af45084f926e60a499b6acab3a790e2e4e0735d9.png" alt="\newcommand{\ones}{{\bf 1}}
\begin{array}{ll}
\mbox{minimize} & -\bar p^T x + \mu x^T S x \\
\mbox{subject to} & \ones^T x = 1, \quad x \succeq 0
\end{array}" /></p>
</div><p>for a sequence of positive values of <img class="math" src="_images/math/2d8c833ed800824727cd7bd2fb9de1a12ad7e674.png" alt="\mu"/>. The code below computes
the trade-off curve and produces two figures using the
<a class="reference external" href="http://matplotlib.sourceforge.net">Matplotlib</a> package.</p>
<img alt="_images/portfolio2.png" src="_images/portfolio2.png" style="width: 400px;" />
<img alt="_images/portfolio1.png" src="_images/portfolio1.png" style="width: 400px;" />
<div class="highlight-python"><div class="highlight"><pre><span class="kn">from</span> <span class="nn">math</span> <span class="kn">import</span> <span class="n">sqrt</span>
<span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span>
<span class="kn">from</span> <span class="nn">cvxopt.blas</span> <span class="kn">import</span> <span class="n">dot</span>
<span class="kn">from</span> <span class="nn">cvxopt.solvers</span> <span class="kn">import</span> <span class="n">qp</span>
<span class="kn">import</span> <span class="nn">pylab</span>
<span class="c"># Problem data.</span>
<span class="n">n</span> <span class="o">=</span> <span class="mi">4</span>
<span class="n">S</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([[</span> <span class="mf">4e-2</span><span class="p">,</span> <span class="mf">6e-3</span><span class="p">,</span> <span class="o">-</span><span class="mf">4e-3</span><span class="p">,</span> <span class="mf">0.0</span> <span class="p">],</span>
<span class="p">[</span> <span class="mf">6e-3</span><span class="p">,</span> <span class="mf">1e-2</span><span class="p">,</span> <span class="mf">0.0</span><span class="p">,</span> <span class="mf">0.0</span> <span class="p">],</span>
<span class="p">[</span><span class="o">-</span><span class="mf">4e-3</span><span class="p">,</span> <span class="mf">0.0</span><span class="p">,</span> <span class="mf">2.5e-3</span><span class="p">,</span> <span class="mf">0.0</span> <span class="p">],</span>
<span class="p">[</span> <span class="mf">0.0</span><span class="p">,</span> <span class="mf">0.0</span><span class="p">,</span> <span class="mf">0.0</span><span class="p">,</span> <span class="mf">0.0</span> <span class="p">]])</span>
<span class="n">pbar</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="o">.</span><span class="mi">12</span><span class="p">,</span> <span class="o">.</span><span class="mi">10</span><span class="p">,</span> <span class="o">.</span><span class="mo">07</span><span class="p">,</span> <span class="o">.</span><span class="mo">03</span><span class="p">])</span>
<span class="n">G</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>
<span class="n">G</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span>
<span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>
<span class="n">A</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">1.0</span><span class="p">,</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>
<span class="n">b</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">1.0</span><span class="p">)</span>
<span class="c"># Compute trade-off.</span>
<span class="n">N</span> <span class="o">=</span> <span class="mi">100</span>
<span class="n">mus</span> <span class="o">=</span> <span class="p">[</span> <span class="mi">10</span><span class="o">**</span><span class="p">(</span><span class="mf">5.0</span><span class="o">*</span><span class="n">t</span><span class="o">/</span><span class="n">N</span><span class="o">-</span><span class="mf">1.0</span><span class="p">)</span> <span class="k">for</span> <span class="n">t</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="n">N</span><span class="p">)</span> <span class="p">]</span>
<span class="n">portfolios</span> <span class="o">=</span> <span class="p">[</span> <span class="n">qp</span><span class="p">(</span><span class="n">mu</span><span class="o">*</span><span class="n">S</span><span class="p">,</span> <span class="o">-</span><span class="n">pbar</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">,</span> <span class="n">A</span><span class="p">,</span> <span class="n">b</span><span class="p">)[</span><span class="s">'x'</span><span class="p">]</span> <span class="k">for</span> <span class="n">mu</span> <span class="ow">in</span> <span class="n">mus</span> <span class="p">]</span>
<span class="n">returns</span> <span class="o">=</span> <span class="p">[</span> <span class="n">dot</span><span class="p">(</span><span class="n">pbar</span><span class="p">,</span><span class="n">x</span><span class="p">)</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">portfolios</span> <span class="p">]</span>
<span class="n">risks</span> <span class="o">=</span> <span class="p">[</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">dot</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">S</span><span class="o">*</span><span class="n">x</span><span class="p">))</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">portfolios</span> <span class="p">]</span>
<span class="c"># Plot trade-off curve and optimal allocations.</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">figure</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">facecolor</span><span class="o">=</span><span class="s">'w'</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">plot</span><span class="p">(</span><span class="n">risks</span><span class="p">,</span> <span class="n">returns</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">xlabel</span><span class="p">(</span><span class="s">'standard deviation'</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">ylabel</span><span class="p">(</span><span class="s">'expected return'</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">axis</span><span class="p">([</span><span class="mi">0</span><span class="p">,</span> <span class="mf">0.2</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mf">0.15</span><span class="p">])</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">title</span><span class="p">(</span><span class="s">'Risk-return trade-off curve (fig 4.12)'</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">yticks</span><span class="p">([</span><span class="mf">0.00</span><span class="p">,</span> <span class="mf">0.05</span><span class="p">,</span> <span class="mf">0.10</span><span class="p">,</span> <span class="mf">0.15</span><span class="p">])</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">figure</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">facecolor</span><span class="o">=</span><span class="s">'w'</span><span class="p">)</span>
<span class="n">c1</span> <span class="o">=</span> <span class="p">[</span> <span class="n">x</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">portfolios</span> <span class="p">]</span>
<span class="n">c2</span> <span class="o">=</span> <span class="p">[</span> <span class="n">x</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="n">x</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">portfolios</span> <span class="p">]</span>
<span class="n">c3</span> <span class="o">=</span> <span class="p">[</span> <span class="n">x</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="n">x</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">x</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">portfolios</span> <span class="p">]</span>
<span class="n">c4</span> <span class="o">=</span> <span class="p">[</span> <span class="n">x</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="n">x</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">x</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">+</span> <span class="n">x</span><span class="p">[</span><span class="mi">3</span><span class="p">]</span> <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">portfolios</span> <span class="p">]</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">fill</span><span class="p">(</span><span class="n">risks</span> <span class="o">+</span> <span class="p">[</span><span class="o">.</span><span class="mi">20</span><span class="p">],</span> <span class="n">c1</span> <span class="o">+</span> <span class="p">[</span><span class="mf">0.0</span><span class="p">],</span> <span class="s">'#F0F0F0'</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">fill</span><span class="p">(</span><span class="n">risks</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">::</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">risks</span><span class="p">,</span> <span class="n">c2</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">::</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">c1</span><span class="p">,</span> <span class="n">facecolor</span> <span class="o">=</span> <span class="s">'#D0D0D0'</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">fill</span><span class="p">(</span><span class="n">risks</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">::</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">risks</span><span class="p">,</span> <span class="n">c3</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">::</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">c2</span><span class="p">,</span> <span class="n">facecolor</span> <span class="o">=</span> <span class="s">'#F0F0F0'</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">fill</span><span class="p">(</span><span class="n">risks</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">::</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">risks</span><span class="p">,</span> <span class="n">c4</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">::</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">c3</span><span class="p">,</span> <span class="n">facecolor</span> <span class="o">=</span> <span class="s">'#D0D0D0'</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">axis</span><span class="p">([</span><span class="mf">0.0</span><span class="p">,</span> <span class="mf">0.2</span><span class="p">,</span> <span class="mf">0.0</span><span class="p">,</span> <span class="mf">1.0</span><span class="p">])</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">xlabel</span><span class="p">(</span><span class="s">'standard deviation'</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">ylabel</span><span class="p">(</span><span class="s">'allocation'</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">text</span><span class="p">(</span><span class="o">.</span><span class="mi">15</span><span class="p">,</span><span class="o">.</span><span class="mi">5</span><span class="p">,</span><span class="s">'x1'</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">text</span><span class="p">(</span><span class="o">.</span><span class="mi">10</span><span class="p">,</span><span class="o">.</span><span class="mi">7</span><span class="p">,</span><span class="s">'x2'</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">text</span><span class="p">(</span><span class="o">.</span><span class="mo">05</span><span class="p">,</span><span class="o">.</span><span class="mi">7</span><span class="p">,</span><span class="s">'x3'</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">text</span><span class="p">(</span><span class="o">.</span><span class="mo">01</span><span class="p">,</span><span class="o">.</span><span class="mi">7</span><span class="p">,</span><span class="s">'x4'</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">title</span><span class="p">(</span><span class="s">'Optimal allocations (fig 4.12)'</span><span class="p">)</span>
<span class="n">pylab</span><span class="o">.</span><span class="n">show</span><span class="p">()</span>
</pre></div>
</div>
</div>
<div class="section" id="second-order-cone-programming">
<span id="s-socpsolver"></span><h2>Second-Order Cone Programming<a class="headerlink" href="#second-order-cone-programming" title="Permalink to this headline">¶</a></h2>
<p>The function <a title="cvxopt.solvers.socp" class="reference internal" href="#cvxopt.solvers.socp"><tt class="xref docutils literal"><span class="pre">socp</span></tt></a> is a simpler interface to
<a title="cvxopt.solvers.coneqp" class="reference internal" href="#cvxopt.solvers.coneqp"><tt class="xref docutils literal"><span class="pre">conelp</span></tt></a> for
cone programs with no linear matrix inequality constraints.</p>
<dl class="function">
<dt id="cvxopt.solvers.socp">
<tt class="descclassname">cvxopt.solvers.</tt><tt class="descname">socp</tt><big>(</big><em>c</em><span class="optional">[</span>, <em>Gl</em>, <em>hl</em><span class="optional">[</span>, <em>Gq</em>, <em>hq</em><span class="optional">[</span>, <em>A</em>, <em>b</em><span class="optional">[</span>, <em>solver</em><span class="optional">[</span>, <em>primalstart</em><span class="optional">[</span>, <em>dualstart</em><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.solvers.socp" title="Permalink to this definition">¶</a></dt>
<dd><p>Solves the pair of primal and dual second-order cone programs</p>
<div class="math">
<p><img src="_images/math/cdd797a6ddbbc6d531d242e8477e3d03ef039677.png" alt="\begin{array}[t]{ll}
\mbox{minimize} & c^T x \\
\mbox{subject to} & G_k x + s_k = h_k, \quad k = 0, \ldots, M \\
& Ax = b \\
& s_0 \succeq 0 \\
& s_{k0} \geq \|s_{k1}\|_2, \quad k = 1,\ldots,M
\end{array}" /></p>
</div><p>and</p>
<div class="math">
<p><img src="_images/math/48959eadc206a5205ea6220c002e34ecfc56db25.png" alt="\begin{array}[t]{ll}
\mbox{maximize} & - \sum_{k=0}^M h_k^Tz_k - b^T y \\
\mbox{subject to} & \sum_{k=0}^M G_k^T z_k + A^T y + c = 0 \\
& z_0 \succeq 0 \\
& z_{k0} \geq \|z_{k1}\|_2, \quad k=1,\ldots,M.
\end{array}" /></p>
</div><p>The inequalities</p>
<div class="math">
<p><img src="_images/math/f5e4cd18619ee7f651ab49db6de2bb97de14bd98.png" alt="s_0 \succeq 0, \qquad z_0 \succeq 0" /></p>
</div><p>are componentwise vector inequalities. In the other inequalities, it
is assumed that the variables are partitioned as</p>
<div class="math">
<p><img src="_images/math/208cbfe014aba5e7e2a46a6d382991da92f36f74.png" alt="\newcommand{\reals}{{\mbox{\bf R}}}
s_k = (s_{k0}, s_{k1}) \in\reals\times\reals^{r_{k}-1}, \qquad
z_k = (z_{k0}, z_{k1}) \in\reals\times\reals^{r_{k}-1}, \qquad
k=1,\ldots,M." /></p>
</div><p>The input argument <tt class="docutils literal"><span class="pre">c</span></tt> is a real single-column dense matrix. The
arguments <tt class="docutils literal"><span class="pre">Gl</span></tt> and <tt class="docutils literal"><span class="pre">hl</span></tt> are the coefficient matrix <img class="math" src="_images/math/ece9cd1cf6a947d28fd135a387023993c1cff4fc.png" alt="G_0"/> and
the righthand side <img class="math" src="_images/math/2ccfe97aad19720278a939bedb093af63f8ec959.png" alt="h_0"/> of the componentwise inequalities.
<tt class="docutils literal"><span class="pre">Gl</span></tt> is a real dense or sparse matrix; <tt class="docutils literal"><span class="pre">hl</span></tt> is a real single-column
dense matrix. The default values for <tt class="docutils literal"><span class="pre">Gl</span></tt> and <tt class="docutils literal"><span class="pre">hl</span></tt> are matrices
with zero rows.</p>
<p>The argument <tt class="docutils literal"><span class="pre">Gq</span></tt> is a list of <img class="math" src="_images/math/5d1e4485dc90c450e8c76826516c1b2ccb8fce16.png" alt="M"/> dense or sparse matrices
<img class="math" src="_images/math/8db8d2c3b6325306a87e8a10b0e5358afb2f23eb.png" alt="G_1"/>, ..., <img class="math" src="_images/math/4bb8d1af6d1d1da03c879b4d35c7ea51813c4e9a.png" alt="G_M"/>. The argument <tt class="docutils literal"><span class="pre">hq</span></tt> is a list of
<img class="math" src="_images/math/5d1e4485dc90c450e8c76826516c1b2ccb8fce16.png" alt="M"/> dense single-column matrices <img class="math" src="_images/math/32d78aae1741ff43c6f40e2077f1ab67900cca2c.png" alt="h_1"/>, ldots,
<img class="math" src="_images/math/4554cc0b90e8722fe8ca11c108832c9fbaeb647d.png" alt="h_M"/>. The elements of <tt class="docutils literal"><span class="pre">Gq</span></tt> and <tt class="docutils literal"><span class="pre">hq</span></tt> must have at least one
row. The default values of <tt class="docutils literal"><span class="pre">Gq</span></tt> and <tt class="docutils literal"><span class="pre">hq</span></tt> are empty lists.</p>
<p><tt class="docutils literal"><span class="pre">A</span></tt> is dense or sparse matrix and <tt class="docutils literal"><span class="pre">b</span></tt> is a single-column dense
matrix. The default values for <tt class="docutils literal"><span class="pre">A</span></tt> and <tt class="docutils literal"><span class="pre">b</span></tt> are matrices with
zero rows.</p>
<p>The <tt class="docutils literal"><span class="pre">solver</span></tt> argument is used to choose between two solvers: the
CVXOPT <a title="cvxopt.solvers.conelp" class="reference internal" href="#cvxopt.solvers.conelp"><tt class="xref docutils literal"><span class="pre">conelp</span></tt></a> solver (used when
<tt class="docutils literal"><span class="pre">solver</span></tt> is absent or equal
to <tt class="xref xref docutils literal"><span class="pre">None</span></tt> and the external solver MOSEK (<tt class="docutils literal"><span class="pre">solver</span></tt> is
<tt class="xref docutils literal"><span class="pre">'mosek'</span></tt>); see the section <a class="reference internal" href="#s-external"><em>Optional Solvers</em></a>. With the
<tt class="xref docutils literal"><span class="pre">'mosek'</span></tt> option the code does not accept problems with equality
constraints.</p>
<p><tt class="docutils literal"><span class="pre">primalstart</span></tt> and <tt class="docutils literal"><span class="pre">dualstart</span></tt> are dictionaries with optional
primal, respectively, dual starting points. <tt class="docutils literal"><span class="pre">primalstart</span></tt> has
elements <tt class="xref docutils literal"><span class="pre">'x'</span></tt>, <tt class="xref docutils literal"><span class="pre">'sl'</span></tt>, <tt class="xref docutils literal"><span class="pre">'sq'</span></tt>.
<tt class="docutils literal"><span class="pre">primalstart['x']</span></tt> and <tt class="docutils literal"><span class="pre">primalstart['sl']</span></tt> are
single-column dense matrices with the initial values of <img class="math" src="_images/math/26eeb5258ca5099acf8fe96b2a1049c48c89a5e6.png" alt="x"/> and
<img class="math" src="_images/math/058418cc5858eeab7f1ceb92f70b1c00fe7fe5d6.png" alt="s_0"/>; <tt class="docutils literal"><span class="pre">primalstart['sq']</span></tt> is a list of single-column
matrices with the initial values of <img class="math" src="_images/math/7ae90d71491f591ab5a16d19ee7629e8226ec9ce.png" alt="s_1"/>, ldots, <img class="math" src="_images/math/699b12aae3e02312980eb11d3b32acff89a71ff9.png" alt="s_M"/>.
The initial values must satisfy the inequalities in the primal problem
strictly, but not necessarily the equality constraints.</p>
<p><tt class="docutils literal"><span class="pre">dualstart</span></tt> has elements <tt class="xref docutils literal"><span class="pre">'y'</span></tt>, <tt class="xref docutils literal"><span class="pre">'zl'</span></tt>, <tt class="xref docutils literal"><span class="pre">'zq'</span></tt>.
<tt class="docutils literal"><span class="pre">dualstart['y']</span></tt> and <tt class="docutils literal"><span class="pre">dualstart['zl']</span></tt> are single-column
dense matrices with the initial values of <img class="math" src="_images/math/092e364e1d9d19ad5fffb0b46ef4cc7f2da02c1c.png" alt="y"/> and <img class="math" src="_images/math/bab9abe98679312d2a3308c76188cf2cbc492f68.png" alt="z_0"/>.
<tt class="docutils literal"><span class="pre">dualstart['zq']</span></tt> is a list of single-column matrices with the
initial values of <img class="math" src="_images/math/9ea31e5c5613f025b5be8aca425d318168491d89.png" alt="z_1"/>, ldots, <img class="math" src="_images/math/0f40544ba8e65435a6bd704399b347d25ce947fc.png" alt="z_M"/>. These values must
satisfy the dual inequalities strictly, but not necessarily the
equality constraint.</p>
<p>The arguments <tt class="docutils literal"><span class="pre">primalstart</span></tt> and <tt class="docutils literal"><span class="pre">dualstart</span></tt> are ignored when the
MOSEK solver is used.</p>
<p><tt class="xref docutils literal"><span class="pre">socp</span></tt> returns a dictionary that include entries with keys
<tt class="xref docutils literal"><span class="pre">'status'</span></tt>, <tt class="xref docutils literal"><span class="pre">'x'</span></tt>, <tt class="xref docutils literal"><span class="pre">'sl'</span></tt>, <tt class="xref docutils literal"><span class="pre">'sq'</span></tt>,
<tt class="xref docutils literal"><span class="pre">'y'</span></tt>, <tt class="xref docutils literal"><span class="pre">'zl'</span></tt>, <tt class="xref docutils literal"><span class="pre">'zq'</span></tt>. The <tt class="xref docutils literal"><span class="pre">'sl'</span></tt> and
<tt class="xref docutils literal"><span class="pre">'zl'</span></tt> fields are matrices with the primal slacks and dual
variables associated with the componentwise linear inequalities.
The <tt class="xref docutils literal"><span class="pre">'sq'</span></tt> and <tt class="xref docutils literal"><span class="pre">'zq'</span></tt> fields are lists with the primal
slacks and dual variables associated with the second-order cone
inequalities. The other entries in the output dictionary have the
same meaning as in the output of
<a title="cvxopt.solvers.conelp" class="reference internal" href="#cvxopt.solvers.conelp"><tt class="xref docutils literal"><span class="pre">conelp</span></tt></a>.</p>
</dd></dl>
<p>As an example, we solve the second-order cone program</p>
<div class="math">
<p><img src="_images/math/f429bacb9935d242fb93509e5b154822ed2d1df7.png" alt="\begin{array}{ll}
\mbox{minimize} & -2x_1 + x_2 + 5x_3 \\*[2ex]
\mbox{subject to} & \left\| \left[\begin{array}{c}
-13 x_1 + 3 x_2 + 5 x_3 - 3 \\
-12 x_1 + 12 x_2 - 6 x_3 - 2 \end{array}\right] \right\|_2
\leq -12 x_1 - 6 x_2 + 5x_3 - 12 \\*[2ex]
& \left\| \left[\begin{array}{c}
-3 x_1 + 6 x_2 + 2 x_3 \\
x_1 + 9 x_2 + 2 x_3 + 3 \\
-x_1 - 19 x_2 + 3 x_3 - 42 \end{array}\right] \right\|_2
\leq -3x_1 + 6x_2 - 10x_3 + 27.
\end{array}" /></p>
</div><div class="highlight-python"><div class="highlight"><pre><span class="gp">>>> </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">solvers</span>
<span class="gp">>>> </span><span class="n">c</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="o">-</span><span class="mf">2.</span><span class="p">,</span> <span class="mf">1.</span><span class="p">,</span> <span class="mf">5.</span><span class="p">])</span>
<span class="gp">>>> </span><span class="n">G</span> <span class="o">=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">(</span> <span class="p">[[</span><span class="mf">12.</span><span class="p">,</span> <span class="mf">13.</span><span class="p">,</span> <span class="mf">12.</span><span class="p">],</span> <span class="p">[</span><span class="mf">6.</span><span class="p">,</span> <span class="o">-</span><span class="mf">3.</span><span class="p">,</span> <span class="o">-</span><span class="mf">12.</span><span class="p">],</span> <span class="p">[</span><span class="o">-</span><span class="mf">5.</span><span class="p">,</span> <span class="o">-</span><span class="mf">5.</span><span class="p">,</span> <span class="mf">6.</span><span class="p">]]</span> <span class="p">)</span> <span class="p">]</span>
<span class="gp">>>> </span><span class="n">G</span> <span class="o">+=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">(</span> <span class="p">[[</span><span class="mf">3.</span><span class="p">,</span> <span class="mf">3.</span><span class="p">,</span> <span class="o">-</span><span class="mf">1.</span><span class="p">,</span> <span class="mf">1.</span><span class="p">],</span> <span class="p">[</span><span class="o">-</span><span class="mf">6.</span><span class="p">,</span> <span class="o">-</span><span class="mf">6.</span><span class="p">,</span> <span class="o">-</span><span class="mf">9.</span><span class="p">,</span> <span class="mf">19.</span><span class="p">],</span> <span class="p">[</span><span class="mf">10.</span><span class="p">,</span> <span class="o">-</span><span class="mf">2.</span><span class="p">,</span> <span class="o">-</span><span class="mf">2.</span><span class="p">,</span> <span class="o">-</span><span class="mf">3.</span><span class="p">]]</span> <span class="p">)</span> <span class="p">]</span>
<span class="gp">>>> </span><span class="n">h</span> <span class="o">=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">(</span> <span class="p">[</span><span class="o">-</span><span class="mf">12.</span><span class="p">,</span> <span class="o">-</span><span class="mf">3.</span><span class="p">,</span> <span class="o">-</span><span class="mf">2.</span><span class="p">]</span> <span class="p">),</span> <span class="n">matrix</span><span class="p">(</span> <span class="p">[</span><span class="mf">27.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">3.</span><span class="p">,</span> <span class="o">-</span><span class="mf">42.</span><span class="p">]</span> <span class="p">)</span> <span class="p">]</span>
<span class="gp">>>> </span><span class="n">sol</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">socp</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">Gq</span> <span class="o">=</span> <span class="n">G</span><span class="p">,</span> <span class="n">hq</span> <span class="o">=</span> <span class="n">h</span><span class="p">)</span>
<span class="gp">>>> </span><span class="n">sol</span><span class="p">[</span><span class="s">'status'</span><span class="p">]</span>
<span class="go">optimal</span>
<span class="gp">>>> </span><span class="k">print</span> <span class="n">sol</span><span class="p">[</span><span class="s">'x'</span><span class="p">]</span>
<span class="go">[-5.02e+00]</span>
<span class="go">[-5.77e+00]</span>
<span class="go">[-8.52e+00]</span>
<span class="gp">>>> </span><span class="k">print</span> <span class="n">sol</span><span class="p">[</span><span class="s">'zq'</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span>
<span class="go">[ 1.34e+00]</span>
<span class="go">[-7.63e-02]</span>
<span class="go">[-1.34e+00]</span>
<span class="gp">>>> </span><span class="k">print</span> <span class="n">sol</span><span class="p">[</span><span class="s">'zq'</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span>
<span class="go">[ 1.02e+00]</span>
<span class="go">[ 4.02e-01]</span>
<span class="go">[ 7.80e-01]</span>
<span class="go">[-5.17e-01]</span>
</pre></div>
</div>
</div>
<div class="section" id="semidefinite-programming">
<span id="s-sdpsolver"></span><h2>Semidefinite Programming<a class="headerlink" href="#semidefinite-programming" title="Permalink to this headline">¶</a></h2>
<p>The function <a title="cvxopt.solvers.sdp" class="reference internal" href="#cvxopt.solvers.sdp"><tt class="xref docutils literal"><span class="pre">sdp</span></tt></a> is a simple interface to
<a title="cvxopt.solvers.conelp" class="reference internal" href="#cvxopt.solvers.conelp"><tt class="xref docutils literal"><span class="pre">conelp</span></tt></a> for cone
programs with no second-order cone constraints. It also provides the
option of using the DSDP semidefinite programming solver.</p>
<dl class="function">
<dt id="cvxopt.solvers.sdp">
<tt class="descclassname">cvxopt.solvers.</tt><tt class="descname">sdp</tt><big>(</big><em>c</em><span class="optional">[</span>, <em>Gl</em>, <em>hl</em><span class="optional">[</span>, <em>Gs</em>, <em>hs</em><span class="optional">[</span>, <em>A</em>, <em>b</em><span class="optional">[</span>, <em>solver</em><span class="optional">[</span>, <em>primalstart</em><span class="optional">[</span>, <em>dualstart</em><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><span class="optional">]</span><big>)</big><a class="headerlink" href="#cvxopt.solvers.sdp" title="Permalink to this definition">¶</a></dt>
<dd><p>Solves the pair of primal and dual semidefinite programs</p>
<div class="math">
<p><img src="_images/math/c123375fddc2a35885eb9c2b060ad0c41a37e224.png" alt="\newcommand{\svec}{\mathop{\mathbf{vec}}}
\begin{array}[t]{ll}
\mbox{minimize} & c^T x \\
\mbox{subject to} & G_0 x + s_0 = h_0 \\
& G_k x + \svec{(s_k)} = \svec{(h_k)},
\quad k = 1, \ldots, N \\
& Ax = b \\
& s_0 \succeq 0 \\
& s_k \succeq 0, \quad k=1,\ldots,N
\end{array}" /></p>
</div><p>and</p>
<div class="math">
<p><img src="_images/math/f5937df8d764f5fe56c90796b10f06456eaea62a.png" alt="\newcommand{\Tr}{\mathop{\mathbf{tr}}}
\newcommand{\svec}{\mathop{\mathbf{vec}}}
\begin{array}[t]{ll}
\mbox{maximize} & -h_0^Tz_0 - \sum_{k=1}^N \Tr(h_kz_k) - b^Ty \\
\mbox{subject to} & G_0^Tz_0 + \sum_{k=1}^N G_k^T \svec(z_k) +
A^T y + c = 0 \\
& z_0 \succeq 0 \\
& z_k \succeq 0, \quad k=1,\ldots,N.
\end{array}" /></p>
</div><p>The inequalities</p>
<div class="math">
<p><img src="_images/math/f5e4cd18619ee7f651ab49db6de2bb97de14bd98.png" alt="s_0 \succeq 0, \qquad z_0 \succeq 0" /></p>
</div><p>are componentwise vector inequalities. The other inequalities are
matrix inequalities (ie, the require the lefthand sides to be positive
semidefinite). We use the notation <img class="math" src="_images/math/bf7782808286990f4316d2e900ae9022e0fb7689.png" alt="\mathbf{vec}(z)"/> to denote
a symmetric matrix <img class="math" src="_images/math/b13f21416d84e13708696f34dea81026cda583c9.png" alt="z"/> stored in column major order as a column
vector.</p>
<p>The input argument <tt class="docutils literal"><span class="pre">c</span></tt> is a real single-column dense matrix. The
arguments <tt class="docutils literal"><span class="pre">Gl</span></tt> and <tt class="docutils literal"><span class="pre">hl</span></tt> are the coefficient matrix <img class="math" src="_images/math/ece9cd1cf6a947d28fd135a387023993c1cff4fc.png" alt="G_0"/> and
the righthand side <img class="math" src="_images/math/2ccfe97aad19720278a939bedb093af63f8ec959.png" alt="h_0"/> of the componentwise inequalities.
<tt class="docutils literal"><span class="pre">Gl</span></tt> is a real dense or sparse matrix; <tt class="docutils literal"><span class="pre">hl</span></tt> is a real
single-column dense matrix. The default values for <tt class="docutils literal"><span class="pre">Gl</span></tt> and <tt class="docutils literal"><span class="pre">hl</span></tt>
are matrices with zero rows.</p>
<p><tt class="docutils literal"><span class="pre">Gs</span></tt> and <tt class="docutils literal"><span class="pre">hs</span></tt> are lists of length <img class="math" src="_images/math/fc97ef67268cd4e91bacdf12b8901d7036c9a056.png" alt="N"/> that specify the
linear matrix inequality constraints. <tt class="docutils literal"><span class="pre">Gs</span></tt> is a list of <img class="math" src="_images/math/fc97ef67268cd4e91bacdf12b8901d7036c9a056.png" alt="N"/>
dense or sparse real matrices <img class="math" src="_images/math/8db8d2c3b6325306a87e8a10b0e5358afb2f23eb.png" alt="G_1"/>, ldots, <img class="math" src="_images/math/4bb8d1af6d1d1da03c879b4d35c7ea51813c4e9a.png" alt="G_M"/>. The
columns of these matrices can be interpreted as symmetric matrices
stored in column major order, using the BLAS <tt class="xref docutils literal"><span class="pre">'L'</span></tt>-type storage
(i.e., only the entries corresponding to lower triangular positions
are accessed). <tt class="docutils literal"><span class="pre">hs</span></tt> is a list of <img class="math" src="_images/math/fc97ef67268cd4e91bacdf12b8901d7036c9a056.png" alt="N"/> dense symmetric matrices
<img class="math" src="_images/math/32d78aae1741ff43c6f40e2077f1ab67900cca2c.png" alt="h_1"/>, ldots, <img class="math" src="_images/math/e626b4609099cd3fc0c2fd48091b8153b57417c9.png" alt="h_N"/>. Only the lower triangular elements
of these matrices are accessed. The default values for <tt class="docutils literal"><span class="pre">Gs</span></tt> and
<tt class="docutils literal"><span class="pre">hs</span></tt> are empty lists.</p>
<p><tt class="docutils literal"><span class="pre">A</span></tt> is a dense or sparse matrix and <tt class="docutils literal"><span class="pre">b</span></tt> is a single-column dense
matrix. The default values for <tt class="docutils literal"><span class="pre">A</span></tt> and <tt class="docutils literal"><span class="pre">b</span></tt> are matrices with zero
rows.</p>
<p>The <tt class="docutils literal"><span class="pre">solver</span></tt> argument is used to choose between two solvers: the
CVXOPT <a title="cvxopt.solvers.conelp" class="reference internal" href="#cvxopt.solvers.conelp"><tt class="xref docutils literal"><span class="pre">conelp</span></tt></a> solver
(used when <tt class="docutils literal"><span class="pre">solver</span></tt> is absent or equal
to <tt class="xref xref docutils literal"><span class="pre">None</span></tt>) and the external solver DSDP5 (<tt class="docutils literal"><span class="pre">solver</span></tt> is
<tt class="xref docutils literal"><span class="pre">'dsdp'</span></tt>); see the section <a class="reference internal" href="#s-external"><em>Optional Solvers</em></a>. With the
<tt class="xref docutils literal"><span class="pre">'dsdp'</span></tt> option the code does not accept problems with equality
constraints.</p>
<p>The optional argument <tt class="docutils literal"><span class="pre">primalstart</span></tt> is a dictionary with keys
<tt class="xref docutils literal"><span class="pre">'x'</span></tt>, <tt class="xref docutils literal"><span class="pre">'sl'</span></tt>, and <tt class="xref docutils literal"><span class="pre">'ss'</span></tt>, used as an optional
primal starting point. <tt class="docutils literal"><span class="pre">primalstart['x']</span></tt> and
<tt class="docutils literal"><span class="pre">primalstart['sl']</span></tt> are single-column dense matrices with the
initial values of <img class="math" src="_images/math/26eeb5258ca5099acf8fe96b2a1049c48c89a5e6.png" alt="x"/> and <img class="math" src="_images/math/058418cc5858eeab7f1ceb92f70b1c00fe7fe5d6.png" alt="s_0"/>;
<tt class="docutils literal"><span class="pre">primalstart['ss']</span></tt> is a list of square matrices with the initial
values of <img class="math" src="_images/math/7ae90d71491f591ab5a16d19ee7629e8226ec9ce.png" alt="s_1"/>, ldots, <img class="math" src="_images/math/ebb25f78e509bd7d344981884394d69d4ccef94d.png" alt="s_N"/>. The initial values must
satisfy the inequalities in the primal problem strictly, but not
necessarily the equality constraints.</p>
<p><tt class="docutils literal"><span class="pre">dualstart</span></tt> is a dictionary with keys <tt class="xref docutils literal"><span class="pre">'y'</span></tt>, <tt class="xref docutils literal"><span class="pre">'zl'</span></tt>,
<tt class="xref docutils literal"><span class="pre">'zs'</span></tt>, used as an optional dual starting point.
<tt class="docutils literal"><span class="pre">dualstart['y']</span></tt> and <tt class="docutils literal"><span class="pre">dualstart['zl']</span></tt> are single-column
dense matrices with the initial values of <img class="math" src="_images/math/092e364e1d9d19ad5fffb0b46ef4cc7f2da02c1c.png" alt="y"/> and <img class="math" src="_images/math/bab9abe98679312d2a3308c76188cf2cbc492f68.png" alt="z_0"/>.
<tt class="docutils literal"><span class="pre">dualstart['zs']</span></tt> is a list of square matrices with the initial
values of <img class="math" src="_images/math/9ea31e5c5613f025b5be8aca425d318168491d89.png" alt="z_1"/>, ldots, <img class="math" src="_images/math/9bb5bea50ae28bd840c3d2b526f4104435879613.png" alt="z_N"/>. These values must satisfy
the dual inequalities strictly, but not necessarily the equality
constraint.</p>
<p>The arguments <tt class="docutils literal"><span class="pre">primalstart</span></tt> and <tt class="docutils literal"><span class="pre">dualstart</span></tt> are ignored when the
DSDP solver is used.</p>
<p><tt class="xref docutils literal"><span class="pre">sdp</span></tt> returns a dictionary that includes entries with keys
<tt class="xref docutils literal"><span class="pre">'status'</span></tt>, <tt class="xref docutils literal"><span class="pre">'x'</span></tt>, <tt class="xref docutils literal"><span class="pre">'sl'</span></tt>, <tt class="xref docutils literal"><span class="pre">'ss'</span></tt>,
<tt class="xref docutils literal"><span class="pre">'y'</span></tt>, <tt class="xref docutils literal"><span class="pre">'zl'</span></tt>, <tt class="xref docutils literal"><span class="pre">'ss'</span></tt>. The <tt class="xref docutils literal"><span class="pre">'sl'</span></tt> and
<tt class="xref docutils literal"><span class="pre">'zl'</span></tt> fields are matrices with the primal slacks and dual
variables associated with the componentwise linear inequalities.
The <tt class="xref docutils literal"><span class="pre">'ss'</span></tt> and <tt class="xref docutils literal"><span class="pre">'zs'</span></tt> fields are lists with the primal
slacks and dual variables associated with the second-order cone
inequalities. The other entries in the output dictionary have the
same meaning as in the output of
<a title="cvxopt.solvers.conelp" class="reference internal" href="#cvxopt.solvers.conelp"><tt class="xref docutils literal"><span class="pre">conelp</span></tt></a>.</p>
</dd></dl>
<p>We illustrate the calling sequence with a small example.</p>
<blockquote>
<div class="math">
<p><img src="_images/math/131c4578e1d0555aabdbdc52cdbe7b840cecb293.png" alt="\begin{array}{ll}
\mbox{minimize} & x_1 - x_2 + x_3 \\
\mbox{subject to}
& x_1 \left[ \begin{array}{cc}
-7 & -11 \\ -11 & 3
\end{array}\right] +
x_2 \left[ \begin{array}{cc}
7 & -18 \\ -18 & 8
\end{array}\right] +
x_3 \left[ \begin{array}{cc}
-2 & -8 \\ -8 & 1
\end{array}\right] \preceq
\left[ \begin{array}{cc}
33 & -9 \\ -9 & 26
\end{array}\right] \\*[1ex]
& x_1 \left[ \begin{array}{ccc}
-21 & -11 & 0 \\
-11 & 10 & 8 \\
0 & 8 & 5
\end{array}\right] +
x_2 \left[ \begin{array}{ccc}
0 & 10 & 16 \\
10 & -10 & -10 \\
16 & -10 & 3
\end{array}\right] +
x_3 \left[ \begin{array}{ccc}
-5 & 2 & -17 \\
2 & -6 & -7 \\
-17 & 8 & 6
\end{array}\right] \preceq
\left[ \begin{array}{ccc}
14 & 9 & 40 \\
9 & 91 & 10 \\
40 & 10 & 15
\end{array} \right]
\end{array}" /></p>
</div></blockquote>
<div class="highlight-python"><div class="highlight"><pre><span class="gp">>>> </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">solvers</span>
<span class="gp">>>> </span><span class="n">c</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">([</span><span class="mf">1.</span><span class="p">,</span><span class="o">-</span><span class="mf">1.</span><span class="p">,</span><span class="mf">1.</span><span class="p">])</span>
<span class="gp">>>> </span><span class="n">G</span> <span class="o">=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="o">-</span><span class="mf">7.</span><span class="p">,</span> <span class="o">-</span><span class="mf">11.</span><span class="p">,</span> <span class="o">-</span><span class="mf">11.</span><span class="p">,</span> <span class="mf">3.</span><span class="p">],</span>
<span class="go"> [ 7., -18., -18., 8.],</span>
<span class="go"> [-2., -8., -8., 1.]]) ]</span>
<span class="gp">>>> </span><span class="n">G</span> <span class="o">+=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="o">-</span><span class="mf">21.</span><span class="p">,</span> <span class="o">-</span><span class="mf">11.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="o">-</span><span class="mf">11.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">,</span> <span class="mf">8.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">8.</span><span class="p">,</span> <span class="mf">5.</span><span class="p">],</span>
<span class="go"> [ 0., 10., 16., 10., -10., -10., 16., -10., 3.],</span>
<span class="go"> [ -5., 2., -17., 2., -6., 8., -17., -7., 6.]]) ]</span>
<span class="gp">>>> </span><span class="n">h</span> <span class="o">=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="mf">33.</span><span class="p">,</span> <span class="o">-</span><span class="mf">9.</span><span class="p">],</span> <span class="p">[</span><span class="o">-</span><span class="mf">9.</span><span class="p">,</span> <span class="mf">26.</span><span class="p">]])</span> <span class="p">]</span>
<span class="gp">>>> </span><span class="n">h</span> <span class="o">+=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="mf">14.</span><span class="p">,</span> <span class="mf">9.</span><span class="p">,</span> <span class="mf">40.</span><span class="p">],</span> <span class="p">[</span><span class="mf">9.</span><span class="p">,</span> <span class="mf">91.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">],</span> <span class="p">[</span><span class="mf">40.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">,</span> <span class="mf">15.</span><span class="p">]])</span> <span class="p">]</span>
<span class="gp">>>> </span><span class="n">sol</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">sdp</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">Gs</span><span class="o">=</span><span class="n">G</span><span class="p">,</span> <span class="n">hs</span><span class="o">=</span><span class="n">h</span><span class="p">)</span>
<span class="gp">>>> </span><span class="k">print</span> <span class="n">sol</span><span class="p">[</span><span class="s">'x'</span><span class="p">]</span>
<span class="go">[-3.68e-01]</span>
<span class="go">[ 1.90e+00]</span>
<span class="go">[-8.88e-01]</span>
<span class="gp">>>> </span><span class="k">print</span> <span class="n">sol</span><span class="p">[</span><span class="s">'zs'</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span>
<span class="go">[ 3.96e-03 -4.34e-03]</span>
<span class="go">[-4.34e-03 4.75e-03]</span>
<span class="gp">>>> </span><span class="k">print</span> <span class="n">sol</span><span class="p">[</span><span class="s">'zs'</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span>
<span class="go">[ 5.58e-02 -2.41e-03 2.42e-02]</span>
<span class="go">[-2.41e-03 1.04e-04 -1.05e-03]</span>
<span class="go">[ 2.42e-02 -1.05e-03 1.05e-02]</span>
</pre></div>
</div>
<p>Only the entries in <tt class="docutils literal"><span class="pre">Gs</span></tt> and <tt class="docutils literal"><span class="pre">hs</span></tt> that correspond to lower triangular
entries need to be provided, so in the example <tt class="docutils literal"><span class="pre">h</span></tt> and <tt class="docutils literal"><span class="pre">G</span></tt> may also be
defined as follows.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="gp">>>> </span><span class="n">G</span> <span class="o">=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="o">-</span><span class="mf">7.</span><span class="p">,</span> <span class="o">-</span><span class="mf">11.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">3.</span><span class="p">],</span>
<span class="go"> [ 7., -18., 0., 8.],</span>
<span class="go"> [-2., -8., 0., 1.]]) ]</span>
<span class="gp">>>> </span><span class="n">G</span> <span class="o">+=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="o">-</span><span class="mf">21.</span><span class="p">,</span> <span class="o">-</span><span class="mf">11.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">,</span> <span class="mf">8.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">5.</span><span class="p">],</span>
<span class="go"> [ 0., 10., 16., 0., -10., -10., 0., 0., 3.],</span>
<span class="go"> [ -5., 2., -17., 0., -6., 8., 0., 0., 6.]]) ]</span>
<span class="gp">>>> </span><span class="n">h</span> <span class="o">=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="mf">33.</span><span class="p">,</span> <span class="o">-</span><span class="mf">9.</span><span class="p">],</span> <span class="p">[</span><span class="mf">0.</span><span class="p">,</span> <span class="mf">26.</span><span class="p">]])</span> <span class="p">]</span>
<span class="gp">>>> </span><span class="n">h</span> <span class="o">+=</span> <span class="p">[</span> <span class="n">matrix</span><span class="p">([[</span><span class="mf">14.</span><span class="p">,</span> <span class="mf">9.</span><span class="p">,</span> <span class="mf">40.</span><span class="p">],</span> <span class="p">[</span><span class="mf">0.</span><span class="p">,</span> <span class="mf">91.</span><span class="p">,</span> <span class="mf">10.</span><span class="p">],</span> <span class="p">[</span><span class="mf">0.</span><span class="p">,</span> <span class="mf">0.</span><span class="p">,</span> <span class="mf">15.</span><span class="p">]])</span> <span class="p">]</span>
</pre></div>
</div>
</div>
<div class="section" id="exploiting-structure">
<span id="s-conelp-struct"></span><h2>Exploiting Structure<a class="headerlink" href="#exploiting-structure" title="Permalink to this headline">¶</a></h2>
<p>By default, the functions
<a title="cvxopt.solvers.conelp" class="reference internal" href="#cvxopt.solvers.conelp"><tt class="xref docutils literal"><span class="pre">conelp</span></tt></a> and
<a title="cvxopt.solvers.coneqp" class="reference internal" href="#cvxopt.solvers.coneqp"><tt class="xref docutils literal"><span class="pre">coneqp</span></tt></a> exploit no
problem structure except (to some limited extent) sparsity. Two mechanisms
are provided for implementing customized solvers that take advantage of
problem structure.</p>
<dl class="docutils">
<dt><strong>Providing a function for solving KKT equations</strong></dt>
<dd><p class="first">The most expensive step of each iteration of
<a title="cvxopt.solvers.conelp" class="reference internal" href="#cvxopt.solvers.conelp"><tt class="xref docutils literal"><span class="pre">conelp</span></tt></a> or
<a title="cvxopt.solvers.coneqp" class="reference internal" href="#cvxopt.solvers.coneqp"><tt class="xref docutils literal"><span class="pre">coneqp</span></tt></a> is the solution of a set of
linear equations (<em>KKT equations</em>) of the form</p>
<div class="math" id="equation-e-conelp-kkt">
<p><span class="eqno">(1)</span><img src="_images/math/b8b7119bfcdc51fa8538564d5633d180c2271df6.png" alt="\left[\begin{array}{ccc}
P & A^T & G^T \\
A & 0 & 0 \\
G & 0 & -W^T W
\end{array}\right]
\left[\begin{array}{c} u_x \\ u_y \\ u_z \end{array}\right]
=
\left[\begin{array}{c} b_x \\ b_y \\ b_z \end{array}\right]" /></p>
</div><p>(with <img class="math" src="_images/math/7339a7b861543525b6c1d74544fc0f2b79e65611.png" alt="P = 0"/> in <tt class="xref docutils literal"><span class="pre">conelp</span></tt>). The matrix <img class="math" src="_images/math/10cb764f88509fb1c8012366993fdbee98f31bc5.png" alt="W"/> depends
on the current iterates and is defined as follows. We use the notation
of the sections <a class="reference internal" href="#s-conelp"><em>Linear Cone Programs</em></a> and <a class="reference internal" href="#s-coneqp"><em>Quadratic Cone Programs</em></a>. Let</p>
<div class="math">
<p><img src="_images/math/9324affab9ba9d5021117be41d8b14381c5a5448.png" alt="\newcommand{\svec}{\mathop{\mathbf{vec}}}
u = \left(u_\mathrm{l}, \; u_{\mathrm{q},0}, \; \ldots, \;
u_{\mathrm{q},M-1}, \; \svec{(u_{\mathrm{s},0})}, \;
\ldots, \; \svec{(u_{\mathrm{s},N-1})}\right), \qquad
\newcommand{\reals}{{\mbox{\bf R}}}
\newcommand{\symm}{{\mbox{\bf S}}}
u_\mathrm{l} \in\reals^l, \qquad
u_{\mathrm{q},k} \in\reals^{r_k}, \quad k = 0,\ldots,M-1, \qquad
u_{\mathrm{s},k} \in\symm^{t_k}, \quad k = 0,\ldots,N-1." /></p>
</div><p>Then <img class="math" src="_images/math/10cb764f88509fb1c8012366993fdbee98f31bc5.png" alt="W"/> is a block-diagonal matrix,</p>
<div class="math">
<p><img src="_images/math/fc7c8d2c4d8382a728d705c58741344d7787112f.png" alt="\newcommand{\svec}{\mathop{\mathbf{vec}}}
Wu = \left( W_\mathrm{l} u_\mathrm{l}, \;
W_{\mathrm{q},0} u_{\mathrm{q},0}, \; \ldots, \;
W_{\mathrm{q},M-1} u_{\mathrm{q},M-1},\;
W_{\mathrm{s},0} \svec{(u_{\mathrm{s},0})}, \; \ldots, \;
W_{\mathrm{s},N-1} \svec{(u_{\mathrm{s},N-1})} \right)" /></p>
</div><p>with the following diagonal blocks.</p>
<ul>
<li><p class="first">The first block is a <em>positive diagonal scaling</em> with a vector
<img class="math" src="_images/math/96ab646de7704969b91c76a214126b45f2b07b25.png" alt="d"/>:</p>
<div class="math">
<p><img src="_images/math/29169a7341170ee1c3bc87f30bcfec4fc1fddb1c.png" alt="\newcommand{\diag}{\mbox{\bf diag}\,}
W_\mathrm{l} = \diag(d), \qquad
W_\mathrm{l}^{-1} = \diag(d)^{-1}." /></p>
</div><p>This transformation is symmetric:</p>
<div class="math">
<p><img src="_images/math/81dbf963b31f68c91c05f21b40ed2f9199978e1e.png" alt="W_\mathrm{l}^T = W_\mathrm{l}." /></p>
</div></li>
<li><p class="first">The next <img class="math" src="_images/math/5d1e4485dc90c450e8c76826516c1b2ccb8fce16.png" alt="M"/> blocks are positive multiples of <em>hyperbolic
Householder transformations</em>:</p>
<div class="math">
<p><img src="_images/math/fc20ea3a2b3a3d97990a8d2095b1b1252c5fdfa4.png" alt="W_{\mathrm{q},k} = \beta_k ( 2 v_k v_k^T - J), \qquad
W_{\mathrm{q},k}^{-1} = \frac{1}{\beta_k} ( 2 Jv_k v_k^T J - J),
\qquad k = 0,\ldots,M-1," /></p>
</div><p>where</p>
<div class="math">
<p><img src="_images/math/5f835d2d4a213eff54596ede687eff1c913db934.png" alt="\beta_k > 0, \qquad v_{k0} > 0, \qquad v_k^T Jv_k = 1, \qquad
J = \left[\begin{array}{cc} 1 & 0 \\ 0 & -I \end{array}\right]." /></p>
</div><p>These transformations are also symmetric:</p>
<div class="math">
<p><img src="_images/math/a5bae4d3ef0ce383b5baf135e82b596b52067dcf.png" alt="W_{\mathrm{q},k}^T = W_{\mathrm{q},k}." /></p>
</div></li>
<li><p class="first">The last <img class="math" src="_images/math/fc97ef67268cd4e91bacdf12b8901d7036c9a056.png" alt="N"/> blocks are <em>congruence transformations</em> with
nonsingular matrices:</p>
<div class="math">
<p><img src="_images/math/fbd258f087f50a0416d11bc990440a6d32ec879a.png" alt="\newcommand{\svec}{\mathop{\mathbf{vec}}}
W_{\mathrm{s},k} \svec{(u_{\mathrm{s},k})} =
\svec{(r_k^T u_{\mathrm{s},k} r_k)}, \qquad
W_{\mathrm{s},k}^{-1} \svec{(u_{\mathrm{s},k})} =
\svec{(r_k^{-T} u_{\mathrm{s},k} r_k^{-1})}, \qquad
k = 0,\ldots,N-1." /></p>
</div><p>In general, this operation is not symmetric:</p>
<div class="math">
<p><img src="_images/math/37a07a60f26280afd1716c6202e5d5c410456463.png" alt="\newcommand{\svec}{\mathop{\mathbf{vec}}}
W_{\mathrm{s},k}^T \svec{(u_{\mathrm{s},k})} =
\svec{(r_k u_{\mathrm{s},k} r_k^T)}, \qquad \qquad
W_{\mathrm{s},k}^{-T} \svec{(u_{\mathrm{s},k})} =
\svec{(r_k^{-1} u_{\mathrm{s},k} r_k^{-T})}, \qquad \qquad
k = 0,\ldots,N-1." /></p>
</div></li>
</ul>
<p>It is often possible to exploit problem structure to solve
<a href="#equation-e-conelp-kkt">(1)</a> faster than by standard methods. The last argument
<tt class="docutils literal"><span class="pre">kktsolver</span></tt> of <a title="cvxopt.solvers.conelp" class="reference internal" href="#cvxopt.solvers.conelp"><tt class="xref docutils literal"><span class="pre">conelp</span></tt></a> and
<a title="cvxopt.solvers.coneqp" class="reference internal" href="#cvxopt.solvers.coneqp"><tt class="xref docutils literal"><span class="pre">coneqp</span></tt></a> allows the user to
supply a Python function for solving the KKT equations. This
function will be called as <tt class="docutils literal"><span class="pre">f</span> <span class="pre">=</span> <span class="pre">kktsolver(W)</span></tt>, where <tt class="docutils literal"><span class="pre">W</span></tt> is a
dictionary that contains the parameters of the scaling:</p>
<ul class="simple">
<li><tt class="docutils literal"><span class="pre">W['d']</span></tt> is the positive vector that defines the diagonal
scaling. <tt class="docutils literal"><span class="pre">W['di']</span></tt> is its componentwise inverse.</li>
<li><tt class="docutils literal"><span class="pre">W['beta']</span></tt> and <tt class="docutils literal"><span class="pre">W['v']</span></tt> are lists of length <img class="math" src="_images/math/5d1e4485dc90c450e8c76826516c1b2ccb8fce16.png" alt="M"/>
with the coefficients and vectors that define the hyperbolic
Householder transformations.</li>
<li><tt class="docutils literal"><span class="pre">W['r']</span></tt> is a list of length <img class="math" src="_images/math/fc97ef67268cd4e91bacdf12b8901d7036c9a056.png" alt="N"/> with the matrices that
define the the congruence transformations. <tt class="docutils literal"><span class="pre">W['rti']</span></tt> is a
list of length <img class="math" src="_images/math/fc97ef67268cd4e91bacdf12b8901d7036c9a056.png" alt="N"/> with the transposes of the inverses of the
matrices in <tt class="docutils literal"><span class="pre">W['r']</span></tt>.</li>
</ul>
<p>The function call <tt class="docutils literal"><span class="pre">f</span> <span class="pre">=</span> <span class="pre">kktsolver(W)</span></tt> should return a routine for
solving the KKT system <a href="#equation-e-conelp-kkt">(1)</a> defined by <tt class="docutils literal"><span class="pre">W</span></tt>. It will
be called as <tt class="docutils literal"><span class="pre">f(bx,</span> <span class="pre">by,</span> <span class="pre">bz)</span></tt>. On entry, <tt class="docutils literal"><span class="pre">bx</span></tt>, <tt class="docutils literal"><span class="pre">by</span></tt>, <tt class="docutils literal"><span class="pre">bz</span></tt>
contain the righthand side. On exit, they should contain the solution
of the KKT system, with the last component scaled, i.e., on exit,</p>
<div class="math">
<p><img src="_images/math/3649d418d0750fb66f68e828cfec83faca966498.png" alt="b_x := u_x, \qquad b_y := u_y, \qquad b_z := W u_z." /></p>
</div><p>In other words, the function returns the solution of</p>
<div class="last math">
<p><img src="_images/math/b64d772fd47d88c4e63bef5ba1cb73e8627e9088.png" alt="\left[\begin{array}{ccc}
P & A^T & G^TW^{-1} \\
A & 0 & 0 \\
G & 0 & -W^T
\end{array}\right]
\left[\begin{array}{c}
\hat u_x \\ \hat u_y \\ \hat u_z
\end{array}\right]
=
\left[\begin{array}{c}
b_x \\ b_y \\ b_z
\end{array}\right]." /></p>
</div></dd>
<dt><strong>Specifying constraints via Python functions</strong></dt>
<dd><p class="first">In the default use of <a title="cvxopt.solvers.conelp" class="reference internal" href="#cvxopt.solvers.conelp"><tt class="xref docutils literal"><span class="pre">conelp</span></tt></a> and
<a title="cvxopt.solvers.coneqp" class="reference internal" href="#cvxopt.solvers.coneqp"><tt class="xref docutils literal"><span class="pre">coneqp</span></tt></a>, the linear
constraints and the quadratic term in the objective are parameterized
by CVXOPT matrices <tt class="docutils literal"><span class="pre">G</span></tt>, <tt class="docutils literal"><span class="pre">A</span></tt>, <tt class="docutils literal"><span class="pre">P</span></tt>. It is possible to specify
these parameters via Python functions that evaluate the corresponding
matrix-vector products and their adjoints.</p>
<ul>
<li><p class="first">If the argument <tt class="docutils literal"><span class="pre">G</span></tt> of <tt class="xref docutils literal"><span class="pre">conelp</span></tt> or <tt class="xref docutils literal"><span class="pre">coneqp</span></tt> is a
Python function, then
<tt class="docutils literal"><span class="pre">G(x,</span> <span class="pre">y[,</span> <span class="pre">alpha</span> <span class="pre">=</span> <span class="pre">1.0,</span> <span class="pre">beta</span> <span class="pre">=</span> <span class="pre">0.0,</span> <span class="pre">trans</span> <span class="pre">=</span> <span class="pre">'N'])</span></tt>
should evaluate the matrix-vector products</p>
<blockquote>
<div class="math">
<p><img src="_images/math/821e47dcc0a42053d3c3c5a35937cd39888d4bf1.png" alt="y := \alpha Gx + \beta y \quad
(\mathrm{trans} = \mathrm{'N'}), \qquad
y := \alpha G^T x + \beta y \quad
(\mathrm{trans} = \mathrm{'T'})." /></p>
</div></blockquote>
</li>
<li><p class="first">Similarly, if the argument <tt class="docutils literal"><span class="pre">A</span></tt> is a Python function, then
<tt class="docutils literal"><span class="pre">A(x,</span> <span class="pre">y[,</span> <span class="pre">alpha</span> <span class="pre">=</span> <span class="pre">1.0,</span> <span class="pre">beta</span> <span class="pre">=</span> <span class="pre">0.0,</span> <span class="pre">trans</span> <span class="pre">=</span> <span class="pre">'N'])</span></tt>
should evaluate the matrix-vector products</p>
<blockquote>
<div class="math">
<p><img src="_images/math/49ac9835ee2e9a28724b6b48183cc8082f2181b1.png" alt="y := \alpha Ax + \beta y \quad
(\mathrm{trans} = \mathrm{'N'}), \qquad
y := \alpha A^T x + \beta y \quad
(\mathrm{trans} = \mathrm{'T'})." /></p>
</div></blockquote>
</li>
<li><p class="first">If the argument <tt class="docutils literal"><span class="pre">P</span></tt> of <tt class="xref docutils literal"><span class="pre">coneqp</span></tt> is a Python function, then
<tt class="docutils literal"><span class="pre">P(x,</span> <span class="pre">y[,</span> <span class="pre">alpha</span> <span class="pre">=</span> <span class="pre">1.0,</span> <span class="pre">beta</span> <span class="pre">=</span> <span class="pre">0.0])</span></tt>
should evaluate the matrix-vector products</p>
<blockquote>
<div class="math">
<p><img src="_images/math/2f877c26508a30a5c47ee96f8b69027da87c62f7.png" alt="y := \alpha Px + \beta y." /></p>
</div></blockquote>
</li>
</ul>
<p class="last">If <tt class="docutils literal"><span class="pre">G</span></tt>, <tt class="docutils literal"><span class="pre">A</span></tt>, or <tt class="docutils literal"><span class="pre">P</span></tt> are Python functions, then the argument
<tt class="docutils literal"><span class="pre">kktsolver</span></tt> must also be provided.</p>
</dd>
</dl>
<p>We illustrate these features with three applications.</p>
<p><strong>Example: 1-norm approximation</strong></p>
<blockquote>
<p>The optimization problem</p>
<div class="math">
<p><img src="_images/math/3ca0e9bfd6892d48d77c87a33bcc228c3a017ec0.png" alt="\begin{array}{ll}
\mbox{minimize} & \|Pu-q\|_1
\end{array}" /></p>
</div><p>can be formulated as a linear program</p>
<div class="math">
<p><img src="_images/math/8f89ee4ea94d9b2fbe9036b74316e5cb4951ad09.png" alt="\newcommand{\ones}{{\bf 1}}
\begin{array}{ll}
\mbox{minimize} & \ones^T v \\
\mbox{subject to} & -v \preceq Pu - q \preceq v.
\end{array}" /></p>
</div><p>By exploiting the structure in the inequalities, the cost of an
iteration of an interior-point method can be reduced to the cost of
least-squares problem of the same dimensions. (See section 11.8.2 in
the book
<a class="reference external" href="http://www.stanford.edu/~boyd/cvxbook">Convex Optimization</a>.)
The code below takes advantage of this fact.</p>
<div class="highlight-python"><pre>from cvxopt import blas, lapack, solvers, matrix, spmatrix, mul, div
def l1(P, q):
"""
Returns the solution u, w of the l1 approximation problem
(primal) minimize ||P*u - q||_1
(dual) maximize q'*w
subject to P'*w = 0
||w||_infty <= 1.
"""
m, n = P.size
# Solve the equivalent LP
#
# minimize [0; 1]' * [u; v]
# subject to [P, -I; -P, -I] * [u; v] <= [q; -q]
#
# maximize -[q; -q]' * z
# subject to [P', -P']*z = 0
# [-I, -I]*z + 1 = 0
# z >= 0.
c = matrix(n*[0.0] + m*[1.0])
def G(x, y, alpha = 1.0, beta = 0.0, trans = 'N'):
if trans=='N':
# y := alpha * [P, -I; -P, -I] * x + beta*y
u = P*x[:n]
y[:m] = alpha * ( u - x[n:]) + beta * y[:m]
y[m:] = alpha * (-u - x[n:]) + beta * y[m:]
else:
# y := alpha * [P', -P'; -I, -I] * x + beta*y
y[:n] = alpha * P.T * (x[:m] - x[m:]) + beta * y[:n]
y[n:] = -alpha * (x[:m] + x[m:]) + beta * y[n:]
h = matrix([q, -q])
dims = {'l': 2*m, 'q': [], 's': []}
def F(W):
"""
Returns a function f(x, y, z) that solves
[ 0 0 P' -P' ] [ x[:n] ] [ bx[:n] ]
[ 0 0 -I -I ] [ x[n:] ] [ bx[n:] ]
[ P -I -D1^{-1} 0 ] [ z[:m] ] = [ bz[:m] ]
[-P -I 0 -D2^{-1} ] [ z[m:] ] [ bz[m:] ]
where D1 = diag(di[:m])^2, D2 = diag(di[m:])^2 and di = W['di'].
"""
# Factor A = 4*P'*D*P where D = d1.*d2 ./(d1+d2) and
# d1 = di[:m].^2, d2 = di[m:].^2.
di = W['di']
d1, d2 = di[:m]**2, di[m:]**2
D = div( mul(d1,d2), d1+d2 )
A = P.T * spmatrix(4*D, range(m), range(m)) * P
lapack.potrf(A)
def f(x, y, z):
"""
On entry bx, bz are stored in x, z. On exit x, z contain the solution,
with z scaled: z./di is returned instead of z.
""""
# Solve for x[:n]:
#
# A*x[:n] = bx[:n] + P' * ( ((D1-D2)*(D1+D2)^{-1})*bx[n:]
# + (2*D1*D2*(D1+D2)^{-1}) * (bz[:m] - bz[m:]) ).
x[:n] += P.T * ( mul(div(d1-d2, d1+d2), x[n:]) + mul(2*D, z[:m]-z[m:]) )
lapack.potrs(A, x)
# x[n:] := (D1+D2)^{-1} * (bx[n:] - D1*bz[:m] - D2*bz[m:] + (D1-D2)*P*x[:n])
u = P*x[:n]
x[n:] = div(x[n:] - mul(d1, z[:m]) - mul(d2, z[m:]) + mul(d1-d2, u), d1+d2)
# z[:m] := d1[:m] .* ( P*x[:n] - x[n:] - bz[:m])
# z[m:] := d2[m:] .* (-P*x[:n] - x[n:] - bz[m:])
z[:m] = mul(d[:m], u - x[n:] - z[:m])
z[m:] = mul(d[m:], -u - x[n:] - z[m:])
return f
sol = solvers.conelp(c, G, h, dims, kktsolver = F)
return sol['x'][:n], sol['z'][m:] - sol['z'][:m]</pre>
</div>
</blockquote>
<p><strong>Example: SDP with diagonal linear term</strong></p>
<blockquote>
<p>The SDP</p>
<div class="math">
<p><img src="_images/math/dcb8f8492ae1de33fb0a0d243d10ae040422e12f.png" alt="\newcommand{\diag}{\mbox{\bf diag}\,}
\newcommand{\ones}{{\bf 1}}
\begin{array}{ll}
\mbox{minimize} & \ones^T x \\
\mbox{subject to} & W + \diag(x) \succeq 0
\end{array}" /></p>
</div><p>can be solved efficiently by exploiting properties of the diag
operator.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">blas</span><span class="p">,</span> <span class="n">lapack</span><span class="p">,</span> <span class="n">solvers</span><span class="p">,</span> <span class="n">matrix</span>
<span class="k">def</span> <span class="nf">mcsdp</span><span class="p">(</span><span class="n">w</span><span class="p">):</span>
<span class="sd">"""</span>
<span class="sd"> Returns solution x, z to</span>
<span class="sd"> (primal) minimize sum(x)</span>
<span class="sd"> subject to w + diag(x) >= 0</span>
<span class="sd"> (dual) maximize -tr(w*z)</span>
<span class="sd"> subject to diag(z) = 1</span>
<span class="sd"> z >= 0.</span>
<span class="sd"> """</span>
<span class="n">n</span> <span class="o">=</span> <span class="n">w</span><span class="o">.</span><span class="n">size</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
<span class="n">c</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">1.0</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>
<span class="k">def</span> <span class="nf">G</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="n">beta</span> <span class="o">=</span> <span class="mf">0.0</span><span class="p">,</span> <span class="n">trans</span> <span class="o">=</span> <span class="s">'N'</span><span class="p">):</span>
<span class="sd">"""</span>
<span class="sd"> y := alpha*(-diag(x)) + beta*y.</span>
<span class="sd"> """</span>
<span class="k">if</span> <span class="n">trans</span><span class="o">==</span><span class="s">'N'</span><span class="p">:</span>
<span class="c"># x is a vector; y is a symmetric matrix in column major order.</span>
<span class="n">y</span> <span class="o">*=</span> <span class="n">beta</span>
<span class="n">y</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">-=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="n">x</span>
<span class="k">else</span><span class="p">:</span>
<span class="c"># x is a symmetric matrix in column major order; y is a vector.</span>
<span class="n">y</span> <span class="o">*=</span> <span class="n">beta</span>
<span class="n">y</span> <span class="o">-=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="n">x</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span>
<span class="k">def</span> <span class="nf">cngrnc</span><span class="p">(</span><span class="n">r</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">):</span>
<span class="sd">"""</span>
<span class="sd"> Congruence transformation</span>
<span class="sd"> x := alpha * r'*x*r.</span>
<span class="sd"> r and x are square matrices.</span>
<span class="sd"> """</span>
<span class="c"># Scale diagonal of x by 1/2.</span>
<span class="n">x</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">*=</span> <span class="mf">0.5</span>
<span class="c"># a := tril(x)*r</span>
<span class="n">a</span> <span class="o">=</span> <span class="o">+</span><span class="n">r</span>
<span class="n">tx</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>
<span class="n">blas</span><span class="o">.</span><span class="n">trmm</span><span class="p">(</span><span class="n">tx</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">side</span> <span class="o">=</span> <span class="s">'L'</span><span class="p">)</span>
<span class="c"># x := alpha*(a*r' + r*a')</span>
<span class="n">blas</span><span class="o">.</span><span class="n">syr2k</span><span class="p">(</span><span class="n">r</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">tx</span><span class="p">,</span> <span class="n">trans</span> <span class="o">=</span> <span class="s">'T'</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="n">alpha</span><span class="p">)</span>
<span class="n">x</span><span class="p">[:]</span> <span class="o">=</span> <span class="n">tx</span><span class="p">[:]</span>
<span class="n">dims</span> <span class="o">=</span> <span class="p">{</span><span class="s">'l'</span><span class="p">:</span> <span class="mi">0</span><span class="p">,</span> <span class="s">'q'</span><span class="p">:</span> <span class="p">[],</span> <span class="s">'s'</span><span class="p">:</span> <span class="p">[</span><span class="n">n</span><span class="p">]}</span>
<span class="k">def</span> <span class="nf">F</span><span class="p">(</span><span class="n">W</span><span class="p">):</span>
<span class="sd">"""</span>
<span class="sd"> Returns a function f(x, y, z) that solves</span>
<span class="sd"> -diag(z) = bx</span>
<span class="sd"> -diag(x) - r*r'*z*r*r' = bz</span>
<span class="sd"> where r = W['r'][0] = W['rti'][0]^{-T}.</span>
<span class="sd"> """</span>
<span class="n">rti</span> <span class="o">=</span> <span class="n">W</span><span class="p">[</span><span class="s">'rti'</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span>
<span class="c"># t = rti*rti' as a nonsymmetric matrix.</span>
<span class="n">t</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>
<span class="n">blas</span><span class="o">.</span><span class="n">gemm</span><span class="p">(</span><span class="n">rti</span><span class="p">,</span> <span class="n">rti</span><span class="p">,</span> <span class="n">t</span><span class="p">,</span> <span class="n">transB</span> <span class="o">=</span> <span class="s">'T'</span><span class="p">)</span>
<span class="c"># Cholesky factorization of tsq = t.*t.</span>
<span class="n">tsq</span> <span class="o">=</span> <span class="n">t</span><span class="o">**</span><span class="mi">2</span>
<span class="n">lapack</span><span class="o">.</span><span class="n">potrf</span><span class="p">(</span><span class="n">tsq</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">):</span>
<span class="sd">"""</span>
<span class="sd"> On entry, x contains bx, y is empty, and z contains bz stored</span>
<span class="sd"> in column major order.</span>
<span class="sd"> On exit, they contain the solution, with z scaled</span>
<span class="sd"> (vec(r'*z*r) is returned instead of z).</span>
<span class="sd"> We first solve</span>
<span class="sd"> ((rti*rti') .* (rti*rti')) * x = bx - diag(t*bz*t)</span>
<span class="sd"> and take z = - rti' * (diag(x) + bz) * rti.</span>
<span class="sd"> """</span>
<span class="c"># tbst := t * bz * t</span>
<span class="n">tbst</span> <span class="o">=</span> <span class="o">+</span><span class="n">z</span>
<span class="n">cngrnc</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="n">tbst</span><span class="p">)</span>
<span class="c"># x := x - diag(tbst) = bx - diag(rti*rti' * bz * rti*rti')</span>
<span class="n">x</span> <span class="o">-=</span> <span class="n">tbst</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span>
<span class="c"># x := (t.*t)^{-1} * x = (t.*t)^{-1} * (bx - diag(t*bz*t))</span>
<span class="n">lapack</span><span class="o">.</span><span class="n">potrs</span><span class="p">(</span><span class="n">tsq</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span>
<span class="c"># z := z + diag(x) = bz + diag(x)</span>
<span class="n">z</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">+=</span> <span class="n">x</span>
<span class="c"># z := -vec(rti' * z * rti)</span>
<span class="c"># = -vec(rti' * (diag(x) + bz) * rti</span>
<span class="n">cngrnc</span><span class="p">(</span><span class="n">rti</span><span class="p">,</span> <span class="n">z</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="o">-</span><span class="mf">1.0</span><span class="p">)</span>
<span class="k">return</span> <span class="n">f</span>
<span class="n">sol</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">conelp</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">w</span><span class="p">[:],</span> <span class="n">dims</span><span class="p">,</span> <span class="n">kktsolver</span> <span class="o">=</span> <span class="n">F</span><span class="p">)</span>
<span class="k">return</span> <span class="n">sol</span><span class="p">[</span><span class="s">'x'</span><span class="p">],</span> <span class="n">sol</span><span class="p">[</span><span class="s">'z'</span><span class="p">]</span>
</pre></div>
</div>
</blockquote>
<dl class="docutils">
<dt><strong>Example: Minimizing 1-norm subject to a 2-norm constraint</strong></dt>
<dd><p class="first">In the second example, we use a similar trick to solve the problem</p>
<div class="math">
<p><img src="_images/math/3e2caf480789aba90884fce313eff58bbd1edcfd.png" alt="\begin{array}{ll}
\mbox{minimize} & \|u\|_1 \\
\mbox{subject to} & \|Au - b\|_2 \leq 1.
\end{array}" /></p>
</div><p>The code below is efficient, if we assume that the number of rows in
<img class="math" src="_images/math/019e9892786e493964e145e7c5cf7b700314e53b.png" alt="A"/> is greater than or equal to the number of columns.</p>
<div class="last highlight-python"><div class="highlight"><pre><span class="k">def</span> <span class="nf">qcl1</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">b</span><span class="p">):</span>
<span class="sd">"""</span>
<span class="sd"> Returns the solution u, z of</span>
<span class="sd"> (primal) minimize || u ||_1</span>
<span class="sd"> subject to || A * u - b ||_2 <= 1</span>
<span class="sd"> (dual) maximize b^T z - ||z||_2</span>
<span class="sd"> subject to || A'*z ||_inf <= 1.</span>
<span class="sd"> Exploits structure, assuming A is m by n with m >= n.</span>
<span class="sd"> """</span>
<span class="n">m</span><span class="p">,</span> <span class="n">n</span> <span class="o">=</span> <span class="n">A</span><span class="o">.</span><span class="n">size</span>
<span class="c"># Solve equivalent cone LP with variables x = [u; v].</span>
<span class="c">#</span>
<span class="c"># minimize [0; 1]' * x</span>
<span class="c"># subject to [ I -I ] * x <= [ 0 ] (componentwise)</span>
<span class="c"># [-I -I ] * x <= [ 0 ] (componentwise)</span>
<span class="c"># [ 0 0 ] * x <= [ 1 ] (SOC)</span>
<span class="c"># [-A 0 ] [ -b ]</span>
<span class="c">#</span>
<span class="c"># maximize -t + b' * w</span>
<span class="c"># subject to z1 - z2 = A'*w</span>
<span class="c"># z1 + z2 = 1</span>
<span class="c"># z1 >= 0, z2 >=0, ||w||_2 <= t.</span>
<span class="n">c</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="n">n</span><span class="o">*</span><span class="p">[</span><span class="mf">0.0</span><span class="p">]</span> <span class="o">+</span> <span class="n">n</span><span class="o">*</span><span class="p">[</span><span class="mf">1.0</span><span class="p">])</span>
<span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span> <span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span> <span class="o">+</span> <span class="n">m</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">))</span>
<span class="n">h</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="mf">1.0</span>
<span class="n">h</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">:]</span> <span class="o">=</span> <span class="o">-</span><span class="n">b</span>
<span class="k">def</span> <span class="nf">G</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="n">beta</span> <span class="o">=</span> <span class="mf">0.0</span><span class="p">,</span> <span class="n">trans</span> <span class="o">=</span> <span class="s">'N'</span><span class="p">):</span>
<span class="n">y</span> <span class="o">*=</span> <span class="n">beta</span>
<span class="k">if</span> <span class="n">trans</span><span class="o">==</span><span class="s">'N'</span><span class="p">:</span>
<span class="c"># y += alpha * G * x</span>
<span class="n">y</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">+=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="p">(</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">])</span>
<span class="n">y</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">]</span> <span class="o">+=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="p">(</span><span class="o">-</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">])</span>
<span class="n">y</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">:]</span> <span class="o">-=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="n">A</span><span class="o">*</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span>
<span class="k">else</span><span class="p">:</span>
<span class="c"># y += alpha * G'*x</span>
<span class="n">y</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">+=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="p">(</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">A</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="n">x</span><span class="p">[</span><span class="o">-</span><span class="n">m</span><span class="p">:])</span>
<span class="n">y</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">-=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="p">(</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">+</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">])</span>
<span class="k">def</span> <span class="nf">Fkkt</span><span class="p">(</span><span class="n">W</span><span class="p">):</span>
<span class="sd">"""</span>
<span class="sd"> Returns a function f(x, y, z) that solves</span>
<span class="sd"> [ 0 G' ] [ x ] = [ bx ]</span>
<span class="sd"> [ G -W'*W ] [ z ] [ bz ].</span>
<span class="sd"> """</span>
<span class="c"># First factor</span>
<span class="c">#</span>
<span class="c"># S = G' * W**-1 * W**-T * G</span>
<span class="c"># = [0; -A]' * W3^-2 * [0; -A] + 4 * (W1**2 + W2**2)**-1</span>
<span class="c">#</span>
<span class="c"># where</span>
<span class="c">#</span>
<span class="c"># W1 = diag(d1) with d1 = W['d'][:n] = 1 ./ W['di'][:n]</span>
<span class="c"># W2 = diag(d2) with d2 = W['d'][n:] = 1 ./ W['di'][n:]</span>
<span class="c"># W3 = beta * (2*v*v' - J), W3^-1 = 1/beta * (2*J*v*v'*J - J)</span>
<span class="c"># with beta = W['beta'][0], v = W['v'][0], J = [1, 0; 0, -I].</span>
<span class="c"># As = W3^-1 * [ 0 ; -A ] = 1/beta * ( 2*J*v * v' - I ) * [0; A]</span>
<span class="n">beta</span><span class="p">,</span> <span class="n">v</span> <span class="o">=</span> <span class="n">W</span><span class="p">[</span><span class="s">'beta'</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="n">W</span><span class="p">[</span><span class="s">'v'</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span>
<span class="n">As</span> <span class="o">=</span> <span class="mi">2</span> <span class="o">*</span> <span class="n">v</span> <span class="o">*</span> <span class="p">(</span><span class="n">v</span><span class="p">[</span><span class="mi">1</span><span class="p">:]</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="n">A</span><span class="p">)</span>
<span class="n">As</span><span class="p">[</span><span class="mi">1</span><span class="p">:,:]</span> <span class="o">*=</span> <span class="o">-</span><span class="mf">1.0</span>
<span class="n">As</span><span class="p">[</span><span class="mi">1</span><span class="p">:,:]</span> <span class="o">-=</span> <span class="n">A</span>
<span class="n">As</span> <span class="o">/=</span> <span class="n">beta</span>
<span class="c"># S = As'*As + 4 * (W1**2 + W2**2)**-1</span>
<span class="n">S</span> <span class="o">=</span> <span class="n">As</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="n">As</span>
<span class="n">d1</span><span class="p">,</span> <span class="n">d2</span> <span class="o">=</span> <span class="n">W</span><span class="p">[</span><span class="s">'d'</span><span class="p">][:</span><span class="n">n</span><span class="p">],</span> <span class="n">W</span><span class="p">[</span><span class="s">'d'</span><span class="p">][</span><span class="n">n</span><span class="p">:]</span>
<span class="n">d</span> <span class="o">=</span> <span class="mf">4.0</span> <span class="o">*</span> <span class="p">(</span><span class="n">d1</span><span class="o">**</span><span class="mi">2</span> <span class="o">+</span> <span class="n">d2</span><span class="o">**</span><span class="mi">2</span><span class="p">)</span><span class="o">**-</span><span class="mi">1</span>
<span class="n">S</span><span class="p">[::</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">+=</span> <span class="n">d</span>
<span class="n">lapack</span><span class="o">.</span><span class="n">potrf</span><span class="p">(</span><span class="n">S</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">):</span>
<span class="c"># z := - W**-T * z</span>
<span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="n">div</span><span class="p">(</span> <span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">],</span> <span class="n">d1</span> <span class="p">)</span>
<span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="n">div</span><span class="p">(</span> <span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">],</span> <span class="n">d2</span> <span class="p">)</span>
<span class="n">z</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">:]</span> <span class="o">-=</span> <span class="mf">2.0</span><span class="o">*</span><span class="n">v</span><span class="o">*</span><span class="p">(</span> <span class="n">v</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">*</span><span class="n">z</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">blas</span><span class="o">.</span><span class="n">dot</span><span class="p">(</span><span class="n">v</span><span class="p">[</span><span class="mi">1</span><span class="p">:],</span> <span class="n">z</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">:])</span> <span class="p">)</span>
<span class="n">z</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">:]</span> <span class="o">*=</span> <span class="o">-</span><span class="mf">1.0</span>
<span class="n">z</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">:]</span> <span class="o">/=</span> <span class="n">beta</span>
<span class="c"># x := x - G' * W**-1 * z</span>
<span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-=</span> <span class="n">div</span><span class="p">(</span><span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">],</span> <span class="n">d1</span><span class="p">)</span> <span class="o">-</span> <span class="n">div</span><span class="p">(</span><span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">],</span> <span class="n">d2</span><span class="p">)</span> <span class="o">+</span> <span class="n">As</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="n">z</span><span class="p">[</span><span class="o">-</span><span class="p">(</span><span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">):]</span>
<span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">+=</span> <span class="n">div</span><span class="p">(</span><span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">],</span> <span class="n">d1</span><span class="p">)</span> <span class="o">+</span> <span class="n">div</span><span class="p">(</span><span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">],</span> <span class="n">d2</span><span class="p">)</span>
<span class="c"># Solve for x[:n]:</span>
<span class="c">#</span>
<span class="c"># S*x[:n] = x[:n] - (W1**2 - W2**2)(W1**2 + W2**2)^-1 * x[n:]</span>
<span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-=</span> <span class="n">mul</span><span class="p">(</span> <span class="n">div</span><span class="p">(</span><span class="n">d1</span><span class="o">**</span><span class="mi">2</span> <span class="o">-</span> <span class="n">d2</span><span class="o">**</span><span class="mi">2</span><span class="p">,</span> <span class="n">d1</span><span class="o">**</span><span class="mi">2</span> <span class="o">+</span> <span class="n">d2</span><span class="o">**</span><span class="mi">2</span><span class="p">),</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:])</span>
<span class="n">lapack</span><span class="o">.</span><span class="n">potrs</span><span class="p">(</span><span class="n">S</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span>
<span class="c"># Solve for x[n:]:</span>
<span class="c">#</span>
<span class="c"># (d1**-2 + d2**-2) * x[n:] = x[n:] + (d1**-2 - d2**-2)*x[:n]</span>
<span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">+=</span> <span class="n">mul</span><span class="p">(</span> <span class="n">d1</span><span class="o">**-</span><span class="mi">2</span> <span class="o">-</span> <span class="n">d2</span><span class="o">**-</span><span class="mi">2</span><span class="p">,</span> <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">])</span>
<span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">=</span> <span class="n">div</span><span class="p">(</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:],</span> <span class="n">d1</span><span class="o">**-</span><span class="mi">2</span> <span class="o">+</span> <span class="n">d2</span><span class="o">**-</span><span class="mi">2</span><span class="p">)</span>
<span class="c"># z := z + W^-T * G*x</span>
<span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">+=</span> <span class="n">div</span><span class="p">(</span> <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">],</span> <span class="n">d1</span><span class="p">)</span>
<span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">]</span> <span class="o">+=</span> <span class="n">div</span><span class="p">(</span> <span class="o">-</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">],</span> <span class="n">d2</span><span class="p">)</span>
<span class="n">z</span><span class="p">[</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">:]</span> <span class="o">+=</span> <span class="n">As</span><span class="o">*</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span>
<span class="k">return</span> <span class="n">f</span>
<span class="n">dims</span> <span class="o">=</span> <span class="p">{</span><span class="s">'l'</span><span class="p">:</span> <span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">,</span> <span class="s">'q'</span><span class="p">:</span> <span class="p">[</span><span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">],</span> <span class="s">'s'</span><span class="p">:</span> <span class="p">[]}</span>
<span class="n">sol</span> <span class="o">=</span> <span class="n">solvers</span><span class="o">.</span><span class="n">conelp</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">,</span> <span class="n">dims</span><span class="p">,</span> <span class="n">kktsolver</span> <span class="o">=</span> <span class="n">Fkkt</span><span class="p">)</span>
<span class="k">if</span> <span class="n">sol</span><span class="p">[</span><span class="s">'status'</span><span class="p">]</span> <span class="o">==</span> <span class="s">'optimal'</span><span class="p">:</span>
<span class="k">return</span> <span class="n">sol</span><span class="p">[</span><span class="s">'x'</span><span class="p">][:</span><span class="n">n</span><span class="p">],</span> <span class="n">sol</span><span class="p">[</span><span class="s">'z'</span><span class="p">][</span><span class="o">-</span><span class="n">m</span><span class="p">:]</span>
<span class="k">else</span><span class="p">:</span>
<span class="k">return</span> <span class="bp">None</span><span class="p">,</span> <span class="bp">None</span>
</pre></div>
</div>
</dd>
<dt><strong>Example: 1-norm regularized least-squares</strong></dt>
<dd><p class="first">As an example that illustrates how structure can be exploited in
<a title="cvxopt.solvers.coneqp" class="reference internal" href="#cvxopt.solvers.coneqp"><tt class="xref docutils literal"><span class="pre">coneqp</span></tt></a>, we consider the 1-norm
regularized least-squares problem</p>
<div class="math">
<p><img src="_images/math/98a42473d3645f925ce069e48a478746fb82e9b6.png" alt="\begin{array}{ll}
\mbox{minimize} & \|Ax - y\|_2^2 + \|x\|_1
\end{array}" /></p>
</div><p>with variable <img class="math" src="_images/math/26eeb5258ca5099acf8fe96b2a1049c48c89a5e6.png" alt="x"/>. The problem is equivalent to the quadratic
program</p>
<div class="math">
<p><img src="_images/math/7da7f3d84cc8689757c290b7e2f239e242887694.png" alt="\newcommand{\ones}{{\bf 1}}
\begin{array}{ll}
\mbox{minimize} & \|Ax - y\|_2^2 + \ones^T u \\
\mbox{subject to} & -u \preceq x \preceq u
\end{array}" /></p>
</div><p>with variables <img class="math" src="_images/math/26eeb5258ca5099acf8fe96b2a1049c48c89a5e6.png" alt="x"/> and <img class="math" src="_images/math/9ad99798ec4c38e165cf517cb9e02b1c9e824103.png" alt="u"/>. The implementation below is
efficient when <img class="math" src="_images/math/019e9892786e493964e145e7c5cf7b700314e53b.png" alt="A"/> has many more columns than rows.</p>
<div class="last highlight-python"><div class="highlight"><pre><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">matrix</span><span class="p">,</span> <span class="n">spdiag</span><span class="p">,</span> <span class="n">mul</span><span class="p">,</span> <span class="n">div</span><span class="p">,</span> <span class="n">blas</span><span class="p">,</span> <span class="n">lapack</span><span class="p">,</span> <span class="n">solvers</span><span class="p">,</span> <span class="n">sqrt</span>
<span class="kn">import</span> <span class="nn">math</span>
<span class="k">def</span> <span class="nf">l1regls</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">y</span><span class="p">):</span>
<span class="sd">"""</span>
<span class="sd"> Returns the solution of l1-norm regularized least-squares problem</span>
<span class="sd"> minimize || A*x - y ||_2^2 + || x ||_1.</span>
<span class="sd"> """</span>
<span class="n">m</span><span class="p">,</span> <span class="n">n</span> <span class="o">=</span> <span class="n">A</span><span class="o">.</span><span class="n">size</span>
<span class="n">q</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">1.0</span><span class="p">,</span> <span class="p">(</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>
<span class="n">q</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="mf">2.0</span> <span class="o">*</span> <span class="n">A</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="n">y</span>
<span class="k">def</span> <span class="nf">P</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">alpha</span> <span class="o">=</span> <span class="mf">1.0</span><span class="p">,</span> <span class="n">beta</span> <span class="o">=</span> <span class="mf">0.0</span> <span class="p">):</span>
<span class="sd">"""</span>
<span class="sd"> v := alpha * 2.0 * [ A'*A, 0; 0, 0 ] * u + beta * v</span>
<span class="sd"> """</span>
<span class="n">v</span> <span class="o">*=</span> <span class="n">beta</span>
<span class="n">v</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">+=</span> <span class="n">alpha</span> <span class="o">*</span> <span class="mf">2.0</span> <span class="o">*</span> <span class="n">A</span><span class="o">.</span><span class="n">T</span> <span class="o">*</span> <span class="p">(</span><span class="n">A</span> <span class="o">*</span> <span class="n">u</span><span class="p">[:</span><span class="n">n</span><span class="p">])</span>
<span class="k">def</span> <span class="nf">G</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">alpha</span><span class="o">=</span><span class="mf">1.0</span><span class="p">,</span> <span class="n">beta</span><span class="o">=</span><span class="mf">0.0</span><span class="p">,</span> <span class="n">trans</span><span class="o">=</span><span class="s">'N'</span><span class="p">):</span>
<span class="sd">"""</span>
<span class="sd"> v := alpha*[I, -I; -I, -I] * u + beta * v (trans = 'N' or 'T')</span>
<span class="sd"> """</span>
<span class="n">v</span> <span class="o">*=</span> <span class="n">beta</span>
<span class="n">v</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">+=</span> <span class="n">alpha</span><span class="o">*</span><span class="p">(</span><span class="n">u</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">u</span><span class="p">[</span><span class="n">n</span><span class="p">:])</span>
<span class="n">v</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">+=</span> <span class="n">alpha</span><span class="o">*</span><span class="p">(</span><span class="o">-</span><span class="n">u</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">u</span><span class="p">[</span><span class="n">n</span><span class="p">:])</span>
<span class="n">h</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="mi">2</span><span class="o">*</span><span class="n">n</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>
<span class="c"># Customized solver for the KKT system</span>
<span class="c">#</span>
<span class="c"># [ 2.0*A'*A 0 I -I ] [x[:n] ] [bx[:n] ]</span>
<span class="c"># [ 0 0 -I -I ] [x[n:] ] = [bx[n:] ].</span>
<span class="c"># [ I -I -D1^-1 0 ] [zl[:n]] [bzl[:n]]</span>
<span class="c"># [ -I -I 0 -D2^-1 ] [zl[n:]] [bzl[n:]]</span>
<span class="c">#</span>
<span class="c"># where D1 = W['di'][:n]**2, D2 = W['di'][n:]**2.</span>
<span class="c">#</span>
<span class="c"># We first eliminate zl and x[n:]:</span>
<span class="c">#</span>
<span class="c"># ( 2*A'*A + 4*D1*D2*(D1+D2)^-1 ) * x[:n] =</span>
<span class="c"># bx[:n] - (D2-D1)*(D1+D2)^-1 * bx[n:] +</span>
<span class="c"># D1 * ( I + (D2-D1)*(D1+D2)^-1 ) * bzl[:n] -</span>
<span class="c"># D2 * ( I - (D2-D1)*(D1+D2)^-1 ) * bzl[n:]</span>
<span class="c">#</span>
<span class="c"># x[n:] = (D1+D2)^-1 * ( bx[n:] - D1*bzl[:n] - D2*bzl[n:] )</span>
<span class="c"># - (D2-D1)*(D1+D2)^-1 * x[:n]</span>
<span class="c">#</span>
<span class="c"># zl[:n] = D1 * ( x[:n] - x[n:] - bzl[:n] )</span>
<span class="c"># zl[n:] = D2 * (-x[:n] - x[n:] - bzl[n:] ).</span>
<span class="c">#</span>
<span class="c"># The first equation has the form</span>
<span class="c">#</span>
<span class="c"># (A'*A + D)*x[:n] = rhs</span>
<span class="c">#</span>
<span class="c"># and is equivalent to</span>
<span class="c">#</span>
<span class="c"># [ D A' ] [ x:n] ] = [ rhs ]</span>
<span class="c"># [ A -I ] [ v ] [ 0 ].</span>
<span class="c">#</span>
<span class="c"># It can be solved as</span>
<span class="c">#</span>
<span class="c"># ( A*D^-1*A' + I ) * v = A * D^-1 * rhs</span>
<span class="c"># x[:n] = D^-1 * ( rhs - A'*v ).</span>
<span class="n">S</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">m</span><span class="p">,</span><span class="n">m</span><span class="p">))</span>
<span class="n">Asc</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">m</span><span class="p">,</span><span class="n">n</span><span class="p">))</span>
<span class="n">v</span> <span class="o">=</span> <span class="n">matrix</span><span class="p">(</span><span class="mf">0.0</span><span class="p">,</span> <span class="p">(</span><span class="n">m</span><span class="p">,</span><span class="mi">1</span><span class="p">))</span>
<span class="k">def</span> <span class="nf">Fkkt</span><span class="p">(</span><span class="n">W</span><span class="p">):</span>
<span class="c"># Factor</span>
<span class="c">#</span>
<span class="c"># S = A*D^-1*A' + I</span>
<span class="c">#</span>
<span class="c"># where D = 2*D1*D2*(D1+D2)^-1, D1 = d[:n]**-2, D2 = d[n:]**-2.</span>
<span class="n">d1</span><span class="p">,</span> <span class="n">d2</span> <span class="o">=</span> <span class="n">W</span><span class="p">[</span><span class="s">'di'</span><span class="p">][:</span><span class="n">n</span><span class="p">]</span><span class="o">**</span><span class="mi">2</span><span class="p">,</span> <span class="n">W</span><span class="p">[</span><span class="s">'di'</span><span class="p">][</span><span class="n">n</span><span class="p">:]</span><span class="o">**</span><span class="mi">2</span>
<span class="c"># ds is square root of diagonal of D</span>
<span class="n">ds</span> <span class="o">=</span> <span class="n">math</span><span class="o">.</span><span class="n">sqrt</span><span class="p">(</span><span class="mf">2.0</span><span class="p">)</span> <span class="o">*</span> <span class="n">div</span><span class="p">(</span> <span class="n">mul</span><span class="p">(</span> <span class="n">W</span><span class="p">[</span><span class="s">'di'</span><span class="p">][:</span><span class="n">n</span><span class="p">],</span> <span class="n">W</span><span class="p">[</span><span class="s">'di'</span><span class="p">][</span><span class="n">n</span><span class="p">:]),</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">d1</span><span class="o">+</span><span class="n">d2</span><span class="p">)</span> <span class="p">)</span>
<span class="n">d3</span> <span class="o">=</span> <span class="n">div</span><span class="p">(</span><span class="n">d2</span> <span class="o">-</span> <span class="n">d1</span><span class="p">,</span> <span class="n">d1</span> <span class="o">+</span> <span class="n">d2</span><span class="p">)</span>
<span class="c"># Asc = A*diag(d)^-1/2</span>
<span class="n">Asc</span> <span class="o">=</span> <span class="n">A</span> <span class="o">*</span> <span class="n">spdiag</span><span class="p">(</span><span class="n">ds</span><span class="o">**-</span><span class="mi">1</span><span class="p">)</span>
<span class="c"># S = I + A * D^-1 * A'</span>
<span class="n">blas</span><span class="o">.</span><span class="n">syrk</span><span class="p">(</span><span class="n">Asc</span><span class="p">,</span> <span class="n">S</span><span class="p">)</span>
<span class="n">S</span><span class="p">[::</span><span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">+=</span> <span class="mf">1.0</span>
<span class="n">lapack</span><span class="o">.</span><span class="n">potrf</span><span class="p">(</span><span class="n">S</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">g</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">):</span>
<span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="mf">0.5</span> <span class="o">*</span> <span class="p">(</span> <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">mul</span><span class="p">(</span><span class="n">d3</span><span class="p">,</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:])</span> <span class="o">+</span>
<span class="n">mul</span><span class="p">(</span><span class="n">d1</span><span class="p">,</span> <span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">+</span> <span class="n">mul</span><span class="p">(</span><span class="n">d3</span><span class="p">,</span> <span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">]))</span> <span class="o">-</span> <span class="n">mul</span><span class="p">(</span><span class="n">d2</span><span class="p">,</span> <span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">-</span>
<span class="n">mul</span><span class="p">(</span><span class="n">d3</span><span class="p">,</span> <span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:]))</span> <span class="p">)</span>
<span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="n">div</span><span class="p">(</span> <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">],</span> <span class="n">ds</span><span class="p">)</span>
<span class="c"># Solve</span>
<span class="c">#</span>
<span class="c"># S * v = 0.5 * A * D^-1 * ( bx[:n] -</span>
<span class="c"># (D2-D1)*(D1+D2)^-1 * bx[n:] +</span>
<span class="c"># D1 * ( I + (D2-D1)*(D1+D2)^-1 ) * bzl[:n] -</span>
<span class="c"># D2 * ( I - (D2-D1)*(D1+D2)^-1 ) * bzl[n:] )</span>
<span class="n">blas</span><span class="o">.</span><span class="n">gemv</span><span class="p">(</span><span class="n">Asc</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span>
<span class="n">lapack</span><span class="o">.</span><span class="n">potrs</span><span class="p">(</span><span class="n">S</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span>
<span class="c"># x[:n] = D^-1 * ( rhs - A'*v ).</span>
<span class="n">blas</span><span class="o">.</span><span class="n">gemv</span><span class="p">(</span><span class="n">Asc</span><span class="p">,</span> <span class="n">v</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">alpha</span><span class="o">=-</span><span class="mf">1.0</span><span class="p">,</span> <span class="n">beta</span><span class="o">=</span><span class="mf">1.0</span><span class="p">,</span> <span class="n">trans</span><span class="o">=</span><span class="s">'T'</span><span class="p">)</span>
<span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="n">div</span><span class="p">(</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">],</span> <span class="n">ds</span><span class="p">)</span>
<span class="c"># x[n:] = (D1+D2)^-1 * ( bx[n:] - D1*bzl[:n] - D2*bzl[n:] )</span>
<span class="c"># - (D2-D1)*(D1+D2)^-1 * x[:n]</span>
<span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">=</span> <span class="n">div</span><span class="p">(</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">-</span> <span class="n">mul</span><span class="p">(</span><span class="n">d1</span><span class="p">,</span> <span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">])</span> <span class="o">-</span> <span class="n">mul</span><span class="p">(</span><span class="n">d2</span><span class="p">,</span> <span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:]),</span> <span class="n">d1</span><span class="o">+</span><span class="n">d2</span> <span class="p">)</span>\
<span class="o">-</span> <span class="n">mul</span><span class="p">(</span> <span class="n">d3</span><span class="p">,</span> <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="p">)</span>
<span class="c"># zl[:n] = D1^1/2 * ( x[:n] - x[n:] - bzl[:n] )</span>
<span class="c"># zl[n:] = D2^1/2 * ( -x[:n] - x[n:] - bzl[n:] ).</span>
<span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="n">mul</span><span class="p">(</span> <span class="n">W</span><span class="p">[</span><span class="s">'di'</span><span class="p">][:</span><span class="n">n</span><span class="p">],</span> <span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">-</span> <span class="n">z</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="p">)</span>
<span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">=</span> <span class="n">mul</span><span class="p">(</span> <span class="n">W</span><span class="p">[</span><span class="s">'di'</span><span class="p">][</span><span class="n">n</span><span class="p">:],</span> <span class="o">-</span><span class="n">x</span><span class="p">[:</span><span class="n">n</span><span class="p">]</span> <span class="o">-</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="o">-</span> <span class="n">z</span><span class="p">[</span><span class="n">n</span><span class="p">:]</span> <span class="p">)</span>
<span class="k">return</span> <span class="n">g</span>
<span class="k">return</span> <span class="n">solvers</span><span class="o">.</span><span class="n">coneqp</span><span class="p">(</span><span class="n">P</span><span class="p">,</span> <span class="n">q</span><span class="p">,</span> <span class="n">G</span><span class="p">,</span> <span class="n">h</span><span class="p">,</span> <span class="n">kktsolver</span> <span class="o">=</span> <span class="n">Fkkt</span><span class="p">)[</span><span class="s">'x'</span><span class="p">][:</span><span class="n">n</span><span class="p">]</span>
</pre></div>
</div>
</dd>
</dl>
</div>
<div class="section" id="optional-solvers">
<span id="s-external"></span><h2>Optional Solvers<a class="headerlink" href="#optional-solvers" title="Permalink to this headline">¶</a></h2>
<p>CVXOPT includes optional interfaces to several other optimization
libraries.</p>
<dl class="docutils">
<dt><strong>GLPK</strong></dt>
<dd><a title="cvxopt.solvers.lp" class="reference internal" href="#cvxopt.solvers.lp"><tt class="xref docutils literal"><span class="pre">lp</span></tt></a> with the <tt class="docutils literal"><span class="pre">solver</span></tt> option set to
<tt class="xref docutils literal"><span class="pre">'glpk'</span></tt> uses the
simplex algorithm in <a class="reference external" href="http://www.gnu.org/software/glpk/glpk.html">GLPK (GNU Linear Programming Kit)</a>.</dd>
<dt><strong>MOSEK</strong></dt>
<dd><a title="cvxopt.solvers.lp" class="reference internal" href="#cvxopt.solvers.lp"><tt class="xref docutils literal"><span class="pre">lp</span></tt></a>, <a title="cvxopt.solvers.socp" class="reference internal" href="#cvxopt.solvers.socp"><tt class="xref docutils literal"><span class="pre">socp</span></tt></a>,
and <a title="cvxopt.solvers.qp" class="reference internal" href="#cvxopt.solvers.qp"><tt class="xref docutils literal"><span class="pre">qp</span></tt></a> with the <tt class="docutils literal"><span class="pre">solver</span></tt> option
set to <tt class="xref docutils literal"><span class="pre">'mosek'</span></tt> option use <a class="reference external" href="http://www.mosek.com">MOSEK</a>
version 5.</dd>
<dt><strong>DSDP</strong></dt>
<dd><a title="cvxopt.solvers.sdp" class="reference internal" href="#cvxopt.solvers.sdp"><tt class="xref docutils literal"><span class="pre">sdp</span></tt></a> with the <tt class="docutils literal"><span class="pre">solver</span></tt> option set to
<tt class="xref docutils literal"><span class="pre">'dsdp'</span></tt> uses
the <a class="reference external" href="http://www-unix.mcs.anl.gov/DSDP">DSDP5.8</a>.</dd>
</dl>
<p>GLPK, MOSEK and DSDP are not included in the CVXOPT distribution and
need to be installed separately.</p>
</div>
<div class="section" id="algorithm-parameters">
<span id="s-parameters"></span><h2>Algorithm Parameters<a class="headerlink" href="#algorithm-parameters" title="Permalink to this headline">¶</a></h2>
<p>In this section we list some algorithm control parameters that can be
modified without editing the source code. These control parameters are
accessible via the dictionary <tt class="xref docutils literal"><span class="pre">solvers.options</span></tt>. By default the
dictionary is empty and the default values of the parameters are used.</p>
<p>One can change the parameters in the default solvers by
adding entries with the following key values.</p>
<dl class="docutils">
<dt><tt class="xref docutils literal"><span class="pre">'show_progress'</span></tt></dt>
<dd><tt class="xref xref docutils literal"><span class="pre">True</span></tt> or <tt class="xref xref docutils literal"><span class="pre">False</span></tt>; turns the output to the screen on or
off (default: <tt class="xref xref docutils literal"><span class="pre">True</span></tt>).</dd>
<dt><tt class="xref docutils literal"><span class="pre">'maxiters'</span></tt></dt>
<dd>maximum number of iterations (default: <tt class="xref docutils literal"><span class="pre">100</span></tt>).</dd>
<dt><tt class="xref docutils literal"><span class="pre">'abstol'</span></tt></dt>
<dd>absolute accuracy (default: <tt class="xref docutils literal"><span class="pre">1e-7</span></tt>).</dd>
<dt><tt class="xref docutils literal"><span class="pre">'reltol'</span></tt></dt>
<dd>relative accuracy (default: <tt class="xref docutils literal"><span class="pre">1e-6</span></tt>).</dd>
<dt><tt class="xref docutils literal"><span class="pre">'feastol'</span></tt></dt>
<dd>tolerance for feasibility conditions (default: <tt class="xref docutils literal"><span class="pre">1e-7</span></tt>).</dd>
<dt><tt class="xref docutils literal"><span class="pre">'refinement'</span></tt></dt>
<dd>number of iterative refinement steps when solving KKT equations
(default: <tt class="xref docutils literal"><span class="pre">0</span></tt> if the problem has no second-order cone or matrix
inequality constraints; <tt class="xref docutils literal"><span class="pre">1</span></tt> otherwise).</dd>
</dl>
<p>For example the command</p>
<div class="highlight-python"><div class="highlight"><pre><span class="gp">>>> </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">solvers</span>
<span class="gp">>>> </span><span class="n">solvers</span><span class="o">.</span><span class="n">options</span><span class="p">[</span><span class="s">'show_progress'</span><span class="p">]</span> <span class="o">=</span> <span class="bp">False</span>
</pre></div>
</div>
<p>turns off the screen output during calls to the solvers.</p>
<p>The tolerances <tt class="xref docutils literal"><span class="pre">'abstol'</span></tt>, <tt class="xref docutils literal"><span class="pre">'reltol'</span></tt> and <tt class="xref docutils literal"><span class="pre">'feastol'</span></tt>
have the following meaning. <a title="cvxopt.solvers.conelp" class="reference internal" href="#cvxopt.solvers.conelp"><tt class="xref docutils literal"><span class="pre">conelp</span></tt></a>
terminates with status <tt class="xref docutils literal"><span class="pre">'optimal'</span></tt> if</p>
<div class="math">
<p><img src="_images/math/a8d0548e81d41514430788f0faf3d247c82a6b64.png" alt="s \succeq 0, \qquad
\frac{\|Gx + s - h\|_2} {\max\{1,\|h\|_2\}} \leq
\epsilon_\mathrm{feas}, \qquad
\frac{\|Ax-b\|_2}{\max\{1,\|b\|_2\}} \leq \epsilon_\mathrm{feas},
\qquad" /></p>
</div><p>and</p>
<div class="math">
<p><img src="_images/math/9cb4d73f6ab0d3b8d69adb041e6659d7408e2b9c.png" alt="z \succeq 0, \qquad
\frac{\|G^Tz + A^Ty + c\|_2}{\max\{1,\|c\|_2\}} \leq
\epsilon_\mathrm{feas}," /></p>
</div><p>and</p>
<div class="math">
<p><img src="_images/math/7694bb8a11c78790d1c12572c04a6df59e94c05c.png" alt="s^T z \leq \epsilon_\mathrm{abs} \qquad \mbox{or} \qquad
\left( \min\left\{c^Tx, h^T z + b^Ty \right\} < 0 \quad
\mbox{and} \quad
\frac{s^Tz} {-\min\{c^Tx, h^Tz + b^T y\}} \leq \epsilon_\mathrm{rel}
\right)." /></p>
</div><p>It returns with status <tt class="xref docutils literal"><span class="pre">'primal</span> <span class="pre">infeasible'</span></tt> if</p>
<div class="math">
<p><img src="_images/math/a27183e0007f4567dab53885ee2d927f4d50e99b.png" alt="z \succeq 0, \qquad \qquad
\frac{\|G^Tz +A^Ty\|_2}{\max\{1, \|c\|_2\}} \leq
\epsilon_\mathrm{feas}, \qquad
h^Tz +b^Ty = -1." /></p>
</div><p>It returns with status <tt class="xref docutils literal"><span class="pre">'dual</span> <span class="pre">infeasible'</span></tt> if</p>
<div class="math">
<p><img src="_images/math/bb097746083c5ae7ae0044d78c10841dde34c10d.png" alt="s \succeq 0, \qquad \qquad
\frac{\|Gx+s\|_2}{\max\{1, \|h\|_2\}} \leq \epsilon_\mathrm{feas},
\qquad
\frac{\|Ax\|_2}{\max\{1, \|b\|_2\}} \leq \epsilon_\mathrm{feas},
\qquad c^Tx = -1." /></p>
</div><p>The functions <a title="cvxopt.solvers.lp" class="reference internal" href="#cvxopt.solvers.lp"><tt class="xref docutils literal"><span class="pre">lp</span> </tt></a>,
<a title="cvxopt.solvers.socp" class="reference internal" href="#cvxopt.solvers.socp"><tt class="xref docutils literal"><span class="pre">socp</span></tt></a> and
<a title="cvxopt.solvers.sdp" class="reference internal" href="#cvxopt.solvers.sdp"><tt class="xref docutils literal"><span class="pre">sdp</span></tt></a> call <tt class="xref docutils literal"><span class="pre">conelp</span></tt>
and hence use the same stopping criteria.</p>
<p>The function <a title="cvxopt.solvers.coneqp" class="reference internal" href="#cvxopt.solvers.coneqp"><tt class="xref docutils literal"><span class="pre">coneqp</span></tt></a> terminates with
status <tt class="xref docutils literal"><span class="pre">'optimal'</span></tt> if</p>
<div class="math">
<p><img src="_images/math/35966a8389b47f5a99dc5c8d378f99a4bbff5068.png" alt="s \succeq 0, \qquad
\frac{\|Gx + s - h\|_2} {\max\{1,\|h\|_2\}} \leq
\epsilon_\mathrm{feas}, \qquad
\frac{\|Ax-b\|_2}{\max\{1,\|b\|_2\}} \leq \epsilon_\mathrm{feas}," /></p>
</div><p>and</p>
<div class="math">
<p><img src="_images/math/128a89e677c6def54cb57ef44a64cc8307b73877.png" alt="z \succeq 0, \qquad
\frac{\|Px + G^Tz + A^Ty + q\|_2}{\max\{1,\|q\|_2\}} \leq
\epsilon_\mathrm{feas}," /></p>
</div><p>and at least one of the following three conditions is satisfied:</p>
<div class="math">
<p><img src="_images/math/c48cfb5af92e06a6a0527d035f9d5e76400dfb79.png" alt="s^T z \leq \epsilon_\mathrm{abs}" /></p>
</div><p>or</p>
<div class="math">
<p><img src="_images/math/95694f9b1e540b7079bdfc5f79c1f6b8fb13a9eb.png" alt="\left( \frac{1}{2}x^TPx + q^Tx < 0, \quad
\mbox{and}\quad \frac{s^Tz} {-(1/2)x^TPx - q^Tx} \leq
\epsilon_\mathrm{rel} \right)" /></p>
</div><p>or</p>
<div class="math">
<p><img src="_images/math/a78f26c0461f724d749e656e8ee0ce1b2d636c23.png" alt="\left( L(x,y,z) > 0 \quad \mbox{and} \quad \frac{s^Tz}
{L(x,y,z)} \leq \epsilon_\mathrm{rel} \right)." /></p>
</div><p>Here</p>
<div class="math">
<p><img src="_images/math/c69fb9977daf1ac7d84818c99c45e2afaf8dce8d.png" alt="L(x,y,z) = \frac{1}{2}x^TPx + q^Tx + z^T (Gx-h) + y^T(Ax-b)." /></p>
</div><p>The function <a title="cvxopt.solvers.qp" class="reference internal" href="#cvxopt.solvers.qp"><tt class="xref docutils literal"><span class="pre">qp</span></tt></a> calls
<tt class="xref docutils literal"><span class="pre">coneqp</span></tt> and hence uses the same
stopping criteria.</p>
<p>The control parameters listed in the GLPK documentation are set to their
default values and can be customized by making an entry in
<tt class="xref docutils literal"><span class="pre">solvers.options</span></tt>. The keys in the dictionary are strings with the
name of the GLPK parameter. For example, the command</p>
<div class="highlight-python"><div class="highlight"><pre><span class="gp">>>> </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">solvers</span>
<span class="gp">>>> </span><span class="n">solvers</span><span class="o">.</span><span class="n">options</span><span class="p">[</span><span class="s">'LPX_K_MSGLEV'</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span>
</pre></div>
</div>
<p>turns off the screen output subsequent calls
<a title="cvxopt.solvers.lp" class="reference internal" href="#cvxopt.solvers.lp"><tt class="xref docutils literal"><span class="pre">lp</span></tt></a> with the <tt class="xref docutils literal"><span class="pre">'glpk'</span></tt> option.</p>
<p>The MOSEK interior-point algorithm parameters are set to their default
values. They can be modified by adding an entry
<tt class="xref docutils literal"><span class="pre">solvers.options['MOSEK']</span></tt>. This entry is a dictionary with
MOSEK parameter/value pairs, with the parameter names imported from
<tt class="xref docutils literal"><span class="pre">pymosek</span></tt>. For details see Section 14.1.3 of the
<a class="reference external" href="http://www.mosek.com/fileadmin/products/5_0/tools/doc/html/pyapi/index.html">MOSEK Python API Manual</a>.</p>
<p>For example the commands</p>
<div class="highlight-python"><div class="highlight"><pre><span class="gp">>>> </span><span class="kn">from</span> <span class="nn">cvxopt</span> <span class="kn">import</span> <span class="n">solvers</span>
<span class="gp">>>> </span><span class="kn">import</span> <span class="nn">pymosek</span>
<span class="gp">>>> </span><span class="n">solvers</span><span class="o">.</span><span class="n">options</span><span class="p">[</span><span class="s">'MOSEK'</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="n">pymosek</span><span class="o">.</span><span class="n">iparam</span><span class="o">.</span><span class="n">log</span><span class="p">:</span> <span class="mi">0</span><span class="p">}</span>
</pre></div>
</div>
<p>turn off the screen output during calls of
<tt class="xref docutils literal"><span class="pre">lp</span></tt> or <tt class="xref docutils literal"><span class="pre">socp</span></tt> with
the <tt class="xref docutils literal"><span class="pre">'mosek'</span></tt> option.</p>
<p>The following control parameters in <tt class="xref docutils literal"><span class="pre">solvers.options</span></tt> affect the
execution of the DSDP algorithm:</p>
<dl class="docutils">
<dt><tt class="xref docutils literal"><span class="pre">'DSDP_Monitor'</span></tt></dt>
<dd>the interval (in number of iterations) at which output is printed to
the screen (default: <tt class="xref docutils literal"><span class="pre">0</span></tt>).</dd>
<dt><tt class="xref docutils literal"><span class="pre">'DSDP_MaxIts'</span></tt></dt>
<dd>maximum number of iterations.</dd>
<dt><tt class="xref docutils literal"><span class="pre">'DSDP_GapTolerance'</span></tt></dt>
<dd>relative accuracy (default: <tt class="xref docutils literal"><span class="pre">1e-5</span></tt>).</dd>
</dl>
</div>
</div>
</div>
</div>
</div>
<div class="sphinxsidebar">
<div class="sphinxsidebarwrapper">
<h3><a href="index.html">Table Of Contents</a></h3>
<ul>
<li><a class="reference external" href="#">Cone Programming</a><ul>
<li><a class="reference external" href="#linear-cone-programs">Linear Cone Programs</a></li>
<li><a class="reference external" href="#quadratic-cone-programs">Quadratic Cone Programs</a></li>
<li><a class="reference external" href="#linear-programming">Linear Programming</a></li>
<li><a class="reference external" href="#quadratic-programming">Quadratic Programming</a></li>
<li><a class="reference external" href="#second-order-cone-programming">Second-Order Cone Programming</a></li>
<li><a class="reference external" href="#semidefinite-programming">Semidefinite Programming</a></li>
<li><a class="reference external" href="#exploiting-structure">Exploiting Structure</a></li>
<li><a class="reference external" href="#optional-solvers">Optional Solvers</a></li>
<li><a class="reference external" href="#algorithm-parameters">Algorithm Parameters</a></li>
</ul>
</li>
</ul>
<h4>Previous topic</h4>
<p class="topless"><a href="spsolvers.html"
title="previous chapter">Sparse Linear Equations</a></p>
<h4>Next topic</h4>
<p class="topless"><a href="solvers.html"
title="next chapter">Nonlinear Convex Optimization</a></p>
<div id="searchbox" style="display: none">
<h3>Quick search</h3>
<form class="search" action="search.html" method="get">
<input type="text" name="q" size="18" />
<input type="submit" value="Go" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
<p class="searchtip" style="font-size: 90%">
Enter search terms or a module, class or function name.
</p>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="solvers.html" title="Nonlinear Convex Optimization"
>next</a></li>
<li class="right" >
<a href="spsolvers.html" title="Sparse Linear Equations"
>previous</a> |</li>
<li><a href="http://abel.ee.ucla.edu/cvxopt">CVXOPT home</a> |</li>
<li><a href="index.html">user's guide</a> </li>
</ul>
</div>
<div class="footer">
Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 0.6.5.
</div>
</body>
</html>
