S -free Sets for Polynomial Optimization
and Oracle-Based Cuts

Daniel Bienstock, Chen Chen, Gonzalo Muñoz, IEOR, Columbia University
May, 2017

SIAM OPT 2017

S -free sets for PolyOpt – 1

Background
The Polyhedral
Approach
Tightening P with an
S -free set C
conv(P \ int(C)) istrickyIntersection cuts andmaximal S -free sets
(Non-Exhaustive)
Additional Literature

BackgroundOur Contributions
Oracle-Based Cuts
Polynomial Optimization
Conclusion

SIAM OPT 2017

S -free sets for PolyOpt – 2

The Polyhedral Approach
Background
The Polyhedral
Approach

Consider a mathematical program of the following form

Tightening P with an
S -free set C
conv(P \ int(C)) istrickyIntersection cuts andmaximal S -free sets
(Non-Exhaustive)
Additional Literature
Our Contributions
Oracle-Based Cuts
Polynomial Optimization

min cT x
subject to x ∈ S ∩ P.
P := {x ∈ Rn |Ax ≤ b} is a polyhedral set, and S ⊂ Rn is a
closed set.
Can we strengthen P with cuts?

Conclusion

SIAM OPT 2017

S -free sets for PolyOpt – 3

The Polyhedral Approach
Background
The Polyhedral
Approach

Consider a mathematical program of the following form

Tightening P with an
S -free set C
conv(P \ int(C)) istrickyIntersection cuts andmaximal S -free sets
(Non-Exhaustive)
Additional Literature
Our Contributions
Oracle-Based Cuts
Polynomial Optimization
Conclusion

SIAM OPT 2017

min cT x
subject to x ∈ S ∩ P.
P := {x ∈ Rn |Ax ≤ b} is a polyhedral set, and S ⊂ Rn is a
closed set.
Can we strengthen P with cuts?
We shall focus on the geometric approach: cuts via S -free sets.
(Many other ways to generate cuts, e.g. disjunctions, algebraicarguments, combinatorics, convex cuts, etc.)

S -free sets for PolyOpt – 3

Tightening P with an S -free set C
Background
The Polyhedral
ApproachP

Tightening P with an
S -free set C
conv(P \ int(C)) istrickyIntersection cuts andmaximal S -free sets
(Non-Exhaustive)
Additional Literature
Our Contributions

S

Oracle-Based Cuts
Polynomial Optimization
Conclusion

Let S be some closed set. Example: a rectangle P . Want toseparate the extreme point marked with a red circle from S .
SIAM OPT 2017

S -free sets for PolyOpt – 4

Tightening P with an S -free set C
BackgroundP

The Polyhedral
Approach
Tightening P with an
S -free set C
conv(P \ int(C)) istrickyIntersection cuts andmaximal S -free sets

C

(Non-Exhaustive)
Additional Literature
Our Contributions

S

Oracle-Based Cuts
Polynomial Optimization
Conclusion

C is an S -free set [Dey and Wolsey 2010]: a closed convex set withan interior that does not intersect with S .
SIAM OPT 2017

S -free sets for PolyOpt – 4

Tightening P with an S -free set C
Background
The Polyhedral
ApproachP

Tightening P with an
S -free set C
conv(P \ int(C)) istrickyIntersection cuts andmaximal S -free sets

C

(Non-Exhaustive)
Additional Literature
Our Contributions

S

Oracle-Based Cuts
Polynomial Optimization
Conclusion

We obtain a cut by subtracting C from P .
SIAM OPT 2017

S -free sets for PolyOpt – 4

Tightening P with an S -free set C
Background
The Polyhedral
Approachconv(Pnint(C))

Tightening P with an
S -free set C
conv(P \ int(C)) istrickyIntersection cuts andmaximal S -free sets
(Non-Exhaustive)
Additional LiteratureS

Our Contributions
Oracle-Based Cuts
Polynomial Optimization
Conclusion

Applying the single cut gives us conv(P \ C ).

SIAM OPT 2017

S -free sets for PolyOpt – 4

conv(P \ int(C)) is tricky
Background
The Polyhedral
Approach
Tightening P with an
S -free set C
conv(P \ int(C)) istrickyIntersection cuts andmaximal S -free sets
(Non-Exhaustive)
Additional Literature
Our Contributions
Oracle-Based Cuts
Polynomial Optimization
Conclusion

SIAM OPT 2017

More than one cut, possibly an infinite number are needed.
Separation is generally NP-Hard, e.g. P a polytope, C a ballmodels an NP-complete set containment problem.

S -free sets for PolyOpt – 5

conv(P \ int(C)) is tricky
Background
The Polyhedral
Approach
Tightening P with an
S -free set C
conv(P \ int(C)) istrickyIntersection cuts andmaximal S -free sets
(Non-Exhaustive)
Additional Literature
Our Contributions
Oracle-Based Cuts

Balas, 1971 (see also Tuy, 1964): If P is a simplicial cone then theintersection cut guarantees separation over conv(P \ int(C))
Simplicial cone: n linearly independent linear inequalities
Simplicial conic relaxation P ′ ⊇ P is easily obtained from a basic
solution of P
With less ambition we go for conv(P ′ \ int(C))
Intersection cut is described in closed form → fast separation of
extreme points of P using P ′Polynomial Optimization
Conclusion

SIAM OPT 2017

S -free sets for PolyOpt – 5

Intersection cuts and maximal S -free sets
Background
The Polyhedral
Approach

Bigger C , deeper cuts.

Tightening P with an
S -free set CP

conv(P \ int(C)) istrickyIntersection cuts andmaximal S -free sets
(Non-Exhaustive)
Additional LiteratureC

Our Contributions

S

Oracle-Based Cuts
Polynomial Optimization
Conclusion

C0

An S -free set C is maximal S -free if it is not contained in anotherS -free set.
SIAM OPT 2017

S -free sets for PolyOpt – 6

(Non-Exhaustive) Additional Literature
Background
The Polyhedral
Approach
Tightening P with an
S -free set C
conv(P \ int(C)) istrickyIntersection cuts andmaximal S -free sets
(Non-Exhaustive)
Additional Literature
Our Contributions
Oracle-Based Cuts
Polynomial Optimization
Conclusion

SIAM OPT 2017

Maximal S -free sets and minimal valid inequalities: [Basu et al.
2010], [Conforti et al. 2014], [Cornuejols, Wolsey, Yildiz, 2015],[Kilinc-Karzan 2015], etc.
Intersection cuts and for mixed-integer conic programs
programming: [Atamturk and Narayanan 2010], [Belotti et al., 2013],[Andersen and Jensen, 2013], [Dadush, Dey, Vielma 2011],[Modaresi, Kilinc, Vielma 2015/2016], etc.
Intersection cuts for bilevel optimization: [Fischetti, Monaci, Sinni,
2016].
Generalized intersection cut procedures: [Balas and Margot, 2013],[Balas, Kazachkov, Margot 2016]

S -free sets for PolyOpt – 7

Our Contributions
Background
The Polyhedral
Approach
Tightening P with an
S -free set C
conv(P \ int(C)) istricky1) A simple, generic way to generate S -free sets that ensures
separation. Also, a corresponding cutting plane method for arbitraryclosed sets, guaranteed to converge on bounded problems.
2) A study of maximal S -free sets for polynomial optimization

Intersection cuts andmaximal S -free sets
(Non-Exhaustive)
Additional Literature
Our Contributions
Oracle-Based Cuts
Polynomial Optimization
Conclusion

SIAM OPT 2017

S -free sets for PolyOpt – 8

Background
Oracle-Based Cuts
Distance Oracle
Cut Closure
Convergence
Polynomial Optimization
Conclusion

SIAM OPT 2017

Oracle-Based Cuts

S -free sets for PolyOpt – 9

Distance Oracle
Background
Oracle-Based Cuts
Distance Oracle

Suppose we have an oracle for a closed set S that gives us the
distance d(x, S) from any point x ∈ Rn to the nearest point in S .

Cut Closure
Convergence
Polynomial Optimization
Conclusion

SIAM OPT 2017

S -free sets for PolyOpt – 10

Distance Oracle
Background
Oracle-Based Cuts
Distance Oracle
Cut Closure
Convergence
Polynomial Optimization
Conclusion

SIAM OPT 2017

Suppose we have an oracle for a closed set S that gives us the
distance d(x, S) from any point x ∈ Rn to the nearest point in S .
Examples:Integer programming: if S is the lattice, then one can round.
Polynomial optimization: distance can be calculated to arbitrary
accuracy in polynomial time
Cardinality constraints: nearest vector of card (k) can be obtainedby rounding.

S -free sets for PolyOpt – 10

Distance Oracle
Background
Oracle-Based Cuts
Distance Oracle
Cut Closure
Convergence
Polynomial Optimization
Conclusion

SIAM OPT 2017

Suppose we have an oracle for a closed set S that gives us the
distance d(x, S) from any point x ∈ Rn to the nearest point in S .
Examples:Integer programming: if S is the lattice, then one can round.
Polynomial optimization: distance can be calculated to arbitrary
accuracy in polynomial time
Cardinality constraints: nearest vector of card (k) can be obtainedby rounding.
Observation. The ball centered around x with radius d(x, S) is
S -free. Call it B(x, d(x, S)).
We shall call the corresponding intersection cut an oracle ball cut.

S -free sets for PolyOpt – 10

Cut Closure Convergence
Background
Oracle-Based Cuts
Distance Oracle
Cut Closure
Convergence

Start with a polytope P0 . Define Pk+1 as Pk intersected withconv(Pk \ int(B(x, d(x, S)))) for every extreme point x. This is therank k oracle cut closure.

Polynomial Optimization
Conclusion

SIAM OPT 2017

S -free sets for PolyOpt – 11

Cut Closure Convergence
Background
Oracle-Based Cuts
Distance Oracle
Cut Closure
Convergence
Polynomial Optimization

Start with a polytope P0 . Define Pk+1 as Pk intersected withconv(Pk \ int(B(x, d(x, S)))) for every extreme point x. This is therank k oracle cut closure.
Theorem: limk→∞ Pk = conv(S ∩ P ).

Conclusion

SIAM OPT 2017

S -free sets for PolyOpt – 11

Cut Closure Convergence
Background
Oracle-Based Cuts
Distance Oracle
Cut Closure
Convergence
Polynomial Optimization
Conclusion

SIAM OPT 2017

Start with a polytope P0 . Define Pk+1 as Pk intersected withconv(Pk \ int(B(x, d(x, S)))) for every extreme point x. This is therank k oracle cut closure.
Theorem: limk→∞ Pk = conv(S ∩ P ).
Corollary: given an inexact but arbitrarily accurate distance oracle,
we can obtain arbitrarily close (in terms of Hausdorff distance)
polyhedral approximation to conv(S ∩ P ) in finite time.
Borrows from proof technique used in [Averkov 2011].

S -free sets for PolyOpt – 11

Background
Oracle-Based Cuts
Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization
Lifted Polynomial
Representation

Polynomial Optimization

S -free sets for
Polynomial
Optimization
Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 12

Polynomial Optimization
Background
Oracle-Based Cuts
Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimizationz ∗ := inf p0 (x)x∈S

S := {x ∈ Rn |p1 (x) ≥ 0, ..., pm (x) ≥ 0}

Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization
Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 13

Cuts for Polynomial Optimization
Background
Oracle-Based Cuts
Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization
Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization[Saxena, Bonami, Lee 2010/2011] Disjunctive cuts from MILP
inner-approximation + convex cuts
Applies to bounded polynomial optimization[Ghaddar, Vera, Anjos 2011] Projections of moment relaxations.
Generalizes Balas, Ceria, Cornuejols lifting. Separation notguaranteed in general.
Older literature on convex envelopes of functions, e.g. multilinear.

Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 14

Cuts for Polynomial Optimization
Background
Oracle-Based Cuts
Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization
Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization
Violation Ball
Max Full-Dim OPF
Sets are Cones[Saxena, Bonami, Lee 2010/2011] Disjunctive cuts from MILP
inner-approximation + convex cuts
Applies to bounded polynomial optimization[Ghaddar, Vera, Anjos 2011] Projections of moment relaxations.
Generalizes Balas, Ceria, Cornuejols lifting. Separation notguaranteed in general.
Older literature on convex envelopes of functions, e.g. multilinear.
Our intersection cuts (using e.g. the ball) guarantee polynomial-time
separation without boundedness assumptions.

Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 14

Lifted Polynomial Representation
Background
Oracle-Based Cuts
Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization[Shor 1987], [Lovasz and Schrijver 1991] Define a vector ofmonomials, m = [1, x1 , ..., xn , x1 x2 , x1 x3 , ..., xkn ]. Let
M = mmT .
Polynomial optimization can be formulated as

Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization
Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone

minhA0 , M is.t. hAi , M i ≤ bi , i = 1, ..., m.
This is a linear programming relaxation with respect to M .
P
hAi , M i :=aij mij is the inner product.

Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 15

Lifted Polynomial Representation
Background
Oracle-Based Cuts
Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization[Shor 1987], [Lovasz and Schrijver 1991] Define a vector ofmonomials, m = [1, x1 , ..., xn , x1 x2 , x1 x3 , ..., xkn ]. Let
M = mmT .
Polynomial optimization can be formulated as

Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization
Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup

minhA0 , M is.t. hAi , M i ≤ bi , i = 1, ..., m.
This is a linear programming relaxation with respect to M .
P
hAi , M i :=aij mij is the inner product.
Equivalency when M  0, rank(M ) = 1 and consistency
constraints. Dropping the rank constraint gives the moment
relaxation [Lasserre, SIAMOPT 2001].

Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 15

S -free sets for Polynomial Optimization
Background

Geometric notions are with respect to a vectorized space, e.g.

Oracle-Based Cuts
Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization
Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization

M ∈ S2×2 → {M11 , M12 , M22 } ∈ R3
A convex set (in the appropriate vectorized space) is
outer-product-free (OPF) if no point in the interior corresponds to amatrix that can be represented as an outer-product.
A set is maximal OPF if no OPF set strictly contains it.

Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 16

S -free sets for Polynomial Optimization
Background

Geometric notions are with respect to a vectorized space, e.g.

Oracle-Based Cuts
Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization
Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization
Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative Semidefinite

M ∈ S2×2 → {M11 , M12 , M22 } ∈ R3
A convex set (in the appropriate vectorized space) is
outer-product-free (OPF) if no point in the interior corresponds to amatrix that can be represented as an outer-product.
A set is maximal OPF if no OPF set strictly contains it.
It turns out OPF sets can have nice structure and lead to easily
generated intersection cuts.

Pi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 16

Violation Ball
Background
Oracle-Based Cuts
Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization

Using a modification by Dax (2016) of the Eckart-Young-Mirksy
theorem, we can find the nearest (by Frobenius norm) outer-productto a given matrix. This uses eigenvalues, and hence can begenerated (to specified precision) in polynomial time.

Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization
Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 17

Max Full-Dim OPF Sets are Cones
Background
Oracle-Based Cuts

Theorem: Let C ⊂ Sn×n be an outer-product-free set with full
dimension. Then clcone(C) is outer-product-free.

Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization
Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization
Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 18

Negative Semidefinite Pi
Background

hPi , M i ≥ 0

Oracle-Based Cuts

Theorem: Every such halfspace with Pi NSD is maximal
outer-product-free.
These halfspaces yield the standard outer approximation cut for
SDP: M  0 ⇐⇒ cT M c ≥ 0∀c ∈ Rn .

Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization
Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization
Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 19

The 2 × 2 cone
Background
Oracle-Based Cuts

Define Ci,j := {M ∈ Sn×n |M[i,j]  0}
Theorem: Ci,j is max OPF for 1 ≤ i 6= j ≤ n.

Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization
Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization
Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 20

Characterization for 2 × 2
Background
Oracle-Based Cuts
Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization

The 3-dimensional case.
Theorem: For n = 2, the maximal OPF set are C1,2 and halfspacesof the form hP, M i ≥ 0, where P is NSD.
i.e. the PSD cone and halfspaces with boundaries that support thecone

Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization
Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 21

Cuts
Background
Oracle-Based Cuts
Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization
Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization
Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative Semidefinite

Pi

Recall: we want every extreme point of our relaxation to be anouter-product, i.e. PSD and rank one.
Any non-PSD extreme point can be separated by theouter-approximation cuts cT M c ≥ 0.
Any PSD extreme point with rank greater than 1 can be separated
by the intersection cut given by Ci,j for some i, j [Chen, Oren,
Atamturk 2016].
The oracle cut can be strengthened by recentering the ball andtaking the conic hull (complicated expression but computationallyfast).

The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 22

Numerical Experiments: Setup
Background
Oracle-Based Cuts
Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization
Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization
Violation Ball

Pure cutting plane algorithm implemented in Python using
combinations of the following cuts:
OB (Oracle Ball Cuts), SO (Strengthened Oracle Cuts)
OA (Outer Approximation Cuts), 2x2 (2x2 Principal Minor Cuts)
LP solver: Gurobi 7.0.1
Hardware: 20-core server, Intel Xeon 3.10GHz CPU, 264 GB RAM
26 QCQP problems from GLOBALLib (6-63 variables)
99 BoxQP instances (21-126 variables)

Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 23

Numerical Experiments: Results
Background
Oracle-Based Cuts
Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization

Cut Family
OBSO
OA
2x2 + OA
SO+2x2+OA

Lifted Polynomial
Representation

Initial Gap
1387.92%

End Gap
1387.85%
1387.83%
1001.81%1003.33%
1069.59%

Closed Gap
1.00%
8.77%
8.61%
32.61%
31.91%# Cuts
16.48
18.56
353.40284.98174.79

Iters
17.20
19.52
83.76
118.08107.16Time (s)
2.59
4.14
33.25
30.40
29.55

LPTime (%)
2.06%
2.29%
7.51%
15.03%
12.56%

Table 1: Averages for GLOBALLib instances

S -free sets for
Polynomial
Optimization
Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts

Cut Family
OBSO
OA
2x2 + OA
SO+2x2+OA

Initial Gap
103.59%End Gap
103.56%103.33%30.88%
32.84%
33.43%

Closed Gap
0.04%
0.34%
75.55%
74.52%
74.03%# Cuts
12.84
14.34
676.90349.21227.39

Iters
13.62
15.45
137.52140.40136.93Time (s)127.15132.07459.28473.18475.38

LPTime (%)
0.40%
0.49%
31.80%
28.76%
26.59%

Numerical
Experiments: Setup
Numerical
Experiments: Results

Table 2: Averages for BoxQP instances

Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 24

Comparison with V2: BoxQP
Background
Oracle-Based Cuts

V2: second-order conic outer-approximation of PSD constraint MIP
to derive disjunctive cuts

Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization
Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization
Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 25

Comparison with V2: GLOBALLib
Background
Oracle-Based Cuts
Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization
Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization
Violation Ball
Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results

Instance
Ex2 1 1Ex2 1 5
Ex2 1 6
Ex2 1 8
Ex2 1 9Ex3 1 1
Ex3 1 2
Ex3 1 4Ex5 2 2 case1
Ex5 2 2 case2
Ex5 2 2 case3
Ex5 2 4

V2 Gap72.62%
99.98%
99.95%
84.70%
98.79%
15.94%
99.99%
86.31%
0.00%
0.00%
0.36%
79.31%

V2 Time704.400.17
3397.653632.28
1587.943600.27
0.08
21.26
0.02
0.05
0.36
68.93

Gap Closed
53.21%
99.68%
93.87%
73.23%
29.87%
0.34%
99.98%
29.49%
2.05%
0.00%
0.00%
29.04%

Time
0.41
0.13
0.95
19.13
36.9
0.55
0.04
0.26
0.47
0.26
0.16
5.69

Table 3: Comparison with V2 on GLOBALLib instances

Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 26

Comparison with V2: GLOBALLib
Background
Oracle-Based Cuts
Polynomial Optimization
Polynomial
Optimization
Cuts for Polynomial
Optimization
Lifted Polynomial
Representation

S -free sets for
Polynomial
Optimization
Violation Ball

Instance
Ex5 3 2
Ex5 4 2
Ex9 1 4
Ex9 2 1
Ex9 2 2
Ex9 2 6
Ex9 2 8

V2 Gap
7.27%
27.57%
0.00%
60.04%
88.29%
87.93%-

V2 Time245.823614.380.60
2372.643606.36
2619.02-

Gap Closed
0.00%
0.24%
0.00%
54.17%
77.90%
90.45%
83.27%

Time
2.33
0.59
0.34
28.37
30.84
0.12
0.12

Max Full-Dim OPF
Sets are Cones
Negative SemidefinitePi
The 2 × 2 cone
Characterization for

2×2
Cuts
Numerical
Experiments: Setup
Numerical
Experiments: Results
Comparison with V2:
BoxQP

SIAM OPT
Comparison
with2017
V2:

S -free sets for PolyOpt – 27

Background
Oracle-Based Cuts
Polynomial Optimization
Conclusion
Take-homes
Thanks!

Conclusion

SIAM OPT 2017

S -free sets for PolyOpt – 28

Take-homes
Background
Oracle-Based Cuts
Polynomial Optimization
Conclusion
Take-homes
Thanks!

SIAM OPT 2017

We introduced an oracle-based intersection cut for closed sets.
Furthermore, we constructed a convergent cutting plane algorithm
that uses this oracle to ’ping’ the set S . All of this is done without
using any explicit structure about S .
Outer-product-free sets provide a new way to generate cuts forpolynomial optimization.

S -free sets for PolyOpt – 29Thanks!
Background

Preprint available:

Oracle-Based Cuts

http://arxiv.org/abs/1610.04604

Polynomial Optimization
Conclusion
Take-homes
Thanks!

SIAM OPT 2017

S -free sets for PolyOpt – 30