Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

extoperators.htm @ 37

Last change on this file since 37 was 37, checked in by (none), 14 years ago
Added original make3d
File size: 33.5 KB

Line
1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
2	<html>
3
4	<head>
5	<meta http-equiv="Content-Language" content="en-us">
6	<title>YALMIP Example : Linear regression</title>
7	<meta http-equiv="Content-Type" content="text/html; charset=windows-1251">
8	<meta content="Microsoft FrontPage 6.0" name="GENERATOR">
9	<meta name="ProgId" content="FrontPage.Editor.Document">
10	<link href="yalmip.css" type="text/css" rel="stylesheet">
11	<base target="_self">
12	</head>
13
14	<body leftmargin="0" topmargin="0">
15
16	<div align="left">
17	<table border="0" cellpadding="4" cellspacing="3" style="border-collapse: collapse" bordercolor="#000000" width="100%" align="left" height="100%">
18	<tr>
19	<td width="100%" align="left" height="100%" valign="top">
20	<h2>Nonlinear operators</h2>
21	<hr noshade size="1" color="#000000">
22	<p>YALMIP supports modeling of nonlinear, often non-differentiable,
23	operators that typically occur in convex programming. Nine simple operators
24	are currently supported: <b>min</b>, <b>max</b>, <b>abs</b>, <b>sqrt</b>,
25	<b>norm</b>, <b>sumk</b>, <b>sumabsk</b>, <b>geomean</b> and <b>cpower</b>,
26	and users can easily add their own (<a href="#operatorformat">see</a> the end of this page). The operators
27	can be used intuitively, and YALMIP will automatically try to find out
28	if they are used in a way that enables a convex representation. Although
29	this can simplify the modeling phase significantly in some cases, it
30	is recommended not to use these operators unless you know how to model
31	them by your self using epigraphs and composition rules of convex and
32	concave functions, why and when it can be done etc. The text-book
33	<a href="readmore.htm#BOYDVAN2003">[S. Boyd and L. Vandenberghe]</a>
34	should be a suitable introduction for the beginner. </p>
35	<p>In addition to modeling convex and concave operators and perform
36	automatic analysis and derivation of equivalent conic programs, YALMIP
37	also uses the nonlinear operator framework for implementing
38	<a href="logic.htm">logic expression</a> involving <b>or</b> and <b>
39	and</b>, and in the same vein but on a higher level, to handle piecewise
40	functions in <a href="reference.htm#pwf">pwf</a>.</p>
41	<p>The nonlinear operator framework was initially implemented for
42	functions that can be modelled rigorously using conic constraints
43	and additional variables. However, there are many functions that
44	cannot be exactly modelled using conic constraints, such as
45	exponential functions and logarithms, but are convex or
46	concave, and of course can be analyzed in terms of convexity
47	preserving operations. These function are supported in a framework
48	called evaluation based nonlinear operators. The models using these
49	general convex functions will be analysed for convexity, but the
50	resulting model will be a problem that only can be solved using
51	a general nonlinear solver, such as <a href="solvers.htm#fmincon">
52	fmincon</a>. See <a href="#evaluationbased">evaluation based nonlinear operators</a>. Note that
53	this extension still is experimental and not intended for large
54	problems.</p>
55	<h3><a name="propagation"></a>Convexity analysis in 10 lines</h3>
56	<p>Without going into theoretical details, the convexity analysis is
57	based on epi- and hypograph formulations, and composition rules. For
58	the compound expression <b>f = h(g(x))</b>, it holds that (For
59	simplicity, we write increasing, decreasing, convex and concave, but
60	the correct notation would be nondecreasing, nonincreasing, convex
61	or affine and concave or affine. This notation us used throughout
62	this manual and inside YALMIP)</p>
63	<div align="center">
64	<table border="1" bgcolor="#EEEEEE" bordercolor="#000000" id="table1">
65	<tr>
66	<td bordercolorlight="#FFFFFF" bordercolordark="#FFFFFF">
67	<b>f</b> is <i>convex</i> if <b>h</b> is <i>convex</i> and
68	<i>increasing</i> and <b>g</b> is <i>convex</i><br>
69	<b>f</b> is <i>convex</i> if <b>h</b> is <i>convex</i> and
70	<i>decreasing</i> and <b>g</b> is <i>concave</i> <br>
71	<b>f</b> is <i>concave</i> if <b>h</b> is <i>concave</i>
72	and <i>increasing</i> and <b>g</b> is <i>concave</i>
73	<br>
74	<b>f</b> is <i>concave</i> if <b>h</b> is <i>concave</i>
75	and <i>decreasing</i> and <b>g</b> is <i>convex</i></td>
76	</tr>
77	</table>
78	</div>
79	<p>Based on this information, it is possible to recursively analyze
80	convexity of a complex expression involving convex and concave functions.
81	When <a href="reference.htm#solvesdp">solvesdp</a> is called, YALMIP
82	checks the convexity of objective function and constraints by using
83	information about the properties of the operators. If YALMIP manage
84	to prove convexity, graph formulations of the operators are automatically
85	introduced. This means that the operator is replaced with a graph, i.e.,
86	a set of constraints. </p>
87	<div align="center">
88	<table border="1" bgcolor="#EEEEEE" bordercolor="#000000" id="table2">
89	<tr>
90	<td bordercolorlight="#FFFFFF" bordercolordark="#FFFFFF">
91	<b>epigraph: t</b> represents convex function <b>f(x)</b>
92	: replace with <b>t<font face="Tahoma">≥</font>f(x)</b><br>
93	<b>hypograph</b>: <b>t</b> represents concave function <b>
94	f(x)</b> : replace with <b>t<font face="Tahoma">≤</font>f(x)</b></td>
95	</tr>
96	</table>
97	</div>
98	<p align="left">Of course, in order for this to be useful, the epigraph
99	representation has to be represented using standard constraints, such
100	as conic constraints.</p>
101	<h3 align="left">The operators</h3>
102	<p align="left">The operators defined in the current release are
103	described in the table below. This information might be useful to
104	understand how and when YALMIP can derive convexity.</p>
105	<div align="center">
106	<table border="1" width="86%" id="table7" bordercolor="#000000" style="border-collapse: collapse" bgcolor="#EEEEEE">
107	<tr>
108	<td>
109	<p align="center"><b>Name</b></td>
110	<td>
111	<p align="center"><b>Convex/Concave</b></td>
112	<td>
113	<p align="center"><b>Monotinicity</b></td>
114	<td width="468">
115	<p align="center"><b>Comments</b></td>
116	</tr>
117	<tr>
118	<td align="center">abs</td>
119	<td bgcolor="#FFFFFF" align="center">convex</td>
120	<td bgcolor="#FFFFFF" align="center">none</td>
121	<td width="468" bgcolor="#FFFFFF" height="31"> </td>
122	</tr>
123	<tr>
124	<td align="center">min</td>
125	<td bgcolor="#FFFFFF" align="center">concave</td>
126	<td bgcolor="#FFFFFF" align="center">increasing</td>
127	<td width="468" bgcolor="#FFFFFF"> </td>
128	</tr>
129	<tr>
130	<td align="center">max</td>
131	<td bgcolor="#FFFFFF" align="center">convex</td>
132	<td bgcolor="#FFFFFF" align="center">increasing</td>
133	<td width="468" bgcolor="#FFFFFF"> </td>
134	</tr>
135	<tr>
136	<td align="center">norm</td>
137	<td bgcolor="#FFFFFF" align="center">convex</td>
138	<td bgcolor="#FFFFFF" align="center">none</td>
139	<td width="468" bgcolor="#FFFFFF">All standard norms (1,2, inf and Frobenius) can be used
140	(applicable on both vectors and matrices.)</td>
141	</tr>
142	<tr>
143	<td align="center">sumk</td>
144	<td bgcolor="#FFFFFF" align="center">convex</td>
145	<td bgcolor="#FFFFFF" align="center">See comment</td>
146	<td width="468" bgcolor="#FFFFFF">Defines the sum of the
147	k largest elements of a vector, or the sum of the k
148	largest eigenvalues of a symmetric matrix. Increasing
149	for vector arguments, no monotinicity defined for
150	eigenvalue operator.</td>
151	</tr>
152	<tr>
153	<td align="center">sumabsk</td>
154	<td bgcolor="#FFFFFF" align="center">convex</td>
155	<td bgcolor="#FFFFFF" align="center">none</td>
156	<td width="468" bgcolor="#FFFFFF">Defines the sum of the
157	k largest absolute value elements of a vector, or the
158	sum of the k largest absolute value eigenvalues of a
159	symmetric matrix. </td>
160	</tr>
161	<tr>
162	<td align="center">geomean</td>
163	<td bgcolor="#FFFFFF" align="center">concave</td>
164	<td bgcolor="#FFFFFF" align="center">See comment</td>
165	<td width="468" bgcolor="#FFFFFF">For vector arguments, the operator is increasing. For
166	symmetric matrix argument, the operator is defined as the
167	geometric mean of the eigenvalues. No monotinicity
168	defined for eigenvalue operator</td>
169	</tr>
170	<tr>
171	<td align="center">cpower</td>
172	<td bgcolor="#FFFFFF" align="center">See comment</td>
173	<td bgcolor="#FFFFFF" align="center">See comment</td>
174	<td width="468" bgcolor="#FFFFFF">Convexity-aware
175	version of power. For negative powers, the operator is convex and decreasing.
176	For positive powers less than one, the operator is concave
177	and increasing. Positive powers larger than 1 gives a convex
178	increasing operator.</td>
179	</tr>
180	<tr>
181	<td align="center">sqrt</td>
182	<td bgcolor="#FFFFFF" align="center">concave</td>
183	<td bgcolor="#FFFFFF" align="center">increasing</td>
184	<td width="468" bgcolor="#FFFFFF">Short for
185	cpower(x,0.5)</td>
186	</tr>
187	</table>
188	</div>
189	<h3>Standard use</h3>
190	<p>Consider once again the <a href="linearregression.htm">linear regression
191	problem</a>.</p>
192	<table cellpadding="10" width="100%">
193	<tr>
194	<td class="xmpcode">
195	<pre>a = [1 2 3 4 5 6]';
196	t = (0:0.2:2*pi)';
197	x = [sin(t) sin(2t) sin(3t) sin(4t) sin(5t) sin(6*t)];
198	y = xa+(-4+8rand(length(x),1));
199	a_hat = sdpvar(6,1);
200	residuals = y-x*a_hat;</pre>
201	</td>
202	</tr>
203	</table>
204	<p>Using <b>abs</b> and <b>max</b>, we can easily solve the L<sub>1</sub>
205	and the L<sub>∞</sub> problem (Note that the <b>abs</b> operator currently
206	has performance issues and should be avoided for large arguments. Moreover, explicitly creating
207	absolute values when minimizing the L<sub>∞</sub> error is
208	unnecessarily complicated).
209	</p>
210	<table cellpadding="10" width="100%">
211	<tr>
212	<td class="xmpcode">
213	<pre>solvesdp([],sum(abs(residuals)));
214	a_L1 = double(a_hat)
215	solvesdp([],max(abs(residuals)));
216	a_Linf = double(a_hat)</pre>
217	</td>
218	</tr>
219	</table>
220	<p>YALMIP automatically concludes that the objective functions can be
221	modeled using some additional linear inequalities, adds these, and solves
222	the problems. We can simplify the code even more by using the <b>norm</b>
223	operator (this is much faster for large-scale problems due to implementation
224	issues in YALMIP). Here we also compute the least-squares solution (note
225	that this norm will generate a second-order cone constraint).</p>
226	<table cellpadding="10" width="100%">
227	<tr>
228	<td class="xmpcode">
229	<pre>solvesdp([],norm(residuals,1));
230	a_L1 = double(a_hat)
231	solvesdp([],norm(residuals,2));
232	a_L2 = double(a_hat)
233	solvesdp([],norm(residuals,inf));
234	a_Linf = double(a_hat)</pre>
235	</td>
236	</tr>
237	</table>
238	<p>The following piece of code shows how we easily can solve a regularized
239	problem.</p>
240	<table cellpadding="10" width="100%">
241	<tr>
242	<td class="xmpcode">
243	<pre>solvesdp([],1e-3*norm(a_hat,2)+norm(residuals,inf));
244	a_regLinf = double(a_hat)</pre>
245	</td>
246	</tr>
247	</table>
248	<p>The <b>norm</b> operator is used exactly as the built-in norm function
249	in MATLAB, both for vectors and matrices. Hence it can be used also
250	to minimize the largest singular value (2-norm in matrix case), or the
251	Frobenious norm of a matrix.</p>
252	<p>The <code>double</code> command of-course applies also to the nonlinear
253	operators (<b>double</b>(<b>OPERATOR</b>(<b>X</b>)) returns <b>OPERATOR</b>(<b>double</b>(<b>X</b>)).</p>
254	<table cellpadding="10" width="100%">
255	<tr>
256	<td class="xmpcode">
257	<pre>double(1e-3*norm(a_hat,2)+norm(residuals,inf))
258	<font color="#000000">ans =
259	3.1175</font></pre>
260	</td>
261	</tr>
262	</table>
263	<p><a name="geomean2"></a>A construction useful for maximizing determinants
264	of positive definite matrices is the function <b>(det P)<sup>1/m</sup></b>,
265	for positive definite matrix P, where <b>m</b> is the dimension of
266	<b>P</b>. This concave function, called <b>geomean</b> in YALMIP, is
267	supported as an extended operator. Note that the positive semidefiniteness
268	constraint on <b>P</b> is added automatically by YALMIP.</p>
269	<table cellpadding="10" width="100%">
270	<tr>
271	<td class="xmpcode">
272	<pre>D = randn(5,5);
273	P = sdpvar(5,5);
274	solvesdp(set(P < D*D'),-geomean(P));</pre>
275	</td>
276	</tr>
277	</table>
278	<p>The command can be applied also on positive vectors, and will then
279	model the geometric mean of the elements. We can use this to find the analytic
280	center of a set of linear inequalities (note that this is absolutely
281	not the recommended way to compute the analytic center.)</p>
282	<table cellpadding="10" width="100%">
283	<tr>
284	<td class="xmpcode">
285	<pre>A = randn(15,2);
286	b = rand(15,1)*5;</pre>
287	<pre>x = sdpvar(2,1);
288	solvesdp([],-geomean(b-A*x)); % Maximize product of elements in b-Ax, s.t Ax < b</pre>
289	</td>
290	</tr>
291	</table>
292	<p>Rather advanced constructions are possible, and YALMIP will try derive
293	an equivalent convex model.</p>
294	<table cellpadding="10" width="100%" id="table3">
295	<tr>
296	<td class="xmpcode">
297	<pre>sdpvar x y z
298	F = set(max(1,x)+max(y^2,z) < 3)+set(max(1,-min(x,y)) < 5)+set(norm([x;y],2) < z);
299	sol = solvesdp(F,max(x,z)-min(y,z)-z);</pre>
300	</td>
301	</tr>
302	</table>
303	<h3><a name="polynomials"></a>Polynomial and sigmonial expressions</h3>
304	<p>By default, polynomial expressions (except quadratics) are not analyzed
305	with respect to convexity and conversion to a conic model is not performed.
306	Hence, if you add a constraint such as <code>set(x^4 + y^8-x^0.5 < 10)</code>,
307	YALMIP may complain about convexity, even though we can see that the
308	expression is convex and can be represented using conic constraints.
309	More importantly, YALMIP will not try to derive an equivalent conic
310	model. However, by using the command <b>cpower</b> instead, rational
311	powers can be used. </p>
312	<p>To illustrate this, first note the difference between a monomial
313	generated using overloaded power and a variable generated <b>cpower</b>.</p>
314	<table cellpadding="10" width="100%" id="table4">
315	<tr>
316	<td class="xmpcode">
317	<pre>sdpvar x
318	x^4
319	<font color="#000000">Polynomial scalar (real, homogeneous, 1 variable)</font>
320	cpower(x,4)
321	<font color="#000000">Linear scalar (real, derived, 1 variable)</font></pre>
322	</td>
323	</tr>
324	</table>
325	<p>The property <i>derived</i> indicates that YALMIP will try to replace the
326	variable with its epigraph formulation when the problem is solved. Working
327	with these convexity-aware monomials is no different than usual.</p>
328	<table cellpadding="10" width="100%" id="table5">
329	<tr>
330	<td class="xmpcode">
331	<pre>sdpvar x y
332	F = set(cpower(x,4) + cpower(y,4) < 10) + set(cpower(x,2/3) + cpower(y,2/3) > 1);
333	plot(F,[x y]);</pre>
334	</td>
335	</tr>
336	</table>
337	<p>Note that when you plot sets with constraints involving nonlinear
338	operators and polynomials, it is recommended that you specify the variables
339	of interest in the second argument (YALMIP may otherwise plot the set
340	with respect to auxiliary variables introduced during the construction
341	of the conic model.)</p>
342	<p>Do not use these operators unless you really need them. The conic
343	representation of rational powers easily grow large.</p>
344	<h3>Limitations</h3>
345	<p>If the convexity propagation fails, an error will be issued (error
346	code 14). Note that this does not imply that the model is nonconvex,
347	but only means that the simple sufficient conditions used for checking
348	convexity were violated. Failure is however typically an indication
349	of a bad model, and most often due to an actual nonconvex part in the
350	model. The problems above are all convex, but not this problem below,
351	due to the way <b>min</b> enters in the constraint.</p>
352	<table cellpadding="10" width="100%">
353	<tr>
354	<td class="xmpcode">
355	<pre>sdpvar x y z
356	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);
357	sol = solvesdp(F,max(x,z)-min(y,z)-z);
358	sol.info
359
360	<font color="#000000">ans =
361	Convexity check failed (Expected convex function in constraint #2 at level 2)</font></pre>
362	</td>
363	</tr>
364	</table>
365	<p>In the same sense, this problem fails due to a nonconvex objective
366	function.</p>
367	<table cellpadding="10" width="100%">
368	<tr>
369	<td class="xmpcode">
370	<pre>sdpvar x y z
371	F = set(max(1,x)+max(y^2,z) < 3);
372	sol = solvesdp(F,-norm([x;y]));
373	sol.info
374	<font color="#000000">
375	ans =
376	Convexity check failed (Expected concave function in objective at level 1)</font></pre>
377	</td>
378	</tr>
379	</table>
380	<p>This following problem is however convex, but convexity propagation
381	fails.</p>
382	<table cellpadding="10" width="100%" id="table6">
383	<tr>
384	<td class="xmpcode">
385	<pre>sdpvar x
386	sol = solvesdp([],norm(max([1 1-x 1+x])))
387	sol.info
388	<font color="#000000">
389	ans =
390	Convexity check failed (Monotonicity required at objective at level 1)</font></pre>
391	</td>
392	</tr>
393	</table>
394	<p>The described operators cannot be used in polynomial expressions
395	in the current implementation. The following problem is trivially convex
396	but fails.</p>
397	<table cellpadding="10" width="100%" id="table8">
398	<tr>
399	<td class="xmpcode">
400	<pre>sdpvar x y
401	sol = solvesdp([],norm([x;y])^2);
402	sol.info
403
404	<font color="#000000">ans =
405	Convexity check failed (Operator in polynomial in objective)</font></pre>
406	</td>
407	</tr>
408	</table>
409	<p>Another limitation is that the operators not are allowed in cone
410	and semidefinite constraints.</p>
411	<table cellpadding="10" width="100%" id="table10">
412	<tr>
413	<td class="xmpcode">
414	<pre>sdpvar x y
415	sol = solvesdp(set(cone(max(x,y,1),2)),x+y);
416	sol.info
417
418	<font color="#000000">ans =
419	Convexity propagation failed (YALMIP)</font></pre>
420	</td>
421	</tr>
422	</table>
423	<p>In practice, these limitations should not pose a major problem. A
424	better model is possible (and probably recommended) in most cases if
425	these situations occur. </p>
426	<h3><a name="milp"></a>Mixed integer models</h3>
427	<p>In some cases when the convexity analysis fails, it is possible
428	to tell YALMIP to switch from a graph based approach to a mixed
429	integer model based approach. In other words, if no graph model can
430	be derived, YALMIP introduces integer variables to model the
431	operators. This is currently implemented for <b>min</b>, <b>
432	max</b>, <b>abs</b> and linear <b>norm</b> for real arguments. By default, this feature
433	is not invoked, but can be activated by <code>sdpsettings('allowmilp',1)</code>.</p>
434	<p>Consider the following simple example which fails due to the
435	non-convex use of the convex <b>abs</b> operator</p>
436	<table cellpadding="10" width="100%" id="table12">
437	<tr>
438	<td class="xmpcode">
439	<pre>sdpvar x y
440	F = set(abs(abs(x+1)+3) > y)+set(0<x<3);
441	sol = solvesdp(F,-y);
442	sol.info
443	<font color="#000000"> Convexity check failed (Expected concave function in constraint #1 at level 1)</font></pre>
444	</td>
445	</tr>
446	</table>
447	<p>By turning on the mixed integer fall back model, a mixed integer
448	LP is generated and the problem is easily solved.</p>
449	<table cellpadding="10" width="100%" id="table13">
450	<tr>
451	<td class="xmpcode">
452	<pre>sdpvar x y
453	F = set(abs(abs(x+1)+3) > y)+set(0<x<3);
454	sol = solvesdp(F,-y,sdpsettings('allowmilp',1));
455	double([x y])
456	<font color="#000000">ans =
457	3.0000 7.0000</font></pre>
458	</td>
459	</tr>
460	</table>
461	<p>If you know that your model is non-convex and will require a
462	mixed integer model, you can bypass the initial attempt to generate
463	the graph model by using <code>sdpsettings('allowmilp',2)</code>.</p>
464	<h3><a name="evaluationbased"></a>Evaluation based nonlinear operators</h3>
465	<p>YALMIP now also supports experimental support for general
466	convex/concave functions that cannot be modelled using conic
467	representations. The main difference when working with these
468	operators is that the problem always requires a general nonlinear
469	solver to solved, such as<a href="solvers.htm#fmincon"> fmincon</a>.
470	All convexity analysis is still performed tough.</p>
471	<table cellpadding="10" width="100%" id="table14">
472	<tr>
473	<td class="xmpcode">
474	<pre>sdpvar x
475	solvesdp(set(exp(2*x + 1) < 1),-x,sdpsettings('solver','fmincon'));
476	double(x)
477	<font color="#000000">ans =
478	-0.5000</font></pre>
479	<pre>double(exp(2*x + 1))
480	<font color="#000000">ans =
481	1</font></pre>
482	</td>
483	</tr>
484	</table>
485	<p>Note that this feature still is very limited and experimental.
486	Too see how you can add our own function, see the
487	<a href="#entropy">example for scalar entropy</a>. </p>
488	<p>As a word of caution, note that<a href="solvers.htm#fmincon"> fmincon</a>
489	performs pretty bad on problems with functions that aren't defined
490	everywhere, such as logarithms. Hence, solving problem involving
491	these functions can easily lead to problems. It is highly
492	recommended to at least provide a feasible solution, or even better,
493	to use the inverse operator to formulate the problem. Consider the
494	following trivial example of finding the analytic center of a unit
495	cube centered at the point (3,3,3)</p>
496	<table cellpadding="10" width="100%" id="table16">
497	<tr>
498	<td class="xmpcode">
499	<pre>x = sdpvar(3,1);
500	p = [1-(x-3);(x-3)+1]
501
502	% Not recommended
503	solvesdp([],-sum(log(p)));
504
505	% Better
506	assign(x,[3.1;3.2;3.3]);
507	solvesdp([],-sum(log(p)),sdpsettings('usex0',1));
508
509	% Best (well, adding initials on x and t would be even better)
510	t = sdpvar(3,1);
511	solvesdp(exp(t) < p ,-sum(t));</pre>
512	<pre>
513	</pre>
514	</td>
515	</tr>
516	</table>
517	<h3>Behind the scene</h3>
518	<p>If you want to look at the model that YALMIP generates, you can use
519	the two commands <code>model</code> and <code>expandmodel</code>. Please
520	note that these expanded models never should be used manually. The commands
521	described below should only be used for illustrating the process that
522	goes on behind the scenes.</p>
523	<p>With the command <code>model</code>, the epi- or hypograph model
524	of the variable is returned. As an example, to model the maximum of
525	two scalars <b>x</b> and <b>y</b>, YALMIP generates two linear inequalities.</p>
526	<table cellpadding="10" width="100%">
527	<tr>
528	<td class="xmpcode">
529	<pre>sdpvar x y
530	t = max([x y]);
531	F = model(t)
532	<font color="#000000">++++++++++++++++++++++++++++++++++++++++++++
533	\| ID\| Constraint\| Type\|
534	++++++++++++++++++++++++++++++++++++++++++++
535	\| #1\| Numeric value\| Element-wise 1x2\|
536	++++++++++++++++++++++++++++++++++++++++++++</font>
537	sdisplay(sdpvar(F(1)))
538	<font color="#000000">ans =
539	'-x+t' '-y+t'</font></pre>
540	</td>
541	</tr>
542	</table>
543	<p>For more advanced models with recursively used nonlinear operators,
544	the function <code>model</code> will not generate the complete model
545	since it does not recursively expand the arguments. For this case, use
546	the command <code>expandmodel</code>. This command takes two arguments,
547	a set of constraints and an objective function. To expand an expression,
548	just let the expression take the position as the objective function.
549	Note that the command assumes that the expansion is performed in order
550	to prove a convex function, hence if you expression is meant to be concave,
551	you need to negate it. To illustrate this, let us expand the objective
552	function in an extension of the geometric mean example above.</p>
553	<table cellpadding="10" width="100%">
554	<tr>
555	<td class="xmpcode">
556	<pre>A = randn(15,2);
557	b = rand(15,1)*5;</pre>
558	<pre>x = sdpvar(2,1);
559	expandmodel([],-geomean([b-A*x;min(x)]))
560	<font color="#000000">+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
561	\| ID\| Constraint\| Type\|
562	+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
563	\| #1\| Numeric value\| Element-wise 2x1\|
564	\| #2\| Numeric value\| Second order cone constraint 3x1\|
565	\| #3\| Numeric value\| Second order cone constraint 3x1\|
566	\| #4\| Numeric value\| Second order cone constraint 3x1\|
567	\| #5\| Numeric value\| Second order cone constraint 3x1\|
568	\| #6\| Numeric value\| Second order cone constraint 3x1\|
569	\| #7\| Numeric value\| Second order cone constraint 3x1\|
570	\| #8\| Numeric value\| Second order cone constraint 3x1\|
571	\| #9\| Numeric value\| Second order cone constraint 3x1\|
572	\| #10\| Numeric value\| Second order cone constraint 3x1\|
573	\| #11\| Numeric value\| Second order cone constraint 3x1\|
574	\| #12\| Numeric value\| Second order cone constraint 3x1\|
575	\| #13\| Numeric value\| Second order cone constraint 3x1\|
576	\| #14\| Numeric value\| Second order cone constraint 3x1\|
577	\| #15\| Numeric value\| Second order cone constraint 3x1\|
578	\| #16\| Numeric value\| Second order cone constraint 3x1\|
579	+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</font></pre>
580	</td>
581	</tr>
582	</table>
583	<p>The result is two linear inequalities related to the <b>min</b> operator
584	and 15 second order cone constraints used for the conic representation
585	of the geometric mean.</p>
586	<h3><a name="operatorformat"></a>Adding new operators</h3>
587	<p>If you want to add your own operator, all you need to do is to create
588	1 file. This file should be able to return the numerical value of the
589	operator for a numerical input, and return the epigraph (or hypograph)
590	and a descriptive structure of the operator when the first input is
591	<code>'graph'</code>. As an example, the following file implements the
592	nonlinear operator <b>tracenorm</b>. This convex operator returns <b>
593	sum(svd(X))</b> for matrices <b>X</b>. This value can also be described
594	as the minimizing argument of the optimization problem <b>min<sub>t,A,B</sub>
595	t</b> subject to <b>set([A X;X' B] > 0) + set(trace(A)+trace(B) < 2*t)</b>.</p>
596	<table cellpadding="10" width="100%">
597	<tr>
598	<td class="xmpcode">
599	<pre>function varargout = tracenorm(varargin)
600
601	switch class(varargin{1})
602
603	case 'double' % What is the <font color="#FF0000">numerical value</font> (needed for displays etc)
604	varargout{1} = sum(svd(varargin{1}));
605
606	case 'char' % YALMIP send 'graph' when it wants the epigraph or hypograph
607	switch varargin{1}
608	case 'graph'
609	t = varargin{2}; % 2nd arg is the extended operator variable
610	X = varargin{3}; % 3rd arg and above are args user used when defining t.
611	A = sdpvar(size(X,1));
612	B = sdpvar(size(X,2));
613	F = set([A X;X' B] > 0) + set(trace(A)+trace(B) < 2*t);
614
615	% <font color="#FF0000">Return epigraph model
616	</font>varargout{1} = F;
617	% <font color="#FF0000">a description </font>
618	properties.convexity = 'convex';<font color="#FF0000"> % convex \| none \| concave</font>
619	properties.monotonicity = 'none';<font color="#FF0000"> % increasing \| none \| decreasing</font>
620	properties.definiteness = 'positive';<font color="#FF0000"> % negative \| none \| positive</font>
621	varargout{2} = properties;
622	% <font color="#FF0000">and the argument
623	</font> varargout{3} = X;
624
625	case 'milp'
626	varargout{1} = [];
627	varargout{2} = [];
628	varargout{3} = [];
629
630	otherwise
631	error('Something is very wrong now...')
632	end
633
634	case 'sdpvar' % Always the same.
635	varargout{1} = yalmip('addextendedvariable',mfilename,varargin{:});
636
637	otherwise
638	end</pre>
639	</td>
640	</tr>
641	</table>
642	<p>The function <code>sumk.m</code> in YALMIP is implemented using this
643	framework and might serve as an additional fairly simple example. The
644	overloaded operator <code>norm.m</code> is also defined using this method,
645	but is a bit more involved, since it supports different norms. Note
646	that we with a slight abuse of notation use the terms increasing and
647	decreasing instead of nondecreasing and nonincreasing.</p>
648	<h3><a name="operatorformat0"></a>Adding new operators with mixed
649	integer models</h3>
650	<p>If the convexity analysis fails, it is possible to have fall back
651	alternative models based on integer variables. If the operator is
652	called with the flag <code>milp</code>, a mixed integer exact model
653	can be
654	returned. As an illustration, here is a stripped down version of the
655	epigraph and MILP model of the absolute value of a real scalar.</p>
656	<table cellpadding="10" width="100%" id="table11">
657	<tr>
658	<td class="xmpcode">
659	<pre>function varargout = scalarrealabs(varargin)
660
661	switch class(varargin{1})
662
663	case 'double'
664	varargout{1} = abs(varargin{1});
665
666	case 'char' % YALMIP send 'graph' when it wants the epigraph or hypograph
667	switch varargin{1}
668	case 'graph'
669	t = varargin{2};
670	X = varargin{3};
671	<font color="#FF0000"> </font>varargout{1} = set(-t <= X <= t);
672	properties.convexity = 'convex';<font color="#FF0000"> </font>
673	properties.monotonicity = 'none';<font color="#FF0000">
674	</font> properties.definiteness = 'positive';<font color="#FF0000"> </font>
675	varargout{2} = properties;
676	varargout{3} = X;
677
678	case <font color="#FF0000">'milp'
679	</font> t = varargin{2};
680	X = varargin{3};
681	d = binvar(1,1); % d=1 means x>0, d=0 means x<0
682	F = set([]);
683	M = 1e4; % Big-M constant
684	F = F + set(x >= -M*(1-d)) % d=1 means x >= 0
685	F = F + set(x <= M*d) % d=0 means x <= 0
686	F = F + set(-M(1-d) <= t-x <= M(1-d); % d=1 means t = X
687	F = F + set(-Md <= t+x <= Md; % d=0 means t = -X
688
689	varargout{1} = F;
690	properties.convexity = '<font color="#FF0000">milp</font>';<font color="#FF0000"> </font>
691	properties.monotonicity = '<font color="#FF0000">milp</font>';<font color="#FF0000">
692	</font> properties.definiteness = '<font color="#FF0000">milp</font>';<font color="#FF0000"> </font>
693	varargout{2} = properties;
694	varargout{3} = X;
695
696	otherwise
697	error('Something is very wrong now...')
698	end
699
700	case 'sdpvar' % Always the same.
701	varargout{1} = yalmip('addextendedvariable',mfilename,varargin{:});
702
703	otherwise
704	end</pre>
705	</td>
706	</tr>
707	</table>
708	<p>MILP models are most often based on so called big-M models. For
709	these methods to work well, it is important to have as small
710	constants M as possible, but in the code above, we just picked a
711	number. For the MILP models defined by default in YALMIP (<b>min</b>,
712	<b>max</b>, <b>abs</b> and linear <b>norms</b>), more effort is spent on
713	choosing the
714	constants. To learn more about how you can do this for your model,
715	please check out the code for these models.</p>
716	<h3><a name="entropy"></a>Adding evaluation based nonlinear
717	operators</h3>
718	<p>General convex and concave functions are support in YALMIP by the
719	evaluation based nonlinear operator framework. The definition of
720	these operators are almost identical to the definition of standard
721	nonlinear operators. The following code implements a (simplified
722	version) of a scalar entropy measure <b>-xlog(x)</b>.</p>
723	<table cellpadding="10" width="100%" id="table15">
724	<tr>
725	<td class="xmpcode">
726	<pre>function varargout = entropy(varargin)
727
728	switch class(varargin{1})</pre>
729	<pre> case 'double' % What is the numerical value of this argument (needed for displays etc)
730	varargout{1} = <font color="#FF0000">-varargin{1}*log(varargin{1})</font>;
731
732	case 'sdpvar' % Overloaded operator for SDPVAR objects.
733	varargout{1} = yalmip('addEvalVariable',mfilename,varargin{1}); </pre>
734	<pre> case 'char' % YALMIP sends 'graph' when it wants the epigraph, hypograph or domain definition
735	switch varargin{1}
736	case 'graph'
737	t = varargin{2};
738	X = varargin{3}; </pre>
739	<pre><font color="#FF0000"> </font>% This is different from standard extended operators.
740	% Just do it!<font color="#FF0000">
741	</font>F = SetupEvaluationVariable(varargin{:});<font color="#FF0000">
742	</font>
743	% Now add your own code, typically domain constraints
744	<font color="#FF0000">F = F + set(X > 0);</font>
745
746	% Let YALMIP know about convexity etc
747	varargout{1} = F;
748	varargout{2} = struct('convexity','concave','monotonicity','none','definiteness','none');
749	varargout{3} = X; </pre>
750	<pre> case 'milp' % No MILP model available for entropy
751	varargout{1} = [];
752	varargout{2} = [];
753	varargout{3} = [];
754	otherwise
755	error('ENTROPY called with CHAR argument?');
756	end
757	otherwise
758	error('ENTROPY called with invalid argument.');
759	end</pre>
760	</td>
761	</tr>
762	</table>
763	<p>The evaluation based framework is primarily intended for scalar
764	functions, but can be extended to support element-wise vector functions. See the
765	implementation of the overloaded log operator for details.</p>
766	</td>
767	</tr>
768	</table>
769	<p> </div>
770
771	</body>
772
773	</html>

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: proiecte/pmake3d/make3d_original/Make3dSingleImageStanford_version0.1/third_party/opt/yalmip/htmldata/extoperators.htm @ 37

Download in other formats: