1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
function [x,Z,ul,info,time] = ...
sp(F,blck_szs,c,x0,Z0,nu,abstol,reltol,tv,maxiters);
% [x,Z,ul,info,time] = ...
% sp(F,blck_szs,c,x0,Z0,nu,abstol,reltol,tv,maxiters);
%
% 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
%
% 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
%
% Input arguments:
% - F: matrix with m+1 columns,
% F = [ F_0^1(:) F_1^1(:) ... F_m^1(:) ]
% [ F_0^2(:) F_1^2(:) ... F_m^2(:) ]
% [ ... ... ... ]
% [ F_0^L(:) F_1^L(:) ... F_m^L(:) ]
% F_i^j is the jth diagonal block of F_i.
% F_1, ..., F_m must be linearly independent.
% NOTE: F will be modified by symmex if terminated by an
% interrupt.
% - blck_szs: L-vector with dimensions of the diagonal blocks
% the jth block of F ( F_i^j has dimension blck_szs(j) ).
% - c: m-vector, specifies primal objective.
% - x0: m-vector, strictly primal feasible.
% - Z0: [ Z0^1(:); ... ; Z0^L(:) ]
% must be strictly dual feasible.
% - nu: >= 1.0. Controls rate of convergence.
% - abstol: absolute tolerance.
% - reltol: relative tolerance. Has a special meaning when negative.
% - tv: target value (see above).
% - maxiters: >= 0, max. number of iterations
%
% Output arguments:
% - x, Z: last primal and dual iterate
% - ul: ul(1) is c'*x; ul(2) is -Tr F_0*Z
% - info: 'maxiters exceeded', 'target reached',
% 'unachievable target', 'relative accuracy reached',
% or 'absolute accuracy reached'
% - time: [ user time (sec.), system time (sec.), no of iters ]
|
