-
Notifications
You must be signed in to change notification settings - Fork 1
/
readme.txt
354 lines (246 loc) · 11.7 KB
/
readme.txt
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
SparsePOP
(A Sparse SemiDefinite Programming Relaxation of
Polynomial Optimization Problems)
Hayato Waki, Sunyoung Kim, Masakazu Kojima,
Masakazu Muramatsu, Hiroshi Sugimoto and Makoto Yamashita
----------------------------------------
Index
1. Overview
2. System Requirements
3. Installation Guide
4. Usage of SparsePOP
5. Acknowledgements
6. License
7. E-mail address
8. History
----------------------------------------
1. Overview
SparesPOP is a MATLAB package for a sparse semidefinite
programming (SDP) relaxation method for approximating a
global optimal value and solution of a polynomial optimization
problem (POP) proposed by Waki et al. The sparse SDP relaxation
exploits a sparse structure of polynomials in POPs when applying
"a hierarchy of LMI relaxations of increasing dimensions" by
Lasserre. The efficiency of SparsePOP to approximate optimal
solutions of POPs is thus increased, and larger scale POPs can
be handled.
Two versions of SparsePOP are available in this package:
(A) MATLAB only version
(B) MATLAB with C++ version
(A) will always be installed, while (B) is optional.
The functions and capabilities of the two versions are identical.
Some of time-consuming parts of (B) is coded in C++, thus, it is
faster in generating SDP problems than (A). We recommend to use (B)
whenever possible, although in many cases (A) is sufficient.
2. System Requirements
The following software packages are required for SparsePOP.
i. MATLAB R2009b or later for Mac OSX
MATLAB R2008a or later for Linux
ii. SeDuMi, SDPT3, SDPA or CDP
to call SeDuMi from SparsePOP for solving an SDP relaxation problem
If you want to use (B), then you need appropriate C++ compilers,
compatible with MATLAB, to compile the programs.
NOTE: If Symbolic Math Toolbox is available on your computer,
SparsePOP can handle a gms file which contains parentheses,
e.g. Bex2_1_2.gms.
NOTE2: If Optimization Toolbox 4.0 or later is available on your
computer, you can refine approximated solutions of SparsePOP by
using some functions in Optimization Toolbox. See Section 3.4 in
User Manual for more detail.
NOTE3: We recommend to install Xcode to compile mex files if
you use SparsePOP on Mac OSX. In particular, llvm-gcc and llvm-g++
in Xcode are available for compiling mex files in SparsePOP. See the
following webpage for the detail:
http://www.mathworks.com/matlabcentral/answers/103258-mex-on-mavericks-with-r2012b
NOTE4: SeDuMi in Github (2014-08-14) has two bugs to use it. We list
two modifications of SeDuMi:
(1) Remove % in the head of the 792nd line in sedumi.m
(2) Replace the 77th line in eigK.m by
lab(li+1:li+nl) = x(xi+1:xi+nl);
3. Installation Guide
See install.txt in the top directory of SparsePOP. After installing
SparsePOP, add the path of SparsePOP in your MATLAB search path.
4. Usage of SparsePOP
We assume that SDPA and/or SeDuMi have been already installed on
your computer and that the paths of SparsePOP, their folders and
subfolders have been already added in your Matlab search path.
The usage of SparsePOP is explained in the user manual in the
top directory of SparsePOP.
If you get the error message like ``Invalid MEX File Errors”, you
restart your matlab with LD_PRELOAD=``the path of your libstdc++.so”,
e.g.,
$ LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libstdc++.so.6 matlab
5. Acknowledgments
The authors are grateful to Dr. Mevissen Martine,
Mr. Dan Gugenheim, Mr. Victor Magron, Dr. Hanne Ackermann
and Mr. Ye Wang for bug reports.
6. License
This software is distributed under GNU General Public License 2.0
7. E-mail address
kojima-spop@is.titech.ac.jp
Please send a message if you have any questions, ideas, or
bug reports.
8. History
Version 3.03 (Septermber 11, 2018)
(1) Modified sdpSolve.m and m-files in Solvers.
(2) Modified readGMS.m
(3) SDPNAL++ is available to solve the genrated SDP
relaxation problems. Recommend MATLAB R2014b or later.
Version 3.02 (December 30, 2016)
(1) Modified readGMS.m to deal with gms file which contains some
white spaces.
(2) Modified readGMS.m to deal with gms file which contains
parenthesises.
Version 3.01 (October 10, 2015)
(1) SparsePOP automatically adds the paths of the directory and
subdirectories.
Version 3.00 (September 30, 2014)
(1) SparsePOP returns a lucid message when it cannot allocate
an array due to the integer overflow.
(2) Modified simplifyPolynomial.m. Since output of built-in function
`unique' in MATLAB changed from R2013a or later, this function returned
a wrong result.
(3) Implemented a reduction method described in the following paper:
``AN EXTENSION OF THE ELIMINATION METHOD FOR A SPARSE SOS POLYNOMIALby
H. Waki and M. Muramatsu''
This method works in only MATLAB by setting param.reduceMomentMatSW = 2.
** This method works in only MATLAB when param.reduceMomentMatSW = 2 **
** is set. We recommend to use this parameter for small POPs with **
** the number of variables involved in POP up to 70. **
(4) Add a parameter for reducing the moment matrices more aggressively.
Any candidate for solution of POP may not be retrieved, while a smaller
SDP relaxation problems may be obtained. In fact, this reduction may be
remove some SDP variables which correspond to variables in the original
POP.
** This reduction works in both MATLAB and C++ when **
** param.aggressiveSW = 1 **
** Combining param.reduceMomentMatSW = 1 or 2 with this, a much **
** smaller SDP relaxation may be obatined. **
(5) Implemented an SDP relaxation described in the following paper:
``A Perturbed Sums of Squares Theorem for Polynomial Optimization and
its Applications by H. Waki, M. Muramatsu and L. Tuncel''
** This method works in only MATLAB by setting param.sparseSW = 2 **
** and 3. **
** param.sparseSW = 2 for a smaller SDP relax. based on Lasserre **
** param.sparseSW = 3 for a smaller SDP relax. based on Sparse SDP **
** relaxation. **
(6) Fix bugs reported by users
Version 2.99 (February 15, 2012)
(1) SparsePOP can be compiled by mex on Windows 7 with Visual Stadio 2010.
(2) Some elements of the structure SDPinfo returned
from SDPrelaxation.m and SDPrelaxationMex.m are changed:
[Add]
SDPinfo.SeDuMiA: the coefficient matrix A in the SDP with the SeDuMi format
SDPinfo.SeDuMib: the coefficient vector b in the SDP with the SeDuMi format
SDPinfo.SeDuMic: the objective vector c in the SDP with the SeDuMi format
SDPinfo.SeDuMiK: the cone K in the SDP with the SeDuMi format
SDPinfo.objeConstant: trans.objVonstant
SDPinfo.objValScale: trans.objValScale
SDPinfo.Amat: trans.Amat
SDPinfo.bVect: trans.bVect
[Delete]
SDPinfo.K, SDPinfo.A, SDPinfo.b, SDPinfo.c, SDPinfo.K.f, SDPinfo.J.
(3) We checked that SparsePOP can be compiled under a Windows machine with
Microsoft Visual C++ 7.0 or later.
(4) The previous version of readGMS.m recognized the expression `+ - 0.5'
as 0.5, not -0.5. We fixed this bug. The current version read it as `-0.5'.
(5) symamd in SDPrelaxationMex.m returns a segmentation fault for a POP with
unused variables. We fixed this bug.
Version 2.98 (December 15, 2011)
(1) Fixed a bug in readGMS.m. The previous version could not read
the monomials which are located after the keyword ``objvar".
(2) Fixed a bug in deleteVar.m. The previous version might substitute
some fixed values incorrectly for POPs whose lower and upper bounds are
identical.
(3) Some functions for scaling POPs with polynomial sdp constraints
do not work in the current version.
(4) SparsePOP with param.mex=1 returns the same format as param.mex=0
when users set param.detailedInfFile.
Version 2.97 (September 30, 2011)
(1) Fixed a bug in substituteEq.m.
(2) Improved output of information on SDPNAL in solveBySDPNAL.m
and SDPT3 in solveBySDPT3.m.
Version 2.96 (August 31, 2011)
(1) Fixed bugs in compileSparsePOP.m and gen_basisindecies
in conversion.cpp.
(2) Improved the part of checking the linear independency of
the coefficient matrix A.
Version 2.95 (July 30, 2011)
(1) For POPs which have constraints "x in {0,1}" and/or
"x in {-1, +1}", SparsePOP can reduce the size of the
resulting SDP relaxation problem by exploiting their
constraints. This reduction is based on the following paper:
J.B.Lasserre, "An explicit equivalent positive semidefinite
program for nonlinear 0-1 programs", SIAM J.Optim., 12,
pp. 756--769.
* For the reduction for a POP which has constraint "x in {0, 1}",
set param.binarySW = 1.
* For the reduction for a POP which has constraint "x in {-1, +1}",
set param.SquareOneSW = 1.
However, these reductions do not work when user computes error
bounds of an approximated solution obtained by SparsePOP.
(2) The reductions executed by reduceMomentMatSW = 1 and/or
reduceAMatSW = 1 work when user computes error bounds of an
approximated solution obtained by SparsePOP.
(3) We move "class pop_params" from conversion.h into Parameters.h.
(4) Some bugs are fixed.
Version 2.90 (June 21, 2011)
(1) SparsePOP can read the reserved keyword "maximizing objvar"
and "binary variables".
If an input file contains the keyword "maximizing objvar",
then SparsePOP deals with the POP as the maximization problem.
In addition, if an input file contains the keyword
"binary variables", then SparsePOP adds the polynomial
equality x(i)^2 -x(i) = 0 in the original POP for such variables x(i).
(2) Some gams files in GLOBAL Library are added in the directory
example/GMSformat.
(3) In the case where some variables in SDP relaxation problem
corresponding to variables in a given POP are removed by
setting param.reduceMomentMatSW = 1, SparsePOP returns only
the optimal value of the resulting SDP relaxation problem.
(In the previous version, for such a POP, SparsePOP did not
solve the SDP relaxation problem.)
(4) Some bugs are fixed.
Version 2.85 (May 23, 2011)
(1) Some bugs in C++ files are fixed.
The latest sparsepop can handle POPs which contain polynomial
matrix inequalities by setting param.mex = 1.
Version 2.80 (Feburary 7, 2011)
(1) Users can use SDPA, SeDuMi, SDPT3, CSDP and SDPNAL for solving
SDP relaxation problems. Users can tune up paramters of the SDP
solvers by editing files in the subdirectory
SparsePOP280/subPrograms/Mfiles/Solvers.
(2) Small bugs in C++ files are fixed.
Version 2.60 (May 9, 2010)
(1) Add some functions for computing error bounds based on the paper
M. Kojima and M. Yamashita, "Enclosing Ellipsoids and Elliptic
Cylinders of Semialgebraic Sets and Their Application to Error
Bounds in Polynomial Optimization", November 2009.
Version 2.50 (March 30, 2010)
(1) readGMS.m can print lucid error messages for some incorrect
gms files.
(2) The directory example/SDPAformat is removed.
(3) Some bugs are fixed.
Version 2.20 (August 20, 2009)
(1) Users can use SDPA instead of SeDuMi for solving an SDP
relaxation problem. See `readmeRevision.txt' for more detail.
Version 2.15 (June 22, 2009)
(1) The function for writing an SDP as the sdpa sparse
format is modified and included into the function
solveBySeDuMi.m
(2) SparsePOP outputs a file which contains information
on scaling for a given POP. See `readmeRevision.txt' for
more detail.
Version 2.10 (April 3, 2009)
(1) SparsePOP can accept a new input format for a
constrained nonlinear least square problem.
(2) To refine approximated solution obtained by SparsePOP,
users can call some functions in Optimization Toolbox. See
`readmeRevision.txt' for more detail.
Version 2.00 (June, 2007)
(1) For speedup, C++ subroutines are developed.
(2) The second version (B) of SparsePOP are added in
SparsePOP.
(3) Improve user interface.
(4) Some bugs are fixed.
Version 1.20 (September, 2005)