<h2>A taxonomy of curvature<a class="headerlink" href="#a-taxonomy-of-curvature" title="Permalink to this headline">¶</a></h2>
<p>In disciplined convex programming, a scalar expression is classified by
its <em>curvature</em>. There are four categories of curvature: <em>constant</em>,
<em>affine</em>, <em>convex</em>, and <em>concave</em>. For a function
<span class="math">\(f:\mathbf{R}^n\rightarrow\mathbf{R}\)</span> defined on all
<span class="math">\(\mathbf{R}^n\)</span>, the categories have the following meanings:</p>
<div class="math">
\[\begin{split}\begin{array}{lll}
\text{constant} & f(\alpha x + (1-\alpha)y) = f(x) & \forall x,y\in\mathbf{R}^n,~\alpha\in\mathbf{R} \\
\text{affine} & f(\alpha x + (1-\alpha)y) = \alpha f(x) + (1-\alpha) f(y) & \forall x,y\in\mathbf{R}^n,~\alpha\in\mathbf{R} \\
\text{convex} & f(\alpha x + (1-\alpha)y) \leq \alpha f(x) + (1-\alpha) f(y) & \forall x,y\in\mathbf{R}^n,~\alpha\in[0,1] \\
\text{concave} & f(\alpha x + (1-\alpha)y) \geq \alpha f(x) + (1-\alpha) f(y) & \forall x,y\in\mathbf{R}^n,~\alpha\in[0,1]
\end{array}\end{split}\]</div>
<p>Of course, there is significant overlap in these categories. For
example, constant expressions are also affine, and (real) affine
expressions are both convex and concave.</p>
<p>Convex and concave expressions are real by definition. Complex constant
and affine expressions can be constructed, but their usage is more
limited; for example, they cannot appear as the left- or right-hand side
of an inequality constraint.</p>
</div>
<div class="section" id="top-level-rules">
<h2>Top-level rules<a class="headerlink" href="#top-level-rules" title="Permalink to this headline">¶</a></h2>
<p>CVX supports three different types of disciplined convex programs:</p>
<ul class="simple">
<li>A <em>minimization problem</em>, consisting of a convex objective function
and zero or more constraints.</li>
<li>A <em>maximization problem</em>, consisting of a concave objective function
and zero or more constraints.</li>
<li>A <em>feasibility problem</em>, consisting of one or more constraints and no
objective.</li>
</ul>
</div>
<div class="section" id="constraints">
<h2>Constraints<a class="headerlink" href="#constraints" title="Permalink to this headline">¶</a></h2>
<p>Three types of constraints may be specified in disciplined convex
programs:</p>
<ul class="simple">
<li>An <em>equality constraint</em>, constructed using <tt class="docutils literal"><span class="pre">==</span></tt>, where both sides
are affine.</li>
<li>A <em>less-than inequality constraint</em>, using <tt class="docutils literal"><span class="pre"><=</span></tt>, where the left
side is convex and the right side is concave.</li>
<li>A <em>greater-than inequality constraint</em>, using <tt class="docutils literal"><span class="pre">>=</span></tt>, where the left
side is concave and the right side is convex.</li>
</ul>
<p><em>Non</em>-equality constraints, constructed using <tt class="docutils literal"><span class="pre">~=</span></tt>, are never allowed.
(Such constraints are not convex.)</p>
<p>One or both sides of an equality constraint may be complex; inequality
constraints, on the other hand, must be real. A complex equality
constraint is equivalent to two real equality constraints, one for the
real part and one for the imaginary part. An equality constraint with a
real side and a complex side has the effect of constraining the
imaginary part of the complex side to be zero.</p>
<p>As discussed in <a class="reference internal" href="basics.html#sets"><em>Set membership</em></a>, CVX enforces set membership
constraints (<em>e.g.</em>, <span class="math">\(x\in S\)</span>) using equality constraints. The
rule that both sides of an equality constraint must be affine applies to
set membership constraints as well. In fact, the returned value of set
atoms like <tt class="docutils literal"><span class="pre">semidefinite()</span></tt> and <tt class="docutils literal"><span class="pre">lorentz()</span></tt> is affine, so it is
sufficient to simply verify the remaining portion of the set membership
constraint. For composite values like <tt class="docutils literal"><span class="pre">{</span> <span class="pre">x,</span> <span class="pre">y</span> <span class="pre">}</span></tt>, each element must be
affine.</p>
<div class="section" id="strict-inequalities">
<span id="strict"></span><h3>Strict inequalities<a class="headerlink" href="#strict-inequalities" title="Permalink to this headline">¶</a></h3>
<p>As mentioned in <a class="reference internal" href="basics.html#constraints"><em>Constraints</em></a>, strict inequalities <tt class="docutils literal"><span class="pre"><</span></tt>, <tt class="docutils literal"><span class="pre">></span></tt> are interpreted
in an identical fashion to nonstrict inequalities <tt class="docutils literal"><span class="pre">>=</span></tt>, <tt class="docutils literal"><span class="pre"><=</span></tt>. It is important to
note that CVX cannot guarantee that an inequality will be strictly satisfied
at the solution it computes. This is not simply a choice we have made in CVX; it is
a natural consequence of both the underlying mathematics and the
design of convex optimization solvers.
For that reason, we <em>strongly</em> discourage the use of strict inequalities in CVX,
and a future version may remove them altogether.</p>
<p>When a strict inequality is essential to your model, you may need to take additional
steps to ensure compliance. In some cases, this can be accomplished through
<em>normalization</em>. For instance, consider a set of homogeneous equations and inequalities:</p>
<div class="math">
\[A x = 0, \quad C x \preceq 0, \quad x \succ 0\]</div>
<p>Except for the strict inequality, <span class="math">\(x=0\)</span> would be an acceptable solution; indeed
the need to avoid the origin is the very reason for the strict inequality. However, note
that if a given <span class="math">\(x\)</span> satisfies these constraints, then so does
<span class="math">\(\alpha x\)</span> for all <span class="math">\(\alpha>0\)</span>. By eliminating this degree of freedom with
normalization, we can eliminate the strict inequality; for instance:</p>
<div class="math">
\[A x = 0, \quad C x \preceq 0, \quad x \succ 0, \quad \mathbf{1}^T x = 1\]</div>
<p>If normalization is not a valid approach for your model, you may simply need to convert
the strict inequality into a non-strict one by adding a small offset; <em>e.g.</em>, convert
<tt class="docutils literal"><span class="pre">x</span> <span class="pre">></span> <span class="pre">0</span></tt> to, say, <tt class="docutils literal"><span class="pre">x</span> <span class="pre">>=</span> <span class="pre">1e-4</span></tt>. Note that the bound needs to be large enough so
that the underlying solver considers it numerically significant.</p>
<p>Finally, note that for some functions like <tt class="docutils literal"><span class="pre">log(x)</span></tt> and <tt class="docutils literal"><span class="pre">inv_pos(x)</span></tt>, which have domains
defined by strict inequalities, the domain restriction is handled <em>by the function itself</em>.
You do not need to add an explicit constraint <tt class="docutils literal"><span class="pre">x</span> <span class="pre">></span> <span class="pre">0</span></tt> to your model to guarantee
that the solution is positive.</p>
</div>
</div>
<div class="section" id="expression-rules">
<span id="expressions"></span><h2>Expression rules<a class="headerlink" href="#expression-rules" title="Permalink to this headline">¶</a></h2>
<p>So far, the rules as stated are not particularly restrictive, in that
all convex programs (disciplined or otherwise) typically adhere to them.
What distinguishes disciplined convex programming from more general
convex programming are the rules governing the construction of the
expressions used in objective functions and constraints.</p>
<p>Disciplined convex programming determines the curvature of scalar
expressions by recursively applying the following rules. While this list
may seem long, it is for the most part an enumeration of basic rules of
convex analysis for combining convex, concave, and affine forms: sums,
multiplication by scalars, and so forth.</p>
<ul class="simple">
<li>A valid constant expression is<ul>
<li>any well-formed Matlab expression that evaluates to a finite
value.</li>
</ul>
</li>
<li>A valid affine expression is<ul>
<li>a valid constant expression;</li>
<li>a declared variable;</li>
<li>a valid call to a function in the atom library with an affine
result;</li>
<li>the sum or difference of affine expressions;</li>
<li>the product of an affine expression and a constant.</li>
</ul>
</li>
<li>A valid convex expression is<ul>
<li>a valid constant or affine expression;</li>
<li>a valid call to a function in the atom library with a convex
result;</li>
<li>an affine scalar raised to a constant power <span class="math">\(p\geq 1\)</span>,
<p>Following standard practice in convex analysis, convex functions are
interpreted as <span class="math">\(+\infty\)</span> when the argument is outside the domain
of the function, and concave functions are interpreted as
<span class="math">\(-\infty\)</span> when the argument is outside its domain. In other words,
convex and concave functions in CVX are interpreted as their
<em>extended-valued extensions</em>.</p>
<p>This has the effect of automatically constraining the argument of a
function to be in the function’s domain. For example, if we form
<tt class="docutils literal"><span class="pre">sqrt(x+1)</span></tt> in a CVX specification, where <tt class="docutils literal"><span class="pre">x</span></tt> is a variable,
then <tt class="docutils literal"><span class="pre">x</span></tt> will automatically be constrained to be larger than or equal
to <span class="math">\(-1\)</span>. There is no need to add a separate constraint, <tt class="docutils literal"><span class="pre">x>=-1</span></tt>,
to enforce this.</p>
<p>Monotonicity of a function is determined in the extended sense, <em>i.e.</em>,
<em>including the values of the argument outside its domain</em>. For example,
<tt class="docutils literal"><span class="pre">sqrt(x)</span></tt> is determined to be nondecreasing since its value is
constant (<span class="math">\(-\infty\)</span>) for negative values of its argument; then
jumps <em>up</em> to <span class="math">\(0\)</span> for argument zero, and increases for positive
values of its argument.</p>
<p>CVX does <em>not</em> consider a function to be convex or concave if it is
so only over a portion of its domain, even if the argument is
constrained to lie in one of these portions. As an example, consider the
function <span class="math">\(1/x\)</span>. This function is convex for <span class="math">\(x>0\)</span>, and
concave for <span class="math">\(x<0\)</span>. But you can never write <tt class="docutils literal"><span class="pre">1/x</span></tt> in CVX
(unless <tt class="docutils literal"><span class="pre">x</span></tt> is constant), even if you have imposed a constraint such
as <tt class="docutils literal"><span class="pre">x>=1</span></tt>, which restricts <tt class="docutils literal"><span class="pre">x</span></tt> to lie in the convex portion of
function <span class="math">\(1/x\)</span>. You can use the CVX function <tt class="docutils literal"><span class="pre">inv_pos(x)</span></tt>,
defined as <span class="math">\(1/x\)</span> for <span class="math">\(x>0\)</span> and <span class="math">\(\infty\)</span> otherwise, for
the convex portion of <span class="math">\(1/x\)</span>; CVX recognizes this function as
convex and nonincreasing. In CVX, you can express the concave
portion of <span class="math">\(1/x\)</span>, where <span class="math">\(x\)</span> is negative, using
<tt class="docutils literal"><span class="pre">-inv_pos(-x)</span></tt>, which will be correctly recognized as concave and
nonincreasing.</p>
<p>For functions with multiple arguments, curvature is always considered
<em>jointly</em>, but monotonicity can be considered on an
<em>argument-by-argument</em> basis. For example, the function
\[\begin{split}f_{\text{quad\_over\_lin}}(x,y) = \begin{cases} |x|^2/y & y > 0 \\ +\infty & y\leq 0 \end{cases}\end{split}\]</div>
<p>is jointly convex in both <span class="math">\(x\)</span> and <span class="math">\(y\)</span>, but it is monotonic
(nonincreasing) only in <span class="math">\(y\)</span>.</p>
<p>Some functions are convex, concave, or affine only for a <em>subset</em> of its
arguments. For example, the function <tt class="docutils literal"><span class="pre">norm(x,p)</span></tt> where <tt class="docutils literal"><span class="pre">p</span> <span class="pre">\geq</span> <span class="pre">1</span></tt> is
convex only in its first argument. Whenever this function is used in a
CVX specification, then, the remaining arguments must be constant,
or CVX will issue an error message. Such arguments correspond to a
function’s parameters in mathematical terminology; <em>e.g.</em>,</p>
<p>So it seems fitting that we should refer to such arguments as
<em>parameters</em> in this context as well. Henceforth, whenever we speak of a
CVX function as being convex, concave, or affine, we will assume
that its parameters are known and have been given appropriate, constant
values.</p>
</div>
<div class="section" id="compositions">
<h2>Compositions<a class="headerlink" href="#compositions" title="Permalink to this headline">¶</a></h2>
<p>A basic rule of convex analysis is that convexity is closed under
composition with an affine mapping. This is part of the DCP ruleset as
well:</p>
<ul class="simple">
<li>A convex, concave, or affine function may accept an affine expression
(of compatible size) as an argument. The result is convex, concave,
or affine, respectively.</li>
</ul>
<p>For example, consider the function <tt class="docutils literal"><span class="pre">square(x)</span></tt>, which is provided in
the CVX atom library. This function squares its argument; <em>i.e.</em>, it
computes <tt class="docutils literal"><span class="pre">x.*x</span></tt>. (For array arguments, it squares each element
independently.) It is in the CVX atom library, and known to be
convex, provided its argument is real. So if <tt class="docutils literal"><span class="pre">x</span></tt> is a real variable of
dimension <span class="math">\(n\)</span>, <tt class="docutils literal"><span class="pre">a</span></tt> is a constant <span class="math">\(n\)</span>-vector, and <tt class="docutils literal"><span class="pre">b</span></tt> is
a constant, the expression</p>
<div class="highlight-none"><div class="highlight"><pre>square( a' * x + b )
</pre></div>
</div>
<p>is accepted by CVX, which knows that it is convex.</p>
<p>The affine composition rule above is a special case of a more
sophisticated composition rule, which we describe now. We consider a
function, of known curvature and monotonicity, that accepts multiple
arguments. For <em>convex</em> functions, the rules are:</p>
<ul class="simple">
<li>If the function is nondecreasing in an argument, that argument must
be convex.</li>
<li>If the function is nonincreasing in an argument, that argument must
be concave.</li>
<li>If the function is neither nondecreasing or nonincreasing in an
argument, that argument must be affine.</li>
</ul>
<p>If each argument of the function satisfies these rules, then the
expression is accepted by CVX, and is classified as convex. Recall
that a constant or affine expression is both convex and concave, so any
argument can be affine, including as a special case, constant.</p>
<p>The corresponding rules for a concave function are as follows:</p>
<ul class="simple">
<li>If the function is nondecreasing in an argument, that argument must
be concave.</li>
<li>If the function is nonincreasing in an argument, that argument must
be convex.</li>
<li>If the function is neither nondecreasing or nonincreasing in an
argument, that argument must be affine.</li>
</ul>
<p>In this case, the expression is accepted by CVX, and classified as
concave.</p>
<p>For more background on these composition rules, see <a class="reference external" href="http://www.stanford.edu/~boyd/cvxbook">Convex
Optimization</a>, Section 3.2.4.
In fact, with the exception of scalar quadratic expressions, the entire
DCP ruleset can be thought of as special cases of these six rules.</p>
<p>Let us examine some examples. The maximum function is convex and
nondecreasing in every argument, so it can accept any convex expressions
as arguments. For example, if <tt class="docutils literal"><span class="pre">x</span></tt> is a vector variable, then</p>
<div class="highlight-none"><div class="highlight"><pre>max( abs( x ) )
</pre></div>
</div>
<p>obeys the first of the six composition rules and is therefore accepted
by CVX, and classified as convex. As another example, consider the
sum function, which is both convex and concave (since it is affine), and
nondecreasing in each argument. Therefore the expressions</p>
<div class="highlight-none"><div class="highlight"><pre>sum( square( x ) )
sum( sqrt( x ) )
</pre></div>
</div>
<p>are recognized as valid in CVX, and classified as convex and
concave, respectively. The first one follows from the first rule for
convex functions; and the second one follows from the first rule for
concave functions.</p>
<p>Most people who know basic convex analysis like to think of these
examples in terms of the more specific rules: a maximum of convex
functions is convex, and a sum of convex (concave) functions is convex
(concave). But these rules are just special cases of the general
composition rules above. Some other well known basic rules that follow
from the general composition rules are:</p>
<ul class="simple">
<li>a nonnegative multiple of a convex (concave) function is convex
(concave);</li>
<li>a nonpositive multiple of a convex (concave) function is concave
(convex).</li>
</ul>
<p>Now we consider a more complex example in depth. Suppose <tt class="docutils literal"><span class="pre">x</span></tt> is a
vector variable, and <tt class="docutils literal"><span class="pre">A</span></tt>, <tt class="docutils literal"><span class="pre">b</span></tt>, and <tt class="docutils literal"><span class="pre">f</span></tt> are constants with
appropriate dimensions. CVX recognizes the expression</p>
<p>as concave. Consider the term <tt class="docutils literal"><span class="pre">sqrt(f'*x)</span></tt>. CVX recognizes that
<tt class="docutils literal"><span class="pre">sqrt</span></tt> is concave and <tt class="docutils literal"><span class="pre">f'*x</span></tt> is affine, so it concludes that
<tt class="docutils literal"><span class="pre">sqrt(f'*x)</span></tt> is concave. Now consider the second term
<tt class="docutils literal"><span class="pre">min(4,1.3-norm(A*x-b))</span></tt>. CVX recognizes that <tt class="docutils literal"><span class="pre">min</span></tt> is concave
and nondecreasing, so it can accept concave arguments. CVX
recognizes that <tt class="docutils literal"><span class="pre">1.3-norm(A*x-b)</span></tt> is concave, since it is the
difference of a constant and a convex function. So CVX concludes
that the second term is also concave. The whole expression is then
recognized as concave, since it is the sum of two concave functions.</p>
<p>The composition rules are sufficient but not necessary for the
classification to be correct, so some expressions which are in fact
convex or concave will fail to satisfy them, and so will be rejected by
CVX. For example, if <tt class="docutils literal"><span class="pre">x</span></tt> is a vector variable, the expression</p>
<div class="highlight-none"><div class="highlight"><pre>sqrt( sum( square( x ) ) )
</pre></div>
</div>
<p>is rejected by CVX, because there is no rule governing the
composition of a concave nondecreasing function with a convex function.
Of course, the workaround is simple in this case: use <tt class="docutils literal"><span class="pre">norm(</span> <span class="pre">x</span> <span class="pre">)</span></tt>
instead, since <tt class="docutils literal"><span class="pre">norm</span></tt> is in the atom library and known by CVX to
<h2>Monotonicity in nonlinear compositions<a class="headerlink" href="#monotonicity-in-nonlinear-compositions" title="Permalink to this headline">¶</a></h2>
<p>Monotonicity is a critical aspect of the rules for nonlinear
compositions. This has some consequences that are not so obvious, as we
shall demonstrate here by example. Consider the expression</p>
<div class="highlight-none"><div class="highlight"><pre>square( square( x ) + 1 )
</pre></div>
</div>
<p>where <tt class="docutils literal"><span class="pre">x</span></tt> is a scalar variable. This expression is in fact convex,
since <span class="math">\((x^2+1)^2 = x^4+2x^2+1\)</span> is convex. But CVX will reject
the expression, because the outer <tt class="docutils literal"><span class="pre">square</span></tt> cannot accept a convex
argument. Indeed, the square of a convex function is not, in general,
convex: for example, <span class="math">\((x^2-1)^2 = x^4-2x^2+1\)</span> is not convex.</p>
<p>There are several ways to modify the expression above to comply with the
ruleset. One way is to write it as <tt class="docutils literal"><span class="pre">x^4</span> <span class="pre">+</span> <span class="pre">2*x^2</span> <span class="pre">+</span> <span class="pre">1</span></tt>, which CVX
recognizes as convex, since CVX allows positive even integer powers
using the <tt class="docutils literal"><span class="pre">^</span></tt> operator. (Note that the same technique, applied to the
function <span class="math">\((x^2-1)^2\)</span>, will fail, since its second term is
concave.)</p>
<p>Another approach is to use the alternate outer function <tt class="docutils literal"><span class="pre">square_pos</span></tt>,
included in the CVX library, which represents the function
and <tt class="docutils literal"><span class="pre">square_pos</span></tt> coincide when their arguments are nonnegative. But
<tt class="docutils literal"><span class="pre">square_pos</span></tt> is nondecreasing, so it can accept a convex argument.
Thus, the expression</p>
<div class="highlight-none"><div class="highlight"><pre>square_pos( square( x ) + 1 )
</pre></div>
</div>
<p>is mathematically equivalent to the rejected version above (since the
argument to the outer function is always positive), but it satisfies the
DCP ruleset and is therefore accepted by CVX.</p>
<p>This is the reason several functions in the CVX atom library come in
two forms: the “natural” form, and one that is modified in such a way
that it is monotonic, and can therefore be used in compositions. Other
such “monotonic extensions” include <tt class="docutils literal"><span class="pre">sum_square_pos</span></tt> and
<tt class="docutils literal"><span class="pre">quad_pos_over_lin</span></tt>. If you are implementing a new function yourself,
you might wish to consider if a monotonic extension of that function
would also be useful.</p>
</div>
<div class="section" id="scalar-quadratic-forms">
<span id="quadforms"></span><h2>Scalar quadratic forms<a class="headerlink" href="#scalar-quadratic-forms" title="Permalink to this headline">¶</a></h2>
<p>In its pure form, the DCP ruleset forbids even the use of simple
quadratic expressions such as <tt class="docutils literal"><span class="pre">x</span> <span class="pre">*</span> <span class="pre">x</span></tt> (assuming <tt class="docutils literal"><span class="pre">x</span></tt> is a scalar
variable). For practical reasons, we have chosen to make an exception to
the ruleset to allow for the recognition of certain specific quadratic
forms that map directly to certain convex quadratic functions (or their
<p>CVX detects the quadratic expressions such as those on the left
above, and determines whether or not they are convex or concave; and if
so, translates them to an equivalent function call, such as those on the
right above.</p>
<p>CVX examines each <em>single</em> product of affine expressions, and each
<em>single</em> squaring of an affine expression, checking for convexity; it
will not check, for example, sums of products of affine expressions. For
example, given scalar variables <tt class="docutils literal"><span class="pre">x</span></tt> and <tt class="docutils literal"><span class="pre">y</span></tt>, the expression</p>
<div class="highlight-none"><div class="highlight"><pre>x ^ 2 + 2 * x * y + y ^2
</pre></div>
</div>
<p>will cause an error in CVX, because the second of the three terms
<tt class="docutils literal"><span class="pre">2</span> <span class="pre">*</span> <span class="pre">x</span> <span class="pre">*</span> <span class="pre">y</span></tt>, is neither convex nor concave. But the equivalent
expressions</p>
<div class="highlight-none"><div class="highlight"><pre>( x + y ) ^ 2
( x + y ) * ( x + y )
</pre></div>
</div>
<p>will be accepted.</p>
<p>CVX actually completes the square when it comes
across a scalar quadratic form, so the form need not be symmetric. For
example, if <tt class="docutils literal"><span class="pre">z</span></tt> is a vector variable, <tt class="docutils literal"><span class="pre">a</span></tt>, <tt class="docutils literal"><span class="pre">b</span></tt> are constants, and
<tt class="docutils literal"><span class="pre">Q</span></tt> is positive definite, then</p>
<div class="highlight-none"><div class="highlight"><pre>( z + a )' * Q * ( z + b )
</pre></div>
</div>
<p>will be recognized as convex. Once a quadratic form has been verified by
CVX, it can be freely used in any way that a normal convex or
concave expression can be, as described in <a class="reference internal" href="#expressions"><em>Expression rules</em></a>.</p>
<p>Quadratic forms should actually be used <em>less frequently</em> in disciplined
convex programming than in a more traditional mathematical programming
framework, where a quadratic form is often a smooth substitute for a
nonsmooth form that one truly wishes to use. In CVX, such
substitutions are rarely necessary, because of its support for nonsmooth
functions. For example, the constraint</p>
<div class="highlight-none"><div class="highlight"><pre>sum( ( A * x - b ) .^ 2 ) <= 1
</pre></div>
</div>
<p>is equivalently represented using the Euclidean norm:</p>
<div class="highlight-none"><div class="highlight"><pre>norm( A * x - b ) <= 1
</pre></div>
</div>
<p>With modern solvers, the second form is more naturally represented using
a second-order cone constraint—so the second form may actually be more
efficient. In fact, in our experience, the non-squared form will often
be handled more accurately. So we strongly encourage you to re-evaluate
the use of quadratic forms in your models, in light of the new
capabilities afforded by disciplined convex programming.</p>