Primal and dual active-set methods for convex quadratic programming

Computational methods are proposed for solving a convex quadratic program (QP). Active-set methods are defined for a particular primal and dual formulation of a QP with general equality constraints and simple lower bounds on the variables. In the first part of the paper, two methods are proposed, one primal and one dual. These methods generate a sequence of iterates that are feasible with respect to the equality constraints associated with the optimality conditions of the primal–dual form. The primal method maintains feasibility of the primal inequalities while driving the infeasibilities of the dual inequalities to zero. The dual method maintains feasibility of the dual inequalities while moving to satisfy the primal inequalities. In each of these methods, the search directions satisfy a KKT system of equations formed from Hessian and constraint components associated with an appropriate column basis. The composition of the basis is specified by an active-set strategy that guarantees the nonsingularity of each set of KKT equations. Each of the proposed methods is a conventional active-set method in the sense that an initial primal- or dual-feasible point is required. In the second part of the paper, it is shown how the quadratic program may be solved as a coupled pair of primal and dual quadratic programs created from the original by simultaneously shifting the simple-bound constraints and adding a penalty term to the objective function. Any conventional column basis may be made optimal for such a primal–dual pair of shifted-penalized problems. The shifts are then updated using the solution of either the primal or the dual shifted problem. An obvious application of this approach is to solve a shifted dual QP to define an initial feasible point for the primal (or vice versa). The computational performance of each of the proposed methods is evaluated on a set of convex problems from the CUTEst test collection.

The authors would like to thank two referees for constructive comments that significantly improved the presentation.

Authors and Affiliations

1. Optimization and Systems Theory, Department of Mathematics, KTH Royal Institute of Technology, 100 44, Stockholm, Sweden

   Anders Forsgren

2. Department of Mathematics, University of California, San Diego, La Jolla, CA, 92093-0112, USA

   Philip E. Gill & Elizabeth Wong

Corresponding author

Correspondence to Elizabeth Wong.

A. Forsgren—Research supported by the Swedish Research Council (VR).

P. E. Gill, E. Wong—Research supported in part by Northrop Grumman Aerospace Systems, and National Science Foundation Grants DMS-1318480 and DMS-1361421.

Appendix

The appendix concerns some basic results used in previous sections. The first result shows that the nonsingularity of a KKT matrix may be established by checking that the two row blocks \(\big (H \ \ A^T \big )\) and \(\big (A \ \ -M \big )\) have full row rank.

Proposition 5

Assume that H and M are symmetric, positive semidefinite matrices. The vectors u and v satisfy

if and only if

Proof

If (26) holds, then (25) holds, which establishes the “if” direction. Now assume that u and v are vectors such that (25) holds. Then,

Adding these equations gives the identity \(u^T\!H u + v^T\!M v = 0\). But then, the symmetry and semidefiniteness of H and M imply \(u^T\!H u=0\) and \(v^T\!M v = 0\). This can hold only if \(H u = 0\) and \(M v=0\). If \(Hu=0\) and \(M v=0\), (25) gives \(A^T\!v=0\) and \(Au=0\), which implies that (26) holds, which completes the proof. \(\square \)

The next result shows that when checking a subset of the columns of a symmetric positive semidefinite matrix for linear dependence, it is only the diagonal block that is of importance. The off-diagonal block may be ignored.

Proposition 6

Let H be a symmetric, positive semidefinite matrix partitioned as

Then,

Proof

If H is positive semidefinite, then \(H_{11}\) is positive semidefinite, and it holds that

if and only if

if and only if \(H_{11} u = 0\), as required. \(\square \)

In the following propositions, the distinct integers k and l, together with integers from the index sets \(\mathcal {B}\) and \(\mathcal {N}\) define a partition of \(\mathcal {I}= \{1\), 2, ..., \(n\}\), i.e., \(\mathcal {I}= \mathcal {B}\cup \{k\} \cup \{l\} \cup \mathcal {N}\). If w is any n-vector, the \(n_{ B}\)-vector \(w_{ B}\) and \(w_{ N}\)-vector \(w_{ N}\) denote the vectors of components of w associated with \(\mathcal {B}\) and \(\mathcal {N}\). For the symmetric Hessian H, the matrices \(H_{ BB }\) and \(H_{ NN }\) denote the subset of rows and columns of H associated with the sets \(\mathcal {B}\) and \(\mathcal {N}\) respectively. The unsymmetric matrix of components \(h_{ij}\) with \(i\in \mathcal {B}\) and \(j\in \mathcal {N}\) will be denoted by \(H_{ BN }\). Similarly, \(A_{ B}\) and \(A_{ N}\) denote the matrices of columns associated with \(\mathcal {B}\) and \(\mathcal {N}\).

The next result concerns the row rank of the \(\big (A \ \ -M \big )\) block of the KKT matrix.

Proposition 7

If the matrix \(\big ( a_l \ \ a_k \ \ A_{ B} \ \ -M \big )\) has full row rank, and there exist \(\Delta x_l\), \(\Delta x_k\), \(\Delta x_{ B}\), and \(\Delta y\) such that \(a_l \Delta x_l + a_k \Delta x_k + A_{ B}\Delta x_{ B}+ M \Delta y=0\) with \(\Delta x_k\ne 0\), then \(\big ( a_l \ \ A_{ B} \ \ -M \big )\) has full row rank.

Proof

It must be established that \(u^T\!\begin{pmatrix} a_l&A_{ B}&-M \end{pmatrix}=0\) implies that \(u=0\). For a given u, let \(\gamma = -u^T\!a_k\), so that

Then,

As \(\Delta x_k\ne 0\), it must hold that \(\gamma = 0\), in which case

As \(\big ( a_l \ \ a_k \ \ A_{ B} \ \ -M \big )\) has full row rank by assumption, it follows that \(u=0\) and \(\big ( a_l \ \ A_{ B} \ \ -M \big )\) must have full row rank. \(\square \)

An analogous result holds concerning the \(\big (H \ \ A^T \big )\) block of the KKT matrix.

Proposition 8

If \(\big (H_{ BB }^{} \ \ A_{ B}^T \big )\) has full row rank, and there exist quantities \(\Delta x_{ N}\), \(\Delta x_{ B}\), \(\Delta y\), and \(\Delta z_k\) such that

with \(\Delta z_k \ne 0\), then the matrix

has full row rank.

Proof

Let \(\big (\mu \ \ v^T \big )\) be any vector such that

The assumed identity (27) gives

As \(\Delta z_k\ne 0\) by assumption, it must hold that \(\mu =0\). The full row rank of \(\big (H_{ BB }^{} \ \ A_{ B}^T \big )\) then gives \(v = 0\) and

must have full row rank. Proposition 5 implies that this is equivalent to

having full row rank. \(\square \)

The next proposition concerns the primal subiterations when the constraint index k is moved from \(\mathcal {B}\) to \(\mathcal {N}\). In particular, it is shown that the \(K_l\) matrix is nonsingular after a subiteration.

Proposition 9

Assume that (\(\Delta x_l\), \(\Delta x_k\), \(\Delta x_{ B}\), \(-\Delta y\), \(-\Delta z_l\)) is the unique solution of the equations

and that \(\Delta x_k\ne 0\). Then, the matrices \(K_l\) and \(K_k\) are nonsingular, where

Proof

By assumption, the Eq. (28) have a unique solution with \(\Delta x_k\ne 0\). This implies that there is no solution of the overdetermined equations

Given an arbitrary matrix D and nonzero vector f, the fundamental theorem of linear algebra implies that if \(D w = f\) has no solution, then there exists a vector v such that \(v^T\!f \ne 0\). The application of this result to (29) implies the existence of a nontrivial vector (\(\Delta \widetilde{x}_l\), \(\Delta \widetilde{x}_k\), \(\Delta \widetilde{x}_{ B}\), \(-\Delta \widetilde{y}\), \(-\Delta \widetilde{z}_l\), \(-\Delta \widetilde{z}_k\)) such that

(30)

with \(\Delta \widetilde{z}_l\ne 0\). The last equation of (30) gives \(\Delta \widetilde{x}_l + \Delta \widetilde{z}_l=0\), in which case \(\Delta \widetilde{x}_l \Delta \widetilde{z}_l = -\Delta \widetilde{z}_l^2 <0\) because \(\Delta \widetilde{z}_l\ne 0\). Any solution of (30) may be viewed as a solution of the equations \(H \Delta \widetilde{x}- A^T\!\Delta \widetilde{y}- \Delta \widetilde{z}= 0\), \(A \Delta \widetilde{x}+ M \Delta \widetilde{y}= 0\), \(\Delta \widetilde{z}_{ B}=0\), and \(\Delta \widetilde{x}_i = 0\) for \(i\in \{ 1\), 2, ..., \(n\} {\setminus } \{ l \} {\setminus } \{ k \}\). An argument similar to that used to establish Proposition 2 gives

which implies that \(\Delta \widetilde{x}_k \Delta \widetilde{z}_k > 0\), with \(\Delta \widetilde{x}_k\ne 0\) and \(\Delta \widetilde{z}_k\ne 0\).

As the search direction is unique, it follows from (28) that \(\big ( h_{{ Bl }}^{} \ \ H_{{ Bk }}^{} \ \ H_{ BB }^{} \ \ A_{ B}^T \big )\) has full row rank, and Proposition 6 implies that \(\big (H_{ BB }^{} \ \ A_{ B}^T \big )\) has full row rank. Hence, as \(\Delta \widetilde{z}_l\ne 0\), it follows from (30) and Proposition 8 that the matrix

has full row rank, which is equivalent to the matrix

having full row rank by Proposition 6,

Again, the search direction is unique and (28) implies that \(\big ( a_l \ \ a_k \ \ A_{ B} \ \ -M \big )\) has full row rank. As \(\Delta \widetilde{x}_k\ne 0\), Proposition 7 implies that \(\big ( a_l \ \ A_{ B} \ \ -M \big )\) must have full row rank. Consequently, Proposition 5 implies that \(K_l\) is nonsingular.

As \(\Delta \widetilde{x}_k\), \(\Delta \widetilde{x}_l\), \(\Delta \widetilde{z}_k\) and \(\Delta \widetilde{z}_l\) are all nonzero, the roles of k and l may be reversed to give the result that \(K_k\) is nonsingular. \(\square \)

The next proposition concerns the situation when a constraint index k is moved from \(\mathcal {N}\) to \(\mathcal {B}\) in a dual subiteration. In particular, it is shown that the resulting matrix \(K_{ B}\) defined after a subiteration is nonsingular.

Proposition 10

Assume that there is a unique solution of the equations

with \(\Delta z_k\ne 0\). Then, the matrices \(K_l\) and \(K_k\) are nonsingular, where

Proof

As (31) has a unique solution with \(\Delta z_k\ne 0\), there is no solution of

The fundamental theorem of linear algebra applied to (32) implies the existence of a solution of

(33)

with \(\Delta \widetilde{z}_l\ne 0\). It follows from (33) that \(\Delta \widetilde{x}_l+\Delta \widetilde{z}_l=0\). As \(\Delta \widetilde{z}_l\ne 0\), this implies \(\Delta \widetilde{x}_l \Delta \widetilde{z}_l<0\). The solution of (33) may be regarded as a solution of the homogeneous equations \(H \Delta x- A^T\!\Delta y- \Delta z= 0\), \(A \Delta x+ M \Delta y= 0\), with \(\Delta z_i = 0\), for \(i\in \mathcal {B}\), and \(\Delta x_i = 0\), for \(i\in \{1,\dots ,n\}{\setminus }\{k\}{\setminus }\{l\}\). Hence, Proposition 2 gives

so that \(\Delta \widetilde{x}_k \Delta \widetilde{z}_k > 0\). Hence, it must hold that \(\Delta \widetilde{x}_k\ne 0\) and \(\Delta \widetilde{z}_k\ne 0\).

As \(\Delta \widetilde{x}_k\ne 0\), \(\Delta \widetilde{x}_l\ne 0\), \(\Delta \widetilde{z}_k\ne 0\) and \(\Delta \widetilde{z}_l\ne 0\), the remainder of the proof is analogous to that of Proposition 9. \(\square \)

The next result gives expressions for the primal and dual objective functions in terms of the computed search directions.

Proposition 11

Assume that (x, y, z) satisfies the primal and dual equality constraints

Consider the partition \(\{1\), 2, ..., \(n\}= \mathcal {B}\cup \{l\}\cup \mathcal {N}\) such that \(x_{ N}+q_{ N}=0\) and \(z_{ B}+r_{ B}=0\). If the components of the direction (\(\Delta x\), \(\Delta y\), \(\Delta z\)) satisfy (9), then the primal and dual objective functions for (\(\hbox {PQP}_{q,r}\)) and (\(\hbox {DQP}_{q,r}\)), i.e.,

satisfy the identities

Proof

The directional derivative of the primal objective function is given by

where the identity \(Hx+c = A^T\!y +z\) has been used in (34a) and the identities \(A\Delta x+ M\Delta y=0\), \(\Delta x_N=0\) and \(z_{ B}+r_{ B}=0\) have been used in (34b).

The curvature in the direction (\(\Delta x,\Delta y\)) is given by

where the last step follows from Proposition 2.

The directional derivative of the dual objective function is given by

where the identity \(H \Delta x-A^T\!\Delta y-\Delta z=0\) has been used in (36c) and the identities \(Ax + My - b = 0\), \(x_{ N}+q_{ N}=0\) and \(\Delta z_{ B}=0\) have been used in (36e).

As z only appears linearly in the dual objective function, it follows from the structure of the Hessian matrices of \(f_{ P}(x,y)\) and \(f_{ D}(x,y,z)\) in combination with (35) that

\(\square \)

The final result shows that there is no loss of generality in assuming that \(\big (A \ \ M \big )\) has full row rank in (\(\hbox {PQP}_{q,r}\)).

Proposition 12

There is no loss of generality in assuming that \(\big (A \ \ M \big )\) has full row rank in (\(\hbox {PQP}_{q,r}\)).

Proof

Let (x, y, z) be any vector satisfying (2a) and (2b). Assume that \(\big (A \ \ M \big )\) has linearly dependent rows, and that \(\big (A \ \ M \big )\) and b may be partitioned conformally such that

with \(\big ( A_{1} \ \ M_{11} \ \ M_{12} \big )\) having full row rank, and

with \(A_1\in \mathbb {R}^{m_1\times n}\) and \(A_2\in \mathbb {R}^{m_2\times n}\) for some matrix \(N\in \mathbb {R}^{m_2\times m_1}\). From the linear dependence of the rows of \(\big (A \ \ M \big )\), it follows that x, y and z satisfy (2a) and (2b) if and only if

It follows from (37) that \(M_{12} = M_{11} N^T\) and \(A_2^T=A_1^T N^T\), so that x, y and z satisfy (2a) and (2b) if and only if

We may now define \(\widetilde{y}_1=y_1+N^T\!y_2\) and replace (2b) and (2a) by the system

By assumption, \(\big ( A_{1} \ \ M_{11} \ \ M_{12} \big )\) has full row rank. Proposition 6 implies that \(\big (A_{1} \ \ M_{11} \big )\) has full row rank. This gives an equivalent problem for which \(\big (A_{1} \ \ M_{11} \big )\) has full row rank. \(\square \)

Reprints and permissions