[PDF] Chapter 16 Quadratic Optimization Problems

View - Download Chapter 16 Quadratic Optimization Problems

Previous PDF

Next PDF

Chapter16

QuadraticOptimizationPro blems

16.1Quadratic Optimization:ThePositive Definite

Case Inthis chapter,we considertwoclassesofquadraticopti- mizationproblemsthatap pearfrequentlyinengi neering andincom puters cience(especiallyincomput ervision):

1.Minimizing

f(x)= 1 2 x Ax+x b overallx"R n ,orsubjecttolinearora necon- straints.

2.Minimizing

f(x)= 1 2 x Ax+x b overtheu nitsphere . 699

700CHAPTER16.QUADRATIC OPTIMIZAT IONPROBLEMS

Inbot hcases,Aisasym metr icmatrix.Wealsoseek

necessaryandsu cientconditionsforftoh aveaglobal minimum.

Manyproble msinphysicsandengineeri ngcanb estated

asthe minimizationofsome energyfunction ,withor withoutconstraint s. Indeed,itis afundamen talpr incipleofm echanicsthat natureactssoas tominimizeener gy. Furthermore,ifaphysicalsystemisin astabl est ateof equilibrium,thentheenergyinth atstateshouldb emin- imal. Thesimplest kindofenergyfunction isaq uadra ticfunc- tion.

16.1.QUADRATICOP TIMIZATION:THEPOSITIVED EFINITECASE701

Suchfunctionsc anbeconv enientlyde finedinthe form

P(x)=x

Ax#x b, whereAisasym metr icn$nmatrix,andx,b,arevectors inR n ,viewedascolumnvectors. Actually,forreasonsthat willbeclearshortly ,itispref er- ableto putafactor 1 2 infron tofthequadratic term ,so that P(x)= 1 2 x Ax#x b.

Thequestion is,underwhatconditions( onA)doesP(x)

haveaglobalminimum, prefe rablyunique ?

702CHAPTER16.QUADRATIC OPTIMIZAT IONPROBLEMS

Wegi veacompletea nsw ertotheabovequestionint wo

stages:

1.Inthis section,wesho wthatifAissymm etricposi-

tivedefinite,th enP(x)hasauniqueglobalminimum preciselywhen Ax=b.

2.InSection 16.2,wegivenecessar yandsu !cientcon-

ditionsinthe generalcas e,inter msofthepseudo- inverseofA.

Web eginwiththematr ixversionof Definition 14.2.

isa matr ixwhoseeigenvaluesarestrictlyp ositive, and asymmetricpositivesemidefinitematrixisam atrix whoseeigenv aluesarenonnegative.

16.1.QUADRATICOP TIMIZATION:THEPOSITIVED EFINITECASE703

Equivalentcriteriaaregiveninthe followin gprop osition.

Proposition16.1.GivenanyEuclidean space Eof

dimensionn,thefol lowingprop ertieshold: definitei &x,f(x)'>0 forall x"Ewithx(=0. semidefinitei &x,f(x)')0 forall x"E. Somespec ialnotationiscustomary(esp eciallyinthefie ld ofconv exoptinization)toexpresst hatasymmetricma- trixispo sitivedefin iteorpositivesemidefinite.

704CHAPTER16.QUADRATIC OPTIMIZAT IONPROBLEMS

wew riteA*0ifAisposit ivesemidefiniteandwewrite

A+0ifAisp ositivedefinite.

Itshouldb enoted thatw ecandefinether elation

A*B betweenanytwon$nmatrices(symmetricorn ot)i"

A#Bissym metricpositivesemidefinite.

Itiseasy toc heckt hatthisrelation isactuallyapartial orderonmatr ices,called thepositivesemidefinitecone

Section2.4.

IfAissymm etricpositivedefinite,itiseasilycheck ed thatA #1 isalsosym met ricpositivedefinite.

Also,ifCisasym metr icpositivedefinitem$mmatrix

andAisan m$nmatrixofrankn(andsom)n), thenA

CAissymm etricpositivedefinite.

16.1.QUADRATICOP TIMIZATION:THEPOSITIVED EFINITECASE705

Wec annowprov ethat

P(x)= 1 2 x Ax#x b hasaglobal minimum whenAissymm etricpositivedef- inite.

Proposition16.2.Givenaquadraticfunction

P(x)= 1 2 x Ax#x b, ifAissymmetric positivedefinite,thenP(x)hasa uniqueglobal minimumforthesolutionof thelinear systemAx=b.Theminimum valueofP(x)is P(A #1 b)=# 1 2 b A #1 b.

706CHAPTER16.QUADRATIC OPTIMIZAT IONPROBLEMS

Remarks:

(1)Thequadrat icfunctionP(x)isalsogivenby P(x)= 1 2 x Ax#b x, butt hedefinitionus ingx bismor econvenientfor theproof ofProposition16. 2. (2)IfP(x)containsaconstanttermc"R,sothat P(x)= 1 2 x Ax#x b+c, theproo fofProposition16 .2stillsh owsthatP(x) hasa uniqueglobalm ini mumfor x=A #1 b,butthe minimalvalueis P(A #1 b)=# 1 2 b A #1 b+c.

16.1.QUADRATICOP TIMIZATION:THEPOSITIVED EFINITECASE707

Thus,whenth eenergy functionP(x)ofasystemisgiven

byaq uad raticfunction P(x)= 1 2 x Ax#x b, whereAissym metricpositivedefinite,findingtheglob al minimumofP(x)isequivalent tosolvingthelinear systemAx=b.

Sometimes,itisusefultorecastaline arproble mAx=b

asav ariational problem(findingtheminimumofsom e energyfunction ).

However,veryoften,aminimization problemcomeswith

extraconstraintsthatmustbesa tisfiedforall admissibl e solutions.

708CHAPTER16.QUADRATIC OPTIMIZAT IONPROBLEMS

Forinst ance,wemaywanttominimizeth equadr atic

function Q(y 1 ,y 2 1 2 y 2 1 +y 2 2 subjecttotheconstraint 2y 1 #y 2 =5.

Thesolut ionforwhichQ(y

1 ,y 2 )isminimumisnolonger (y 1 ,y 2 )=(0,0),butinstead, (y 1 ,y 2 )=(2,#1),aswill besh ownlater.

Geometrically,thegraph ofthefun ctiondefinedb y

z=Q(y 1 ,y 2 )inR 3 isapar aboloidof revolutionPwith axisofr evolution Oz.

Theconstr aint

2y 1 #y 2 =5 correspondstotheverticalplan eHparalleltothez-axis andcont ainingthelineofequation2 y 1 #y 2 =5inthe xy-plane.

16.1.QUADRATICOP TIMIZATION:THEPOSITIVED EFINITECASE709

Thus,theconst rainedminimumof Qislocat edonthe

parabolathatisthe interse ction oftheparab oloidPwith theplan eH. ofthe abovekindi stousethemethodofLagrangemul- tipliers.

Definition16.3.Thequadraticconstrained minimiza-

tionpr oblemconsistsinminimizing aquad raticfunction Q(y)= 1 2 y C #1 y#b y subjecttothelinear constraints A y=f, whereC #1 isanm$msymmetricpositiv edefinitema- trix,Aisanm$nmatrixofrankn(sotha tm)n), andwhere b,y"R m (viewedascolumnv ectors),and f"R n (viewedasacolumnv ector).

710CHAPTER16.QUADRATIC OPTIMIZAT IONPROBLEMS

Thereason forusingC

#1 insteadofCist hatthecon- strainedminimizationprob lemhasanin terpretationas arisesnaturallyis C(seeStra ng[33]).

SinceCandC

#1 arebothsym metricpositive definite, thisdoesn'tma keanydi erence,buti tseemspreferable tostic ktoStrang's nota tion.

Themet hodofLagrangeconsistsinincorporatingthe

nconstraintsA y=fintothequadr aticfunction

Q(y),byintroducingextravariables!=(!

1quotesdbs_dbs17.pdfusesText_23

[PDF] lagrange multipliers pdf

[PDF] lagrangian field theory pdf

[PDF] laman race 2020

[PDF] lambda return value

[PDF] lambda trailing return type

[PDF] lana del rey age 2012

[PDF] lana del rey songs ranked billboard

[PDF] lana del rey the greatest album

[PDF] lancet diet study

[PDF] lancet nutrition

[PDF] lands end trail map pdf

[PDF] landwarnet blackboard learn

[PDF] lane bryant annual bra sale

[PDF] lane bryant annual bra sale 2019

[PDF] lane bryant bogo bra sale