Présentation PowerPoint - Princeton

Présentation PowerPoint - Princeton

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

Recently Viewed Presentations

  • Learning to Program With Alice - Carnegie Mellon School of ...

    Learning to Program With Alice - Carnegie Mellon School of ...

    kind of a vague story. Ninja and samurai have stolen money and they get caught by amme and a dog. Much fighting. chase_fish. generic. loops. chase_horse. this is another love spell one - this time cast by douglas the tree...
  • Ancient River Valley Civilizations - PBworks

    Ancient River Valley Civilizations - PBworks

    Japan's isolation Like China, Japan had practiced isolation for a long time Fearing loss of independence, Japan conceded to trade with the U.S. and agreed to demands of Mathew Perry Japan began to industrialize and modernize its country Japanese studied...
  • Choice page Tudalen ddewis

    Choice page Tudalen ddewis

    www.wjec.co.uk - GCSE D&T. View all teaching specifications, Specimen assessment materials, Teacher Guidance documents, Principal Examiner reports for each Unit 1 focus area examination, Principal Moderator's report for Unit 2 CAT, Teachers' Assessment Materials and Guidance. www.wjecservices.co.uk (Centre specific account...
  • Chemical Bonding - Ms. Richardson's Science

    Chemical Bonding - Ms. Richardson's Science

    Chemical Bonding. Atoms bond with each other in order to become stable. To do this, atoms will lose, gain or share valence electrons in order to obtain a stable octet.
  • Module One Introduction to the Security Industry

    Module One Introduction to the Security Industry

    Prior to class, try to find video portraying large crowds (e.g., a sporting event, at a large retail sale). Show the video clip(s) to participants; have participants identify the need for security professionals in each situation and what the role...
  • Mega MANIAc AWARDS November, 2014 6th grade RESPECT

    Mega MANIAc AWARDS November, 2014 6th grade RESPECT

    7 th Grade. Excellence - Always Doing . Your Best. Liam Adams. Hannah . Bahorski. Christian Burke. Michael Ceglarz. Noelle Chan. Dana Holt. Caleb Jackson. Michayla ...
  • Suf x i f e r P fix

    Suf x i f e r P fix

    Suffix Root Prefix Combining Form Veterinary Terminology TM Tachycardia: abnormally fast heart rate Abnormally fast Tachy- Polyuria: producing much urine Many, much, multiple Poly- Malocclusion: poor positioning of the teeth Bad, poor Mal- Hypothermia: abnormally low body temperature Insufficient, abnormally...
  • The Production of Pyruvate and acetaldehyde during the ...

    The Production of Pyruvate and acetaldehyde during the ...

    2- Gluconeogenesis • Is a metabolic pathway that results in the generation. of glucose from non-carbohydrate carbon substrates. such as lactate, glycerol.