SieveSDP/readme.txt at master · unc-optimization/SieveSDP · GitHub

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
60
61
62
63
64
65
66
67
68
69
70
71
72
Sieve-SDP ([1]) is a preprocessing algorithm for semidefinite programming of the form

	min. <C, X>
	s.t. A(X) == b
	     X in K

where K is the direct product of R^p, R^q_+ and S^r_+ (Euclidean space, nonnegative orthant, and positive semidefinite cones). It is a MATLAB-based software. For detail, call

	>> help SieveSDP;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% HOW TO FORMULATE A PROBLEM %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The input/output format of Sieve-SDP is Mosek Matlab format ([2, Section 9.7]). To load a problem ``problem.mat” in Matlab, call
	>> prob = load(‘problem.mat’);

If the problem is stored in a different formats supported by Mosek, e.g., Task format, call
	>> [~, res] = mosekopt(['read(problem.task.gz)']);
	>> prob = res.prob;
in order to convert the problem to Mosek Matlab format. To convert it back, call
	>> mosekopt(['min write(problem.task.gz)'], prob);

If the problem is stored in SeDuMi format ([4]), call
	>> prob = convert_sedumi2mosek(problem_A, problem_b, problem_c, problem_K);
in order to convert the problem to Mosek Matlab format. To convert it back, call
	>> [problem_A, problem_b, problem_c, problem_K] = convert_mosek2sedumi(prob);

The folder “test examples” contains 9 datasets saved as .zip files. After unzipping a dataset, you will see SDP problems saved as .mat files. They are already in Mosek Matlab format, which is Sieve-SDP input/output format. They are SDP relaxations of polynomial optimization problems from [6] generated by Gloptipoly 3 ([7]), as one of the datasets tested in [1]. Other datasets tested in [1] include [8] and …

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% HOW TO PREPROCESS A PROBLEM USING SIEVE-SDP %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

To preprocess a problem using SieveSDP, call
	>> [probr, info] = SieveSDP(prob);

If info.infeasible == 1, then problem is infeasible. Otherwise, to solve a reduced problem by Mosek, call
	>> [rcode, res] = mosekopt(‘minimize’, probr);

The problem solution is saved in ‘res’, c.f. [2].

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% HOW TO RECOVER ORIGINAL SOLUTION %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

If solution of original (before-preprocessed) problem is desired, call
	>> [x_original, X_original] = recoveryPrimal(res, info);
where ‘info’ is an output from the call SieveSDP, ‘x_original’ corresponds to linear variables, and ‘X_original’ corresponds to PSD variables.

If solution of original dual problem
	max. <b, y>
	s.t. A^* (y) + Z = C
	     Z in K^*
is desired, set
	>> option.DR = 1;
and call SieveSDP by
	>> [probr, info] = SieveSDP(prob, option);
After solving the problem by Mosek, call
	[y_original, z_original, Z_original, info1] = recoveryDual(res, info);
Dual recovery may not always succeed ([5]). Its success status is saved in ‘info1’.

———-

[1] Y. Zhu, G. Pataki, TD Quoc. Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs. Mathematical Programming Computation 11.3 (2019): 503-586.
[2] http://docs.mosek.com/7.0/toolbox/A_guided_tour.html
[3] http://docs.mosek.com/8.1/matlabfusion/supported-file-formats.html
[4] http://sedumi.ie.lehigh.edu/sedumi/files/sedumi-downloads/SeDuMi_Guide_11.pdf
[5] G. Pataki. Bad semidefinite programs: they all look the same[J]. SIAM Journal on Optimization, 2017, 27(1): 146-172.
[6] Mareike Dressler, Sadik Iliman, and Timo de Wolff. An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming. Journal of Symbolic Computation, 2018.
[7] http://homepages.laas.fr/henrion/software/gloptipoly/
[8] http://plato.asu.edu/ftp/sdp/