Chapter 3 Quadratic Programming

1 Optimization I; Chapter 356 Chapter 3 Quadratic Constrained Quadratic Programming problemsA special case of the NLP arises when the objective functionalfis quadraticand the constraintsh, gare linear inx lRn. Such an NLP is called a QuadraticProgramming (QP) problem. Its general form isminimizef(x) :=12xTBx xTb( )overx lRnsubject toA1x=c( )A2x d ,( )whereB lRn nis symmetric,A1 lRm n, A2 lRp n, andb lRn, c lRm, d we shall see in this Chapter , the QP ( )-( ) can be solved iterativelyby active set strategies or interior point methods where each iteration requiresthe solution of an equality constrained QP Equality constrained Quadratic programmingIf only equality constraints are imposed, the QP ( )-( ) reduces tominimizef(x) :=12xTBx xTb( )overx lRnsubject toAx=c ,( )whereA lRm n, m n. For the time being we assume thatAhas full KKT conditions for the solutionx lRnof the QP ( ),( ) give riseto the following linear system(B ATA0) =:K(x )=(bc),( )where lRmis the associated Lagrange denote byZ lRn (n m)the matrix whose columns span KerA, ,AZ= I; Chapter 357 Definition KKT matrix and reduced HessianThe matrixKin ( ) is called the KKT matrix and the matrixZTBZ isreferred to as the reduced Existence and uniquenessAssume thatA lRm nhas full row rankm nand that the reduced HessianZTBZis positive definite.

2 Then, the KKT matrixKis nonsingular. Hence,the KKT system ( ) has a unique solution (x , ).Proof:The proof is left as an exercise. Under the conditions of the previous lemma, it follows that the second ordersufficient optimality conditions are satisfied so thatx is a strict local minimizerof the QP ( ),( ). A direct argument shows thatx is in fact a Global minimizerLet the assumptions of Lemma be satisfied and let (x , ) be the uniquesolution of the KKT system ( ). Then,x is the unique global solution of theQP ( ),( ).Proof:Letx Fbe a feasible point, ,Ax=c, andp:=x x. Then,Ap= 0. Substitutingx=x pinto the objective functional, we getf(x) =12(x p)TB(x p) (x p)Tb==12pTBp pTBx +pTb+f(x ).Now, ( ) impliesBx =b AT . ObservingAp= 0, we havepTBx =pT(b AT ) =pTb (Ap)T = 0,whencef(x) =12pTBp+f(x ).In view ofp KerA, we can writep=Zu , u lRn m, and hence,f(x) =12uTZTBZu+f(x ).SinceZTBZis positive definite, we deducef(x)> f(x ). Consequently,x isthe unique global minimizer of the QP ( ),( ).

3 Optimization I; Chapter Direct solution of the KKT systemAs far as the direct solution of the KKT system ( ) is concerned, we distinguishbetween symmetric factorization and the range- space and null - space Symmetric indefinite factorizationA possible way to solve the KKT system ( ) is to provide a symmetric fac-torization of the KKT matrix according toPTKP=LDLT,( )wherePis an appropriately chosen permutation matrix ,Lis lower triangularwith diag(L) =I, andDis block on ( ), the KKT system ( ) is solved as follows:solveLy=PT(bc),( )solveD y=y ,( )solveLT y= y ,( )set(x )=P y .( ) Range- space approachThe range- space approach applies, ifB lRn nis symmetric positive Gauss elimination of the primal variablex leads to the Schur complementsystemAB 1AT =AB 1b c( )with the Schur complementS lRm mgiven byS:=AB 1AT. The range- space approach is particularly effective, if Bis well conditioned and easily invertible ( ,Bis diagonal or block-diagonal), B 1is known explicitly ( , by means of a quasi-Newton updating for-mula), the numbermof equality constraints is I; Chapter null - space approachThe null - space approach does not require regularity ofBand thus has a widerrange of applicability than the range- space assume thatA lRm nhas full row rankmand thatZTBZis positivedefinite, whereZ lRn (n m)is the matrix whose columns span KerAwhichcan be computed by QR factorization (cf.)

4 Chapter ).We partition the vectorx according tox =Y wY+ZwZ,( )whereY lRn mis such that [Y Z] lRn nis nonsingular andwY lRm, wZ lRn ( ) into the second equation of ( ), we obtainAx =AY wY+AZ = 0wZ=c ,( ) ,Y wYis a particular solution ofAx= lRm nhas rankmand [Y Z] lRn nis nonsingular, the productmatrixA[Y Z] = [AY0] lRm mis nonsingular. Hence,wYis well determinedby ( ).On the other hand, substituting ( ) into the first equation of ( ), we getBY wY+BZwZ+AT =b .Multiplying byZTand observingZTAT= (AZ)T= 0 yieldsZTBZwZ=ZTb ZTBY wY.( )The reduced KKT system ( ) can be solved by a Cholesky factorization of thereduced HessianZTBZ lR(n m) (n m). OncewYandwZhave been computedas the solutions of ( ) and ( ),x is obtained according to ( ).Finally, the Lagrange multiplier turns out to be the solution of the linear systemarising from the multiplication of the first equation in ( ) byYT:(AY)T =YTb YTBx .( ) Iterative solution of the KKT systemIf the direct solution of the KKT system ( ) is computationally too costly,the alternative is to use an iterative method.

5 An iterative solver can be ap-plied either to the entire KKT system or, as in the range- space and null -spaceapproach, use the special structure of the KKT I; Chapter Krylov methodsThe KKT matrixK lR(n+m) (n+m)is indefinite. In fact, ifAhas full row rankm,Khasnpositive andmnegative eigenvalues. Therefore, for the iterativesolution of ( ) Krylov subspace methods like GMRES (Generalized MinimumRESidual) and QMR (Quasi Minimum Residual) are appropriate Transforming range- space iterationsWe assumeB lRn nto be symmetric positive definite and suppose that Bissome symmetric positive definite and easily invertible approximation ofBsuchthat B 1B chooseKL lR(n+m) (n+m)as the lower triangular block matrixKL=(I0 A B 1I),( )which gives rise to the regular splittingKLK=( B AT0 S) =:M1 ( B(I B 1B) 0A(I B 1B) 0) =:M2 0,( )where S lRm mis given by S:= A B 1AT.( )We set := (x, )T, := (b, c) an iterate (0) lRn+m, we compute (k), k lN,by means of thetransforming range- space iterations (k+1)= (k)+M 11KL( K (k)) =( )= (I M 11 KLK) (k)+M 11KL , k transforming range- space iteration ( ) will be implemented as follows:d(k)= (d(k)1, d(k)2)T:= K (k),( )KLd(k)= (d(k)1, A B 1d(k)1+d(k)2)T,( )M1 (k)=KLd(k),( ) (k+1)= (k)+ (k).

6 ( )Optimization I; Chapter Transforming null - space iterationsWe assume thatx lRnand Rmadmit the decompositionx= (x1, x2)T, x1 lRm1, x2 lRn m1,( ) = ( 1, 2)T, 1 lRm1, 2 lRm m1,( )and thatA lRm nandB lRn ncan be partitioned by means ofA=(A11A12A21A22), B=(B11B12B21B22),( )whereA11, B11 lRm1 m1with the right-hand side in ( ) accordingly, the KKT system takes theform B11B12|AT11AT21B21B22|AT12AT22 | A11A12|0 0A21A22|0 0 x 1x 2 1 2 = b1b2 c1c2 .( )We rearrange ( ) by exchanging the second and third rows and columns B11AT11|B12AT21A110|A120 | B21AT12|B22AT22A210|A220 x 1 1 x 2 2 = b1c1 b2c2 .( )ObservingB12=BT21, in block form ( ) can be written as follows(A BTB D) =:K( 1 2) =: =( 1 2) =: ,( )where i:= (x i, i)T, i:= (bi, ci)T,1 i note that block Gauss elimination in ( ) leads to the Schur complementsystem(A BT0S)( 1 2)=( 1 2 Ba 1 1).( )The Schur complementSis given byS=D BA 1BT,( )Optimization I; Chapter 362whereA 1=(0A 111A T11 A T11B11A 111).

7 ( )We assume that A11 lRm1 m1is an easily invertible approximation ofA11anddefine A=(B11 AT11 A110).( )We remark that the inverse of Ais given as in ( ) withA 111, A T11replacedby A 111and A T11, introduce the right transformKR=(I A 1BT0I),( )which gives rise to the regular splittingKKR=( A0B S) =:M1 ((I A A 1) A( I+A A 1)BT00) =:M2 0,( )where S:=D B A 1BT.( )Given a start iterate (0)= ( (0)1, (0)2)T, we solve the KKT system ( ) bythe transforming null - space iterations (k+1)= (k)+KRM 11( K (k)) =( )= (I KRM 11K) (k)+KRM 11 , k Active set strategies for convex QP Primal active set strategiesWe consider the constrained QP problemminimizef(x) :=12xTBx xTb( )overx lRnsubject toCx=c( )Ax d ,( )Optimization I; Chapter 363whereB lRn nis symmetric positive definite,C lRm n, A lRp n, andb lRn, c lRm, d write the matricesAandCin the formA= a1 ap , ai lRn, C= c1 cm , ci lRn.( )The inequality constraints ( ) can be equivalently stated asaTix di,1 i m.

8 ( )The primal active set strategy is an iterative procedure:Given a feasible iteratex( ), 0,we determine an active setIac(x( )) {1, .., p}( )and consider the corresponding constraints as equality constraints, whereas theremaining inequality constraints are disregarded. Settingp=x( ) x , b( )=Bx( ) b ,( )we findf(x) =f(x( ) p) =12pTBp (b( ))Tp+g ,whereg:=12(x( ))TBx( ) bTx( ).The equality constrained QP problem to be solved at the ( +1)-st iterationstep is then:minimize12pTBp (b( ))Tp( )overp lRnsubject toCp= 0( )aTip= 0, i Iac(x( )),( )We denote the solution of ( )-( ) byp( ). The new iteratex( +1)is thenobtained according tox( +1)=x( ) p( ), [0,1],( )where is chosen such thatx( +1)stays particular, fori Iac(x( )) we haveaTix( +1)=aTix( ) aTip( )=aTix( ) I; Chapter 364On the other hand, ifaTip( ) 0 for somei / Iac(x( )), it follows thataTix( +1)=aTix( ) aTip( ) aTix( ) , ifaTip( )<0 fori / Iac(x( )), we haveaTix( +1)=aTix( ) aTip( ) di aTix( ) diaTip( ).

9 Consequently, in order to guarantee feasibility, we choose := min (1,mini/ Iax(x( ))aTix( ) diaTip( )).( )aTip( )<0We defineIb`(p( )) :={i / Iac(x( ))|aTip( )<0,mini/ Iax(x( ))aTix( ) diaTip( )<1}.( )Clearly,aTix( +1)=aTi(x( ) p( ))=di, i Ib`(x( )).Therefore,Ib`(p( )) is referred to as the set of blocking specifyIac(x( +1)) by adding toIac(x( )) the most restrictive blocking con-straint:Iac(x( +1)) :=( )Iac(x( )) {j Ib`(x( )|aTjx( ) djaTjp( )= mini/ Iac(x( ))aTix( ) diaTip( )}.aTip( )<0 Further information with respect to a proper specification of the set of activeconstraints is provided by systematically checking the KKT conditions:Assume thatp( )= 0 is the solution of the QP problem ( )-( ). Sincep( )satisfies the KKT conditions associated with that QP problem, there existLagrange multipliers ( ) lRmand ( )i, i Iac(x( )), such that b( )= (Bx( ) b) = m i=1 ( )ici i Iac(x( )) ( )iai.( )If we set ( )i:= 0, i {1, .., p}\Iac(x( )),Optimization I; Chapter 365it is clear thatx( ), ( ), and ( )satisfy the first KKT condition with respectto the original QP problem ( )-( ).)

10 Sincex( )is feasible, the second and third KKT conditions also hold check the fourth KKT condition in terms of the sign of the multiplier ( ):If ( )i 0, i Iac(x( )),the fourth KKT condition holds true. Consequently,x( )is a strict local mini-mum, sinceBis symmetric positive the other hand, if there existsj Iac(x( )) such that ( )j<0,we remove that constraint from the active set. We show that this strategyproduces a directionpin the subsequent iteration step that is feasible withrespect to the dropped constraint:Theorem Feasible and descent direction for active set strategyWe assume that x lRnsatisfies the KKT conditions for the QP problem( )-( ), , in particular ( ) holds true. Further, assume that theconstraint gradientsci,1 i m, ai, i Iac( x) are linearly independent. Fi-nally, suppose there isj Iac( x) such that j< the solution of the QP problemminimize12pTBp bTp( )overp lRnsubject toCp= 0( )aTip= 0, i Iac( x)\{j}.( )where b:=B x ,pis a feasible direction for the constraintj, ,aTjp , ifpsatisfies the second order sufficient optimality conditions for( )-( ), thenaTjp <0, ,pis a descent a solution of the QP problem ( )-( ), there existLagrange multipliers i,1 i m,and i, i Iac( x), i6=j, such thatBp b= m i=1 ici i Iac( x),i6=j iai.