extoperators.htm

optimization toolbox

    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 dimension of
			<b>P</b>. This concave function, called <b>geomean</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 &lt; D*D&#39;),-geomean(P));</pre>
					</td>
				</tr>
			</table>
			<p>The command can be applied also on positive vectors, and will then 
			model the geometric mean of the elements. We can use this to find the analytic 
			center of a set of linear inequalities (note that this is absolutely 
			not the recommended way to compute the analytic center.)</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([],-geomean(b-A*x)); % Maximize product of elements in b-Ax, s.t Ax &lt; b</pre>
					</td>
				</tr>
			</table>
			<p>Rather advanced constructions are possible, and YALMIP will try derive 
			an equivalent convex model.</p>
			<table cellpadding="10" width="100%" id="table3">
				<tr>
					<td class="xmpcode">
					<pre>sdpvar x y z
F = set(max(1,x)+max(y^2,z) &lt; 3)+set(max(1,-min(x,y)) &lt; 5)+set(norm([x;y],2) &lt; z);
sol = solvesdp(F,max(x,z)-min(y,z)-z);</pre>
					</td>
				</tr>
			</table>
			<h3><a name="polynomials"></a>Polynomial and sigmonial expressions</h3>
			<p>By default, polynomial expressions (except quadratics) are not analyzed 
			with respect to convexity and conversion to a conic model is not performed. 
			Hence, if you add a constraint such as <code>set(x^4 + y^8-x^0.5 &lt; 10)</code>, 
			YALMIP may complain about convexity, even though we can see that the 
			expression is convex and can be represented using conic constraints. 
			More importantly, YALMIP will not try to derive an equivalent conic 
			model. However, by using the command <b>cpower</b> instead, rational 
			powers can be used. </p>
			<p>To illustrate this, first note the difference between a monomial 
			generated using overloaded power and a variable generated <b>cpower</b>.</p>
			<table cellpadding="10" width="100%" id="table4">
				<tr>
					<td class="xmpcode">
					<pre>sdpvar x
x^4
<font color="#000000">Polynomial scalar (real, homogeneous, 1 variable)</font>
cpower(x,4)
<font color="#000000">Linear scalar (real, derived, 1 variable)</font></pre>
					</td>
				</tr>
			</table>
			<p>The property <i>derived</i> indicates that YALMIP will try to replace the 
			variable with its epigraph formulation when the problem is solved. Working 
			with these convexity-aware monomials is no different than usual.</p>
			<table cellpadding="10" width="100%" id="table5">
				<tr>
					<td class="xmpcode">
					<pre>sdpvar x y
F = set(cpower(x,4) + cpower(y,4) &lt; 10) + set(cpower(x,2/3) + cpower(y,2/3) &gt; 1);
plot(F,[x y]);</pre>
					</td>
				</tr>
			</table>
			<p>Note that when you plot sets with constraints involving nonlinear 
			operators and polynomials, it is recommended that you specify the variables 
			of interest in the second argument (YALMIP may otherwise plot the set 
			with respect to auxiliary variables introduced during the construction 
			of the conic model.)</p>
			<p>Do not use these operators unless you really need them. The conic 
			representation of rational powers easily grow large.</p>
			<h3>Limitations</h3>
			<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 problems above are all convex, but not this problem below, 
			due to the way <b>min</b> enters 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) &lt; 3)+set(max(1,<font color="#FF0000">min</font>(x,y)) &lt; 5)+set(norm([x;y],2) &lt; z);
sol = solvesdp(F,max(x,z)-min(y,z)-z);
sol.info

<font color="#000000">ans =
 Convexity check failed (Expected convex function in constraint #2 at level 2)</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) &lt; 3);
sol = solvesdp(F,-norm([x;y]));
sol.info
<font color="#000000">
ans =
 Convexity check failed (Expected concave function in objective at level 1)</font></pre>
					</td>
				</tr>
			</table>
			<p>This following problem is however convex, but convexity propagation 
			fails.</p>
			<table cellpadding="10" width="100%" id="table6">
				<tr>
					<td class="xmpcode">
					<pre>sdpvar x
sol = solvesdp([],norm(max([1 1-x 1+x])))
sol.info
<font color="#000000">
ans =
 Convexity check failed (Monotonicity required at objective at level 1)</font></pre>
					</td>
				</tr>
			</table>
			<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%" id="table8">
				<tr>
					<td class="xmpcode">
					<pre>sdpvar x y
sol = solvesdp([],norm([x;y])^2);
sol.info

<font color="#000000">ans =
 Convexity check failed (Operator in polynomial in objective)</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%" id="table10">
				<tr>
					<td class="xmpcode">
					<pre>sdpvar x y
sol = 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. </p>
			<h3><a name="milp"></a>Mixed integer models</h3>
			<p>In some cases when the convexity analysis fails, it is possible 
			to tell YALMIP to switch from a graph based approach to a mixed 
			integer model based approach. In other words, if no graph model can 
			be derived, YALMIP introduces integer variables to model the 
			operators. This is currently implemented for <b>min</b>, <b>
			max</b>, <b>abs</b> and linear <b>norm</b> for real arguments. By default, this feature 
			is not invoked, but can be activated by <code>sdpsettings('allowmilp',1)</code>.</p>
			<p>Consider the following simple example which fails due to the 
			non-convex use of the convex <b>abs</b> operator</p>
			<table cellpadding="10" width="100%" id="table12">
				<tr>
					<td class="xmpcode">
					<pre>sdpvar x y
F = set(abs(abs(x+1)+3) &gt; y)+set(0&lt;x&lt;3);
sol = solvesdp(F,-y);
sol.info
<font color="#000000"> Convexity check failed (Expected concave function in constraint #1 at level 1)</font></pre>
					</td>
				</tr>
			</table>
			<p>By turning on the mixed integer fall back model, a mixed integer 
			LP is generated and the problem is easily solved.</p>
			<table cellpadding="10" width="100%" id="table13">
				<tr>
					<td class="xmpcode">
					<pre>sdpvar x y
F = set(abs(abs(x+1)+3) &gt; y)+set(0&lt;x&lt;3);
sol = solvesdp(F,-y,sdpsettings('allowmilp',1));
double([x y])
<font color="#000000">ans =
    3.0000    7.0000</font></pre>
					</td>
				</tr>
			</table>
			<p>If you know that your model is non-convex and will require a 
			mixed integer model, you can bypass the initial attempt to generate 
			the graph model by using <code>sdpsettings('allowmilp',2)</code>.</p>
			<h3><a name="evaluationbased"></a>Evaluation based nonlinear operators</h3>
			<p>YALMIP now also supports experimental support for general 
			convex/concave functions that cannot be modelled using conic 
			representations. The main difference when working with these 
			operators is that the problem always requires a general nonlinear 
			solver to solved, such as<a href="solvers.htm#fmincon"> fmincon</a>. 
			All convexity analysis is still performed tough.</p>
			<table cellpadding="10" width="100%" id="table14">
				<tr>
					<td class="xmpcode">
					<pre>sdpvar x
solvesdp(set(exp(2*x + 1) &lt; 1),-x,sdpsettings('solver','fmincon'));
double(x)
<font color="#000000">ans =
   -0.5000</font></pre>
					<pre>double(exp(2*x + 1))
<font color="#000000">ans =
     1</font></pre>
					</td>
				</tr>
			</table>
			<p>Note that this feature still is very limited and experimental. 
			Too see how you can add our own function, see the
			<a href="#entropy">example for scalar entropy</a>. </p>
			<p>As a word of caution, note that<a href="solvers.htm#fmincon"> fmincon</a> 
			performs pretty bad on problems with functions that aren't defined 
			everywhere, such as logarithms. Hence, solving problem involving 
			these functions can easily lead to problems. It is highly 
			recommended to at least provide a feasible solution, or even better, 
			to use the inverse operator to formulate the problem. Consider the 
			following trivial example of finding the analytic center of a unit 
			cube centered at the point (3,3,3)</p>
			<table cellpadding="10" width="100%" id="table16">
				<tr>
					<td class="xmpcode">
					<pre>x = sdpvar(3,1);
p = [1-(x-3);(x-3)+1]

% Not recommended
solvesdp([],-sum(log(p)));

% Better
assign(x,[3.1;3.2;3.3]);
solvesdp([],-sum(log(p)),sdpsettings('usex0',1));

% Best (well, adding initials on x and t would be even better)
t = sdpvar(3,1);
solvesdp(exp(t) &lt; p ,-sum(t));</pre>
					<pre>
</pre>
					</td>
				</tr>
			</table>