Linear and Quadratic Programming

The instruction LQPROG provides quick and efficient solutions to linear and quadratic programming problems. It minimizes either a linear or quadratic function in \(\bf{x}\) subject to

\begin{equation} {\bf{A}}_e {\bf{x}} = {\bf{b}}_e ,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\bf{A}}_l {\bf{x}} \le {\bf{b}}_l ,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\bf{A}}_g {\bf{x}} \ge {\bf{b}}_g \end{equation}

\begin{equation} {\bf{x}}_i \ge 0\,\,{\text{for all}}\,\,i = 1, \ldots ,nneg \label{eq:lqprogramming_positivity} \end{equation}

where, by design, \({\bf{b}}_e \ge 0,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\bf{b}}_l \ge 0,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\bf{b}}_g \ge 0\). A constraint with a naturally negative value of \(\bf{b}\) needs to be sign-flipped.

The constraints are input using matrices \(\bf{A}\) and \(\bf{b}\) constructed as follows:

\begin{equation} {\bf{A}} = \left[ {\begin{array}{*{20}c} {{\bf{A}}_e } \\ {{\bf{A}}_l } \\ {{\bf{A}}_g } \\ \end{array}} \right]\;,\;\;{\bf{b}} = \left[ {\begin{array}{*{20}c} {{\bf{b}}_e } \\ {{\bf{b}}_l } \\ {{\bf{b}}_g } \\ \end{array}} \right] \end{equation}

In other words, equality constraints must be listed first, followed by those inequality constraints which are \(\le\) a non-negative constant, and finally those which are written as \(\ge\) a non-negative constant. You input the constraints to LQPROG using the options A=A matrix and B=B vector. You have to indicate the number of equality constraints with the EQUAL=number of equalities, and the number of \(\ge\) constraints with GE=number of non-negativity constraints. The default for each of those options is 0, so all the input constraints are \(\le\) by default.

For linear programming, all the \(x\)’s are constrained to be non-negative, that is, \(nneg\) in \eqref{eq:lqprogramming_positivity} is the number of variables. By contrast, a quadratic program can handle unbounded arguments since a quadratic form (with positive definite matrix) is unbounded above at large values in all directions. You have to arrange the elements of \(x\) so the ones which are forced non-negative come first. The option NNEG=number of non-negative x’s can be used if there are some that are constrained to be non-negative and some unbounded. By default, all are constrained to be non-negative.

Linear Programming

LQPROG can solve linear programming problems of the form:

\begin{equation} {\mathrm{minimize}}\,\,{\bf{c'x}} \end{equation}

subject to the constraints described above. You input the cost vector with option C=C vector.

In this example, a firm is trying to allocate its advertising budget between magazine and television. Television costs more, but reaches a larger audience. The magazine readership, while smaller, has superior demographics. They want to allocate their budget in the most cost-effective manner given goals of meeting or exceeding total exposures and exposures for subgroups.

minimize \(40m + 200t\) subject to

\begin{equation} \begin{array}{ll} {4m + 40t \ge 160}&{\text{total exposures}} \\ {3m + 10t \ge 60}&{\text{high income}} \\ {8m + 10t \ge 80}&{\text{age group}} \\ {m,t \ge 0}&{} \\ \end{array} \end{equation}

The input matrices for this problem are

\begin{equation} {\bf{A}} = \left[ {\begin{array}{*{20}c} {{\bf{A}}_g } \\ \end{array}} \right]\; = \left[ {\begin{array}{*{20}c} 4 & {40} \\ 3 & {10} \\ 8 & {10} \\ \end{array}} \right]{\kern 1pt} {\kern 1pt} ,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\bf{b}} = \left[ {\begin{array}{*{20}c} {{\bf{b}}_g } \\ \end{array}} \right] = \left[ {\begin{array}{*{20}c} {160} \\ {60} \\ {80} \\ \end{array}} \right],\,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\bf{c}} = \left[ {\begin{array}{*{20}c} {40} & {200} \\ \end{array}} \right] \end{equation}

The input constraints are all \(\ge\), so we need the option GE=3. We can solve the problem with the following program:

dec rect a

dec vect b

compute a=||4.0,40.0|3.0,10.0|8.0,10.0||

compute b=||160.0,60.0,80.0||

lqprog(ge=3,c=||40.0,200.0||,a=a,b=b) x

The output is

In LPROG, minimum = 1000.00000000

Solution x =

10.000000000 3.000000000

Lagrange Multipliers

2.500000000 10.000000000 0.000000000

Quadratic Programming

LQPROG solves quadratic programming problems of the form:

\begin{equation} \mathrm{minimize }\frac{1}{2}{\kern 1pt} {\kern 1pt} {\bf{x'}}{\kern 1pt} {\bf{Q}}{\kern 1pt} {\kern 1pt} {\bf{x}} + {\bf{c'x}} \label{eq:lqprogramming_qprog} \end{equation}

subject to the constraints described earlier. As noted there, you can have components of \(\bf{x}\) which are allowed to be negative, but you must arrange the input matrices so that the ones subject to the non-negativity constraint come first. The Hessian matrix of the objective function, \(\bf{Q}\), is an \(nvar \times nvar\) symmetric matrix. The objective function is input to LQPROG using the options Q=Q matrix and C=C vector.

For quadratic problems, LQPROG uses the active set method with the conjugate gradient method (see Luenberger, 1989). An initial feasible solution is obtained by employing linear programming with artificial variables.

Note that you might have some work to do in transforming a problem to the form \eqref{eq:lqprogramming_qprog}. For instance, suppose that your objective function is

\begin{equation} x_1^2 + x_2^2 + x_3^2 + x_1 x_3 - 10x_1 - 4x_3 \end{equation}

To convert a function like this which is written out as a second order polynomial in \(x_1 ,x_2 , \ldots ,x_n \), call the second order terms \(S_{ij} x_i x_j \). Then the elements for \(\bf{Q}\) are:

\begin{equation} {\bf{Q}}\left( {i,j} \right) = \left\{ {\begin{array}{*{20}c} {2S_{ij} } \hfill & {{\text{for }}i = j} \hfill & {{\text{(diagonal elements)}}} \hfill \\ {S_{ij} } \hfill & {{\text{for }}i \ne j} \hfill & {{\text{(off - diagonal elements)}}} \hfill \\ \end{array}} \right. \label{eq:lqprogramming_qexam1Q} \end{equation}

The diagonal elements of \(\bf{Q}\) are twice the quadratic coefficients on the “squared” terms, so for instance \(Q(1,1)\) should be twice the coefficient on \(x_1^2 \). The off-diagonal elements of \(\bf{Q}\) are set equal to coefficients on the corresponding quadratic term: \(Q(1,2)\) would be the coefficient on \(x_1 x_2 \). For \eqref{eq:lqprogramming_qexam1Q}, the matrices in the objective function are:

\begin{equation} {\bf{Q}} = \left[ {\begin{array}{*{20}c} 2 & 0 & 1 \\ 0 & 2 & 0 \\ 1 & 0 & 2 \\ \end{array}} \right],\,\,\,\,{\bf{c'}} = \left[ { - 10,0, - 4} \right] \end{equation}

Examples

The example QPROG.RPF estimates a regression subject to non-negativity constraints and an adding up constraint. Since the sum of squares is a relatively straightforward quadratic expression, it's a simple application of quadratic programming.

LQPROG is the ideal tool for solving portfolio optimization problems. If you need to solve these subject to a restriction against taking short positions (thus non-negativity constraints on portfolio weights), there is no simple alternative. Example file PORTFOLIO.RPF finds the minimum variance portfolio, and also maps out the mean-variance frontier.