A Quadratic Programming Utility for Three Variables
THIS UTILITY PRESENTLY DOES NOT ACCEPT CONSTRAINTS. THIS CAPABILITY WILL BE ADDED IN THE FUTURE.
This page contains a routine that numerically solves a Quadratic Programming problem with three variables.
Author: E. A. Voorhees, Los Alamos National Laboratory (LANL)
Dongarra, J. J.; J.R. Bunch; C.B. Moler; and G.W. Stewart.
"LINPACK User's Guide"
The utility posted on this page is based on the program "SGEFS.F", written by E. A. Voorhees (LANL).
"SGEFS.F" is part of the SLATEC library of programs, and its original code (written in FORTRAN) can be viewed there.
Quadratic Programming involves solving problems of the form
minimize F(x) = (1/2) xT H x + cT x + α
and is often subject to a number of constraints.
The 1/2 factor is included in the quadratic term to avoid the appearance of a factor of 2 in the derivatives.
F is a scalar called the objective function,
H is a symmetric matrix of real constants, called the Hessian matrix,
c is a vector of real constants, and
α is a real scalar.
Constraints include lower and upper bound constraints
(lb) <= (x): constrains the solution vector, (x), to values greater than or equal to the lower bound vector, (lb);
(x) <= (ub): constrains the solution vector, (x), to values less than or equal to the upper bound vector, (ub)
as well as inequality constraints of the form
[A] (x) >= (b)
Further background on Quadratic Programming is given elewhere on this site. See the posted example for no constraints.
HOW TO USE THIS UTILITY
First, enter the appropriate data values for the H matrix, the c vector, and α.
Taking advantage of the fact that H is symmetric, the user only has to input H values for entries along the diagonal and below the diagonal.
Then indicate whether or not constraints are to be applied.
If constraints are to be applied, make sure to check beside each type of constraint: lower bounds, upper bounds, and/or inequality constraints. If lower bound and/or upper bound constraints are to be applied, make sure to enter three values. For example, if you apply lower bound constraints, ensure you enter three values for the lower bounds. Do not just enter one or two values, leaving two or one data field blank.
In addition, if inequality constraints of the form [A] (x) >= (b) are to be applied, check the selection box beside each condition. If you enter a condition, but do not check the box beside it, this utility will not detect that condition. Up to three conditions may be applied. For inequality constraints of the form [A] (x) <= (b), just negate all data values to be entered for the inequality conditions.
Once all these options have been selected, and all the data values entered, click the Solve button. This utility will calculate the values of x that solve the system and satisfy the constraints (if any). It will also output the value of F at this point.
IMPORTANT: Make sure that Error Code is greater than 0; if it is not, the solution is meaningless.
|If Error Code > 0, it represents a rough estimate of the number of digits of accuracy in the solution, (x).|
|If Error Code < 0, there are errors:|
|Error Code = -1: Fatal Error. [H] is computationally singular. No solution was computed.|
|Error Code = -2: Warning. Solution has no significance.|
|The solution may be inaccurate, or [H] may be poorly scaled.|