$LastChangedDate: 2008-03-26 09:50:39 +0100 (mer, 26 mar 2008)
$
semidef
semidefinite programming
Calling Sequence
[x,Z,ul,info]=semidef(x0,Z0,F,blck_szs,c,options)
Parameters
x0
m x 1 real column vector (must be strictly primal feasible,
see below)
Z0
L x 1 real vector (compressed form of a strictly feasible dual
matrix, see below)
F
L x (m+1) real matrix
blck_szs
p x 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 x 1 real vector
options
row vector with five entries
[nu,abstol,reltol,0,maxiters]
ul
row vector with two entries
Description
[x,Z,ul,info]=semidef(x0,Z0,F,blck_szs,c,options)
solves semidefinite program:
and its dual:
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
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
-trace(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. Notice that 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.
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:
Examples
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