extoperators.htm

optimization toolbox

			<h3>Behind the scene</h3>
			<p>If you want to look at the model that YALMIP generates, you can use 
			the two commands <code>model</code> and <code>expandmodel</code>. Please 
			note that these expanded models never should be used manually. The commands 
			described below should only be used for illustrating the process that 
			goes on behind the scenes.</p>
			<p>With the command <code>model</code>, the epi- or hypograph model 
			of the variable is returned. As an example, to model the maximum of 
			two scalars <b>x</b> and <b>y</b>, YALMIP generates two linear inequalities.</p>
			<table cellpadding="10" width="100%">
				<tr>
					<td class="xmpcode">
					<pre>sdpvar x y
t = max([x y]);
F = model(t)
<font color="#000000">++++++++++++++++++++++++++++++++++++++++++++
|   ID|      Constraint|               Type|
++++++++++++++++++++++++++++++++++++++++++++
|   #1|   Numeric value|   Element-wise 1x2|
++++++++++++++++++++++++++++++++++++++++++++</font>
sdisplay(sdpvar(F(1)))
<font color="#000000">ans =
   &#39;-x+t&#39;    &#39;-y+t&#39;</font></pre>
					</td>
				</tr>
			</table>
			<p>For more advanced models with recursively used nonlinear operators, 
			the function <code>model</code> will not generate the complete model 
			since it does not recursively expand the arguments. For this case, use 
			the command <code>expandmodel</code>. This command takes two arguments, 
			a set of constraints and an objective function. To expand an expression, 
			just let the expression take the position as the objective function. 
			Note that the command assumes that the expansion is performed in order 
			to prove a convex function, hence if you expression is meant to be concave, 
			you need to negate it. To illustrate this, let us expand the objective 
			function in an extension of the geometric mean example above.</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);
expandmodel([],-geomean([b-A*x;min(x)]))
<font color="#000000">+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|    ID|      Constraint|                               Type|
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|    #1|   Numeric value|                   Element-wise 2x1|
|    #2|   Numeric value|   Second order cone constraint 3x1|
|    #3|   Numeric value|   Second order cone constraint 3x1|
|    #4|   Numeric value|   Second order cone constraint 3x1|
|    #5|   Numeric value|   Second order cone constraint 3x1|
|    #6|   Numeric value|   Second order cone constraint 3x1|
|    #7|   Numeric value|   Second order cone constraint 3x1|
|    #8|   Numeric value|   Second order cone constraint 3x1|
|    #9|   Numeric value|   Second order cone constraint 3x1|
|   #10|   Numeric value|   Second order cone constraint 3x1|
|   #11|   Numeric value|   Second order cone constraint 3x1|
|   #12|   Numeric value|   Second order cone constraint 3x1|
|   #13|   Numeric value|   Second order cone constraint 3x1|
|   #14|   Numeric value|   Second order cone constraint 3x1|
|   #15|   Numeric value|   Second order cone constraint 3x1|
|   #16|   Numeric value|   Second order cone constraint 3x1|
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</font></pre>
					</td>
				</tr>
			</table>
			<p>The result is two linear inequalities related to the <b>min</b> operator 
			and 15 second order cone constraints used for the conic representation 
			of the geometric mean.</p>
			<h3><a name="operatorformat"></a>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) 
			and a descriptive structure of the operator when the first input is
			<code>&#39;graph&#39;</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&#39; B] &gt; 0) + set(trace(A)+trace(B) &lt; 2*t)</b>.</p>
			<table cellpadding="10" width="100%">
				<tr>
					<td class="xmpcode">
					<pre>function varargout = tracenorm(varargin)

switch class(varargin{1})    

    case &#39;double&#39; % What is the <font color="#FF0000">numerical value</font> (needed for displays etc)
        varargout{1} = sum(svd(varargin{1}));

    case &#39;char&#39;   % YALMIP send &#39;graph&#39; when it wants the epigraph or hypograph
        switch varargin{1}
	 case &#39;graph&#39;
            t = varargin{2}; % 2nd arg is the extended operator variable
            X = varargin{3}; % 3rd arg and above are args user used when defining t.
            A = sdpvar(size(X,1));
            B = sdpvar(size(X,2));
            F = set([A X;X&#39; B] &gt; 0) + set(trace(A)+trace(B) &lt; 2*t);

            % <font color="#FF0000">Return epigraph model
            </font>varargout{1} = F;
            % <font color="#FF0000">a description </font>
            properties.convexity    = &#39;convex&#39;;<font color="#FF0000">   % convex | none | concave</font>
            properties.monotonicity = &#39;none&#39;;<font color="#FF0000">     % increasing | none | decreasing</font>
            properties.definiteness = &#39;positive&#39;;<font color="#FF0000"> % negative | none | positive</font>  
            varargout{2} = properties;
            % <font color="#FF0000">and the argument
</font>            varargout{3} = X;

         case 'milp'
	    varargout{1} = [];
	    varargout{2} = [];
	    varargout{3} = [];

         otherwise
            error(&#39;Something is very wrong now...&#39;)
        end    

    case &#39;sdpvar&#39; % Always the same. 
        varargout{1} = yalmip(&#39;addextendedvariable&#39;,mfilename,varargin{:});    

    otherwise
end</pre>
					</td>
				</tr>
			</table>
			<p>The function <code>sumk.m</code> in YALMIP is implemented using this 
			framework and might serve as an additional fairly simple example. The 
			overloaded operator <code>norm.m</code> is also defined using this method, 
			but is a bit more involved, since it supports different norms. Note 
			that we with a slight abuse of notation use the terms increasing and 
			decreasing instead of nondecreasing and nonincreasing.</p>
			<h3><a name="operatorformat0"></a>Adding new operators with mixed 
			integer models</h3>
			<p>If the convexity analysis fails, it is possible to have fall back 
			alternative models based on integer variables. If the operator is 
			called with the flag <code>milp</code>, a mixed integer exact model 
			can be 
			returned. As an illustration, here is a stripped down version of the 
			epigraph and MILP model of the absolute value of a real scalar.</p>
			<table cellpadding="10" width="100%" id="table11">
				<tr>
					<td class="xmpcode">
					<pre>function varargout = scalarrealabs(varargin)

switch class(varargin{1})    

    case &#39;double&#39; 
        varargout{1} = abs(varargin{1});

    case &#39;char&#39;   % YALMIP send &#39;graph&#39; when it wants the epigraph or hypograph
        switch varargin{1}
	 case &#39;graph&#39;
            t = varargin{2}; 
            X = varargin{3}; 
<font color="#FF0000">            </font>varargout{1} = set(-t &lt;= X &lt;= t);
            properties.convexity    = &#39;convex&#39;;<font color="#FF0000">   </font>
            properties.monotonicity = &#39;none&#39;;<font color="#FF0000">     
</font>            properties.definiteness = &#39;positive&#39;;<font color="#FF0000"> </font>
            varargout{2} = properties;
            varargout{3} = X;

         case <font color="#FF0000">'milp'
</font>            t = varargin{2}; 
            X = varargin{3}; 
	    d = binvar(1,1); % d=1 means x&gt;0, d=0 means x&lt;0
	    F = set([]);
	    M = 1e4; % Big-M constant
	    F = F + set(x &gt;= -M*(1-d))                     % d=1 means x &gt;= 0
	    F = F + set(x &lt;= M*d)                          % d=0 means x &lt;= 0
	    F = F + set(-M*(1-d) &lt;= t-x &lt;= M*(1-d); % d=1 means t = X
	    F = F + set(-M*d     &lt;= t+x &lt;= M*d;     % d=0 means t = -X

	    varargout{1} = F;
	    properties.convexity    = &#39;<font color="#FF0000">milp</font>&#39;;<font color="#FF0000">   </font>
            properties.monotonicity = &#39;<font color="#FF0000">milp</font>&#39;;<font color="#FF0000">     
</font>            properties.definiteness = &#39;<font color="#FF0000">milp</font>&#39;;<font color="#FF0000"> </font>
	    varargout{2} = properties;
	    varargout{3} = X;

         otherwise
            error(&#39;Something is very wrong now...&#39;)
        end    

    case &#39;sdpvar&#39; % Always the same. 
        varargout{1} = yalmip(&#39;addextendedvariable&#39;,mfilename,varargin{:});    

    otherwise
end</pre>
					</td>
				</tr>
			</table>
			<p>MILP models are most often based on so called big-M models. For 
			these methods to work well, it is important to have as small 
			constants M as possible, but in the code above, we just picked a 
			number. For the MILP models defined by default in YALMIP (<b>min</b>, 
			<b>max</b>, <b>abs</b> and linear <b>norms</b>), more effort is spent on 
			choosing the 
			constants. To learn more about how you can do this for your model, 
			please check out the code for these models.</p>
			<h3><a name="entropy"></a>Adding evaluation based nonlinear 
			operators</h3>
			<p>General convex and concave functions are support in YALMIP by the 
			evaluation based nonlinear operator framework. The definition of 
			these operators are almost identical to the definition of standard 
			nonlinear operators. The following code implements a (simplified 
			version) of a scalar entropy measure <b>-xlog(x)</b>.</p>
			<table cellpadding="10" width="100%" id="table15">
				<tr>
					<td class="xmpcode">
					<pre>function varargout = entropy(varargin)

switch class(varargin{1})</pre>
					<pre>    case 'double' % What is the numerical value of this argument (needed for displays etc)        
	varargout{1} = <font color="#FF0000">-varargin{1}*log(varargin{1})</font>;

    case 'sdpvar' % Overloaded operator for SDPVAR objects.
         varargout{1} = yalmip('addEvalVariable',mfilename,varargin{1});        </pre>
					<pre>    case 'char' % YALMIP sends 'graph' when it wants the epigraph, hypograph or domain definition
        switch varargin{1}
            case 'graph'
                t = varargin{2};
                X = varargin{3};                </pre>
					<pre><font color="#FF0000">                </font>% This is different from standard extended operators.
                % Just do it!<font color="#FF0000">
		</font>F = SetupEvaluationVariable(varargin{:});<font color="#FF0000">
                </font>                
                % Now add your own code, typically domain constraints
                <font color="#FF0000">F = F + set(X &gt; 0);</font>
                
                % Let YALMIP know about convexity etc                
                varargout{1} = F;
                varargout{2} = struct('convexity','concave','monotonicity','none','definiteness','none');
                varargout{3} = X;                </pre>
					<pre>            case 'milp' % No MILP model available for entropy
                    varargout{1} = [];
                    varargout{2} = [];
                    varargout{3} = [];                
            otherwise
                error('ENTROPY called with CHAR argument?');
        end
    otherwise
        error('ENTROPY called with invalid argument.');
end</pre>
					</td>
				</tr>
			</table>
			<p>The evaluation based framework is primarily intended for scalar 
			functions, but can be extended to support element-wise vector functions. See the 
			implementation of the overloaded log operator for details.</p>
			</td>
		</tr>
	</table>
	<p>&nbsp;</div>

</body>

</html>