Chapter 12 Quadratic Optimization Problems

1 Chapter 12 Quadratic Optimization Quadratic Optimization : The Positive DefiniteCaseIn this Chapter , we consider two classes of Quadratic opti-mization Problems that appear frequently in engineeringand in computer science (especially in computer vision) (x)=12x Ax+x bover allx Rn, (x)=12x Ax+x bover the unit 12. Quadratic Optimization PROBLEMSIn both cases,Ais a symmetric matrix. We also seeknecessary and sufficient conditions forfto have a Problems in physics and engineering can be statedas theminimization of some energy function,withorwithout , it is a fundamental principle of mechanics thatnature acts so as to minimize , if a physical system is in a stable state ofequilibrium, then the energy in that state should be simplest kind of energy function is a Quadratic Quadratic Optimization : THE POSITIVE DEFINITE CASE449 Such functions can be conveniently defined in the formP(x)=x Ax x b,whereAis a symmetricn nmatrix, andx, b,arevectorsinRn, , for reasons that will be clear shortly, it is prefer-able to put a factor12in front of the Quadratic term, sothatP(x)=12x Ax x question is, under what conditions (onA)doesP(x)have a global minimum, preferably unique?

2 450 Chapter 12. Quadratic Optimization PROBLEMSWe give a complete answer to the above question in this section, we show that ifAis symmetric posi-tive definite, thenP(x)hasauniqueglobalminimumprecisely whenAx= Section , we give necessary and sufficient con-ditions in the general case, in terms of the pseudo-inverse begin with the matrix version of Definition definite matrixis a matrix whose eigenvalues are strictly positive, andasymmetricpositive semidefinite matrixis a matrixwhose eigenvalues are Quadratic Optimization : THE POSITIVE DEFINITE CASE451 Equivalent criteria are given in the following any Euclidean spaceEofdimensionn, the following properties hold:(1)Every self-adjoint linear mapf:E Eis positivedefinite iff x, f(x) >0for allx Ewithx =0.(2)Every self-adjoint linear mapf:E Eis positivesemidefinite iff x, f(x) 0for allx special notation is customary (especially in the fieldof convex optinization) to express that a symmetric ma-trix is positive definite or positive 12.

3 Quadratic Optimization PROBLEMSD efinition anyn nsymmetric matrixAwe writeA 0ifAis positive semidefinite and we writeA 0ifAis positive should be noted that we can define the relationA Bbetween any twon nmatrices (symmetric or not) iffA Bis symmetric positive is easy to check that this relation is actually a partialorder on matrices, called thepositive semidefinite coneordering;fordetails,seeBoydandVanden berghe[8],Section symmetric positive definite, it is easily checkedthatA 1is also symmetric positive , ifCis a symmetric positive definitem mmatrixandAis anm nmatrix of rankn(and som n),thenA CAis symmetric positive Quadratic Optimization : THE POSITIVE DEFINITE CASE453We can now prove thatP(x)=12x Ax x bhas a global minimum whenAis symmetric positive a Quadratic functionP(x)=12x Ax x b,ifAis symmetric positive definite, thenP(x)has aunique global minimum for the solution of the linearsystemAx=b.

4 The minimum value ofP(x)isP(A 1b)= 12b A 12. Quadratic Optimization PROBLEMSR emarks:(1)The Quadratic functionP(x)isalsogivenbyP(x)=12x Ax b x,but the definition usingx bis more convenient forthe proof of Proposition (2)IfP(x)containsaconstanttermc R,sothatP(x)=12x Ax x b+c,the proof of Proposition still shows thatP(x)has a unique global minimum forx=A 1b,buttheminimal value isP(A 1b)= 12b A 1b+ Quadratic Optimization : THE POSITIVE DEFINITE CASE455 Thus, when the energy functionP(x)ofasystemisgivenby a Quadratic functionP(x)=12x Ax x b,whereAis symmetric positive definite,finding the globalminimum ofP(x)is equivalent to solving the linearsystemAx= , it is useful to recast a linear problemAx=bas a variational problem (finding the minimum of someenergy function).However, very often, a minimization problem comes withextraconstraintsthat must be satisfied for all 12. Quadratic Optimization PROBLEMSFor instance, we may want to minimize the quadraticfunctionQ(y1,y2)=12 y21+y22 subject to the constraint2y1 y2= solution for whichQ(y1,y2)isminimumisnolonger(y1,y2)= (0,0), but instead, (y1,y2)=(2, 1), as willbe shown , the graph of the function defined byz=Q(y1,y2)inR3is a paraboloid of revolutionPwithaxis of constraint2y1 y2=5corresponds to the vertical planeHparallel to thez-axisand containing the line of equation 2y1 y2= Quadratic Optimization .

5 THE POSITIVE DEFINITE CASE457 Thus, the constrained minimum ofQis located on theparabola that is the intersection of the paraboloidPwiththe the above kind is to use the method ofLagrange constrained minimiza-tion problemconsists in minimizing a Quadratic functionQ(y)=12y C 1y b ysubject to the linear constraintsA y=f,whereC 1is anm msymmetric positive definite ma-trix,Ais anm nmatrix of rankn(so thatm n),and whereb, y Rm(viewed as column vectors), andf Rn(viewed as a column vector).458 Chapter 12. Quadratic Optimization PROBLEMSThe reason for usingC 1instead ofCis that the con-strained minimization problem has an interpretation asasetofequilibriumequationsinwhichthema trixthatarises naturally isC(see Strang [27]).SinceCandC 1are both symmetric positive definite,this doesn t make any difference, but it seems preferableto stick to Strang s method of Lagrange consists inincorporating thenconstraintsA y=finto the Quadratic functionQ(y),byintroducingextravariables =( 1.)

6 , n)calledLagrange multipliers, theLagrangianL(y, )=Q(y)+ (A y f)=12y C 1y (b A ) y Quadratic Optimization : THE POSITIVE DEFINITE CASE459We shall prove that our constrained minimization prob-lem has a unique solution given by the system of linearequationsC 1y+A =b,A y=f,which can be written in matrix form as C 1AA 0 y = bf .Note that the matrix of this system is symmetric. Elimi-natingyfrom the first equationC 1y+A =b,we gety=C(b A ),and substituting into the second equation, we getA C(b A )=f,that is,A CA =A Cb 12. Quadratic Optimization PROBLEMSH owever, by a previous remark, sinceCis symmetricpositive definite and the columns ofAare linearly inde-pendent,A CAis symmetric positive definite, and that this way of solving the system requires solvingfor the Lagrange multipliers A ,wealsonotethatthesystem C 1AA 0 y = bf is equivalent to the systeme=b A ,y=Ce,A y= latter system is called theequilibrium equationsbyStrang [27].

7 Quadratic Optimization : THE POSITIVE DEFINITE CASE461 Indeed, Strang shows that the equilibrium equations ofmany physical systems can be put in the above order to prove that our constrained minimization prob-lem has a unique solution, we proceed to prove that theconstrained minimizationofQ(y)subjecttoA y=fis equivalent to theunconstrained maximizationof an-other function P( ).We getP( )byminimizing the LagrangianL(y, )treated as a function 1is symmetric positive definite andL(y, )=12y C 1y (b A ) y f,by Proposition the global minimum (with respect toy)ofL(y, )isobtainedforthesolutionyofC 1y=b A ,and the minimum ofL(y, )isminyL(y, )= 12(A b) C(A b) 12. Quadratic Optimization PROBLEMSL ettingP( )=12(A b) C(A b)+ f,we claim that the solution of theconstrained minimiza-tionofQ(y)subjecttoA y=fis equivalent to theunconstrained maximizationof P( ).In order to prove that the unique minimum of the con-strained problemQ(y)subjecttoA y=fis the uniquemaximum of P( ), we computeQ(y)+P( ).

8 Proposition Quadratic constrained mini-mization problem of Definition has a unique so-lution(y, )given by the system C 1AA 0 y = bf .Furthermore, the component of the above solutionis the unique value for which P( )is Quadratic Optimization : THE POSITIVE DEFINITE CASE463 Remarks:(1)There is a form ofdualitygoing on in this situa-tion. The constrained minimization ofQ(y)subjecttoA y=fis called theprimal problem,andtheun-constrained maximization of P( ) (y)=max P( ).Recalling thate=b A ,sinceP( )=12(A b) C(A b)+ f,we can also writeP( )=12e Ce+ expression often represents the totalpotentialenergyof a system. Again, the optimal solution isthe one that minimizes the potential energy (and thusmaximizes P( )).464 Chapter 12. Quadratic Optimization Problems (2)It is immediately verified that the equations of Propo-sition are equivalent to the equations stating thatthe partial derivatives of the LagrangianL(y, )arenull: L yi=0,i=1.

9 ,m, L j=0,j=1,.., , the constrained minimum ofQ(y)subjecttoA y=fis an extremum of the LagrangianL(y, ).As we showed in Proposition , this extremum cor-responds to simultaneouslyminimizingL(y, )withrespect toyandmaximizingL(y, )withrespectto .Geometrically,suchapointisasaddle pointforL(y, ).(3)The Lagrange multipliers sometimes have a naturalphysical Quadratic Optimization : THE POSITIVE DEFINITE CASE465 Going back to the constrained minimization ofQ(y1,y2)=12(y21+y22)subjectto2y1 y2=5,the Lagrangian isL(y1,y2, )=12 y21+y22 + (2y1 y2 5),and the equations stating that the Lagrangian has a sad-dle point arey1+2 =0,y2 =0,2y1 y2 5= obtain the solution (y1,y2, )=(2, 1, 1).466 Chapter 12. Quadratic Optimization Quadratic Optimization : The General CaseIn this section, we complete the study initiated in and give necessary and sufficient conditions for thequadratic function12x Ax+x bto have a global begin with the following simple fact:Proposition an invertible symmetricmatrix, then the functionf(x)=12x Ax+x bhas a minimum value iffA 0, in which case this op-timal value is obtained for a unique value ofx, namelyx = A 1b, and withf(A 1b)= 12b A Quadratic Optimization : THE GENERAL CASE467 Let us now consider the case of an arbitrary a symmetric matrix, thenthe functionf(x)=12x Ax+x bhas a minimum value iffA 0and(I AA+)b=0,in which case this minimum value isp = 12b A+ , ifA=U Uis an SVD ofA, then theoptimal value is achieved by allx Rnof the formx= A+b+U 0z ,for anyz Rn r, whereris the rank 12.

10 Quadratic Optimization PROBLEMSThe case in which we add either linear constraints of theformC x=0oraffineconstraintsoftheformC x=t(wheret =0)canbereducedtotheunconstrainedcaseusi ng aQR-decomposition us show how to do this for linear constraints of theformC x= we use aQRdecomposition ofC,bypermutingthecolumns, we may assume thatC=Q RS00 ,whereRis anr rinvertible upper triangular matrixandSis anr (m r)matrix(Chas rankr). Quadratic Optimization : THE GENERAL CASE469 Then, if we letx=Q yz ,wherey Rrandz Rn r,then,aftersomecalcula-tions, our original problem becomesminimize12(y ,z )QAQ yz +(y ,z )Qbsubject toy=0,y Rr,z Rn , the constraintC x=0hasbeeneliminated,andif we writeQAQ = G11G12G21G22 andQb= b1b2 ,b1 Rr,b2 Rn r,our problem becomesminimize12z G22z+z b2,z Rn r,the problem solved in Proposition 12. Quadratic Optimization PROBLEMSC onstraints of the formC x=t(wheret =0)canbehandled in a similar this case, we may assume thatCis ann mmatrixwith full rank (so thatm n)andt MAXIMIZING A Quadratic FUNCTION ON THE UNIT Maximizing a Quadratic Function on the UnitSphereIn this section we discuss various Quadratic optimizationproblems mostly arising from computer vision (image seg-mentation and contour grouping).