SECTION 1.10 CONSTRAINED OPTIMIZATION

The present section describes a penalty function method for solving the following problem:

                          maximize F(x)

                          subject to

                          G(x) >= 0, H(x) = 0

where x is an n-vector, G(x) is the NC1-vector (G₁(x),..., G_NC1(x)) and H(x) is the NC2-vector (H₁(x),...,H_NC2(x)). Define

                  B(x)=DLOG(G1(x))+...+DLOG(GNC1(x)),

                  C(x)= 1./G1(x)+...+1./GNC1(x),

                  D(x)=H1(x)**2+...+HNC2(x)**2.

Then unconstrained maximization is performed on either

                  F(x) + XL1*B(x) - D(x)/XL2               (1) 

or

                  F(x) - XL1*C(x) - D(x)/XL2               (2)

where XL₁ and XL₂ are chosen by the user.The user also pre- selects a shrinkage factor and the problem is re-solved with successively smaller values of XL₁ and XL₂. The sequence of solutions converges to the constrained optimum. See F.A. Lootsma, Numerical Methods for Non-Linear Optimization, Academic Press, 1972, Ch. 23 and A.V. Fiacco and G.P. McCormick, "Computational Algorithm for the Sequential Unconstrained Minimization Technique for Nonlinear Programming," Management Science, 10 (1964), 601-617. Note: Although there is no limit on the number of constraints, the printed output of constraint values is truncated after the first 999 constraints of either type.

1. In the MAIN program, the user should include the following statements (in addition to the ones normally required for optimization):

      EXTERNAL PNLT1,CONSTR,FUNC 

where CONSTR and FUNC are the names of the actual subroutines that evaluate the constraints and the function respectively; for PNLT1 see 2a below.

      NC1 = number of inequality constraints
      NC2 = number of equality constraints
      ITERLG = number of consecutive unconstrained optimizations permitted
      CALL CONOPT(X,NP,NC1,NC2,F,METHOD,ITERL,ITERLG,MAX,IER,
     * ACC,FUNC,PNLT1,CONSTR,ALABEL) 

where the remaining arguments have the same meaning as in Section 1.1. The value of the variable NQ and the dimension of the array AINT (see Section 1.1) should exceed that required by the particular optimization algorithm by at least NC1+NC2+3*NP. METHOD may be any of the optimization methods. The starting values read into the array X must be such as to satisfy the inequality constraints. They need not satisfy the equality constraints. For PNLT1 see 2a below.

Convergence: The successive optimizations are performed ITERLG times (but see 3. below) and the sequence of solution values is not tested for convergence. The reason for this is that the optimization problems corresponding to a small number of consecutive shrinkages of XL1 and XL2 sometimes have the same (apparent) solutions. Tests for convergence based on changes in the X-vector would mistakenly conclude that convergence had occurred; yet for even smaller values of XL1 and XL2 the corresponding optimization problem may successfully alter the X-vector. It is therefore important not to set ITERLG too small; a value in excess of 10 seems reasonably conservative. Upon termination, the current values of G(x) and H(x) are provided. If the user feels that the tolerance within which H(x) = 0 is inadequate (say H(x) = 0.1), he may replace the constraints H(x) = 0 with H(x) >= -1.D-4 and -H(x) >= -1.D-4. Note however, that the starting values in the X-vector must satisfy these constraints. In addition the user may employ

      COMMON/BPNLT1/SHRK,XL1,XL2,IVERS1

where

SHRK= shrinkage factor for XL1 and XL2 (default = 0.65)
XL1 = penalty weight of inequality constraints (default = 0.1)
XL2 = penalty weight of equality constraints (default = 0.1)
IVERS1 = 0 optimization employs equation (1) (default = 0)
IVERS1 = 1 optimization employs equation (2)

Upon return from CONOPT, error indications are

IER = -34 Invalid NC1 or NC2
IER = -35 Invalid ITERLG
IER = -36 Function error after constrained optimization
IER = -37 Constraint error after constrained optimization

2. In addition, the user must include the following routines:

a. An auxiliary function subroutine

      SUBROUTINE PNLT1(X,NP,FU0,*)
      IMPLICIT REAL*8 (A-H,O-Z)
      DIMENSION X(NP)
      EXTERNAL FUNC,CONSTR
      CALL PNLT2(X,NP,FU0,*10,FUNC,CONSTR)
      RETURN
10    RETURN 1
      END

where FUNC is the name of the subroutine that evaluates the function to be optimized and where CONSTR is the name of the subroutine that evaluates the G( ) and H( ) constraints. NOTE: the user may not have a subprogram named PNLT2.

b. A constraint subroutine

      SUBROUTINE CONSTR(X,PHI,NC,NP,*)
      IMPLICIT REAL*8 (A-H,O-Z)
      DIMENSION X(NP),PHI(NC)
C FIRST COME NC1 INEQUALITY CONSTRAINTS, I.E., VALUES OF G(X)
      PHI(1) =
       . . .
      PHI(NC1) =
C NEXT COME NC2 EQUALITY CONTRAINTS, I.E. VALUES OF H(X)
      PHI(NC1+1) =
       . . .
      PHI(NC) =
      RETURN
      END 

where NC is the sum of NC1 and NC2. The user need not set this in the MAIN program. NOTE: Possible error conditions may be tested and, should one occur, the user should invoke RETURN 1.

c. The function subroutine SUBROUTINE FUNC(X,NP,FU0,*) see Section 1.1. If an unconstrained optimization in a sequence of CONOPT optimizations encounters a nonstandard termination, the sequence of optimizations is abandoned. The only exception to this is if an optimization exhausts its iteration limit: the point reached is accepted, XL1 and XL2 are modified and a new optimization problem is started. Warning: the initial point X must be such that every component of G(X) is strictly positive.

Return to the Beginning