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 Existence and uniquenessAssume thatA lRm nhas full row rankm nand that the reduced HessianZTBZis positive definite.

3.3.3 Null-space approach The null-space approach does not require regularity of B and thus has a wider range of applicability than the range-space approach. We assume that A 2 lRm£n has full row rank m and that ZTBZ is positive deflnite, where Z 2 lRn£(n¡m) is the matrix whose columns span Ker A which can be computed by QR factorization ...

  Matrix, Space, Null