📄 extoperators.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Language" content="en-us">
<title>YALMIP Example : Linear regression</title>
<meta http-equiv="Content-Type" content="text/html; charset=windows-1251">
<meta content="Microsoft FrontPage 6.0" name="GENERATOR">
<meta name="ProgId" content="FrontPage.Editor.Document">
<link href="yalmip.css" type="text/css" rel="stylesheet">
<base target="_self">
</head>
<body leftmargin="0" topmargin="0">
<div align="left">
<table border="0" cellpadding="4" cellspacing="3" style="border-collapse: collapse" bordercolor="#000000" width="100%" align="left" height="100%">
<tr>
<td width="100%" align="left" height="100%" valign="top">
<h2>Nonlinear operators</h2>
<hr noshade size="1" color="#000000">
<p>YALMIP supports modeling of nonlinear, often non-differentiable,
operators that typically occur in convex programming. Nine simple operators
are currently supported: <b>min</b>, <b>max</b>, <b>abs</b>, <b>sqrt</b>,
<b>norm</b>, <b>sumk</b>, <b>sumabsk</b>, <b>geomean</b> and <b>cpower</b>,
and users can easily add their own (<a href="#operatorformat">see</a> the end of this page). The operators
can be used intuitively, and YALMIP will automatically try to find out
if they are used in a way that enables a convex representation. Although
this can simplify the modeling phase significantly in some cases, it
is recommended not to use these operators unless you know how to model
them by your self using epigraphs and composition rules of convex and
concave functions, why and when it can be done etc. The text-book
<a href="readmore.htm#BOYDVAN2003">[S. Boyd and L. Vandenberghe]</a>
should be a suitable introduction for the beginner. </p>
<p>In addition to modeling convex and concave operators and perform
automatic analysis and derivation of equivalent conic programs, YALMIP
also uses the nonlinear operator framework for implementing
<a href="logic.htm">logic expression</a> involving <b>or</b> and <b>
and</b>, and in the same vein but on a higher level, to handle piecewise
functions in <a href="reference.htm#pwf">pwf</a>.</p>
<p>The nonlinear operator framework was initially implemented for
functions that can be modelled rigorously using conic constraints
and additional variables. However, there are many functions that
cannot be exactly modelled using conic constraints, such as
exponential functions and logarithms, but are convex or
concave, and of course can be analyzed in terms of convexity
preserving operations. These function are supported in a framework
called evaluation based nonlinear operators. The models using these
general convex functions will be analysed for convexity, but the
resulting model will be a problem that only can be solved using
a general nonlinear solver, such as <a href="solvers.htm#fmincon">
fmincon</a>. See <a href="#evaluationbased">evaluation based nonlinear operators</a>. Note that
this extension still is experimental and not intended for large
problems.</p>
<h3><a name="propagation"></a>Convexity analysis in 10 lines</h3>
<p>Without going into theoretical details, the convexity analysis is
based on epi- and hypograph formulations, and composition rules. For
the compound expression <b>f = h(g(x))</b>, it holds that (For
simplicity, we write increasing, decreasing, convex and concave, but
the correct notation would be nondecreasing, nonincreasing, convex
or affine and concave or affine. This notation us used throughout
this manual and inside YALMIP)</p>
<div align="center">
<table border="1" bgcolor="#EEEEEE" bordercolor="#000000" id="table1">
<tr>
<td bordercolorlight="#FFFFFF" bordercolordark="#FFFFFF">
<b>f</b> is <i>convex</i> if <b>h</b> is <i>convex</i> and
<i>increasing</i> and <b>g</b> is <i>convex</i><br>
<b>f</b> is <i>convex</i> if <b>h</b> is <i>convex</i> and
<i>decreasing</i> and <b>g</b> is <i>concave</i> <br>
<b>f</b> is <i>concave</i> if <b>h</b> is <i>concave</i>
and <i>increasing</i> and <b>g</b> is <i>concave</i>
<br>
<b>f</b> is <i>concave</i> if <b>h</b> is <i>concave</i>
and <i>decreasing</i> and <b>g</b> is <i>convex</i></td>
</tr>
</table>
</div>
<p>Based on this information, it is possible to recursively analyze
convexity of a complex expression involving convex and concave functions.
When <a href="reference.htm#solvesdp">solvesdp</a> is called, YALMIP
checks the convexity of objective function and constraints by using
information about the properties of the operators. If YALMIP manage
to prove convexity, graph formulations of the operators are automatically
introduced. This means that the operator is replaced with a graph, i.e.,
a set of constraints. </p>
<div align="center">
<table border="1" bgcolor="#EEEEEE" bordercolor="#000000" id="table2">
<tr>
<td bordercolorlight="#FFFFFF" bordercolordark="#FFFFFF">
<b>epigraph: t</b> represents convex function <b>f(x)</b>
: replace with <b>t<font face="Tahoma">≥</font>f(x)</b><br>
<b>hypograph</b>: <b>t</b> represents concave function <b>
f(x)</b> : replace with <b>t<font face="Tahoma">≤</font>f(x)</b></td>
</tr>
</table>
</div>
<p align="left">Of course, in order for this to be useful, the epigraph
representation has to be represented using standard constraints, such
as conic constraints.</p>
<h3 align="left">The operators</h3>
<p align="left">The operators defined in the current release are
described in the table below. This information might be useful to
understand how and when YALMIP can derive convexity.</p>
<div align="center">
<table border="1" width="86%" id="table7" bordercolor="#000000" style="border-collapse: collapse" bgcolor="#EEEEEE">
<tr>
<td>
<p align="center"><b>Name</b></td>
<td>
<p align="center"><b>Convex/Concave</b></td>
<td>
<p align="center"><b>Monotinicity</b></td>
<td width="468">
<p align="center"><b>Comments</b></td>
</tr>
<tr>
<td align="center">abs</td>
<td bgcolor="#FFFFFF" align="center">convex</td>
<td bgcolor="#FFFFFF" align="center">none</td>
<td width="468" bgcolor="#FFFFFF" height="31"> </td>
</tr>
<tr>
<td align="center">min</td>
<td bgcolor="#FFFFFF" align="center">concave</td>
<td bgcolor="#FFFFFF" align="center">increasing</td>
<td width="468" bgcolor="#FFFFFF"> </td>
</tr>
<tr>
<td align="center">max</td>
<td bgcolor="#FFFFFF" align="center">convex</td>
<td bgcolor="#FFFFFF" align="center">increasing</td>
<td width="468" bgcolor="#FFFFFF"> </td>
</tr>
<tr>
<td align="center">norm</td>
<td bgcolor="#FFFFFF" align="center">convex</td>
<td bgcolor="#FFFFFF" align="center">none</td>
<td width="468" bgcolor="#FFFFFF">All standard norms (1,2, inf and Frobenius) can be used
(applicable on both vectors and matrices.)</td>
</tr>
<tr>
<td align="center">sumk</td>
<td bgcolor="#FFFFFF" align="center">convex</td>
<td bgcolor="#FFFFFF" align="center">See comment</td>
<td width="468" bgcolor="#FFFFFF">Defines the sum of the
k largest elements of a vector, or the sum of the k
largest eigenvalues of a symmetric matrix. Increasing
for vector arguments, no monotinicity defined for
eigenvalue operator.</td>
</tr>
<tr>
<td align="center">sumabsk</td>
<td bgcolor="#FFFFFF" align="center">convex</td>
<td bgcolor="#FFFFFF" align="center">none</td>
<td width="468" bgcolor="#FFFFFF">Defines the sum of the
k largest absolute value elements of a vector, or the
sum of the k largest absolute value eigenvalues of a
symmetric matrix. </td>
</tr>
<tr>
<td align="center">geomean</td>
<td bgcolor="#FFFFFF" align="center">concave</td>
<td bgcolor="#FFFFFF" align="center">See comment</td>
<td width="468" bgcolor="#FFFFFF">For vector arguments, the operator is increasing. For
symmetric matrix argument, the operator is defined as the
geometric mean of the eigenvalues. No monotinicity
defined for eigenvalue operator</td>
</tr>
<tr>
<td align="center">cpower</td>
<td bgcolor="#FFFFFF" align="center">See comment</td>
<td bgcolor="#FFFFFF" align="center">See comment</td>
<td width="468" bgcolor="#FFFFFF">Convexity-aware
version of power. For negative powers, the operator is convex and decreasing.
For positive powers less than one, the operator is concave
and increasing. Positive powers larger than 1 gives a convex
increasing operator.</td>
</tr>
<tr>
<td align="center">sqrt</td>
<td bgcolor="#FFFFFF" align="center">concave</td>
<td bgcolor="#FFFFFF" align="center">increasing</td>
<td width="468" bgcolor="#FFFFFF">Short for
cpower(x,0.5)</td>
</tr>
</table>
</div>
<h3>Standard use</h3>
<p>Consider once again the <a href="linearregression.htm">linear regression
problem</a>.</p>
<table cellpadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>a = [1 2 3 4 5 6]';
t = (0:0.2:2*pi)';
x = [sin(t) sin(2*t) sin(3*t) sin(4*t) sin(5*t) sin(6*t)];
y = x*a+(-4+8*rand(length(x),1));
a_hat = sdpvar(6,1);
residuals = y-x*a_hat;</pre>
</td>
</tr>
</table>
<p>Using <b>abs</b> and <b>max</b>, we can easily solve the L<sub>1</sub>
and the L<sub>∞</sub> problem (Note that the <b>abs</b> operator currently
has performance issues and should be avoided for large arguments. Moreover, explicitly creating
absolute values when minimizing the L<sub>∞</sub> error is
unnecessarily complicated).
</p>
<table cellpadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>solvesdp([],sum(abs(residuals)));
a_L1 = double(a_hat)
solvesdp([],max(abs(residuals)));
a_Linf = double(a_hat)</pre>
</td>
</tr>
</table>
<p>YALMIP automatically concludes that the objective functions can be
modeled using some additional linear inequalities, adds these, and solves
the problems. We can simplify the code even more by using the <b>norm</b>
operator (this is much faster for large-scale problems due to implementation
issues in YALMIP). Here we also compute the least-squares solution (note
that this norm will generate a second-order cone constraint).</p>
<table cellpadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>solvesdp([],norm(residuals,1));
a_L1 = double(a_hat)
solvesdp([],norm(residuals,2));
a_L2 = double(a_hat)
solvesdp([],norm(residuals,inf));
a_Linf = double(a_hat)</pre>
</td>
</tr>
</table>
<p>The following piece of code shows how we easily can solve a regularized
problem.</p>
<table cellpadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>solvesdp([],1e-3*norm(a_hat,2)+norm(residuals,inf));
a_regLinf = double(a_hat)</pre>
</td>
</tr>
</table>
<p>The <b>norm</b> operator is used exactly as the built-in norm function
in MATLAB, both for vectors and matrices. Hence it can be used also
to minimize the largest singular value (2-norm in matrix case), or the
Frobenious norm of a matrix.</p>
<p>The <code>double</code> command of-course applies also to the nonlinear
operators (<b>double</b>(<b>OPERATOR</b>(<b>X</b>)) returns <b>OPERATOR</b>(<b>double</b>(<b>X</b>)).</p>
<table cellpadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>double(1e-3*norm(a_hat,2)+norm(residuals,inf))
<font color="#000000">ans =
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -