📄 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>A recent addition to YALMIP is simplified modeling of nonlinear,
often non-differentiable, operators that typically occur in convex
programming. Six operators are
currently supported: <b>min</b>, <b>max</b>, <b>abs</b>, <b>norm</b>,
<b>sumk</b>, <b>sumabsk</b> and <b>detinv</b>.
These operators can be used rather 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, 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>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.
Moreover, explicitly creating absolute values when minimizing the L<sub>∞</sub>
error is not needed). </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 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 =
3.1175</font></pre>
</td>
</tr>
</table>
<p><a name="geomean2"></a>A construction useful for maximizing determinants of
positive definite matrices is
the function <b>(det P)<sup>1/m</sup></b>, for positive
definite matrix P, where <b>m</b> is the
smallest power of 2 larger than or equal to the dimension of <b>P</b> (hence,
for matrices with dimension equal to a power of two, the function gives
the geometric mean of the eigenvalues of <b>P</b>). This
concave function, called <b>geomean2</b> in YALMIP, is
supported as an extended operator. Note that the positive
semidefiniteness constraint on <b>P</b> is added
automatically by YALMIP.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>D = randn(5,5);
P = sdpvar(5,5);
solvesdp(set(P < D*D'),-geomean2(P));</pre>
</td>
</tr>
</table>
<p>The command can be applied also on positive vectors,
and will then model the product of the elements. We can
use this to find the analytic center of a set of linear
inequalities.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>A = randn(15,2);
b = rand(15,1)*5;</pre>
<pre>x = sdpvar(2,1);
solvesdp([],-geomean2(b-A*x)); % Maximize product of elements in b-Ax, s.t Ax < b</pre>
</td>
</tr>
</table>
<h3>Advanced use</h3>
<p>Rather advanced constructions are possible, and YALMIP
will try derive an equivalent convex model.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>sdpvar x y z
F = set(max(1,x)+max(y^2,z) < 3)+set(max(1,-min(x,y)) < 5)+set(norm([x;y],2) < z);
sol = solvesdp(F,max(x,z)-min(y,z)-z);</pre>
</td>
</tr>
</table>
<p>If the convexity propagation fails, an error will be issued (error
code 14). Note
that this does not imply that the model is nonconvex, but only
means that the simple sufficient conditions used for checking
convexity were violated. Failure is however typically an indication
of a bad model, and most often due to an actual nonconvex part in the
model. The problem above is convex, but not this problem below, due
to the use of the minimizer in the constraint.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>sdpvar x y z
F = set(max(1,x)+max(y^2,z) < 3)+set(max(1,<font color="#FF0000">min</font>(x,y)) < 5)+set(norm([x;y],2) < z);
sol = solvesdp(F,max(x,z)-min(y,z)-z);
sol.info
<font color="#000000">ans =
Convexity propagation failed (YALMIP)</font></pre>
</td>
</tr>
</table>
<p>In the same sense, this problem fails due to a
nonconvex objective function.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>sdpvar x y z
F = set(max(1,x)+max(y^2,z) < 3);
sol = solvesdp(F,-norm([x;y]));
sol.info
<font color="#000000">
ans =
Convexity propagation failed (YALMIP)</font></pre>
</td>
</tr>
</table>
<h3>Adding new operators</h3>
<p>If you want to add your own operator, all you need to
do is to create 1 file. This file should be able to return
the numerical value of the operator for a numerical input,
and return the epigraph (or hypograph) of the
operator when the first input is <code>'graph'</code>. As an example, the following file implements the nonlinear operator
<b>tracenorm</b>. This convex operator returns <b>
sum(svd(X))</b> for matrices
<b>X</b>. This value can also be described as the
minimizing argument of the optimization problem <b>min<sub>t,A,B</sub>
t</b> subject to <b>set([A X;X' B] > 0) +
set(trace(A)+trace(B) < 2*t)</b>.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>function varargout = tracenorm(varargin)
switch class(varargin{1})
case 'double' % What is the <font color="#FF0000">numerical value</font> of this argument (needed for displays etc)
varargout{1} = sum(svd(varargin{1}));
case 'char' % YALMIP send 'graph' when it wants the epigraph or hypograph
if isequal(varargin{1},'graph')
t = varargin{2}; % Second arg is the extended operator variable
X = varargin{3}; % Third arg and above are the args user used when defining t.
A = sdpvar(size(X,1));
B = sdpvar(size(X,2));
F = set([A X;X' B] > 0) + set(trace(A)+trace(B) < 2*t);
varargout{1} = F; % <font color="#FF0000">Epigraph model</font>
varargout{2} = 1; % <font color="#FF0000">Convex operator (-1 for concave)</font>
else
end
case 'sdpvar' % Always the same.
varargout{1} = yalmip('addextendedvariable',mfilename,varargin{:});
otherwise
end</pre>
</td>
</tr>
</table>
<p>The function <code>sumk.m</code>
in YALMIP is implemented using this framework and serve
as good examples. The overloaded operator <code>norm.m</code> is also
defined
using this method, but is a bit more involved, since it
supports different norms.</p>
<h3>Limitations</h3>
<p>The described operators cannot be used in polynomial
expressions in the current implementation. The following
problem is trivially convex but fails.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>sdpvar x y
sol = solvesdp([],norm([x;y])^2);
sol.info
<font color="#000000">ans =
Convexity propagation failed (YALMIP)</font></pre>
</td>
</tr>
</table>
<p>The following constructions is convex but fails.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>sdpvar x y
solvesdp([],norm([x;max(1,x)]));
sol.info
<font color="#000000">ans =
Convexity propagation failed (YALMIP)</font></pre>
</td>
</tr>
</table>
<p>Another limitation is that the operators not are
allowed in cone and semidefinite constraints.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>sdpvar x y
solvesdp(set(cone(max(x,y,1),2)),x+y);
sol.info
<font color="#000000">ans =
Convexity propagation failed (YALMIP)</font></pre>
</td>
</tr>
</table>
<p>In practice, these limitations should not pose a major
problem. A better model is possible (and probably
recommended) in most cases if these situations occur. Note
also the convexity checking algorithm is experimental
and very simple,, and will most likely be improved upon in
a future release.</td>
</tr>
</table>
</div>
</body>
</html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -