[PDF] Convex Optimization Basics Is this convex? What is

View - Download Convex Optimization Basics

Previous PDF

Next PDF

Convex Optimization Basics

Yu-Xiang Wang

CS292A

(Based on Ryan Tibshirani's 10-725)

Last time: convex sets and functions

\Convex calculus" makes it easy to check convexity. Tools:

Denitions of

convex sets and functions , classic examples242Co nvexsets Figure2.2Somesimpl econvexandnonconvexsets .Left.Thehexago n, whichincludesit sboundary(showndarker), isconvex.Middle.Thekidney shapedsetisnotconv ex,sincet heline segmentbe tweenthetwopointsin thesetsho wnasdotsisn otcontainedinthese t.Right.Thesquarec ontains someboundary pointsbutnotothers,andi snotconvex.

Figure2.3Theconv exhullsoftwosets inR

2 .Left.Thecon vexhullofa setoffiftee npoin ts(shownasdots)isthepe ntagon(shownshaded).Right. Theconvex hullofthekidneysha pedsetinfigur e2.2is theshadedset . Roughlyspeaking,a setisconvexifeverypoin tinthe setcanbese enbyeveryot her point,alonganun obstructedstrai ghtpat hbetweenthem,whereunobstructed meanslyinginth eset.Every a!neseti sal soconvex,si nceitcontainstheentire lineb etweenanytwodistinctp ointsinit,andtherefo realsothe linesegment betweenthepoints.Fig ure2.2il lustratessomesimpl econvexand nonconvexsets inR 2

Weca llapointofth efo rm!

1 x 1 k x k ,wher e! 1 k =1and i !0,i=1,...,k,aconvexcombinatio nofth epointsx 1 ,...,x k .Aswitha!ne sets,it canbeshow nthataseti sconvexi fandonlyif itcontainsev eryconvex combinationofitspoints.Aco nvexcombina tiono fpointscanbethoughtofasa mixtureorweightedaverageofth epoints,wi th! i thefra ctionofx i inthemixtur e. Theconvexhullofas etC,denotedconvC,isth eset ofallconvexcom binations ofpoi ntsinC: convC={! 1 x 1 k x k |x i "C,! i !0,i=1,...,k,! 1 k =1}. Asth enamesuggests ,thecon vexhullconvCisalw aysconvex.Itisthesmalles t convexsetthatcontainsC:IfBisan yconvexsetthat containsC,thenconvC# Theidea ofaconvexcombin ation can begeneralizedtoin cludeinfinitesums,in- tegrals,and,inthemostg eneralform ,pro babilit ydistributions.Suppose! 1 2

Chapter3

Convexfunctions

3.1Basicp ropertiesandexampl es

3.1.1Definition

Afunctionf:R

n !Risconvexifdomfisaco nvex setandifforallx, y"domf,and!with0#!#1,w ehave f(!x+(1$!)y)#!f(x)+(1$!)f(y).(3.1) Geometrically,thisinequalitymean sthatthelin esegmentbetween(x,f(x))and (y,f(y)),whic histhechordfromxtoy,liesabovethegraphoff(figure3.1). Afunctionfisstrictlyconvexifstr ictinequalityholdsin(3.1 )wheneverx%=y and0E.g., ismaxn log(1 +eaTx);kAx+bk51o convex? 2

Outline

Today:

Optimization terminology

Properties and rst-order optimality

Equivalent transformations

Hierarchies of Canonical Problems

Many examples!

3

Optimization terminology

Reminder: a convex optimization problem (or

p rogram ) is min x2Df(x) subject togi(x)0; i= 1;:::m Ax=b wherefandgi,i= 1;:::mare all convex, and the optimization domain isD= dom(f)\Tm i=1dom(gi)(often we do not writeD) fis calledcriterion o robj ectivefunction giis calledinequalit yconstraint function

Ifx2D,gi(x)0,i= 1;:::m, andAx=bthenxis called

a feasible p oint The minimum off(x)over all feasible pointsxis called the optimal value , writtenf? 4 Ifxis feasible andf(x) =f?, thenxis calledoptimal ; also called a solution , or a minimizer 1 Ifxis feasible andf(x)f?+, thenxis called-suboptimal Ifxis feasible andgi(x) = 0, then we saygiisactive at x Convex minimization can be reposed as concave maximization min xf(x) subject togi(x)0; i= 1;:::m

Ax=b()max

xf(x) subject togi(x)0; i= 1;:::m Ax=b

Both are called convex optimization problems1

Note: a convex optimization problem need not have solutions, i.e., need not attain its minimum, but we will not be careful about this5

Solution set

LetXoptbe the set of all solutions of convex problem, written X opt= argminf(x) subject togi(x)0; i= 1;:::m Ax=b

Key property:Xoptis aconvex set

Proof: use denitions. Ifx;yare solutions, then for0t1, gi(tx+ (1t)y)tgi(x) + (1t)gi(y)0

A(tx+ (1t)y) =tAx+ (1t)Ay=b

f(tx+ (1t)y)tf(x) + (1t)f(y) =f?

Thereforetx+ (1t)yis also a solution

Another key property: iffis strictly convex, then thesolution is unique , i.e.,Xoptcontains one element 6

Example: lasso

Giveny2Rn,X2Rnp, consider thelasso p roblem:

min kyXk22 subject tokk1s Is this convex? What is the criterion function? The inequality and equality constraints? Feasible set? Is the solution unique, when: npandXhas full column rank? p > n(\high-dimensional" case)? How do our answers change if we changed criterion to

Hub erloss

n X i=1(yixTi); (z) =( 12 z2jzj jzj 12

2else?

7

Example: support vector machines

Giveny2 f1;1gn,X2Rnpwith rowsx1;:::xn, consider the support vector machine o rSVM p roblem: min 0;12 kk22+CnX i=1 i subject toi0; i= 1;:::n y i(xTi+0)1i; i= 1;:::n Is this convex? What is the criterion, constraints, feasible set? Is the solution(;0;)unique? What if changed the criterion to 12 kk22+12

20+CnX

i=1

1:01i?

For original criterion, what aboutcomponent, at the solution? 8quotesdbs_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