Elias: Created page with "==Introduction== ===Overview=== Welcome to the TOMLAB /PENOPT User's Guide. TOMLAB /PENOPT includes either PENSDP or PENBMI (depends on the license) and interfaces between The ..."

2011-10-13T12:55:05Z

Created page with "==Introduction== ===Overview=== Welcome to the TOMLAB /PENOPT User's Guide. TOMLAB /PENOPT includes either PENSDP or PENBMI (depends on the license) and interfaces between The ..."

New page

==Introduction==

===Overview===

Welcome to the TOMLAB /PENOPT User's Guide. TOMLAB /PENOPT includes either PENSDP or PENBMI (depends on the license) and interfaces between The MathWorks' MATLAB and the solver packages from PENOPT GbR. The package includes one of the following solvers:

PENBMI - For large, sparse semidefinite programming problems with linear and bilinear matrix inequality constraints.

PENSDP - For large, sparse linear semidefinite programming problems with linear constraints. It also solves feasibility problems for systems of linear matrix inequalities.

Please visit [http://tomopt.com/tomlab/products/pensdp/ http://tomopt.com/tomlab/products/pensdp/], [http://tomopt.com/tomlab/products/penbmi/ http://tomopt.com/tomlab/products/penbmi/] and [http://www.penopt.com/ http://www.penopt.com] for more information.

For PENBMI two different input formats may be used for the problem formulation: The PENBMI Structural Format, an extension of the PENSDP format for linear problems, and the TOMLAB format for semidefinite prob- lems. Apart from solving the BMI problem, the user can check feasibility of the system of linear and bilinear matrix inequalities.

For PENSDP three different input formats may be used for problem formulation: The standard sparse SDPA format used in SDPLIB, the PENSDP Structural Format, and the TOMLAB format for semidefinite problems.

Problems defined in SeDuMi Matlab format may easily be converted to SDPA format and solved by TOMLAB /PENSDP. The conversion routine, called writesdp, was written by Brian Borcher.

Apart from solving the SDP problem, the user can check feasibility of the system of linear matrix inequalities. The interface between TOMLAB /PENOPT, Matlab and TOMLAB consists of two layers. The first layer gives direct access from Matlab to PENOPT, via calling a Matlab function that calls a pre-compiled MEX file (DLL under Windows, shared library in UNIX) that defines and solves the problem in PENOPT. The second layer is a Matlab function that takes the input in the TOMLAB format, and calls the first layer function. On return the function creates the output in the TOMLAB format.

===Contents of this Manual===

*[[#Using the Matlab Interface]] gives the basic information needed to run the Matlab interface.

*[[#PENOPT Solver Reference]] provides all the solver references for PENBMI and PENSDP.

===Prerequisites===

In this manual we assume that the user is familiar with semidefinite programming, TOMLAB and the Matlab language.

==Using the Matlab Interface==

The main routines in the two-layer design of the interface are shown in <xr id="tab:interfaceRoutines" />. Page and section references are given to detailed descriptions on how to use the routines.

<figtable id="tab:interfaceRoutines">
{|class="wikitable"
|+<caption>The interface routines.</caption>
|-valign="top"
!Function||Description
|-valign="top"
|[[#penbmiTL|penbmiTL]]||The layer two interface routine called by the TOMLAB driver routine ''tomRun''. This routine then calls ''penbmi.m'', which in turn calls ''penbmi.dll''.
|-valign="top"
|[[#penfeas_bmi|penfeas_bmi]]||The layer two TOMLAB interface routine that calls ''pen.m''. Converts the input ''P rob ''format before calling ''penbmiQ.dll ''and converts back to the output ''Result ''structure.
|-valign="top"
|[[#pensdpTL|pensdpTL]]||The layer two interface routine called by the TOMLAB driver routine ''tomRun''. This routine then calls ''pensdp.m'', which in turn calls ''pensdp.dll''.
|-valign="top"
|[[#penfeas_sdp|penfeas_sdp]]||The layer two TOMLAB interface routine that calls ''pen.m''. Converts the input ''P rob ''format before calling ''pensdp.dll ''and converts back to the output ''Result ''structure.
|}
</figtable>

The PENOPT control parameters are possible to set from Matlab.

They can be set as inputs to the interface routine ''penbmiTL'' for example and the others. The user sets fields in a structure called ''Prob.PENOPT''. The following example shows how to set the maximum number of overall iterations.

<pre>
Prob.PENOPT.ioptions(2) = 200; % Setting maximum number of iterations
</pre>

==PENOPT Solver Reference==

The PENOPT solvers are a set of solvers that were developed by the PENOPT GbR. Table 2 lists the solvers included in TOMLAB /PENOPT. The solvers are called using a set of MEX-file interfaces developed as part of TOMLAB. All functionality of the PENOPT solvers are available and changeable in the TOMLAB framework in Matlab.

Detailed descriptions of the TOMLAB /PENOPT solvers are given in the following sections. Also see the M-file help for each solver.

Additional solvers reference guides for the TOMLAB /PENOPT solvers are available for download from the TOM- LAB home page [http://tomopt.com/ http://tomopt.com]. Extensive TOMLAB m-file help is also available, for example ''help penbmiTL ''in Matlab will display the features of the PENBMI solver using the TOMLAB format.

TOMLAB /PENOPT solves

The linear semi-definite programming problem with linear
matrix inequalities is defined as

<math>
\begin{array}{rccccl}
\min\limits_{x} & \multicolumn{5}{l}{f(x) = {c^T}x} \\
& \\
s/t & x_{L} & \leq & x & \leq & x_{U} \\
& b_{L} & \leq & Ax & \leq & b_{U} \\
& \multicolumn{5}{r}{Q^{i}_0 + \Sum{k=1}{n} Q^{i}_{k}x_{k} \preccurlyeq 0,\qquad i=1,\ldots,m.} \\
\end{array}
</math>

where <math>c, x, x_L, x_U \in \MATHSET{R}^n</math>, <math>A \in \MATHSET{R}^{m_l \times n}</math>, <math>b_L,b_U \in \MATHSET{R}^{m_l}</math> and <math>Q^{i}_{k}</math> are symmetric matrices of similar dimensions in each constraint <math>i</math>. If there are several LMI constraints, each may have it's own dimension.

The '''linear semi-definite programming problem with linear matrix inequalities''' ('''sdp''') is defined as are symmetric matrices of similar dimensions in each constraint ''i''. If there are several LMI constraints, each may have it's own dimension.

The '''linear semi-definite programming problem with bilinear matrix inequalities''' ('''bmi''') is defined similarly to but with the matrix following inequality constraints

<math>
Q^{i}_0 + \Sum{k=1}{n} Q^{i}_{k}x_{k} + \Sum{k=1}{n}\Sum{l=1}{n} x_{k}x_{l}K^{i}_{kl} \preccurlyeq 0 \\
</math>

The MEX solvers ''pensdp'' and ''penbmi'' treat '''sdp''' and '''bmi''' problems, respectively. These are available in the TOMLAB /PENSDP and TOMLAB /PENBMI toolboxes.

The MEX-file solver ''pensdp'' available in the TOMLAB /PENSDP toolbox implements a penalty method aimed at large-scale dense and sparse '''sdp''' problems. The interface to the solver allows for data input in the sparse SDPA input format as well as a TOMLAB specific format.

The MEX-file solver ''penbmi ''available in the TOMLAB /PENBMI toolbox is similar to ''pensdp'', with added support for the bilinear matrix inequalities.

The add-on toolbox TOMLAB /PENOPT solves linear semi-definite programming problems with linear and bilinear matrix inequalities. The solvers are listed in Table 2. They are written in a combination of Matlab and C code.

{|class="wikitable"
|+<caption>Solvers in TOMLAB /PENOPT</caption>
!Function||Description
|-valign="top"
|''penbmi''||Sparse and dense linear semi-definite programming using a penalty algorithm.
|-valign="top"
|''penfeas_sdp''||Feasibility check of systems of linear matrix inequalities, using ''pensdp''.
|-valign="top"
|''pensdp''||Sparse and dense linear semi-definite programming using a penalty algorithm.
|-valign="top"
|''penfeas_sdp''||Feasibility check of systems of linear matrix inequalities, using ''pensdp''.
|}

==PENBMI==

TOMLAB /PENBMI was developed in co-operation with PENOPT GbR. The following pages describe the solvers and the feasibility checks.

===penfeas_bmi===

====Purpose====

''penfeas_bmi'' checks the feasibility of a system of bilinear matrix inequalities (BMI):

<math>
A^{0}_i +
\Sum{k=1}{n} A^{(i)}_k x_k +
\Sum{k=1}{n}\Sum{l=1}{n} x_{k} x_{l} K^{(i)}_{kl}
\preccurlyeq 0, \qquad k=1,2,\ldots,m
</math>

with symmetric matrices <math>A_{k}^{i}, K_{kl}^{i} \in \RR^{d_l \times d_l},\,k,l=1,\ldots,n,\,i=1,\ldots,m</math>

====Calling Syntax====

<pre>
[ifeas, feas, xfeas] = penfeas bmi(p, x_0, options)
</pre>

====Description of Inputs====

{|class="wikitable"
!Input||Description
|-valign="top"
|''p''||PENBMI format structure, e.g. from ''sdpa2pen''.
|-valign="top"
|''x_0''||Inital guess of the feasible point. Default = 0.
|-valign="top"
|''options''||Optional 3 ''×'' 1 vector. May be omitted, in which case the defaults below are used.

{|class="wikitable"
|''options(1)''||Output level of PENBMI solver. Default = 0.
|-valign="top"
|''options(2)''||Upper bound on <math>\|x\|_{\infty}</math>. Default = 1000.

If ''< ''0, no box bounds are applied.
|-valign="top"
|''options(3)''||Weighting parameter in the objective function. Default 10-4 .
|}
|}

====Description of Outputs====

{|class="wikitable"
!Output||Description
|-valign="top"
|''ifeas''||Feasibility of the system:

{|class="wikitable"
|-valign="top"
|0||System is strictly feasible
|-valign="top"
|1||System is feasible but not necessarily strictly feasible
|-valign="top"
|-1||System is probably infeasible
|}

|-valign="top"
|''feas''||Value of the minimized maximal eigenvalue of BMI.
|-valign="top"
|''xfeas''||Feasible point
|}

====Algorithm====

The feasibility of the system of BMI's is checked by solving the following '''bmi''' problem:

<math>
\begin{array}{ccccccl}
\min_limits_{x\in\RR^{n},\lambda\in\RR} &
\multicolumn{6}{l}{f(x,\lambda) = \lambda + w \|x\|_2^2} \\
\end{array}
</math>

<math>
\begin{array}{ccccccl}
\mbox{s.t.} & - \xbound & \leq & x & \leq & \xbound \\
& \multicolumn{5}{l}{A_0^i + \Sum{k=1}{n} A_{k}^{i} x_{k}
\preccurlyeq \lambda I_{n \times n},} & i=1,\ldots,m \\
\end{array}
</math>

where ''x''boundis taken from input argument ''options(2)'', or <math>\infty</math> if ''options(2) < ''0.

When <math>\lambda < 0</math>, the system is strictly feasible; when <math>\lambda=0</math>, the system is feasible but has no interior point. When <math>\lambda>0</math> for any ''xbound'', the system may be infeasible.

As the semidefinite problem solved is nonconvex and ''penbmiQ ''is a local method, it cannot be guaranteed that the solution <math>\lambda</math> is a global minimum. Consequently, the (local) optimum <math>\lambda_{toc}</math> found by ''penbmiQ ''may be a positive number (indicating infeasibility), although the system is feasible (i.e., the global optimum <math>\lambda_{glob} < 0</math>). In such a case, the user may try various initial points ''x ''_0, and also different weighting parameter ''w ''(''option(3)'').

In practice, the conditions on feasibility are as follows: <math>\lambda < -10^{-6}</math> means strict feasibility, <math>|\lambda|<10^{-6}</math> means feasibility (not strict) and <math>\lambda > 10^{-6}</math> indicates infeasibility. The user can decide by the actual value of the output parameter ''feas ''(including the optimal <math>\lambda</math>).

For the case when the BMI system is unbounded, we have to add artificial bounds on ''x'', otherwise PENBMI might diverge. Of course, it may happen that the feasible point lies outside these bounds. In this case ''penfeas_bmi'' claims infeasibility, although the system is actually feasible. When in doubts, the user may try to gradually increase ''x''bound (parameter ''options(2)'').

On the other hand, for very ill-conditioned and unbounded systems, the default bound 1000 may be too large and PENBMI may not converge. In this case, the user is advised either to increase the weighting parameter ''w ''(to 0''.''01 and bigger) or to decrease the bound (parameter ''options(2)'') to a smaller number (100-1).

====M-files Used====

''pen.m''

====MEX-files Used====

''penbmiQ''

====See Also====

''penfeas sdp.m''

===penbmiTL===

====Purpose====

Solve (linear) semi-definite programming problems.

''penbmiTL ''solves problems of the form

<math>
\begin{array}{ccccccl}
\min\limits_{x} & \multicolumn{5}{l}{f(x) = c^{T} x} & \\
s/t & x_L & \leq & x & \leq & x_U & \\
{} & b_L & \leq & Ax & \leq & b_U & \\
\multicolumn{7}{l}
{
Q^{(0)}_i +
\Sum{k=1}{n} Q^{(i)}_k x_k +
\Sum{k=1}{n}\Sum{l=1}{n} x_{k} x_{l} K^{(i)}_{kl}
\preceq 0, \qquad k=1,2,\ldots,m
}
\end{array}
</math>

where <math>x,x_L,x_U \in \Rdim{n},\, A \in \Rdim{m_l \times n},\, b_L,b_U
\in \Rdim{m_l}</math> and <math>Q^{(i)}_k</math> are sparse or dense symmetric
matrices. The matrix sizes may vary between different matrix
inequalities but must be the same in each particular constraint.

====Calling Syntax====

<pre>
Result = tomRun('penbmi',Prob,...)
</pre>

====Description of Inputs====

''Prob'' Problem description structure. The following fields are used:

{|class="wikitable"
!Input||Description
|-valign="top"
|''QP.c''||Vector with coefficients for linear objective function.
|-valign="top"
|''A''||Linear constraints matrix.
|-valign="top"
|''b_L''||Lower bound for linear constraints.
|-valign="top"
|''b_U''||Upper bound for linear constraints.
|-valign="top"
|''x_L''||Lower bound on variables.
|-valign="top"
|''x_U''||Upper bound on variables.
|-valign="top"
|''x_0''||Starting point.
|-valign="top"
|''PENOPT''||Structure with special fields for SDP parameters. Fields used are:
|-valign="top"
|''LMI''||Structure array with matrices for the linear terms of the matrix inequalities.

See ''Examples ''on page 17 for a discussion of how to set this correctly.
|-valign="top"
|''ioptions''||8 ''× ''1 vector with options, defaults in (). Any element set to a value less than zero will be replaced by a default value, in some cases fetched from standard Tomlab parameters.
{|class="wikitable"
|''ioptions(1)''||0/1: use default/user defined values for options.
|-valign="top"
|''ioptions(2)''||Maximum number of iterations for overall algorithm (50). If not given, ''Prob.optParam.MaxIter'' is used.
|-valign="top"
|''ioptions(3)''||Maximum number of iterations in unconstrained optimization (100). If not given, ''Prob.optParam.MinorIter ''is used.
|-valign="top"
|''ioptions(4)''||Output level: 0/(1)/2/3 = silent / summary / brief / full.
|-valign="top"
|''ioptions(5)''||(0)/1: Check density of Hessian / Assume dense.
|-valign="top"
|''ioptions(6)''||(0)/1: (Do not) use linesearch in unconstrained minimization.
|-valign="top"
|''ioptions(7)''||(0)/1: (Do not) write solution vector to output file.
|-valign="top"
|''ioptions(8)''||(0)/1: (Do not) write computed multipliers to output file.
|}
|-valign="top"
|''foptions''||1 ''× ''7 vector with options, defaults in ().

{|class="wikitablew"
|''foptions(1) ''||Scaling factor linear constraints; must be positive. (1.0).
|-valign="top"
|foptions(2)||Restriction for multiplier update; linear constraints (0.7).
|-valign="top"
|foptions(3)||Restriction for multiplier update; matrix constraints (0.1).
|-valign="top"
|''foptions(4)''||Stopping criterium for overall algorithm (10-7). Tomlab equivalent: ''Prob.optParam.eps_f''.
|-valign="top"
|''foptions(5)''||Lower bound for the penalty parameters (10''-''6 ).||
|-valign="top"
|''foptions(6)''||Lower bound for the multipliers (10-14).
|-valign="top"
|''foptions(7)''||Stopping criterium for unconstrained minimization (10-2).
|}
|}

====Description of Outputs====

''Result ''Structure with result from optimization. The following fields are changed:

{|class="wikitable"
!Output||Description
|-valign="top"
|''x_k''||Optimal point.
|-valign="top"
|''f_k ''||Function value at optimum.
|-valign="top"
|''g_k ''||Gradient value at optimum, ''c''.
|-valign="top"
|''v_k ''||Lagrange multipliers.
|-valign="top"
|''x_0 ''||Starting point.
|-valign="top"
|''f_0 ''||Function value at start.
|-valign="top"
|''xState ''||State of each variable, described in the TOMLAB User's Guide.
|-valign="top"
|''Iter ''||Number of iterations.
|-valign="top"
|''ExitFlag ''||0: OK.

1: Maximal number of iterations reached.

2: Unbounded feasible region.

3: Rank problems. Can not find any solution point.

4: Illegal ''x 0''.

5: No feasible point ''x 0 ''found.
|-valign="top"
|''Inform''||If ''ExitF lag > ''0, ''I nf orm ''= ''ExitF lag''.
|-valign="top"
|''QP.B''||Optimal active set. See input variable ''QP.B''.
|-valign="top"
|''Solver''||Solver used.
|-valign="top"
|''SolverAlgorithm''||Solver algorithm used.
|-valign="top"
|''FuncEv''||Number of function evaluations. Equal to ''Iter''. ''ConstrEv ''Number of constraint evaluations. Equal to ''Iter''. ''Prob ''Problem structure used.
|}

====Description====

''pensdp'' implements a penalty algorithm based on the PBM method of Ben-Tal and Zibulevsky. It is possible to give input data in three different formats:

*Standard sparse SPDA format
*PENSDP Structural format
*Tomlab Quick format

In all three cases, problem setup is done via ''sdpAssign''.

====See Also====

''sdpAssign.m'', ''sdpa2pen.m'', ''sdpDemo.m'', ''tomlab/docs/penbmi.pdf''

====Warnings====

Currently ''penbmi ''does not work well solving problems of '''sdp '''type.

====Examples====

Setting the LMI constraints is best described by an example. Assume 3 variables ''x ''= (''x''1, ''x''2 , ''x''3) and 2 linear matrix inequalities of sizes 3 ''× ''3 and 2 ''× ''2 respectively, here given on block-diagonal form:

<math>
\left(
\begin{array}{c|c}
\begin{array}{ccc} 0 \\ & 0 \\ && 0\end{array}
\\ \hline
& \begin{array}{cc} 0 \\ & 1 \end{array}
\end{array}
\right) +
\left(
\begin{array}{c|c}
\begin{array}{ccc} 2 & -1 & 0 \\ & 2 & 0 \\ && 2\end{array}
\\ \hline & \begin{array}{cc} 1 \\ & -1 \end{array}
\end{array}
\right)x_1
\\ +
\left(
\begin{array}{c|c}
\begin{array}{ccc} 0 \\ & 0 \\ && 0\end{array}
\\ \hline & \begin{array}{cc} 3 \\ & -3 \end{array}
\end{array}
\right)x_2 +
\left(
\begin{array}{c|c}
\begin{array}{ccc} 2 & 0 &-1 \\ & 2 & 0 \\ && 2\end{array}
\\ \hline & \begin{array}{cc} 0 \\ & 0 \end{array}
\end{array}
\right)x_3 \preceq 0
</math>

The ''LMI'' structure could then be initialized with the following commands:

<pre>
% Constraint 1
>> LMI(1,1).Q0 = [];
>> LMI(1,1).Q = [2 -1 0 ; ...
0 2 0 ; ...
0 0 2];
>> LMI(1,2).Q = [];
>> LMI(1,3).Q = [2 0 -1 ; ...
0 2 0 ; ...
0 0 2];

% Constraint 2, diagonal matrices only
>> LMI(2,1).Q0 = diag( [0, 1] );
>> LMI(2,1).Q = diag( [1,-1] );
>> LMI(2,2).Q = diag( [3,-3] );
>> LMI(2,3).Q = [ ];

% Use LMI in call to sdpAssign:
>> Prob=sdpAssign(c,LMI,...)

% ... or set directly into Prob.PENSDP.LMI field:
>> Prob.PENSDP.LMI = LMI;
</pre>

Some points of interest:

*The ''LMI'' structure must be of correct size. This is important if a LMI constraint has zero matrices for the highest numbered variables. If the above example had zero coefficient matrices for ''x''3 , the user would have to set LMI(1,3).Q = [] explicitly, so that the ''LMI ''structure array is really 2 ''× ''3. (LMI(2,3).Q would automatically become empty in this case, unless set otherwise by the user).

*MATLAB sparse format is allowed and encouraged.

*Only the upper triangular part of each matrix is used (symmetry is assumed).

Input in Sparse SDPA Format is handled by the conversion routine ''sdpa2pen''. For example, the problem defined in ''tomlab/examples/arch0.dat-s ''can be solved using the following statements:

<pre>
>> p = sdpa2pen('arch0.dat-s')
p =
vars: 174
fobj: [1x174 double]
constr: 174
ci: [1x174 double]
bi_dim: [1x174 double]
bi_idx: [1x174 double]
bi_val: [1x174 double]
mconstr: 1
ai_dim: 175
ai_row: [1x2874 double]
ai_col: [1x2874 double]
ai_val: [1x2874 double]
msizes: 161
ai_idx: [175x1 double]
ai_nzs: [175x1 double]
x0: [1x174 double]
ioptions: 0
foptions: []

>> Prob = sdpAssign(p); % Can call sdpAssign with only 'p' structure
>> Result = tomRun('pensdp',Prob); % Call tomRun to solve problem
</pre>

==PENSDP==

TOMLAB /PENSDP was developed in co-operation with PENOPT GbR. The following pages describe the solvers and the feasibility checks.

===penfeas_sdp===

====Purpose====

''penfeas_sdp ''checks the feasibility of a system of linear matrix inequalities (LMI):

<math>
A_0^i + \Sum{k=1}{n} A_{k}^{i} x_{k} \preccurlyeq 0, \qquad i=1,\ldots,m
</math>

with symmetric matrices

<math>
A_{k}^{i} \in \RR^{d_l \times d_l}, \, k=1,\ldots,n, i=1,\ldots,m
</math>

and

<math>
x \in \RR^{n}
</math>

====Calling Syntax====

<pre>
[ifeas, feas, xfeas] = penfeas sdp(p, options)
</pre>

====Description of Inputs====

{|class="wikitable"
!Input||Description
|-valign="top"
|''p''||PENSDP format structure, e.g. from ''sdpa2pen''.
|-valign="top"
|''options''||Optional 2 ''× ''1 vector. May be omitted, in which case the defaults below are used.
|-valign="top"
|''options(1)''||Output level of PENSDP solver. Default = 0.
|-valign="top"
|''options(2)''||Upper bound on ''x 8 ''. Default = 1000.

If ''< ''0, no box bounds are applied.
|}

====Description of Outputs====

{|class="wikitable"
!Output||Description
|-valign="top"
|''ifeas''||Feasibility of the system:
|-valign="top"
|0||System is strictly feasible
|-valign="top"
|1||System is feasible but not necessarily strictly feasible
|-valign="top"
|-1||System is probably infeasible
|-valign="top"
|''feas''||Value of the minimized maximal eigenvalue of LMI.
|-valign="top"
|''xfeas''||Feasible point
|}

====Algorithm====

The feasibility of the system of LMI's is checked by solving the following '''sdp '''problem:

<math>
\begin{array}{ccccccl}
\min\limits_{x\in\RR^{n},\lambda\in\RR} &
\multicolumn{6}{l}{f(x,\lambda) = \lambda} \\
\end{array}
</math>

<math>
\begin{array}{ccccccl}
\mbox{s.t.} & - \xbound & \leq & x & \leq & \xbound \\
& \multicolumn{5}{l}{A_0^i + \Sum{k=1}{n} A_{k}^{i} x_{k}
\preccurlyeq \lambda I_{n \times n},} & i=1,\ldots,m \\
\end{array}
</math>

where ''xbound'' is taken from input argument ''options(2)'', or <math>\infty if \VAR{options(2)} <0</math>.

When <math>\lambda < 0</math>, the system is strictly feasible; when ''? ''= 0, the system is feasible but has no interior point.

When <math>\lambda=0</math> for any <math>x_{bound}</math>, the system is infeasible.

In practice, the conditions on feasibility are as follows:
<math>\lambda < -10^{-6}</math> means strict feasibility,
<math>|\lambda|<10^{-6}</math> means feasibility (not strict) and
<math>\lambda > 10^{-6}</math> indicates infeasibility.

The user can decide by the actual value of the output parameter ''feas ''(including the optimal <math>\lambda</math>).

For the case when the LMI system is unbounded, we have to add artificial bounds on ''x'', otherwise PENSDP might diverge. Of course, it may happen that the feasible point lies outside these bounds. In this case ''penfeas sdp ''claims infeasibility, although the system is actually feasible. When in doubts, the user may try to gradually increase ''x''bound (parameter ''options(2)''). On the other hand, for very ill-conditioned and unbounded systems, the default bound 1000 may be too large and PENSDP may not converge. In this case, the user is advised to decrease parameter ''options(2) ''to a smaller number (100-1).

====M-files Used====

''pen.m''

====MEX-files Used====

''pensdp''

====See Also====

''penfeas bmi.m''

===pensdpTL===

====Purpose====

Solve (linear) semi-definite programming problems.

''pensdpTL ''solves problems of the form

<math>
\begin{array}{ccccccl}
\min\limits_{x} & \multicolumn{5}{l}{f(x) = c^{T} x} & \\
\\
s/t & x_L & \leq & x & \leq & x_U & \\
{} & b_L & \leq & Ax & \leq & b_U & \\
\\
& \multicolumn{3}{l}{Q^{(0)}_i + \sum_{k=1}^{n} Q^{(i)}_k x_k}
& \preceq & 0, & k=1,2,\ldots,m_{LMI} \\
\end{array}
</math>

where <math>x,x_L,x_U \in \Rdim{n},\, A \in \Rdim{m_l \times n},\, b_L,b_U
\in \Rdim{m_l}</math> and <math>Q^{(i)}_k</math> are sparse or dense symmetric matrices. The matrix sizes may vary between different linear matrix inequalities (''LMI'') but must be the same in each particular constraint.

====Calling Syntax====

<pre>
Result = tomRun('pensdp',Prob,...)
</pre>

====Description of Inputs====

''Prob ''Problem description structure. The following fields are used:

{|class="wikitable"
!Input||Description
|-valign="top"
|''QP.c''||Vector with coefficients for linear objective function.
|-valign="top"
|''A ''||Linear constraints matrix.
|-valign="top"
|''b_L ''||Lower bound for linear constraints.
|-valign="top"
|''b_U ''||Upper bound for linear constraints.
|-valign="top"
|''x_L ''||Lower bound on variables.
|-valign="top"
|''x_U ''||Upper bound on variables.
|-valign="top"
|''x_0 ''||Starting point.
|-valign="top"
|''PriLevOpt ''||Print level in ''pensdpTL ''and MEX interface. The print level in the solver is controlled by ''PENOPT.ioptions(4)''.
|-valign="top"
|''PENOPT ''||Structure with special fields for SDP parameters. Fields used are:
|-valign="top"
|''LMI ''||Structure array with matrices for the linear matrix inequalities. See ''Examples'' on page 17 for a discussion of how to set this correctly.
|-valign="top"
|''ioptions ''||8 ''× ''1 vector with options, defaults in (). Any element set to a value less than zero will be replaced by a default value, in some cases fetched from standard Tomlab parameters.

{|class="wikitable"
|''ioptions(1) ''||0/1: use default/user defined values for options.
|-valign="top"
|''ioptions(2) ''||Maximum number of iterations for overall algorithm (50). If not given,

''Prob.optParam.MaxIter ''is1u5sed.
|-valign="top"
|''ioptions(3)''||Maximum number of iterations in unconstrained optimization (100). If not given, ''Prob.optParam.MinorIter ''is used.
|-valign="top"
|''ioptions(4)''||Output level: 0/(1)/2/3 = silent/summary/brief/full. Tomlab parameter: ''Prob.PriLevOpt''.
|-valign="top"
|''ioptions(5)''||(0)/1: Check density of Hessian / Assume dense.
|-valign="top"
|''ioptions(6)''||(0)/1: (Do not) use linesearch in unconstrained minimization. ''ioptions(7) ''(0)/1: (Do not) write solution vector to output file. ''ioptions(8) ''(0)/1: (Do not) write computed multipliers to output file.
|}

|-valign="top"
|''foptions''||7 ''× ''1 vector with optimization parameters, defaults in ():

{|class="wikitable"
|''foptions(1)''||Scaling factor linear constraints; must be positive. (1.0).
|-valign="top"
|''foptions(2)''||Restriction for multiplier update; linear constraints (0.7).
|-valign="top"
|''foptions(3)''||Restriction for multiplier update; matrix constraints (0.1).
|-valign="top"
|''foptions(4)''||Stopping criterium for overall algorithm (10-7). Tomlab equivalent: ''Prob.optParam.eps_f''.
|-valign="top"
|''foptions(5)''||Lower bound for the penalty parameters (10-6).
|-valign="top"
|''foptions(6)''||Lower bound for the multipliers (10-14).
|-valign="top"
|''foptions(7)''||Stopping criterium for unconstrained minimization (10-2).
|}

|}

====Description of Outputs====

''Result ''Structure with result from optimization. The following fields are changed:

{|class="wikitable"
!Output||Description
|-valign="top"
|''x_k''||Optimal point.
|-valign="top"
|''f_k''||Function value at optimum.
|-valign="top"
|''g_k''||Gradient value at optimum, ''c''.
|-valign="top"
|''v_k''||Lagrange multipliers.
|-valign="top"
|''x_0''||Starting point.
|-valign="top"
|''f_0''||Function value at start.
|-valign="top"
|''xState''||State of each variable, described in the TOMLAB User's Guide.
|-valign="top"
|''Iter''||Number of iterations.
|-valign="top"
|''ExitFlag''||0: OK.

1: Maximal number of iterations reached.

2: Unbounded feasible region.

3: Rank problems. Can not find any solution point.

4: Illegal ''x 0''.

5: No feasible point ''x 0 ''found.
|-valign="top"
|''Inform''||If ''ExitF lag > ''0, ''I nf orm ''= ''ExitF lag''.
|-valign="top"
|''QP.B''||Optimal active set. See input variable ''QP.B''.
|-valign="top"
|''Solver''||Solver used.
|-valign="top"
|''SolverAlgorithm''||Solver algorithm used.
|-valign="top"
|''FuncEv''||Number of function evaluations. Equal to ''Iter''. ''ConstrEv ''Number of constraint evaluations. Equal to ''Iter''. ''Prob ''Problem structure used.
|}

====Description====

''pensdp ''implements a penalty algorithm based on the PBM method of Ben-Tal and Zibulevsky. It is possible to give input data in three different formats:

*Standard sparse SPDA format
*PENSDP Structural format
*Tomlab Quick format

In all three cases, problem setup is done via ''sdpAssign''.

====See Also====

''sdpAssign.m'', ''sdpa2pen.m'', ''sdpDemo.m'', ''tomlab/docs/pensdp.pdf'', ''penfeas sdp.m''

====Examples====

Setting the LMI constraints is best described by an example. Assume 3 variables <math>x=(x_1,x_2,x_3)</math> and 2 linear matrix inequalities of sizes 3 ''× ''3 and 2 ''× ''2 respectively, here given on block-diagonal form:

<math>
\left(
\begin{array}{c|c}
\begin{array}{ccc} 0 \\ & 0 \\ && 0\end{array}
\\ \hline
& \begin{array}{cc} 0 \\ & 1 \end{array}
\end{array}
\right) +
\left(
\begin{array}{c|c}
\begin{array}{ccc} 2 & -1 & 0 \\ & 2 & 0 \\ && 2\end{array}
\\ \hline & \begin{array}{cc} 1 \\ & -1 \end{array}
\end{array}
\right)x_1
\\ +
\left(
\begin{array}{c|c}
\begin{array}{ccc} 0 \\ & 0 \\ && 0\end{array}
\\ \hline & \begin{array}{cc} 3 \\ & -3 \end{array}
\end{array}
\right)x_2 +
\left(
\begin{array}{c|c}
\begin{array}{ccc} 2 & 0 &-1 \\ & 2 & 0 \\ && 2\end{array}
\\ \hline & \begin{array}{cc} 0 \\ & 0 \end{array}
\end{array}
\right)x_3 \preceq 0
</math>

The ''LMI'' structure should then be initialized with the following commands:

<pre>
% Constraint 1
>> LMI(1,1).Q0 = [];
>> LMI(1,1).Q = [2 -1 0 ; ...
0 2 0 ; ...
0 0 2];
>> LMI(1,2).Q = [];
>> LMI(1,3).Q = [2 0 -1 ; ...
0 2 0 ; ...
0 0 2];

% Constraint 2, diagonal matrices only
>> LMI(2,1).Q0 = diag( [0, 1] );
>> LMI(2,1).Q = diag( [1,-1] );
>> LMI(2,2).Q = diag( [3,-3] );
>> LMI(2,3).Q = [ ];

% Use LMI in call to sdpAssign:
>> Prob=sdpAssign(c,LMI,...)

% ... or set directly into Prob.PENSDP.LMI field:
>> Prob.PENSDP.LMI = LMI;
</pre>

Some points of interest:

*The ''LMI'' structure must be of correct size. This is important if a LMI constraint has zero matrices for the highest numbered variables. If the above example had zero coefficient matrices for ''x''3 , the user would have to set LMI(1,3).Q = [] explicitly, so that the ''LMI ''structure array is really 2 ''× ''3. (LMI(2,3).Q would automatically become empty in this case, unless set otherwise by the user).
*MATLAB sparse format is allowed and encouraged.
*Only the upper triangular part of each matrix is used (symmetry is assumed).

Input in Sparse SDPA Format is handled by the conversion routine ''sdpa2pen''. For example, the problem defined in ''tomlab/examples/arch0.dat-s ''can be solved using the following statements:
<pre>
>> p = sdpa2pen('arch0.dat-s')
p =
vars: 174
fobj: [1x174 double]
constr: 174
ci: [1x174 double]
bi_dim: [1x174 double]
bi_idx: [1x174 double]
bi_val: [1x174 double]
mconstr: 1
ai_dim: 175
ai_row: [1x2874 double]
ai_col: [1x2874 double]
ai_val: [1x2874 double]
msizes: 161
ai_idx: [175x1 double]
ai_nzs: [175x1 double]
x0: [1x174 double]
ioptions: 0
foptions: []

>> Prob=sdpAssign(p); % Can call sdpAssign with only 'p' structure
>> Result=tomRun('pensdp',Prob); % Call tomRun to solve problem
</pre>

PENOPT - Revision history

Elias at 21:00, 19 January 2012

Elias at 10:53, 15 December 2011

Elias: Created page with "==Introduction== ===Overview=== Welcome to the TOMLAB /PENOPT User's Guide. TOMLAB /PENOPT includes either PENSDP or PENBMI (depends on the license) and interfaces between The ..."

← Older revision		Revision as of 17:00, 19 January 2012
Line 31:		Line 31:
	==Using the Matlab Interface==		==Using the Matlab Interface==

	The main routines in the two-layer design of the interface are shown in ~~<xr id="tab~~:~~interfaceRoutines" />~~. Page and section references are given to detailed descriptions on how to use the routines.		The main routines in the two-layer design of the interface are shown in [[#Table: The interface routines.]]. Page and section references are given to detailed descriptions on how to use the routines.

			====Table: The interface routines.====

	~~<figtable id="tab:interfaceRoutines">~~
	{\|class="wikitable"		{\|class="wikitable"
	~~\|+<caption>The interface routines.</caption>~~
	~~\|-valign="top"~~
	!Function\|\|Description		!Function\|\|Description
	\|-valign="top"		\|-valign="top"
Line 47:		Line 46:
	\|[[#penfeas_sdp\|penfeas_sdp]]\|\|The layer two TOMLAB interface routine that calls ''pen.m''. Converts the input ''P rob ''format before calling ''pensdp.dll ''and converts back to the output ''Result ''structure.		\|[[#penfeas_sdp\|penfeas_sdp]]\|\|The layer two TOMLAB interface routine that calls ''pen.m''. Converts the input ''P rob ''format before calling ''pensdp.dll ''and converts back to the output ''Result ''structure.
	\|}		\|}
	~~</figtable>~~

	The PENOPT control parameters are possible to set from Matlab.		The PENOPT control parameters are possible to set from Matlab.