Difference of Convex (DC) Decomposition of Nonconvex Polynomials with Algebraic Techniques Georgina Hall Princeton, ORFE Joint work with Amir Ali Ahmadi Princeton, ORFE 7/13/2015 MOPTA 2015 1 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques Difference of Convex (DC) programming Problems of the form where: ,, , are convex. 2 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques Concave-Convex Computational Procedure (CCCP) Heuristic for minimizing DC programming problems. Has been used extensively in:

machine learning (sparse support vector machines (SVM), transductive SVMs, sparse principal component analysis) statistical physics (minimizing Bethe and Kikuchi free energies). Idea: Input x initial point Convexify by linearizing Solve convex subproblem x Take to be the solution of convex convex ( ) () affine +1 3 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques Concave-Convex Computational Procedure (CCCP) Toy example: , where

Convexify to obtain Initial point: Minimize and obtain Reiterate 43 21 0 4 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques CCCP for nonconvex polynomial optimization problems (1/2) CCCP relies on input functions being given as a difference of convex functions. What if we dont have access to such a decomposition? We will consider polynomials in variables and of degree Any polynomial can be written as a difference of convex polynomials. Proof by Wang, Schwing and Urtasun Alternative proof given later in this presentation, as corollary of stronger theorem 5 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques CCCP for nonconvex polynomial optimization problems (2/2)

In fact, for any polynomial, an infinite number of decompositions. Example Possible decompositions x Which one would be a natural choice for CCCP? 6 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques Picking the best decomposition (1/2) Algorithm Linearize around a point to obtain convexified version of Idea Pick such that it is as close as possible to affine Mathematical translation Minimize curvature of ( is the hessian of At a point Over a region s.t. convex s.t. convex 7 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques

Picking the best decomposition (2/2) Theorem: Finding the best decomposition of a degree-4 polynomial over a box is NP-hard. Proof idea: Reduction via testing convexity of quartic polynomials is hard (Ahmadi, Olshevsky, Parrilo, Tsitsiklis). The same is likely to hold for the point version, but we have been unable to prove it. How can we efficiently find such a decomposition? 8 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques Convex relaxations for DC decompositions (1/6) SOS, DSOS, SDSOS polynomials (Ahmadi, Majumdar) Families of nonnegative polynomials. Type Characterization Testing membership Sum of squares (sos) , polynomials, s.t. SDP Scaled diagonally dominant sum of squares (sdsos)

p monomials, SOCP Diagonally dominant sum of squares (dsos) p LP 9 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques Convex relaxations for DC decompositions (2/6) convex DSOS-convex, SDSOS-convex, SOS-convex polynomials ( ) 0, Definitions: is dsos-convex if is dsos. is sdsos-convex if is sdsos. is sos-convex if is sos.

sos/sdsos/dsos LP SOCP SDP 10 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques Convex relaxations for DC decompositions (3/6) Comparison of these sets on a parametric family of polynomials: = 0.5 =0 dsos-convex =1 sdsos-convex sos-convex=convex

11 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques Convex relaxations for DC decompositions (4/6) How to use these concepts to do DC decomposition at a point ? Original problem s.t. convex s.t. convex Relaxation 1: sos-convex Relaxation 2: sdsos-convex Relaxation 3: dsos-convex Relaxation 4: sdsos-convex+sdd Relaxation 5: dsos-convex + dd

s.t. s.t. s.t. s.t. sdd (**) s.t. dd (*) sos-convex sdsos-convex dsos-convex SDP SOCP + small SDP LP + small SDP sdsos-convex SOCP dsos-convex LP is diagonally dominant (dd) is sdd diagonal, s.t. dd. 12

DC Decomposition of Nonconvex Polynomials with Algebraic Techniques Convex relaxations for DC decompositions (5/6) Can any polynomial be written as the difference of two dsos/sdsos/sos convex polynomials? Lemma about cones: Let a full dimensional cone ( any vector space). Thenany can be written as . Proof sketch: : K E such that 1 = 1 1 1 2

13 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques Convex relaxations for DC decompositions (6/6) Theorem: Any polynomial can be written as the difference of two dsosconvex polynomials. Corollary: Same holds for sdsos-convex, sos-convex and convex. Proof idea: Need to show that dsos-convex polynomials is full-dimensional cone. Obvious choices (i.e., ) do not work. Induction on : for take 0 > 2( 2) + ( 1) 4( 1) 4 1=1 +1= ( 2 , =1, , 1 2 + 2 4

) 14 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques Comparing the different relaxations (1/4) Impact of relaxations on solving s.t. psd/sdd/dd , s/d/sos-convex for random (). Type of relaxation dsos-convex + dd dsos-convex dsos-convex ++ psd psd sdsos-convex sdsos-convex ++ sdd sdd sdsos-convex + psd sdsos-convex + psd sos-convex + psd MOSEK sos-convex + psd MOSEK sos-convex + psd SEDUMI sos-convex + psd SEDUMI Time (s) Opt value Time (s)

Opt Value Time (s) Opt value 1.05 1.19 1.19 17578.54 15855.77 15855.77 2.79 3.19 3.19 21191.55 19426.13 19426.13 20.80 25.36 25.36 168327.89 146847.73 146847.73 1.21

1.21 1.21 1.21 2.02 2.02 11.48 11.48 1089.41 1089.41 1069.79 1069.79 193.07 193.07 193.06 193.06 5.17 5.17 5.29 5.29 93.74 93.74 10324.12 10324.12 1962.64 1962.64 1957.03 1957.03 317.63 317.63

317.63 317.63 34.66 34.66 39.43 39.43 7936.57 7936.57 7935.72 7935.72 --------------------------------------------------------------------- Computer: 8Gb RAM, 2.40GHz processor 15 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques Comparing the different relaxations (2/4) Iterative decomposition algorithm implemented for unconstrained Decompose using one of the relaxations at point 0 -50000

-100000 -150000 -200000 DSOS DD DSOS PSD SDSOS SDD SDSOS PSD Minimize convexified using an SDP subroutine [Lasserre; de Klerk and Laurent] SOS PSD Value of the objective after 3 mins. Algorithm given above. 5 different relaxations used random with , Average over 25 iterations Solver: Mosek

-250000 16 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques Comparing the different relaxations (3/4) Constrained case: where Single decomposition vs Iterative decomposition Relaxation: s.t. Decompose once at Relaxation: s.t. Decompose at a point sdsos convex sdsos convex Minimize convexified Minimize convexified vs

One min-max decomp. What relaxationover to use? Decompose B Minimize convexified Second relaxation: First relaxation: Equivalent formulation: Original problem: s.t. sos convex convex sdsos-convex sdsos-convex 17 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques Comparing the different relaxations (4/4) Constrained case: single decomposition vs. iterative decomposition vs. min-max decomposition 4000 2000 0 -2000 -4000

le g -8000 Sin -6000 -10000 -12000 om c de p r tI e om c de p in M m ax

Value of the objective after 3 mins. Algorithms described above. random with , Radius random integer between 100 and 400. Average over 200 iterations -14000 -16000 18 DC Decomposition of Nonconvex Polynomials with Algebraic Techniques Main messages To apply CCCP to polynomial optimization, a DC decomposition is needed. Choice of decomposition impacts convergence speed. Not computationally tractable to find best decomposition. Efficient convex relaxations based on the concepts of dsos-convex (LP), sdsos-convex (SOCP), and sos-convex (SDP) polynomials. Dsos-convex and sdsos-convex scale to a larger number of variables. 19 Thank you for listening Questions? 20