Change language to:
Français - 日本語 - Português

See the recommended documentation of this function

Scilab help >> Optimization and Simulation > semidef

# semidef

semidefinite programming

### Calling Sequence

`[x,Z,ul,info]=semidef(x0,Z0,F,blck_szs,c,options)`

### Arguments

x0

m-by-1 real column vector (must be strictly primal feasible, see below)

Z0

L-by-1 real vector (compressed form of a strictly feasible dual matrix, see below)

F

L-by-(m+1) real matrix

blck_szs

p-by-2 integer matrix (sizes of the blocks) defining the dimensions of the (square) diagonal blocks `size(Fi(j)=blck_szs(j) j=1,...,m+1`.

c

m-by-1 real vector

options

a 1-by-5 matrix of doubles `[nu,abstol,reltol,tv,maxiters]`

ul

a 1-by-2 matrix of doubles.

### Description

`semidef` solves the semidefinite program:

and its dual:

exploiting block structure in the matrices `F_i`.

The `Fi's` matrices are stored columnwise in `F` in compressed format: if `F_i^j`, i=0,..,m, j=1,...,L denote the jth (symmetric) diagonal block of `F_i`, then

where `pack(M)`, for symmetric `M`, is the vector `[M(1,1);M(1,2);...;M(1,n);M(2,2);M(2,3);...;M(2,n);...;M(n,n)]` (obtained by scanning rowwise the upper triangular part of `M`).

`blck_szs` gives the size of block `j`, ie, `size(F_i^j)=blck_szs(j)`.

Z is a block diagonal matrix with L blocks ```Z^0, ..., Z^{L-1}```. `Z^j` has size ```blck_szs[j] times blck_szs[j]```. Every block is stored using packed storage of the lower triangular part.

The 1-by-2 matrix of doubles `ul` contains the primal objective value `c'*x` and the dual objective value `-trace(F_0*Z`).

The entries of `options` are respectively:

• `nu`: a real parameter which ntrols the rate of convergence.

• `abstol`: absolute tolerance. The absolute tolerance cannot be lower than 1.0e-8, that is, the absolute tolerance used in the algorithm is the maximum of the user-defined tolerance and the constant tolerance 1.0e-8.

• `reltol`: relative tolerance (has a special meaning when negative).

• `tv`: the target value, only referenced if `reltol < 0`.

• `maxiters`: the maximum number of iterations, a positive integer value.

On output, the `info` variable contains the status of the execution.

• `info=1` if maxiters exceeded,

• `info=2` if absolute accuracy is reached,

• `info=3` if relative accuracy is reached,

• `info=4` if target value is reached,

• `info=5` if target value is not achievable;

• negative values indicate errors.

Convergence criterion is based on the following conditions that is, the algorithm stops if one of the following conditions is true:

• maxiters is exceeded

• duality gap is less than abstol

• primal and dual objective are both positive and duality gap is less than (`reltol` * dual objective) or primal and dual objective are both negative and duality gap is less than (`reltol` * minus the primal objective)

• reltol is negative and primal objective is less than tv or dual objective is greater than `tv`.

### Implementation notes

This function is based on L. Vandenberghe and S. Boyd sp.c program.

### Examples

```F0=[2,1,0,0;
1,2,0,0;
0,0,3,1
0,0,1,3];

F1=[1,2,0,0;
2,1,0,0;
0,0,1,3;
0,0,3,1]

F2=[2,2,0,0;
2,2,0,0;
0,0,3,4;
0,0,4,4];

blck_szs=[2,2];

F01=F0(1:2,1:2);F02=F0(3:4,3:4);
F11=F1(1:2,1:2);F12=F1(3:4,3:4);
F21=F2(1:2,1:2);F22=F2(3:4,3:4);

x0=[0;0]
Z0=2*F0;
Z01=Z0(1:2,1:2);Z02=Z0(3:4,3:4);
FF=[[F01(:);F02(:)],[F11(:);F12(:)],[F21(:);F22(:)]]
ZZ0=[[Z01(:);Z02(:)]];

c=[trace(F1*Z0);trace(F2*Z0)];
options=[10,1.d-10,1.d-10,0,50];

[x,Z,ul,info]=semidef(x0,pack(ZZ0),pack(FF),blck_szs,c,options)

w=vec2list(unpack(Z,blck_szs),[blck_szs;blck_szs]);
Z=sysdiag(w(1),w(2))

c'*x+trace(F0*Z)
spec(F0+F1*x(1)+F2*x(2))
trace(F1*Z)-c(1)
trace(F2*Z)-c(2)```

### References

L. Vandenberghe and S. Boyd, " Semidefinite Programming," Informations Systems Laboratory, Stanford University, 1994.

Ju. E. Nesterov and M. J. Todd, "Self-Scaled Cones and Interior-Point Methods in Nonlinear Programming," Working Paper, CORE, Catholic University of Louvain, Louvain-la-Neuve, Belgium, April 1994.

SP: Software for Semidefinite Programming, http://www.ee.ucla.edu/~vandenbe/sp.html

 << recons Optimization and Simulation vec2list >>