Solves a quadratic programming problem subject to linear equality/inequality constraints.
NEQ The number of linear equality constraints. (Input)
A NCON by NVAR
matrix. (Input)
The matrix contains the equality contraints in
the first NEQ
rows followed by the inequality constraints.
B Vector of length NCON containing right-hand sides of the linear constraints. (Input)
G Vector of length NVAR containing the coefficients of the linear term of the objective function. (Input)
H NVAR by NVAR matrix containing
the Hessian matrix of the objective function. (Input)
H should be symmetric
positive definite; if H is not positive
definite, the algorithm attempts to solve the QP problem with H replaced by a H + DIAGNL * I such that
H + DIAGNL * I is positive
definite. See Comment 3.
SOL Vector of length NVAR containing solution. (Output)
NVAR The number
of variables. (Input)
Default: NVAR = size
(A,2).
NCON The number
of linear constraints. (Input)
Default: NCON = size
(A,1).
LDA Leading
dimension of A
exactly as specified in the dimension statement of the calling
program. (Input)
Default: LDA = size
(A,1).
LDH Leading
dimension of H
exactly as specified in the dimension statement of the calling
program. (Input)
Default: LDH = size
(H,1).
DIAGNL Scalar equal to the multiple of the identity matrix added to H to give a positive definite matrix. (Output)
NACT Final number of active constraints. (Output)
IACT Vector of length NVAR containing the indices of the final active constraints in the first NACT positions. (Output)
ALAMDA Vector of length NVAR containing the Lagrange multiplier estimates of the final active constraints in the first NACT positions. (Output)
MAXITN This
number is the maximum number of iterations allowed. (Input)
If MAXITN is set to 0 the
iteration count is unbounded.
Default: MAXITN = 100000.
SMALL This
constant is used in the determination of the positive definiteness of the
Hessian H.
(Input)
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.
Generic: CALL QPROG (NEQ, A, B, G, H, SOL [, ])
Specific: The specific interface names are S_QPROG and D_QPROG.
Single: CALL QPROG (NVAR, NCON, NEQ, A, LDA, B, G, H, LDH, DIAGNL, SOL, NACT, IACT, ALAMDA)
Double: The double precision name is DQPROG.
The routine QPROG is based on M.J.D. Powells implementation of the Goldfarb and Idnani (1983) dual quadratic programming (QP) algorithm for convex QP problems subject to general linear equality/inequality constraints, i.e., problems of the form
subject to A1x = b1
A1x ≥ b2
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).
1. Workspace may be explicitly provided, if desired, by use of Q2ROG/DQ2ROG. The reference is:
CALL Q2ROG (NVAR, NCON, NEQ, A, LDA, B, G, H, LDH, DIAGNL, SOL, NACT, IACT, ALAMDA, WK)
The additional argument is:
WK Work vector of length (3 * NVAR**2 + 11 * NVAR)/2 + NCON.
2. Informational errors
Type Code
3 1 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.
4 2 The system of equations is inconsistent. There is no solution.
3.
If a perturbation of H, H + DIAGNL * I, was used in the
QP problem, then
H + DIAGNL * I should also be used
in the definition of the Lagrange multipliers.
The quadratic programming problem
is solved.
USE QPROG_INT
USE UMACH_INT
IMPLICIT NONE
! Declare variables
INTEGER LDA, LDH, NCON, NEQ, NVAR
PARAMETER (NCON=2, NEQ=2, NVAR=5, LDA=NCON, LDH=NVAR)
!
INTEGER K, NACT, NOUT
REAL A(LDA,NVAR), ALAMDA(NVAR), B(NCON), G(NVAR), &
H(LDH,LDH), SOL(NVAR)
!
! Set values of A, B, G and H.
! A = ( 1.0 1.0 1.0 1.0 1.0)
! ( 0.0 0.0 1.0 -2.0 -2.0)
!
! B = ( 5.0 -3.0)
!
! G = (-2.0 0.0 0.0 0.0 0.0)
!
! 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)
!
DATA A/1.0, 0.0, 1.0, 0.0, 1.0, 1.0, 1.0, -2.0, 1.0, -2.0/
DATA B/5.0, -3.0/
DATA G/-2.0, 4*0.0/
DATA H/2.0, 5*0.0, 2.0, -2.0, 3*0.0, -2.0, 2.0, 5*0.0, 2.0, &
-2.0, 3*0.0, -2.0, 2.0/
!
CALL QPROG (NEQ, A, B, G, H, SOL)
!
CALL UMACH (2, NOUT)
WRITE (NOUT,99999) (SOL(K),K=1,NVAR)
99999 FORMAT (' The solution vector is', /, ' SOL = (', 5F6.1, &
' )')
!
END
The solution vector is
SOL = ( 1.0
1.0 1.0 1.0 1.0 )
PHONE: 713.784.3131 FAX:713.781.9260 |