SparsePOP : a Sparse Semidefinite Programming Relaxation of Polynomial Optimization Problems
Hayato Waki⋆, Sunyoung Kim†, Masakazu Kojima‡, Masakazu Muramatsu♯ and Hiroshi Sugimoto♭
August 2007
Abstract.
SparesPOP is a MATLAB implementation of the sparse semidefinite programming (SDP) relaxation method for approximating a global optimal solution of a polynomial optimiza- tion problem (POP) proposed by Waki, Kim, Kojima and Muramatsu. 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. For numerical comparison, a test set of POPs from the literature are available at http://www.is.titech.ac.jp/∼kojima/SparsePOP where the software package SparesPOP can also be downloaded.
Key words.
Polynomial optimization problem, sparsity, global optimization, sums of squares optimiza- tion, semidefinite programming relaxation, MATLAB software package
⋆ Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152-8552 Japan. Hay- ato.Waki@is.titech.ac.jp
† Department of Mathematics, Ewha W. University, 11-1 Dahyun-dong, Sudaemoon- gu, Seoul 120-750 Korea. The research was supported by Kosef R01-2005-000- 10271-0. skim@ewha.ac.kr
‡ Department of Mathematical and Computing Sciences, Tokyo Institute of Technol- ogy, 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152-8552 Japan. Research supported by Grant-in-Aid for Scientific Research on Priority Areas 16016234 and by Grant- in-Aid for Scientific Research (B) 19310096. kojima@is.titech.ac.jp
♯ Department of Computer Science, The University of Electro-Communications, Chofugaoka, Chofu-Shi, Tokyo 182-8585 Japan. Research supported in part by Grant-in-Aid for Young Scientists (B) 15740054. muramatu@cs.uec.ac.jp
♭ Department of Mathematical and Computing Sciences, Tokyo Institute of Technol- ogy, 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152-8552 Japan.
1 Introduction
We introduce a Matlab package, SparsePOP for finding global optimal solutions of poly- nomial optimization problems (POPs). An important feature of SparsePOP is ability to exploit the sparsity of POPs so that it can handle POPs of increased dimension. The package is an implementation of the sparse semidefinite programming (SDP) relaxation method for POPs in [18], proposed to improve the efficiency of Lasserre’s hierarchy of LMI relaxations of increasing dimensions [10]. For related work, see [6, 9].
Let Rn and Zn+ denote the n-dimensional Euclidean space and the set of nonnegative integer vectors, respectively. A real-valued polynomial fk(x) in x = (x1, x2, . . . , xn)∈ Rn is expressed as
fk(x) = ∑ α∈Fk
ck(α)xα, x∈ Rn, ck(α) ∈ R, Fk⊂ Zn+
(k = 0, 1, 2, . . . , m), where xα = xα11xα22· · · xαnn for every x = (x1, x2, . . . , xn) ∈ Rn and every α∈ Zn+. We consider a POP of the following form:
minimize f0(x)
subject to fk(x)≥ 0 (k = 1, 2, . . . , ℓ), fk(x) = 0 (k = ℓ + 1, . . . , m), lbdi ≤ xi ≤ ubdi (i = 1, 2, . . . , n),
(1)
where −∞ ≤ lbdi <∞ and −∞ < ubdi ≤ ∞ (i = 1, 2, . . . , n). The optimal value of the POP (1) is denoted by ζ∗.
SparsePOP employs the procedure of constructing an SDP relaxation problem with given parameters, solving it using SeDuMi [13] or SDPA [7], and reporting a global optimal solu- tion or a lower bound of the POP (1). If the obtained solution is not accurate, SparsePOP can be applied again with different values of the parameters to attain an optimal solution of higher accuracy. The computational efficiency of solving (1) thus depends on how the SDP relaxation problem is constructed and solved. We note that the size of SDP which can be handled by SDP solvers such as SeDuMi and SDPA is limited, and that this procedure can be applied more than once for an optimal solution for some POPs. As a result, improving computational efficiency is crucial to the success or the failure of getting an optimal solution of (1).
One of deciding factors in the computational efficiency of the SDP relaxation for the POP (1) is the size of the SDP relaxation problem generated from the POP. In the SDP relaxation method proposed by Lasserre, which is implemented in the software GloptiPoly 3 [4, 5], a positive parameter which we call relaxation order determines the size of the SDP relaxation problem of the POP. More precisely, taking a larger value for the relaxation order results in an SDP relaxation problem of increased size. Although theoretical convergence to the optimal value of the POP (1) is proved in [10] as the relaxation order approaching infinity, the SDP relaxation problem whose size grows rapidly with the relaxation order is hard to solve in practice. This is mainly because solving large-scale SDPs by SDP solvers still remains a computational challenge [8, 12, 15, 16].
The SDP relaxation problem constructed by SpsesePOP is different from the SDP relax- ation problem by [10] in that the correlative sparsity [18] of the POP (1) is extracted from
the objective and constrained polynomials and utilized so that the size of SDP relaxation problem can be reduced. We call the SDP relaxation employed in SparsePOP the sparse SDP relaxation. Theoretical convergence of the sparse SDP relaxation to the optimal value of correlatively sparse POPs [11] supports the use of the sparse SDP relaxation. Sparse- POP also provides the parameters to choose the sparse SDP relaxation or the (dense) SDP relaxation by [10].
Numerical experiments with SparsePOP and GloptiPoly 3 show differences in the number of variables of POPs that can be handled: for example, it is very difficult to solve a POP with more than 20 variables by GloptiPoly 3 while SparsePOP can solve larger-sized POPs.
Indeed, SparsePOP can solve POPs up to 1000 variables if given POPs exactly satisfy the correlative sparsity. The accuracy of the obtained optimal solution by the sparse SDP relaxation is not necessarily as good as the one by the SDP relaxation in [5] in general, however, optimal solutions of desired accuracy are obtained for many problems in practice.
Numerical comparison between SparsePOP and GloptiPoly 3 is discussed in Section 4.
SparsePOP provides various parameters to control the way of solving a given POP. This helps us deal with various POPs more efficiently by specifying the values of parameters depending on the POPs. More precisely, the parameters are aimed to choose the SDP relaxation, reduce numerical difficulties, send necessary parameters to SDP solvers, and control output files. The default values of the parameters are also provided.
This paper is organized as follows. In Section 2, we give a brief introduction of the sparse SDP relaxation [18] for POPs. Section 3 describes the structure of SparsePOP together with a simple execution example for SparsePOP. In Section 4, numerical results comparing SparsePOP and GloptiPoly 3 are shown, and Section 5 contains concluding remarks.
2 SDP relaxation of POPs using csp graphs
We briefly explain the sparse SDP relaxation problem of the POP (1) used in SparsePOP. For simplicity of discussions, the POP (1) considered here does not have equality constraint, any lower bound and any upper bound on the variables xi (i = 1, 2, . . . , n); ℓ = m, lbdi =−∞
and ubdi =∞ (i = 1, 2, . . . , n). See [18] for details of more general cases.
Let N ={1, 2, . . . , n}. For every k = 1, 2, . . . , m, let
Fk ={i ∈ N : αi ≥ 1 for some α ∈ Fk} .
The sparsity of the POP (1) is considered by constructing a graph G(N, E) representing the sparsity structure of (1). More specifically, a pair {i, j} with i ̸= j selected from the node set N is an edge or {i, j} ∈ E if and only if either there is an α ∈ F0 such that αi > 0 and αj > 0 or i, j ∈ Fk for some k = 1, 2, . . . , m. The graph G(N, E) is called s a correlative sparsity pattern (csp) graph. By construction, each Fk is a clique of G(N, E) (k = 1, 2, . . . , m). We then generate a chordal extension G(N, E′) of G(N, E). (See, for example, [1] for the definition and basic properties of chordal graphs). Let C1, C2, . . . , Cp be the maximum cliques of G(N, E′). Note that C1, C2, . . . , Cp can be easily computed because G(N, E′) is a chordal graph.
For every C ⊂ N and ψ ∈ Z+, define ACψ =
{
α∈ Zn+: αj = 0 if j̸∈ C, ∑
i∈C
αi ≤ ψ }
,
and let u(x,ACψ) denote a
( #C + ψ ψ
)
-dimensional column vector consisting of the mono- mials xα (α∈ ACψ), where #C denotes the number of elements in C. We assume that the elements xα (α∈ ACψ) in the vector u(x,ACψ) are arranged according to lexicographically increasing order of α’s. Notice that 0 ∈ ACψ; hence the first element of the column vector u(x,ACψ) is always x0 = 1.
For every k = 0, 1, 2, . . . , m, let ωk =⌈deg(fk(x))/2⌉,
ωmax= max{ωk : k = 0, 1, . . . , m}, (2) and let eCk be the union of some of the maximal cliques C1, C2, . . . , Cp of G(N, E′) such that Fk ⊂ Cj.
To derive an SDP relaxation problem, the POP (1) is first transformed into an equivalent polynomial SDP (PSDP)
minimize f0(x)
subject to u(x,ACωe−ωk k)u(x,ACωe−ωk k)Tfk(x) ≽ O (k = 1, 2, . . . , m), u(x,ACωℓ)u(x,ACωℓ)T ≽ O (ℓ = 1, 2, . . . , p)
(3)
with some relaxation order ω ≥ ωmax. Here B ≽ O denotes that a real symmetric ma- trix B is positive semidefinite. The size of symmetric matrix u(x,ACωe−ωk k)u(x,ACωe−ωk k)T is
( # eCk+ ω− ωk
ω− ωk
)
×
( # eCk+ ω− ωk
ω− ωk
)
(k = 1, 2, . . . , m), and the size of symmetric matrix u(x,ACωℓ)u(x,ACωℓ)T is
( #Cℓ+ ω ω
)
×
( #Cℓ+ ω ω
)
(ℓ = 1, 2, . . . , p). The sym- metric matrices u(x,ACωe−ωk k)u(x,ACωe−ωk k)T and u(x,ACωℓ)u(x,ACωℓ)T are positive semidefi- nite for any x ∈ Rn, and have the element 1 in their upper-left corner. These ensure the equivalence between the POP (1) and the PSDP (3).
We note that the reduction technique proposed in [9] is used to further reduce the size of the supports ACωek−ωk (k = 1, . . . , m) and ACωℓ (ℓ = 1, . . . , p) by elimination redundant elements in the supports.
Since the objective function of the PSDP (3) is a real-valued polynomial and the left hand side of the matrix inequality constraints of the PSDP (3) are real symmetric matrix valued polynomials, we can rewrite the PSDP (3) as
minimize ∑ α∈fF
˜
c0(α)xα subject to Lk(0, ω)− ∑
α∈fF
Lk(α, ω)xα≽ O (k = 1, . . . , m), Mℓ(0, ω)− ∑
α∈fF
Mℓ(α, ω)xα≽ O (ℓ = 1, . . . , p),
for some eF ⊂ Zn+\{0}, ˜c0(α)∈ R (α ∈ eF) and real symmetric matrices Lk(α, ω), Mℓ(α, ω) (α ∈ eF ∪ {0}, (k = 1, . . . , m) (ℓ = 1, . . . , p)). Note that the size of the matrices
Lk(α, ω), Mℓ(α, ω) (α ∈ eF ∪ {0}, (k = 1, . . . , m) (ℓ = 1, . . . , p)) and the number of monomials xα (α∈ eF) are determined by the relaxation order ω.
Each monomial xαis replaced by a single real variable yα, and we have an SDP relaxation problem of the POP (1):
minimize ∑ α∈fF
˜
c0(α)yα
subject to Lk(0, ω)− ∑ α∈fF
Lk(α, ω)yα≽ O (k = 1, . . . , m), Mℓ(0, ω)− ∑
α∈fF
Mℓ(α, ω)yα ≽ O (ℓ = 1, . . . , p),
(4)
which can be solved by standard SDP solvers [13, 14, 17]. We call each Lk(0, ω) −
∑
α∈fFLk(α, ω)yαa localizing matrix, and each Mℓ(0, ω)−∑
α∈fF Mℓ(α, ω)yα a moment matrix.
The SDP relaxation problem (4) is solved by SeDuMi in the numerical experiment in Section 4. The problem is formulated as the dual standard form
maximize bTs subject to c− ATs≽ 0. (5) Here each column index of AT (hence each row index of A) corresponds to an α ∈ eF, s the column vector of yα (α ∈ eF) and b the column vector of −˜c0(α) (α ∈ eF). Note that the coefficient matrices Lk(α, ω) and Mℓ(α, ω) (α∈ eF ∪ {0}) are reshaped into column vectors and arranged in c and −AT.
From the solution obtained by SeDuMi, we can find an approximate solution. Let ζω denote the optimal objective value of the SDP (4), and yαω (α ∈ eF) an optimal solution of the SDP (4). We extract yαω (α ∈ {ei : i ∈ N}), which are induced from the variable xi
(i ∈ N) in the original POP (1), to form an approximate optimal solution xω of the POP (1):
xω = (xω1, xω2, . . . , xωn), xωi = yei (i∈ N).
The relation ζω ≤ ζω′ ≤ ζ∗ ≤ f0(x) holds if ωmax ≤ ω ≤ ω′and if x∈ Rnis a feasible solution of the POP (1). (Recall that ζ∗ denotes the optimal value of the POP (1)). Therefore, if f0(xω)− ζω is zero (or sufficiently small) and if xω satisfies (or approximately satisfies) the constraints fk(x)≥ 0 (k = 1, 2, . . . , m), then xω is an optimal solution (or an approximate optimal solution, respectively) of the POP (1). Theoretically, ζω converges ζ∗ under a moderate assumption [11].
The relaxation order ω, which corresponds to the parameter param.relaxOrder used in SparsePOP, determines both the quality and the size of the SDP relaxation problem (4) of the POP (1). We expect to obtain an approximate optimal solution of the POP (1) with higher accuracy (more precisely, not lower accuracy) by solving the SDP relaxation problem (4) as a larger value is chosen for ω. In practice, however, the size of the SDP relaxation problem (4) becomes larger and the cost of solving the SDP relaxation problem (4) increases very rapidly. Therefore, we usually start the SDP relaxation problem (4) with
Input POP and parameters
readGMS.m GAMS scalar format
SparsePOP format
Check POP and parameters
SDPrelaxation.m
Solve SDP by SeDuMi
printSolution.m param.mex=0
param.mex=1
Print Information SDPrelaxationMex.m
Figure 1: The structure of the main function sparsePOP.m
the relaxation order ω = ωmax, and successively increase ω by 1 if the approximate solution xω obtained is not accurate.
We mention that SparsePOP can solve POPs with polynomial equality constraints, lower, and upper bounds for the variables xi (i ∈ N) as in the POP (1), and also an unconstrained POP that only objective polynomial f0(x) is specified.
3 Structure of SparsePOP
As the structure of the software package SparsePOP is illustrated in Figure 1, SparsePOP accepts a POP of the form (1) as input, and outputs solution information and statistics.
The main part constructs a sparse SDP relaxation problem of the POP and uses SeDuMi to obtain an approximate global optimal solution.
SparsePOP accepts two types of input format: GAMS scalar format [2] or SparsePOP format. SparsePOP format is a set of MATLAB structure and its example is shown in Appendix. The GAMS scalar format is written in a text file. If the name of a file that contains a POP in the GAMS scalar format is given to SparsePOP, readGMS.m reads the file to convert data into SparsePOP format. It is followed by the procedure of checking the correctness of the input POP and parameters, and an SDP relaxation problem is pro- duced by SDPrelaxation.m or SDPrelaxationMex.m depending on the value specified in the parameter param.mex. The speed of SDPrelaxationMex.m in C++ is much faster than Matlab code SDPrelaxation.m, therefore, it is recommended to use SDPrelaxationMex.m when C++ compiler is available. After the SDP relaxation problem is solved by SeDuMi, in- formation and statistics on the obtained solution are printed. At last, information obtained
through the process are returned.
We present a simple example in the GAMS scalar format.
minimize x2 subject to x21 + x22 ≥ 1, x2 ≥ (x1 − 0.5)2. (6) The feasible region of the problem is shown in Figure 2. It is easy to see that the problem (6) has two local optima, and the global optimal solution is (0.97435569, 0.22501332). The optimal value is 0.22501332.
Figure 2: POP (6)
The problem can be described as follows in a file named popexample.gms:
Variables x1,x2,objvar;
Equations e1,e2,e3;
e1.. -x2 + objvar =E= 0;
e2.. x1^2 + x2^2 =G= 1;
e3.. x1^2 + x1- x2 =L= -0.25;
Note that the example is in the GAMS scalar format and the variable objvar is to be minimized by SparsePOP.
SparsePOP is executed by typing the following command to the MATLAB interpreter:
>> [param, SDPobjvalue, POP] = sparsePOP(’popexample.gms’);
The output is printed on the screen as follows.
SparsePOP 2.00 by H.Waki, S.Kim, M.Kojima, M.Muramatsu and H.Sugimoto June 2007
## Computational Results by sparsePOP.m with SeDuMi ##
## Printed by printSolution.m ##
# Problem File Name = popexample.gms
# parameters:
relaxOrder = 1
sparseSW = 1
mex = 0
# SDP solved by SeDuMi: # Approximate optimal value info:
size of A = [5,11] SDPobjValue = +1.7651391e-10
no of nonzeros in A = 13 POP.objValue = +1.2392345e-10 no of LP variables = 2 relative obj error= +5.259e-11 no of FR variables = 0 POP.absError = -7.500e-01
no of SDP blocks = 1 POP.scaledError = -3.750e-01 max size SDP block = 3 # cpu time:
ave.size SDP block = 3.00e+00 cpuTime.conversion= 0.08
# SeDuMi information: cpuTime.SeDuMi = 0.14
SeDuMi.pars.eps = 1.00e-09 cpuTime.total = 0.28
SeDuMiInfo.numerr = 0 # Approximate optimal solution info:
SeDuMiInfo.pinf = 0 POP.xVect
SeDuMiInfo.dinf = 0 =1:-5.0000336e-01 2:+1.2392345e-10 It shows parameter values used, statistics of the SDP relaxation, information given by SeDuMi, information on an approximate optimal solution, and statistics on CPU times.
In the output, we notice the relaxation order 1 was used. The return values param, SDPobjValue, and POP contain the actual parameters used in the execution, the optimal value of the SDP relaxation problem from SeDuMi, which is a lower bound for the example, various information and statistics on the solution, respectively.
We know that the value 1.2392345e-10 returned as SDPobjValue is not an optimal value, rather a lower bound, which can also be observed with the values for POP.absError and POP.scaledError. This indicates that the sparse SDP relaxation problem created with the relaxation order 1 does not provide an accurate optimal solution. In this case, the relaxation order is increased by 1 and SparsePOP is executed again for the example as follows:
>> param.relaxOrder = 2;
>> [param, SDPobjvalue, POP] = sparsePOP(’popexample.gms’,param);
We continue to execute SparsePOP by raising the relaxation order by one until the optimal value is attained. The SDPobjValue obtained with each relaxation order are shown in Table 1.
relaxOrder 1 2 3 4
SDPobjvalue +1.2392345e-10 +2.0101343e-03 +8.8480657e-02 +2.2501332e-01
Table 1: SDPobjValue obtained by increasing the relaxation order
The output of SparsePOP with the relaxation order 4 is shown in Appendix. We notice that the values for POP.absError and POP.scaledError are small. The optimal value of the example was attained because the solution of the example that SparsePOP found was feasible and the objective value was equivalent to the lower bound by the SDP relaxation.
Appendix also includes the SparsePOP format of the example.
4 Comparison between GloptiPoly 3 and SparsePOP
The performance of SparsePOP is compared with GloptiPoly 3 [4] for a set of small-sized constrained problems and a large-sized unconstrained problem selected from [3]. As men- tioned in Section 1, SparsePOP is designed to handle POPs efficiently by utilizing the
correlative sparsity of POPs and thus reducing the size of the resulting SDP relaxation, while GloptiPoly 3 is mostly aimed at small-scale problems as stated in [5]. Numerical re- sults obtained by SparsePOP compared with other software packages including GloptiPoly on test problems from [3] can be found in [18] where the accuracy of the obtained optimal solution and cpu time were shown.
The focus of numerical comparison presented here is to show how much reduction occurs in the size of A in (5) as a result of exploiting the sparsity of POPs. We note that SeDuMi is an implementation of the primal-dual interior-point method and the sparsity of A also plays an important role for solving an SDP relaxation problem. We show cpu time, the size and the nonzero elements of matrix A, which determine the computational efficiency of solving (5) by SeDuMi.
All the numerical experiments were performed on PowerMac G5 2.5Ghz, MacOSX 10.4.10, 2GB memory.
4.1 Small-sized constrained problems
The test problems for small-sized constrained problems selected from [3] are listed in Table 2.
Since it is difficult to solve POPs with more than 20 variables by GloptiPoly 3, problems with less than 20 variables are chosen to compare the numerical results with SparsePOP.
The column n is the number of variables, and m the number of constraints. We note that a lower and a upper bound are added for every variable of the problem in addition to m constraints.
Problem n m
Bex2 1 3 13 9 Bex2 1 5 10 11 Bex9 2 5 8 7 Balkyl 14 7 Bst bpaf1a 10 10
Table 2: The size of test problems
Problem R.order GloptiPoly 3 SparsePOP
ω cpu sizeA nnzA cpu sizeA nnzA
Bex2 1 3 2 224.43 2379× 17885 24532 0.42 134× 1146 2251 Bex2 1 5 2 18.42 1000× 8107 21516 1.85 285× 4167 17576
Bex9 2 5 2 7.15 362× 3612 5141 0.58 130× 799 1201
Balkyl 2 ∗583.42 3059× 21890 29673 ∗1.03 203× 1344 1903 3 ∗∗12.12 38759× 890828 1279257 9.61 834× 10066 14124 Bst bpaf1a 2 36.37 1000× 7986 14380 1.04 195× 1920 4494
Table 3: GloptiPoly 3 vs. SparsePOP
Table 3 shows the numerical results obtained by GloptiPoly 3 and SparsePOP. The column of R.order indicates the relaxation order ω described in Section 2, the numbers in the column of cpu show cpu time in seconds, and sizeA and nnzA mean the size and the number of nonzero elements of A in (5), respectively.
For all problems but Balkyl, optimal solutions were obtained with the relaxation order 2 by both GloptiPoly 3 and SparsePOP. For Balkyl problem, the relaxation order 2 did not provide an optimal solution of desired accuracy. A single asterisk mark in the row of Balkyl problem and the relaxation order 2 means that neither GloptiPoly 3 nor SparsePOP could obtain an optimal solution of POP, although it obtained an optimal solution of the corresponding SDP relaxation problem. Increasing the relaxation order to 3 for Balkyl problem resulted in an optimal solution. A double asterisk mark for Balkyl in the column of GloptiPoly 3 indicates that SeDuMi could not finish solving the SDP relaxation problem due to out-of-memory error, and the number shown with the double asterisk mark is cpu time for generating the SDP relaxation problem. It shows that Balkyl problem was impossible to solve with the relaxation order 3 with GloptiPoly 3 because the size of the resulting SDP relaxation problem was too large to handle by SeDuMi. We observe that the size of the SDP relaxation problem produced by SparsePOP is much smaller than that by GloptiPoly 3, as a result, an optimal solution is obtained with the relaxation order 3. This is the main advantage of utilizing the sparsity of POPs.
Both GloptiPoly 3 and SparsePOP use SeDuMi to solve the SDP relaxation problem.
If we compare cpu time consumed by GloptiPoly 3 and SparsePOP for the problems that can be solved with the relaxation order 2, we notice that SparsePOP spends much less cpu time than GloptiPoly 3. This is because the sizes of the SDP relaxation problems generated by SparsePOP are significantly smaller than those by GloptiPoly 3, which is a result of exploiting the sparsity in SparsePOP.
As an illustrative example, we show how the correlative sparsity is used to reduce the size of the SDP relaxation problem (4) for Bex9 2 5. The problem Bex9 2 5 is
minimize x21− 4x1+ x22 − 6x2+ 13 subject to x1− 2x2+ x3 = 1,
−2x1+ x2 + x4 = 2, 2x1+ x2 + x5 = 14,
x3x6 = 0, x4x7 = 0, x5x8 = 0, 2x1+ x6 − 2x7+ 2x8 = 10, 0≤ x2 ≤ 8, 0 ≤ xi ≤ 10 (i ̸= 2).
We mention that some lower and upper bounds are added to the original problem ex9 2 5 from [3] to improve the performance of the SDP relaxation. See Section 5.6 of [18]. The following is the csp matrix of the problem:
∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗
∗ ∗ ∗ ∗ ∗
∗ ∗ ∗ ∗
∗ ∗ ∗ ∗
∗ ∗ ∗ ∗
∗ ∗ ∗ ∗ ∗
∗ ∗ ∗ ∗ ∗
∗ ∗ ∗ ∗ ∗
.
A graph G(N, E) with N = {1, 2, . . . , 8} can be constructed corresponding to this csp matrix as described in Section 2. After extending the csp graph G(N, E) to a chordal graph G(N, E′), the following 4 cliques are found: {1, 2, 3, 6}, {1, 2, 4, 7}, {1, 2, 5, 8}, and {1, 2, 6, 7, 8}. Notice that (2, 6), (2, 7), (2, 8) elements are fill-ins.
We compare the size of the matrices in (4) used in SparsePOP and GloptiPoly 3. Note that (4) includes two types of matrices, the localizing matrices and the moment matrices, which have been defined as the linearization of
u(x,ACωek−ωk)u(x,ACωe−ωk k)Tfk(x)≽ O (k = 1, 2, . . . , m), and
u(x,ACωℓ)u(x,ACωℓ)T ≽ O (ℓ = 1, 2, . . . , p),
respectively. (Recall the derivation of the SDP relaxation (4) by linearizing the polynomial SDP (3)). In the case of Bex9 2 5, we see ωk = 1 (0, 1, 2, . . . , 7); hence ωmax = 1 by (2). We take the relaxation order ω = 2 ≥ ωmax = 1. The size of the largest clique is 5, and the size of the corresponding moment matrix with the relaxation order ω = 2 is ( 5 + 2
2 )
×
( 5 + 2 2
)
= 21× 21. The size of the other 3 moment matrix is
( 4 + 2 2
) ( ×
4 + 2 2
)
= 15× 15. For the size of the localizing matrices, we let eCk = {1, 2, 3, 6} (k = 1, 4), eCk ={1, 2, 4, 7} (k = 2, 5), eCk = {1, 2, 5, 8} (k = 3, 6), and eC7 = {1, 2, 6, 7, 8}. The size of the largest localizing matrix is
( 5 + 1 1
)
×
( 5 + 1 1
)
= 6× 6 and the size of the other 6 localizing matrices is 5× 5. Therefore, the size of the largest matrix, among the localizing and moment matrices, is 21× 21.
If the sparsity is not used as in GloptiPoly 3, then eCk = Cℓ = N (k = 1, 2, . . . , 7) (ℓ = 1) where N ={1, 2, . . . , 8}. The size of the moment matrix is thus
( 8 + 2 2
)
×
( 8 + 2 2
)
= 45× 45, and the sizes of the 7 localizing matrices are
( 8 + 1 1
)
×
( 8 + 1 1
)
= 9× 9.
Since out-of-memory error frequently occurs when solving large-sized problems, we com- pare memory space needed to store all the moment and the localizing matrices using the correlative sparsity to those generated without using the sparsity for Bex9 2 5. From ((21 · 21) + 3(15 · 15) + 6 · 6 + 6(5 · 5))/((45 · 45) + 7(9 · 9)) ≈ 0.5, the matrices gener- ated using the correlative sparsity takes a smaller amount of space.
We now examine the difference in the number of variables of the SDP relaxation problem (4) using the sparsity and without using the sparsity. If the sparsity is not exploited in constructing (4), the number of variables is
( 8 + 4 4
)
− 1 = 494 from
( n + 2ω 2ω
)
− 1, where ω is the relaxation order and −1 for a constant. The number of variables for the SDP relaxation problem using the correlative sparsity is not easy to compute because some of monomials appear more than once in the constraints of (3) and the same monomials in the different constraints can be linearized independently in (4). When solving the problem using SparsePOP, we can find the actual number of variables using the correlative sparsity, which is 230.
It is shown in Table 3 that the number of variables yα (α ∈ eF) of the SDP relaxation problem (4) for Bex9 2 5, or the number of rows of the coefficient matrix A in its SeDuMi
input format (5), is 130, not 230. This is because the reduction technique [9] mentioned in Section 2 is used to further reduce the number of variables by removing redundant variables. In fact, the reduction technique can be applied by setting a parameter called param.reduceMomentMatrix to 1 in SparsePOP. We also notice that the number of variables used in GloptiPoly 3 is 362, not 494, which indicates that a reduction technique is also employed in GloptiPoly 3.
4.2 A Large-sized unconstrained problem
The chained wood function is tested to compare GloptiPoly 3 and SparsePOP on a large unconstrained problem. The following chained wood function is minimized.
fcw(n)(x) = 1 +∑
i∈J
{100(xi+1− xi)2+ (1− xi+1)2+ 90(xi+3− xi+2)2
+(1− xi+2)2+ 10(xi+1+ xi+3− 2)2+ 0.1(xi+1− xi+3)2} ,
where J = {1, 3, 5, . . . , n − 3}, and n, a multiple of 4, is the number of variables. Table 4 shows the results for n = 8, 16, . . . , 256. All the problems were solved with the relaxation order 2. The numbers in the column of “gen” and “sol” show cpu time in seconds for generating and solving the SDP relaxation problem. The combined cpu time of “gen” and
“sol” is shown in the column of “total”.
Note that GloptiPoly 3 could not handle the problem of n > 16; it did not work for n = 20 due to out-of-memory error. We see that minimizing the chained wood function with n = 256 is solved by SparsePOP. In fact, SparsePOP can solve the problem with n = 1000 as shown in [18]. The csp matrix for the chained wood function is a banded matrix with band-width 7, and the size of the cliques is 7. Thus, the difference in the size of A between SparsePOP and GloptiPoly 3 becomes larger as n increases.
GloptiPoly 3 SparsePOP (mex= 1) SparsePOP (mex= 0)
n gen sol total gen sol total gen sol total
8 0.59 4.27 4.86 0.03 0.21 0.25 0.59 0.22 0.82 16 1.45 2832.0 2833.4 0.05 0.28 0.33 0.41 0.27 0.70
32 −− −− −− 0.14 0.58 0.42 1.00 0.43 1.45
64 −− −− −− 0.48 1.03 1.56 2.57 1.05 3.67
128 −− −− −− 2.82 2.15 5.18 7.29 2.11 9.58
256 −− −− −− 16.77 4.43 21.95 28.91 4.34 33.99
Table 4: Chained-Wood Function
In SparsePOP, the procedure of constructing the polynomial SDP (3) and converting it to the SDP relaxation problem for SeDuMi is coded both in Matlab and C++ so that a user can choose C++ code to reduce the execution time. In Table 4, mex= 1 and mex= 0 indicate the use of C++ code and Matlab code, respectively. It displays that the cpu time for generating SDP relaxation problem using the C++ version is much less than that of Matlab version.
5 Concluding remarks
We have described the structure and the usage of the software package SparsePOP. The com- putational performance of SparsePOP is compared with GloptiPoly 3 on several small-sized problems and a large-sized problems from [3]. Extensive numerical results with SparsePOP were shown in [18]. Although test problems presented here do not include all the prob- lems in [18], similar differences in the size A and computing time between SparsePOP and GloptiPoly 3 are expected. In particular, for unconstrained problems such as the Broyden tridiagonal function and the extended Rosenbrock function shown in [18], numerical results similar to Table 4 can be shown.
Solving POPs has been known difficult mainly because the size of SDP relaxation prob- lems of POPs becomes increasingly large as the degree and the number of variables of POPs grow. In addition, numerical difficulties occur for various reasons. In view of the size of problems that can be handled, SparsePOP is one of the most successful software packages to address these issues among currently available software packages. Main advantage comes from constructing the SDP relaxation problem of reduced size by utilizing the correlative sparsity of POPs. Specifically, we note that unconstrained problems with 1000 variables has been solved using the sparsity. But the solvability heavily depends on the correlative sparsity, or more precisely the size of the maximal cliques of a chordal extension of the correlative sparsity pattern graph of a given POP, and the degree of polynomials. If both of them are small, for instance, the size of the maximal cliques ≤ 5 and the degree of polyno- mials ≤ 4, the number of variables of solvable problems by SparsePOP could be more than 1000. If the correlative sparsity is not found, SparsePOP can efficiently solve constrained POPs with 10− 30 variables.
References
[1] J. R. S. Blair and B. Peyton, “An introduction to chordal graphs and clique trees”, in Graph Theory and Sparse Matrix Computation, A. George, J. R. Gilbert and J. W. H.
Liu, eds., Springer-Verlag, New York, 1993, pp. 1-29.
[2] GAMS HomePage, http://www.gams.com/
[3] GLOBAL Library, http://www.gamsworld.org/global/globallib.htm [4] GlopotiPoly 3, http://www.laas.fr/~henrion/software/gloptipoly3/
[5] D. Henrion and J. B. Lasserre, “GloptiPoly: Global optimization over polynomials with Matlab and SeDuMi”, ACM Transaction on Mathematical Software, 29, 2 (2003) 165-194.
[6] S. Kim, M. Kojima and H. Waki, “Generalized Lagrangian duals and sums of square relaxation of sparse polynomial optimization problems”, SIAM J. Optimization 15 (2005) 697–719.
[7] K. Fujisawa, M. Kojima, K. Nakata SDPA (SemiDefinite Programming Algorithm) user’s manual, Version 5.0, Research Report B-308, Dept. of Mathematical and Com-
puting Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152-8552, Japan (1995).
[8] M. Fukuda, M. Kojima, K. Murota and K. Nakata, “Exploiting sparsity in semidef- inite programming via matrix completion I: general framework”, SIAM Journal on Optimization 11 (2001) 647–674.
[9] M. Kojima, S. Kim and H. Waki, “Sparsity in sums of squares of polynomials”, Math- ematical Programming 103 (2005) 45-62.
[10] J. B. Lasserre: Global optimization with polynomials and the problems of moments, SIAM Journal on Optimization 11 (2001) 796–817.
[11] J. B. Lasserre: Convergent SDP-relaxations in polynomial optimization with sparsity, to appear in SIAM Journal on Optimization.
[12] K. Nakata, M. Yamashita, K. Fujisawa, and M. Kojima, A Parallel Primal-Dual Interior-Point Method for Semidefinite Programs Using Positive Definite Matrix Com- pletion, Parallel Computing, 32 (2006) 24-43.
[13] J. F. Strum, “SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones”, Optimization Methods and Software, 11 & 12 (1999) 625-653.
[14] R. H Tutuncu, K. C. Toh, and M. J. Todd, “Solving semidefinite-quadratic-linear programs using SDPT3”, Mathematical Programming 95 (2003) 189–217.
[15] K.C. Toh and M. Kojima, “Solving some large scale semidefinite programs via the conjugate residual method’, SIAM Journal on Optimization 12 (2002) 669–691.
[16] K. C. Toh, “Solving large scale semidefinite programs via an iterative solver on the augmented systems”, SIAM Journal on Optimization 14 (2004) 670–698.
[17] M. Yamashita, K. Fujisawa and M. Kojima, “Implementation and evaluation of SDPA 6.0 (SemiDefinite Programming Algorithm 6.0)” Optimization Methods and Software 18 (2003) 491-505.
[18] H. Waki, S. Kim, M. Kojima, and M. Muramatsu, “Sums of Squares and Semidefi- nite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity”, SIAM J. Optimization 17 (2006) 218–242.
Appendix: An Example of SparsePOP format
We show the SparsePOP format of the example (6):
minimize x2 subject to x21 + x22 ≥ 1, x2 ≥ (x1 − 0.5)2.
SparsePOP format consists of two structures, objPoly and ineqPolySys, and two ar- rays, lbd and ubd. The structures objPoly and ineqPolySys represent objective polynomial and constraint polynomials, respectively, while lbd and ubd are arrays of lower bounds and
upper bounds of variables. A standard way to use SparsePOP format is to make a function returning these four data. The following function popexample.m generates such data for the example (6):
function [objPoly,ineqPolySys,lbd,ubd] = popexample
% minimize x2
objPoly.typeCone = 1;
objPoly.dimVar = 2;
objPoly.degree = 1;
objPoly.noTerms = 1;
objPoly.supports = [0, 1];
objPoly.coef = 1;
% constraint 1: x1^2 + x2^2 - 1 >= 0 ineqPolySys{1}.typeCone = 1;
ineqPolySys{1}.dimVar = 2;
ineqPolySys{1}.degree = 2;
ineqPolySys{1}.noTerms = 3;
ineqPolySys{1}.supports = [2, 0; 0, 2; 0, 0];
ineqPolySys{1}.coef = [1; 1; -1];
% constraint 2: x2 - x1^2 - x1 - 0.25 >= 0 ineqPolySys{2}.typeCone = 1;
ineqPolySys{2}.dimVar = 2;
ineqPolySys{2}.degree = 2;
ineqPolySys{2}.noTerms = 4;
ineqPolySys{2}.supports = [0, 1; 2 0; 1 0; 0 0];
ineqPolySys{2}.coef = [1; -1;-1;-0.25];
% lower and upper bounds lbd = -1.0e+10*ones(1,2);
ubd = 1.0e+10*ones(1,2);
return
Then, we invoke sparsePOP with relaxation order 4 as follows.
>> param.relaxOrder = 4;
>> [param,SDPobjValue,POP] = sparsePOP(’popexample’, param);
The following output is shown on the screen.
SparsePOP 2.00 by H.Waki, S.Kim, M.Kojima, M.Muramatsu and H.Sugimoto June 2007
## Computational Results by sparsePOP.m with SeDuMi ##
## Printed by printSolution.m ##
# Problem File Name = popexample2
# parameters:
relaxOrder = 4
sparseSW = 1
symbolicMath = 0
# SDP solved by SeDuMi:
size of A = [44,425]
no of nonzeros in A = 922 no of LP variables = 0 no of FR variables = 0 no of SDP blocks = 3 max size SDP block = 15
ave.size SDP block = 1.17e+01
# SeDuMi information:
SeDuMi.pars.eps = 1.00e-09 SeDuMiInfo.numerr = 0
SeDuMiInfo.pinf = 0 SeDuMiInfo.dinf = 0
# Approximate optimal value information:
SDPobjValue = +2.2501332e-01 POP.objValue = +2.2501332e-01 relative obj error = +1.016e-10 POP.absError = -3.480e-09 POP.scaledError = -1.740e-09
# cpu time:
cpuTime.conversion = 0.02
cpuTime.SeDuMi = 0.21
cpuTime.total = 0.23
# Approximate optimal solution information:
POP.xVect =
1:+9.7435569e-01 2:+2.2501332e-01
Now we see that (9.7435569e-01, +2.2501332e-01) is the global optimal solution because it is feasible (i.e., POP.scaledError is small enough) and its objective value (POP.objValue) equals to its lower bound (SDPobjValue).
