quadratic_prog
Solves a quadratic programming problem subject to linear equality or inequality constraints.
Synopsis
#include <imsl.h>
float *imsl_f_quadratic_prog (int m, int n, int meq, float a[], float b[], float g[], float h[], …, 0)
The type double function is imsl_d_quadratic_prog.
Required Arguments
int m (Input)
The number of linear constraints.
int n (Input)
The number of variables.
int meq (Input)
The number of linear equality constraints.
float a[] (Input)
Array of size m × n containing the equality constraints in the first meq rows, followed by the inequality constraints.
float b[] (Input)
Array with m components containing right-hand sides of the linear constraints.
float g[] (Input)
Array with n components containing the coefficients of the linear term of the objective function.
float h[] (Input)
Array of size n × n containing the Hessian matrix of the objective function. It must be symmetric positive definite. If h is not positive definite, the algorithm attempts to solve the QP problem with h replaced by h + diag* I such that h + diag* I is positive definite.
Return Value
A pointer to the solution x of the QP problem. To release this space, use imsl_free. If no solution can be computed, then NULL is returned.
Synopsis with Optional Arguments
#include <imsl.h>
float *imsl_f_quadratic_prog (int m, int n, int meq, float a[], float b[], float g[], float h[],
IMSL_A_COL_DIM, int a_col_dim,
IMSL_MAX_ITN, int max_itn,
IMSL_TOLERANCE, float small,
IMSL_H_COL_DIM, int h_col_dim,
IMSL_RETURN_USER, float x[],
IMSL_DUAL, float **y,
IMSL_DUAL_USER, float y[],
IMSL_ADD_TO_DIAG_H, float *diag,
IMSL_OBJ, float *obj,
0)
Optional Arguments
IMSL_A_COL_DIM, int a_col_dim (Input)
Leading dimension of A exactly as specified in the dimension statement of the calling program.
Default: a_col_dim = n
IMSL_H_COL_DIM, int h_col_dim (Input)
Leading dimension of h exactly as specified in the dimension statement of the calling program.
Default: n_col_dim = n
IMSL_MAX_ITN, int max_itn (Input)
Maximum number of iterations.If max_itn is set to 0, the iteration count is unbounded.
Default: max_itn = 100000
IMSL_TOLERANCE, float small (Input)
This constant is used in the determination of the positive definiteness of the Hessian H. small is also used for the convergence criteria of a constraint violation.
Default: small = 10.0 × machine precision for single precision, and 1000.0 × machine precision for double precision.
IMSL_RETURN_USER, float x[] (Output)
Array with n components containing the solution.
IMSL_DUAL, float **y (Output)
The address of a pointer y to an array with m components containing the Lagrange multiplier estimates. On return, the necessary space is allocated by imsl_f_quadratic_prog. Typically, float *y is declared, and &y is used as an argument.
IMSL_DUAL_USER, float y[] (Output)
A user-allocated array with m components. On return, y contains the Lagrange multiplier estimates.
IMSL_ADD_TO_DIAG_H, float *diag (Output)
Scalar equal to the multiple of the identity matrix added to h to give a positive definite matrix.
IMSL_OBJ, float *obj (Output)
The optimal object function found.
Description
The function imsl_f_quadratic_prog is based on M.J.D. Powell’s implementation of the Goldfarb and Idnani dual quadratic programming (QP) algorithm for convex QP problems subject to general linear equality/inequality constraints (Goldfarb and Idnani 1983); i.e., problems of the form
given the vectors b1, b2, and g, and the matrices H, A1, and A2. H is required to be positive definite. In this case, a unique x solves the problem or the constraints are inconsistent. If H is not positive definite, a positive definite perturbation of H is used in place of H. For more details, see Powell (1983, 1985).
If a perturbation of H, H + αI, is used in the QP problem, then H + αI also should be used in the definition of the Lagrange multipliers.
Examples
Example 1
The quadratic programming problem
is solved.
#include <imsl.h>
int main()
{
int m = 2;
int n = 5;
int meq = 2;
float *x;
float h[ ] = {2.0, 0.0, 0.0, 0.0, 0.0,
0.0, 2.0,-2.0, 0.0, 0.0,
0.0,-2.0, 2.0, 0.0, 0.0,
0.0, 0.0, 0.0, 2.0,-2.0,
0.0, 0.0, 0.0,-2.0, 2.0};
float a[ ] = {1.0, 1.0, 1.0, 1.0, 1.0,
0.0, 0.0, 1.0,-2.0,-2.0};
float b[ ] = {5.0, -3.0};
float g[ ] = {-2.0, 0.0, 0.0, 0.0, 0.0};
/* Solve the QP problem */
x = imsl_f_quadratic_prog (m, n, meq, a, b, g, h, 0);
/* Print x */
imsl_f_write_matrix ("x", 1, 5, x, 0);
}
Output
X
1 2 3 4 5
1 1 1 1 1
Example 2
Another quadratic programming problem
is solved.
#include <imsl.h>
float h[ ] = {2.0, 0.0, 0.0,
0.0, 2.0, 0.0,
0.0, 0.0, 2.0};
float a[ ] = {1.0, 2.0, -1.0,
1.0, -1.0, 1.0};
float b[ ] = {4.0, -2.0};
float g[ ] = {0.0, 0.0, 0.0};
int main()
{
int m = 2;
int n = 3;
int meq = 2;
float obj;
float d[2];
float *x;
/* Solve the QP problem */
x = imsl_f_quadratic_prog (m, n, meq, a, b, g, h,
IMSL_OBJ, &obj,
IMSL_DUAL_USER, d,
0);
/* Print x */
imsl_f_write_matrix ("x", 1, 3, x, 0);
/* Print d */
imsl_f_write_matrix ("d", 1, 2, d, 0);
printf("\n obj = %g \n", obj);
}
Output
x
1 2 3
0.286 1.429 -0.857
d
1 2
1.143 -0.571
obj = 2.85714
Warning Errors
IMSL_NO_MORE_PROGRESS | Due to the effect of computer rounding error, a change in the variables fail to improve the objective function value; usually the solution is close to optimum. |
Fatal Errors
IMSL_SYSTEM_INCONSISTENT | The system of equations is inconsistent. There is no solution. |
