Chapter 3 Quadratic Programming

← Back to document page

Optimization I; Chapter 356Chapter 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 357Definition KKT matrix and reduced HessianThe matrixKin ( ) is called the KKT matrix and the matrixZTBZisreferred to as the reduced Exist

The reduced KKT system (3.9) can be solved by a Cholesky factorization of the reduced Hessian ZTBZ 2 lR(n¡m)£(n¡m). Once w Y and wZ have been computed as the solutions of (3.8) and (3.9), x⁄ is obtained according to (3.7). Finally, the Lagrange multiplier turns out …