[figure]

Polyhedral approximation of the second-order cone: Computational experiments

François Glineur

                     Francois.Glineur@fpms.ac.be

Faculté Polytechnique de Mons Delft University of Technology

HPOPT 99 Rotterdam, June 17, 1999

Polyhedral approximation of the second-order cone: Computational experiments

[figure]

[figure: Outline]

Introduction

⋄ Problem definition

Approximation

⋄ Principle ⋄ Implementation

Test Problems

⋄ Truss topology design ⋄ Convex quadratic optimization ⋄ Computational results ⋄ Accuracy

Concluding remarks

François Glineur, FPMs-TU Delft  Page 2  HPOPT 99, Rotterdam

[figure]

[figure]

Introduction

Second-Order Cone Optimization

Second-order (Lorentz) cone 𝕃^{n} :

𝕃^{n} := {(x_{0}, x) ∈ ℝ_{+} × ℝ^{n} | ∑_{i=1}^{n} x_{i}^{2} ≤ x_{0}^{2}}

General SOCO problem :

min c^{T} x s.t. \{ \begin{matrix}b^{l} ≤ Ax ≤ b^{u}, x^{l} ≤ x ≤ x^{u}, \\ x_{I_{k}} ∈ 𝕃^{n_{k}} ∀k \end{matrix}

with x ∈ ℝ^{n}, I_{k} ⊆ {1, ⋯, n}, #I_{k} = n_{k} + 1 Convex Conic Program, includes

⋄ Linear optimization ⋄ (Convex) Quadratic optimization ⋄ (Convex) Quadratically constrained

quadratic optimization Many applications (robust LO, engineering, portfolio, etc.)

François Glineur, FPMs-TU Delft  Page 3  HPOPT 99, Rotterdam

[figure]

Observation

SOCO software ≪ LO software w.r.t. capability (size) and availability (commercial packages) Idea: try to approximate SOCO with LO, i.e. approximate 𝕃^{n} with a polyhedral cone Π^{n} Accuracy: Π^{n} is an α-approximation of 𝕃^{n} iff

{(x_{0}, x) | ∥x∥ ≤ x_{0}} ⊆ Π^{n} ⊆ {(x_{0}, x) | ∥x∥ ≤ αx_{0}}

Goal: Size of approximation must not increase too much when n increases or α → 1 Direct approach: Circumscribed polyhedral cone ⇒ number of facets exponential in n Ben-Tal & Nemirovski:

⋄ Replace a 𝕃^{n} cone by (n − 1) 𝕃^{2} cones (introducing additional variables)

⋄ Approximate each 𝕃^{2} cone with the

projection of a polyhedral cone

Reference: On polyhedral approximations of the second-order cone, A. Ben-Tal and A. Nemirovsky, technical report, Technion Israel Institute of Technology, 1998

François Glineur, FPMs-TU Delft  Page 4  HPOPT 99, Rotterdam

[figure]

[figure]

Approximation of 𝕃^{n}

Decomposition

Let n even. We have x ∈ 𝕃^{n} iff ∃α, β s.t.

(α, x_{A}) ∈ 𝕃^{\frac{n}{2}} , (β, x_{B}) ∈ 𝕃^{\frac{n}{2}} , (x_{0}, α, β) ∈ 𝕃^{2}

with A = \{1, …, \frac{n}{2}\} and B = \{\frac{n}{2}, …, n\} (due to ∥x∥^{2} = ∥x_{A}∥^{2} + ∥x_{B}∥^{2} ≤ α^{2} + β^{2} ≤ x_{0}^{2}) Let n = 2^{m}. Proceeding recursively, we end up with (n − 1) 𝕃^{2} cones and (n − 2) additional variables (m generations of cones/variables). Easy generalization for any n. If α_{i}-approximation is used for the 𝕃^{2} cones of i^{th} generation, resulting cone has α = ∏_{i=1}^{m} α_{i}

Approximation of 𝕃^{2}

x ∈ 𝕃^{2} ⇔ (\frac{x_{1}}{x_{0}} , \frac{x_{2}}{x_{0}} ) ∈ B^{2} =\{(x, y) | x^{2} + y^{2} ≤ 1\} Approximate the unit disc B^{2} in ℝ^{2} and homogenize the resulting polytope to make an approximating polyhedral cone.

François Glineur, FPMs-TU Delft  Page 5  HPOPT 99, Rotterdam

[figure]

First idea: regular polygon with q inequalities Gives quality α = cos(\frac{π}{q})^{−1} ≈ 1 + \frac{π^{2}}{2q^{2}} ⇒ too expensive (q > 2000 for α = 1 + 10^{−6}) Better idea: use additional variables and project i.e.

x ∈ Π^{2} ⇔ ∃u ∈ ℝ^{m} | (x, u) ∈ P where P is a polytope in ℝ^{3+m} Construction of P Consider the following system

\{ α_{i+1} = α_{i} cos \frac{π}{2^{i}} + β_{i} sin \frac{π}{2^{i}} β_{i+1} = |−α_{i} sin \frac{π}{2^{i}} + β_{i} cos \frac{π}{2^{i}} | , 0 ≤ i < q
\{  \begin{matrix}β_{q} & ≤ & 2 sin \frac{π}{2^{q}} \\ 1 & = & α_{q} cos \frac{π}{2^{q}} + β_{q} sin \frac{π}{2^{q}} \end{matrix}

where q ≥ 1 is a positive parameter. Its projection on (α_{0}, β_{0}) is the boundary of a regular 2^{q}-gon

François Glineur, FPMs-TU Delft  Page 6  HPOPT 99, Rotterdam

[figure]

Figure for q = 3

Take the convex hull and homogenize to get P_{q} ( a = |b| ⟶^{convex hull} a ≥ |b|) Accuracy: α = (cos \frac{π}{2^{q}} )^{−1} ≈ 1 + \frac{π^{2}}{2^{2q+1}} (e.g. α = 1 + 10^{−6} with q = 12) Size: 2q + 1 inequalities, 2q additional variables (small improvement over original construction)

François Glineur, FPMs-TU Delft  Page 7  HPOPT 99, Rotterdam

[figure]

Thus P_{q} := { (x_{0}, α_{0}, β_{0}, …, α_{q}, β_{q}) } s.t.

\{ α_{i+1} = α_{i} cos \frac{π}{2^{i}} + β_{i} sin \frac{π}{2^{i}} β_{i+1} ≥ |α_{i} sin \frac{π}{2^{i}} − β_{i} cos \frac{π}{2^{i}} | for i = 0, … q

\{  \begin{matrix}β_{q} & ≤ & 2 sin \frac{π}{2^{q}} \\ x_{0} & = & α_{q} cos \frac{π}{2^{q}} + β_{q} sin \frac{π}{2^{q}} \end{matrix}

where α_{0} and β_{0} are identified to x_{1} and x_{2}

Combining the cones

For each generation, choose quality q_{i} such that

∏_{i=1}^{m} (cos \frac{π}{2^{q_{i}}} )^{−1} ≤ α

while minimizing total size → P_{α}^{n} ; leads to total number of inequalities and additional variables bounded by O(1)n log \frac{2}{α−1} (optimal) Finally SOCO is approximated by

min c^{T} x s.t. \{ \begin{matrix}b^{l} ≤ Ax ≤ b^{u}, x^{l} ≤ x ≤ x^{u}, \\ (x_{I_{k}}, u_{J_{k}}) ∈ P_{α}^{n} ∀k \end{matrix}

Relaxation arbitrarily close, but guarantee ?

François Glineur, FPMs-TU Delft  Page 8  HPOPT 99, Rotterdam

[figure]

Implementation

⋄ MATLAB 5 on a 233 MHz Pentium PC

⋄ LO and CQO problems solved with the interior-point MOSEK optimizer (E. Andersen)

⋄ SOCO problems solved with the interior-point SeDuMi optimizer (J. Sturm)

We implemented the following procedures

⋄ ApxLor2(q): generates a polyhedral approximation of 𝕃^{2} with q rotation steps

⋄ ApxLorN(n, a): generates a polyhedral approximation of 𝕃^{n} with quality a. Recursive, uses ApxLor2 and a cache of already computed approximations

⋄ ApxLorLP(soc, a): generates an linear approximation of the problem soc with quality a. Each second-order constraint is replaced by its linear approximation given

by ApxLorLP

François Glineur, FPMs-TU Delft  Page 9  HPOPT 99, Rotterdam

[figure]

All q_{i}’s chosen equal ⇒ q = ⌈ log_{2} \frac{π}{arccos α^{−1/m}} ⌉

with total size

O(1)n log \frac{log_{2} n}{α − 1}

[figure]

Test problems

Multi-load truss topology design

min ∑_{i=1}^{n} σ_{i} s.t. \{ \begin{matrix}∥(q_{i1}, …, q_{ik})∥_{2} ≤ σ_{i}, 1 ≤ i ≤ n \\ ∑_{i=1}^{n} q_{il}b_{i} = f_{l}, 1 ≤ l ≤ k \end{matrix}

n = number of bars, k = number of loads, norm minimization problem Dual can be simplified ⇒ QCO problem α-approximation guarantees relative error ϵ on approximated objective such that ϵ ≤ \frac{α−1}{α}

(p^{∗} ≥ p^{∗}(α) ≥ ^{\frac{∑_{i=1}^{n}∥q_{i}^{∗}∥_{2}}{α}} ≥ \frac{p^{∗}}{α})

François Glineur, FPMs-TU Delft  Page 10  HPOPT 99, Rotterdam

[figure]

Computational results

Using random generator by A. Nemirovski Comparison between

⋄ Solving the dual using QCO ⋄ Solving the primal using SOCO up to ϵ

accuracy ⋄ Solving the approximated primal using LO

up to ϵ accuracy Solving the QCO dual always faster → CPU times relative to QCO dual reported Problem p − q − k is with p × q nodal grid (≈ \frac{1}{2}(pq)^{2} bars) and k loading scenarios Observations

⋄ Many small second-order cones ⋄ Expected accuracy attained, often more

than required

François Glineur, FPMs-TU Delft  Page 11  HPOPT 99, Rotterdam

[figure]

Observations

⋄ Approximated primal slower, especially for

larger cones ⋄ Difference between SOCO primal and QCO

dual less important for larger problems ⋄ Increase of CPU time for smaller ϵ larger

for LO than for SOCO

ϵ = 10^{−1} ϵ = 10^{−4} ϵ = 10^{−8}
Prob. SO LO SO LO SO  LO
2-2-4 3.0 2.2 4.0 4.6 5.4  8.0
2-2-8 2.2 3.7 3.0 7.0 4.4 14.6
2-2-16 1.6 6.4 2.2 14.4 3.3 29.4
2-2-32 2.3 13.2 3.1 29.6 4.9 60.7
4-4-3 1.6 7.5 2.3 21.5 2.8 42.4
4-4-4 1.7 18.5 3.0 56.2 4.0 130.6
6-6-4 1.6 12.7 2.0 56.5 2.7 124.3
8-8-2 1.2 4.7 1.6 19.2 1.9 38.2

François Glineur, FPMs-TU Delft  Page 12  HPOPT 99, Rotterdam

[figure]

Convex quadratic problems

min \frac{1}{2}x^{T} Qx + c^{T} x + c_{0} s.t. \{ \begin{matrix}l_{c} ≤ Ax ≤ u_{c} \\ l_{x} ≤ x ≤ u_{x} \end{matrix}

where Q is p.s.d. SOCO model: Let L^{T} L = Q and y ∈ ℝ^{n}, α, β ∈ ℝ additional variables

min \frac{α + β}{2} + c^{T} x + c_{0} s.t. \{ \begin{matrix}l_{c} ≤ Ax ≤ u_{c} \\ l_{x} ≤ x ≤ u_{x} \\ y = Lx \\ β = α + 1 \\ (β, y, α) ∈ 𝕃^{n+1} \end{matrix}

Equivalence because (β, y, α) ∈ 𝕃^{n+1} ⇔ ∥y∥^{2} + α^{2} ≤ β^{2} ⇔ x^{T} L^{T} Lx ≤ α + β

François Glineur, FPMs-TU Delft  Page 13  HPOPT 99, Rotterdam

[figure]

Computational results

Using CQO test set (Maros, Mészáros)

Size QP Approximated QP
Problem  m/n  10^{−1} 10^{−4} 10^{−8}
cvxqp1 s  50/100 .16  2.8  9.7 20.2
dual1  1/85 .27 2.64  6.4 10.8
qstandat 359/1075 .38 3.52 16.7 50.4
dualc1 215/9 .16 .33 .55 .82
primal1  85/325 .33 10.5 34.6 66.7

Observation Approximation slower, even for ϵ = 10^{−1}

But: For problem dualc1, actual relative errors of approximated problems are 9.1 10^{−2}, 1.4 10^{−4} and 1.7 10^{−7} !

François Glineur, FPMs-TU Delft  Page 14  HPOPT 99, Rotterdam

[figure]

Accuracy analysis

To model ∥x∥^{2} ≤ t we use

∥x∥^{2} ≤ t ⇔ (\frac{t + 1}{2}, x, \frac{t − 1}{2}) ∈ 𝕃^{n+1}

But

(\frac{t + 1}{2}, x, \frac{t − 1}{2}) ∈ Π^{n+1}

⇔ x^{2} + \frac{(t − 1)^{2}}{4} ≤ α^{2} \frac{(t + 1)^{2}}{4}
⇔ ∥x∥^{2} ≤ t + (α^{2} − 1)\frac{(t + 1)^{2}}{4}

The ratio \frac{∥x∥^{2}}{t} can be arbitrarily large

\frac{∥x∥^{2}}{t} ≤ 1 + (α^{2} − 1)\frac{(t + 1)^{2}}{4t} ≥ α^{2}

François Glineur, FPMs-TU Delft  Page 15  HPOPT 99, Rotterdam

[figure]

Workaround for QP

⋄ For pure QP use x^{T} Qx = ∥Lx∥^{2} ≤ t^{2} ⋄ When Q is p.d. use

\frac{1}{2}x^{T} Qx + c^{T} x + c_{0} = ∥Lx + l∥^{2} + C ⋄ When Q is p.s.d. ?

François Glineur, FPMs-TU Delft  Page 16  HPOPT 99, Rotterdam

[figure]

[figure]

Concluding remarks

⋄ Clever scheme to approximate 𝕃^{n} with a polyhedral cone

⋄ Computationally less efficient than dedicated solvers

⋄ Same TTD problem 7-8-5 with CPLEX takes 100 sec. with barrier and 8200 sec. with primal simplex

⋄ Cannot always guarantee maximum relative error for the objective in the approximated problem

François Glineur, FPMs-TU Delft  Page 17  HPOPT 99, Rotterdam