Convex Optimization: Modeling And Algorithms

Convex Optimization: Modeling andAlgorithmsLieven VandenbergheElectrical Engineering Department, UC Los AngelesTutorial lectures, 21st Machine Learning Summer SchoolKyoto, August 29-30, 2012

Convex optimization — MLSS 2012Introduction mathematical optimization linear and convex optimization recent history1

Mathematical optimizationminimizef0(x1, . . . , xn)subject to f1(x1, . . . , xn) 0···fm(x1, . . . , xn) 0 a mathematical model of a decision, design, or estimation problem finding a global solution is generally intractable even simple looking nonlinear optimization problems can be very hardIntroduction2

The famous exception: Linear programmingminimize c1x1 · · · c2x2subject to a11x1 · · · a1nxn b1.am1x1 · · · amnxn bm widely used since Dantzig introduced the simplex algorithm in 1948 since 1950s, many applications in operations research, networkoptimization, finance, engineering, combinatorial optimization, . . . extensive theory (optimality conditions, sensitivity analysis, . . . ) there exist very efficient algorithms for solving linear programsIntroduction3

Convex optimization problemminimize f0(x)subject to fi(x) 0,i 1, . . . , m objective and constraint functions are convex: for 0 θ 1fi(θx (1 θ)y) θfi(x) (1 θ)fi(y) can be solved globally, with similar (polynomial-time) complexity as LPs surprisingly many problems can be solved via convex optimization provides tractable heuristics and relaxations for non-convex problemsIntroduction4

History 1940s: linear programmingminimize cT xsubject to aTi x bi,i 1, . . . , m 1950s: quadratic programming 1960s: geometric programming 1990s: semidefinite programming, second-order cone programming,quadratically constrained quadratic programming, robust optimization,sum-of-squares programming, . . .Introduction5

New applications since 1990 linear matrix inequality techniques in control support vector machine training via quadratic programming semidefinite programming relaxations in combinatorial optimization circuit design via geometric programming ℓ1-norm optimization for sparse signal reconstruction applications in structural optimization, statistics, signal processing,communications, image processing, computer vision, quantuminformation theory, finance, power distribution, . . .Introduction6

Advances in convex optimization algorithmsinterior-point methods 1984 (Karmarkar): first practical polynomial-time algorithm for LP 1984-1990: efficient implementations for large-scale LPs around 1990 (Nesterov & Nemirovski): polynomial-time interior-pointmethods for nonlinear convex programming since 1990: extensions and high-quality software packagesfirst-order algorithms fast gradient methods, based on Nesterov’s methods from 1980s extend to certain nondifferentiable or constrained problems multiplier methods for large-scale and distributed optimizationIntroduction7

Overview1. Basic theory and convex modeling convex sets and functions common problem classes and applications2. Interior-point methods for conic optimization conic optimization barrier methods symmetric primal-dual methods3. First-order methods (proximal) gradient algorithms dual techniques and multiplier methods

Convex optimization — MLSS 2012Convex sets and functions convex sets convex functions operations that preserve convexity

Convex setcontains the line segment between any two points in the setx1, x2 C,convexConvex sets and functions0 θ 1 not convexθx1 (1 θ)x2 Cnot convex8

Basic examplesaffine set: solution set of linear equations Ax bhalfspace: solution of one linear inequality aT x b (a 6 0)polyhedron: solution of finitely many linear inequalities Ax bellipsoid: solution of positive definite quadratic inquality(x xc)T A(x xc) 1(A positive definite)norm ball: solution of kxk R (for any norm)positive semidefinite cone: Sn {X Sn X 0}the intersection of any number of convex sets is convexConvex sets and functions9

Example of intersection propertyC {x Rn p(t) 1 for t π/3}where p(t) x1 cos t x2 cos 2t · · · xn cos nt210x2p(t)1 1C0 10π/3t2π/3π 2 2 1x0112C is intersection of infinitely many halfspaces, hence convexConvex sets and functions10

Convex functiondomain dom f is a convex set and Jensen’s inequality holds:f (θx (1 θ)y) θf (x) (1 θ)f (y)for all x, y dom f , 0 θ 1(y, f (y))(x, f (x))f is concave if f is convexConvex sets and functions11

Examples linear and affine functions are convex and concave exp x, log x, x log x are convex xα is convex for x 0 and α 1 or α 0; x α is convex for α 1 norms are convex quadratic-over-linear function xT x/t is convex in x, t for t 0 geometric mean (x1x2 · · · xn)1/n is concave for x 0 log det X is concave on set of positive definite matrices log(ex1 · · · exn ) is convexConvex sets and functions12

Epigraph and sublevel setepigraph: epi f {(x, t) x dom f, f (x) t}epi fa function is convex if and only itsepigraph is a convex setfsublevel sets: Cα {x dom f f (x) α}the sublevel sets of a convex function are convex (converse is false)Convex sets and functions13

Differentiable convex functionsdifferentiable f is convex if and only if dom f is convex andf (y) f (x) f (x)T (y x)for all x, y dom ff (y)f (x) f (x)T (y x)(x, f (x))twice differentiable f is convex if and only if dom f is convex and 2f (x) 0 for all x dom fConvex sets and functions14

Establishing convexity of a function1. verify definition2. for twice differentiable functions, show 2f (x) 03. show that f is obtained from simple convex functions by operationsthat preserve convexity nonnegative weighted sumcomposition with affine functionpointwise maximum and supremumminimizationcompositionperspectiveConvex sets and functions15

Positive weighted sum & composition with affine functionnonnegative multiple: αf is convex if f is convex, α 0sum: f1 f2 convex if f1, f2 convex (extends to infinite sums, integrals)composition with affine function: f (Ax b) is convex if f is convexexamples logarithmic barrier for linear inequalitiesf (x) mXi 1log(bi aTi x) (any) norm of affine function: f (x) kAx bkConvex sets and functions16

Pointwise maximumf (x) max{f1(x), . . . , fm(x)}is convex if f1, . . . , fm are convexexample: sum of r largest components of x Rnf (x) x[1] x[2] · · · x[r]is convex (x[i] is ith largest component of x)proof:f (x) max{xi1 xi2 · · · xir 1 i1 i2 · · · ir n}Convex sets and functions17

Pointwise supremumg(x) sup f (x, y)y Ais convex if f (x, y) is convex in x for each y Aexamples maximum eigenvalue of symmetric matrixλmax(X) sup y T Xykyk2 1 support function of a set CSC (x) sup y T xy CConvex sets and functions18

Minimizationh(x) inf f (x, y)y Cis convex if f (x, y) is convex in (x, y) and C is a convex setexamples distance to a convex set C: h(x) inf y C kx yk optimal value of linear program as function of righthand sideh(x) infy:Ay xcT yfollows by takingf (x, y) cT y,Convex sets and functionsdom f {(x, y) Ay x}19

Compositioncomposition of g : Rn R and h : R R:f (x) h(g(x))f is convex ifg convex, h convex and nondecreasingg concave, h convex and nonincreasing(if we assign h(x) for x dom h)examples exp g(x) is convex if g is convex 1/g(x) is convex if g is concave and positiveConvex sets and functions20

Vector compositioncomposition of g : Rn Rk and h : Rk R:f (x) h(g(x)) h (g1(x), g2(x), . . . , gk (x))f is convex ifgi convex, h convex and nondecreasing in each argumentgi concave, h convex and nonincreasing in each argument(if we assign h(x) for x dom h)examplelogmPexp gi(x) is convex if gi are convexi 1Convex sets and functions21

Perspectivethe perspective of a function f : Rn R is the function g : Rn R R,g(x, t) tf (x/t)g is convex if f is convex on dom g {(x, t) x/t dom f, t 0}examples perspective of f (x) xT x is quadratic-over-linear functionxT xg(x, t) t perspective of negative logarithm f (x) log x is relative entropyg(x, t) t log t t log xConvex sets and functions22

Conjugate functionthe conjugate of a function f isf (y) sup (y T x f (x))x dom ff (x)xyx(0, f (y))f is convex (even if f is not)Convex sets and functions23

Examplesconvex quadratic function (Q 0)1 Tf (x) x Qx21 T 1f (y) y Q y2 negative entropyf (x) nXf (y) xi log xii 1i 1normf (x) kxk f (y) indicator function (C convex) 0x Cf (x) IC (x) otherwiseConvex sets and functionsnX e yi 10kyk 1 otherwisef (y) sup y T xx C24

Convex optimization — MLSS 2012Convex optimization problems linear programming quadratic programming geometric programming second-order cone programming semidefinite programming

Convex optimization problemminimize f0(x)subject to fi(x) 0,Ax bi 1, . . . , mf0, f1, . . . , fm are convex functions feasible set is convex locally optimal points are globally optimal tractable, in theory and practiceConvex optimization problems25

Linear program (LP)minimize cT x dsubject to Gx hAx b inequality is componentwise vector inequality convex problem with affine objective and constraint functions feasible set is a polyhedron cPConvex optimization problemsx 26

Piecewise-linear minimizationminimize f (x) max (aTi x bi)i 1,.,mf (x)aTi x bixequivalent linear programminimize tsubject to aTi x bi t,i 1, . . . , man LP with variables x, t RConvex optimization problems27

ℓ1-Norm and ℓ -norm minimizationℓ1-norm approximation and equivalent LP (kyk1 minimize kAx bk1minimizenXPk yk )yii 1subject to y Ax b yℓ -norm approximation (kyk maxk yk )minimize kAx bk minimize ysubject to y1 Ax b y1(1 is vector of ones)Convex optimization problems28

example: histograms of residuals Ax b (with A is 200 80) forxls argmin kAx bk2,xℓ1 argmin kAx bk110864201.51.00.50.00.51.01.5(Axls b)k1008060401.0 01.5 200.50.00.51.01.5(Axℓ1 b)k1-norm distribution is wider with a high peak at zeroConvex optimization problems29

Robust regression25201510f (t)5 015 20 10 10 550t510 42 points ti, yi (circles), including two outliers function f (t) α βt fitted using 2-norm (dashed) and 1-normConvex optimization problems30

Linear discrimination given a set of points {x1, . . . , xN } with binary labels si { 1, 1} find hyperplane aT x b 0 that strictly separates the two classesa T xi b 0if si 1aT xi b 0 if si 1homogeneous in a, b, hence equivalent to the linear inequalities (in a, b)si(aT xi b) 1,Convex optimization problemsi 1, . . . , N31

Approximate linear separation of non-separable setsminimizeNXi 1max{0, 1 si(aT xi b)} a piecewise-linear minimization problem in a, b; equivalent to an LP can be interpreted as a heuristic for minimizing #misclassified pointsConvex optimization problems32

Quadratic program (QP)minimize (1/2)xT P x q T x rsubject to Gx h P Sn , so objective is convex quadratic minimize a convex quadratic function over a polyhedron f0(x )x PConvex optimization problems33

Linear program with random costminimize cT xsubject to Gx h c is random vector with mean c̄ and covariance Σ hence, cT x is random variable with mean c̄T x and variance xT Σxexpected cost-variance trade-offminimize E cT x γ var(cT x) c̄T x γxT Σxsubject to Gx hγ 0 is risk aversion parameterConvex optimization problems34

Robust linear discriminationH1 {z aT z b 1}H 1 {z aT z b 1}distance between hyperplanes is 2/kak2to separate two sets of points by maximum margin,minimizekak22 aT asubject to si(aT xi b) 1,i 1, . . . , Na quadratic program in a, bConvex optimization problems35

Support vector classifierminimize γkak22 NXi 1γ 0max{0, 1 si(aT xi b)}γ 10equivalent to a quadratic programConvex optimization problems36

Kernel formulationminimize f (Xa) kak22 variables a Rn X RN n with N n and rank Nchange of variablesy Xa,a X T (XX T ) 1y a is minimum-norm solution of Xa y gives convex problem with N variables yminimize f (y) y T Q 1yQ XX T is kernel matrixConvex optimization problems37

Total variation signal reconstructionminimize kx̂ xcork22 γφ(x̂) xcor x v is corrupted version of unknown signal x, with noise v variable x̂ (reconstructed signal) is estimate of x φ : Rn R is quadratic or total variation smoothing penaltyφquad(x̂) n 1Xi 1Convex optimization problems(x̂i 1 x̂i)2,φtv (x̂) n 1Xi 1 x̂i 1 x̂i 38