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.
References:
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"
SIAM, Philadelphia
1979
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.
Before being posted on this page, "SGEFS.F" was translated to Javascript and edited. Although all care was taken to ensure that it was translated accurately, some errors may have crept into the translation. These errors are mine; the original FORTRAN routines have been thoroughly tested and work properly. Please contact the webmaster to report any errors.
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. |