[PDF] Convex Optimization 4 sept. 2009 Boyd &

View - Download Convex Optimization

Previous PDF

Next PDF

Convex Optimization

Lieven Vandenberghe

University of California, Los Angeles

Tutorial lectures, Machine Learning Summer School

University of Cambridge, September 3-4, 2009

Sources:

•Boyd & Vandenberghe,Convex Optimization, 2004

•Courses EE236B, EE236C (UCLA), EE364A, EE364B (Stephen Boyd, Stanford Univ.)

Convex optimization - MLSS 2009

Introduction

•mathematical optimization, modeling, complexity

•convex optimization

•recent history

1

Mathematical optimization

minimizef0(x1,...,xn)

•x= (x1,x2,...,xn)are decision variables

•f0(x1,x2,...,xn)gives the cost of choosingx

•inequalities give constraints thatxmust satisfy a mathematical model of a decision, design, or estimation problem

Introduction2

Limits of mathematical optimization

•how realistic is the model, and how certain are we about it? •is the optimization problem tractable by existing numerical algorithms?

Optimization research

•modelinggeneric techniques for formulating tractable optimization problems •algorithmsexpand class of problems that can be efficiently solved

Introduction3

Complexity of nonlinear optimization

•the general optimization problem is intractable •even simple looking optimization problems can be very hard

Examples

•quadratic optimization problem with many constraints

•minimizing a multivariate polynomial

Introduction4

The famous exception: Linear programming

minimizecTx=n? i=1c ixi •widely used since Dantzig introduced the simplex algorithm in 1948 •since 1950s, many applications in operations research, network optimization, finance, engineering,. . . •extensive theory (optimality conditions, sensitivity, . . . ) •there exist very efficient algorithms for solving linear programs

Introduction5

Solving linear programs

•no closed-form expression for solution

•widely available and reliable software

•for some algorithms, can prove polynomial time •problems with over105variables or constraints solved routinely

Introduction6

Convex optimization problem

minimizef0(x) f •includes least-squares problems and linear programs as special cases •can be solved exactly, with similar complexity as LPs •surprisingly many problems can be solved via convex optimization

Introduction7

History

•1940s: linear programming

minimizecTx

•1950s: quadratic programming

•1960s: geometric programming

•1990s: semidefinite programming, second-order cone programming, quadratically constrained quadratic programming, robust optimization, sum-of-squares programming, . . .

Introduction8

New applications since 1990

•linear matrix inequality techniques in control

•circuit design via geometric programming

•support vector machine learning via quadratic programming •semidefinite programming relaxations in combinatorial optimization •?1-norm optimization for sparse signal reconstruction •applications in structural optimization, statistics, signal processing, communications, image processing, computer vision, quantum information theory, finance, . . .

Introduction9

Algorithms

Interior-point methods

•1984 (Karmarkar): first practical polynomial-time algorithm •1984-1990: efficient implementations for large-scale LPs •around 1990 (Nesterov & Nemirovski): polynomial-time interior-point methods for nonlinear convex programming •since 1990: extensions and high-quality software packages

First-order algorithms

•similar to gradient descent, but with better convergence properties •based on Nesterov"s 'optimal" methods from 1980s •extend to certain nondifferentiable or constrained problems

Introduction10

Outline

•basic theory

-convex sets and functions -convex optimization problems -linear, quadratic, and geometric programming

•cone linear programming and applications

-second-order cone programming -semidefinite programming •some recent developments in algorithms (since 1990) -interior-point methods -fast gradient methods 10

Convex optimization - MLSS 2009

Convex sets and functions

•definition

•basic examples and properties

•operations that preserve convexity

11

Convex set

contains line segment between any two points in the set x

Examples: one convex, two nonconvex sets

Convex sets and functions12

Examples and properties

•solution set of linear equationsAx=b(affine set) •solution set of linear inequalitiesAx?b(polyhedron) •set of positive semidefinite matricesSn+={X?Sn|X?0} •image of a convex set under a linear transformation is convex •inverse image of a convex set under a linear transformation is convex

•intersection of convex sets is convex

Convex sets and functions13

Example of intersection property

wherep(t) =x1cost+x2cos2t+···+xncosnt

0π/32π/3π-101

t p(t) x1 x2 C -2-1012-2-1012 Cis intersection of infinitely many halfspaces, hence convex

Convex sets and functions14

Convex function

domaindomfis a convex set and (x,f(x))(y,f(y)) fis concave if-fis convex

Convex sets and functions15

Epigraph and sublevel set

a function is convex if and only its epigraph is a convex set epif f the sublevel sets of a convex function are convex (converse is false)

Convex sets and functions16

Examples

•expx,-logx,xlogxare convex

•quadratic-over-linear functionxTx/tis convex inx,tfort >0 •geometric mean(x1x2···xn)1/nis concave forx?0 •logdetXis concave on set of positive definite matrices

•log(ex1+···exn)is convex

•linear and affine functions are convex and concave

•norms are convex

Convex sets and functions17

Differentiable convex functions

differentiablefis convex if and only ifdomfis convex and f(y)≥f(x) +?f(x)T(y-x)for allx,y?domf (x,f(x))f(y) f(x) +?f(x)T(y-x) twice differentiablefis convex if and only ifdomfis convex and

2f(x)?0for allx?domf

Convex sets and functions18

Operations that preserve convexity

methods for establishing convexity of a function

1. verify definition

2. for twice differentiable functions, show?2f(x)?0

3. show thatfis obtained from simple convex functions by operations

that preserve convexity

•nonnegative weighted sum

•composition with affine function

•pointwise maximum and supremum

•composition

•minimization

•perspective

Convex sets and functions19

Positive weighted sum&composition with affine function Nonnegative multiple:αfis convex iffis convex,α≥0 Sum:f1+f2convex iff1,f2convex (extends to infinite sums, integrals) Composition with affine function:f(Ax+b)is convex iffis convex

Examples

•log barrier for linear inequalities

f(x) =-m? i=1log(bi-aTix)

•(any) norm of affine function:f(x) =?Ax+b?

Convex sets and functions20

Pointwise maximum

f(x) = max{f1(x),...,fm(x)} is convex iff1, . . . ,fmare convex

Example:sum ofrlargest components ofx?Rn

f(x) =x[1]+x[2]+···+x[r] is convex (x[i]isith largest component ofx) proof:

Convex sets and functions21

Pointwise supremum

g(x) = sup y?Af(x,y) is convex iff(x,y)is convex inxfor eachy? A

Example:maximum eigenvalue of symmetric matrix

max(X) = sup ?y?2=1yTXy

Convex sets and functions22

Composition with scalar functions

composition ofg:Rn→Randh:R→R: f(x) =h(g(x)) fis convex if gconvex,hconvex and nondecreasing gconcave,hconvex and nonincreasing (if we assignh(x) =∞forx?domh)

Examples

•expg(x)is convex ifgis convex

•1/g(x)is convex ifgis concave and positive

Convex sets and functions23

Vector composition

composition ofg:Rn→Rkandh:Rk→R: f(x) =h(g(x)) =h(g1(x),g2(x),...,gk(x)) fis convex if g iconvex,hconvex and nondecreasing in each argument g iconcave,hconvex and nonincreasing in each argument (if we assignh(x) =∞forx?domh)

Examples

?mi=1loggi(x)is concave ifgiare concave and positive

•log?mi=1expgi(x)is convex ifgiare convex

Convex sets and functions24

Minimization

g(x) = infy?Cf(x,y) is convex iff(x,y)is convex inx,yandCis a convex set

Examples

•distance to a convex setC:g(x) = infy?C?x-y?

•optimal value of linear program as function of righthand side g(x) = infy:Ay?xcTy follows by taking f(x,y) =cTy,domf={(x,y)|Ay?x}

Convex sets and functions25

Perspective

theperspectiveof a functionf:Rn→Ris the functiong:Rn×R→R, g(x,t) =tf(x/t) gis convex iffis convex ondomg={(x,t)|x/t?domf, t >0}

Examples

•perspective off(x) =xTxis quadratic-over-linear function g(x,t) =xTx t •perspective of negative logarithmf(x) =-logxis relative entropy g(x,t) =tlogt-tlogx

Convex sets and functions26

Convex optimization - MLSS 2009

Convex optimization problems

•standard form

•linear, quadratic, geometric programming

•modeling languages

27

Convex optimization problem

minimizef0(x) Ax=b f

0,f1, . . . ,fmare convex functions

•feasible set is convex

•locally optimal points are globally optimal

•tractable, both in theory and practice

Convex optimization problems28

Linear program (LP)

minimizecTx+d subject toGx?h Ax=b

•inequality is componentwise vector inequality

•convex problem with affine objective and constraint functions

•feasible set is a polyhedron

Px?-c

Convex optimization problems29

Piecewise-linear minimization

minimizef(x) = maxi=1,...,m(aTix+bi) xa T ix+bif(x)

Equivalent linear program

minimizet an LP with variablesx,t?R

Convex optimization problems30

Linear discrimination

separate two sets of points{x1,...,xN},{y1,...,yM}by a hyperplane a

Txi+b >0, i= 1,...,N

a

Tyi+b <0, i= 1,...,M

homogeneous ina,b, hence equivalent to the linear inequalities (ina,b) a

Convex optimization problems31

Approximate linear separation of non-separable setsquotesdbs_dbs33.pdfusesText_39

[PDF] fonction convexe plusieurs variables

[PDF] modélisation et simulation d'un moteur ? courant continu matlab

[PDF] modélisation mcc

[PDF] simulation mcc simulink

[PDF] asservissement et regulation de vitesse d'un moteur a courant continu

[PDF] modélisation d'un moteur ? courant continu

[PDF] equation differentielle moteur courant continu

[PDF] schéma bloc moteur ? courant continu

[PDF] commande pid d'un moteur ? courant continu pdf

[PDF] modélisation machine asynchrone simulink

[PDF] onduleur triphasé matlab

[PDF] cours de modélisation financière sous excel

[PDF] modélisation financière pdf

[PDF] fiche de lecture les misérables victor hugo pdf

[PDF] modélisation financière exemple