Scilab Function

semidef - semidefinite programming

Calling Sequence

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

Parameters

Description

[x,Z,ul,info]=semidef(x0,Z0,F,blck_szs,c,options) solves semidefinite program:


    minimize    c'*x
    subject to  F_0 + x_1*F_1 + ... + x_m*F_m  >= 0

 and its dual
 
    maximize    -Tr F_0 Z
    subject to  Tr F_i Z = c_i, i=1,...,m
                Z >= 0

   

exploiting block structure in the matrices F_i.

It interfaces L. Vandenberghe and S. Boyd sp.c program.

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

    [ pack(F_0^1)  pack(F_1^1) ...  pack(F_m^1) ]
    [ pack(F_0^2)  pack(F_1^2) ...  pack(F_m^2) ]
F=  [   ...       ...          ...              ]
    [ pack(F_0^L)  pack(F_1^L) ...  pack(F_m^L) ]
   

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 columnwise the lower 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 2 vector ul contains the primal objective value c'*x and the dual objective value -Tr F_0*Z.

The entries of options are respectively: nu = a real parameter which ntrols the rate of convergence. abstol = absolute tolerance. reltol = relative tolerance (has a special meaning when negative). tv target value, only referenced if reltol < 0. iters = on entry: maximum number of iterations >= 0, on exit: the number of iterations taken.

info returns 1 if maxiters exceeded, 2 if absolute accuracy is reached, 3 if relative accuracy is reached, 4 if target value is reached, 5 if target value is not achievable; negative values indicate errors.

Convergence criterion:

 (1) maxiters is exceeded
 (2) duality gap is less than abstol
 (3) 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)
 (4) reltol is negative and
     primal objective is less than tv or dual objective is greater
     than tv
   

Examples