LQPROG Instruction

LQPROG(options) x

Solves linear and quadratic programming problems.

The form of LQPROG has changed over the years and now uses options as the preferred method of inputting the model. See "Older Form" below.

The linear programs take the form

minimize	\({\bf{c'x}}\)
subject to	\({{\bf{A}}_e}{\bf{x}} = {{\bf{b}}_e},\,\,\,{{\bf{A}}_l}{\bf{x}} \le {{\bf{b}}_l},\,\,\,{{\bf{A}}_g}{\bf{x}} \ge {{\bf{b}}_g}\)
	\({x_i} \ge 0\) for all i=1,...,nvar
	where, by design, \({{\bf{b}}_e} \ge 0\), \({{\bf{b}}_l} \ge 0\), \({{\bf{b}}_b} \ge 0\)

nvar is the number of unknowns. Quadratic programs have the same constraints (except, perhaps, on the x’s), and, subject to those constraints, solve the problem:

minimize

\(\frac{1}{2}{\kern 1pt} {\kern 1pt} {\bf{x'}}{\kern 1pt} {\bf{Q}}{\kern 1pt} {\kern 1pt} {\bf{x}} + {\bf{c'x}}\)

To choose quadratic programming, supply a \(\bf{Q}\); for linear programming, don’t provide a \(\bf{Q}\).

Note that, while LQPROG uses a fairly good general-purpose algorithm for solving these problems, it is not designed to handle very large problems with hundreds of variables or constraints.

Parameters

x	VECTOR into which the output will be stored. You don't need to declare this ahead of time.

Options

C=VECTOR supplying coefficients on the function being minimized

Q=RECTANGULAR supplying quadratic term coefficients

These input the matrices controlling the objective function.

If there is a Q matrix, LQPROG does quadratic programming; otherwise it does linear programming.

A=RECTANGULAR supplying constraint coefficients

B=VECTOR supplying constraining values

These supply the coefficients on the equality and inequality constraints. The equality constraints should be listed first, followed by ≤ constraints, and finally any ≥ constraints.

EQUALITIES=number of equality constraints [0]

GE=number of ≥ constraints [0]

By default, all constraints are assumed to be of the form Ax≤ b. You can use the EQUALITIES and GE options if you wish to include equality constraints and constraints of the form Ax≥b. Any equality constraints should be listed first in the A and b arrays, followed by any Ax≤b constraints. List any Ax≥b constraints last.

NNEG=number of of x components which must be non-negative [all]

This can only be used with quadratic programming. You can divide the x vector into the first group which must be non-negative and a second group which are unconstrained. By default, LQPROG assumes that all of the x values must be non-negative.

ITERATIONS=number of iterations [20 or # of constraints, whichever is greater]

CVCRIT=convergence criterion [\(10^{-8}\)]

ITERATIONS sets the maximum number of iterations that will be performed. If the procedure fails to converge in the specified number of iterations, re-execute the instruction with a higher iteration limit. CVCRIT controls the criterion value by which LQPROG determines whether or not the process has converged to a solution. LQPROG will continue iterating until either the change in the dot product of the gradient is smaller than the CVCRIT value, or until the iterations limit is reached. Note that the convergence is not measured by the coefficients as it is in most other numerical optimizations.

TRACE/[NOTRACE]

If you use TRACE, LQPROG will issue a report on the progress of the estimation after each iteration.

[PRINT]/NOPRINT

Controls the printing of results.

FEASIBLE/[NOFEASIBLE]

By default, LQPROG computes the full solution of the problem. You can use the FEASIBLE option to get just the initial feasible solution instead.

Variables Defined

%FUNCVAL	Final value of the function (REAL)
%LAGRANGE	VECTOR of Lagrange multipliers on the constraints

Linear Programming Example

* minimize -2*x1 - 4*x2 - x3 - x4

* subject to x1 + 3*x2 + x4 = 4

* 2*x1 + x2 <= 3

* x2 + 4*x3 + x4 <= 3

declare rectangular amat(3,4)

declare vector cvecx(4) bvec(3)

compute amat = || 1, 3, 0, 1 | 2, 1, 0, 0 | 0, 1, 4, 1 ||

compute cvec = || -2, -4, -1, -1 ||

compute bvec = || 4, 3, 3 ||

lqprog(equalities=1,a=amat,c=cvec,b=bvec) xout

Quadratric Programming Example

* minimize x1*x1 + x2*x2 + x3*x3 + x1*x3 - 10*x1 - 4*x3

* subject to 2*x1 + x2 + x3 = 2

* x1 + 2*x2 + 3*x3 = 5

* 2*x1 + 2*x2 + x3 <= 6

declare rectangular q(3,3) a(3,3)

declare vector c(3) b(3)

compute c = || -10, 0, -4 ||

compute b = || 2, 5, 6 ||

compute a = || 2, 1, 1 | 1, 2, 3 | 2, 2, 1 ||

compute q = || 2, 0, 1 | 0, 2, 0 | 1, 0, 2 ||

lqprog(equalities=2,q=q,c=c,a=a,b=b) results

The example below demonstrates a simple portfolio optimization routine. This finds the global minimum variance portfolio. N is the number of returns, and ExpRet and CovMat are the expected values and covariance matrix of the returns. To modify this for any number of assets, you simply need to change those three variables accordingly.

compute N=3

compute [vect] ExpRet = ||.15,.20,.08||

compute [symm] CovMat = ||.20|.05,.30|-.01,.015,.1||

* Compute the minimum variance portfolio, and its expected return

compute units=%fill(1,N,1.0)

lqprog(q=covMat,a=units,b=1.0,equalities=1) x

compute minr=%dot(x,expRet)

compute maxr=%maxvalue(expRet)

Older Form with Parameters

This is still supported, but we recommend using the newer method with options since they use descriptive names rather than order to determine which is which.

LQPROG(options) x c A b Q

Parameters

x	VECTOR into which the output will be stored. You don't need to declare this ahead of time.
c	VECTOR supplying the coefficients on the function being minimized.
A	RECTANGULAR array supplying the coefficients on the equality and inequality constraints. Equality constraints should be listed first, followed by inequality constraints.
b	VECTOR supplying the constraining values. List values for equality constraints first, followed by values for "less than or equal to" constraints, followed by "greater than or equal to" constraints.
Q	RECTANGULAR array supplying the coefficients on the quadratic terms in the function being minimized. Omit this parameter for linear programming problems.