JMSLTM Numerical Library 4.0

com.imsl.math
Class MinConGenLin

java.lang.Object
  extended bycom.imsl.math.MinConGenLin
All Implemented Interfaces:
Cloneable, Serializable

public class MinConGenLin
extends Object
implements Serializable, Cloneable

Minimizes a general objective function subject to linear equality/inequality constraints.

The class MinConGenLin is based on M.J.D. Powell's TOLMIN, which solves linearly constrained optimization problems, i.e., problems of the form

min f (x)

subject to

A_1x = b_1

A_2xle b_2

x_l le xle x_u

given the vectors b_1, b_2, x_l, and x_u and the matrices A_1 and A_2.

The algorithm starts by checking the equality constraints for inconsistency and redundancy. If the equality constraints are consistent, the method will revise x^0, the initial guess, to satisfy

A_1x =b_1

Next, x^0 is adjusted to satisfy the simple bounds and inequality constraints. This is done by solving a sequence of quadratic programming subproblems to minimize the sum of the constraint or bound violations.

Now, for each iteration with a feasible x^k, let J_k be the set of indices of inequality constraints that have small residuals. Here, the simple bounds are treated as inequality constraints. Let I_k be the set of indices of active constraints. The following quadratic programming problem

min fleft( {x^k } right) + d^T nabla 
  ,fleft( {x^k } right) + {1 over 2}d^T B^k d

subject to

a_jd = 0, ,j in I_k

a_jd  le 0, ,j in J_k

is solved to get (d^k, lambda^k) where a_j is a row vector representing either a constraint in A_1 or A_2 or a bound constraint on x. In the latter case, the a_j = e_j for the bound constraint x_i le 
  (x_u)_i and a_j = -e_i for the constraint -x_i le (x_l)_i. Here, e_i is a vector with 1 as the i-th component, and zeros elsewhere. Variables lambda^k are the Lagrange multipliers, and B^k is a positive definite approximation to the second derivative nabla ^2  f(x^k).

After the search direction d^k is obtained, a line search is performed to locate a better point. The new point x^{k+1}= x^k +alpha^kd^k has to satisfy the conditions

f(x^k + alpha^kd^k) le f(x^k) + 0.1 
  alpha^k (d^k)^Tnabla  f(x^k)

and

(d^k)^Tnabla  f(x^k +alpha ^kd^k) ge 0.7 
  (d^k)^Tnabla  f(x^k)

The main idea in forming the set J_k is that, if any of the equality constraints restricts the step-length alpha^k, then its index is not in J_k. Therefore, small steps are likely to be avoided.

Finally, the second derivative approximation B^K, is updated by the BFGS formula, if the condition

left( {d^K } right)^T nabla fleft( {x^k  + 
  alpha ^k d^k } right) - nabla fleft( {x^k } right) > 0

holds. Let x^k  leftarrow x^{k + 1}, and start another iteration.

The iteration repeats until the stopping criterion

left| {nabla f(x^k ) - A^k lambda ^K } right|_2  le 
  tau

is satisfied. Here tau is the supplied tolerance. For more details, see Powell (1988, 1989).

See Also:
Example 1, Example 2, Serialized Form

Nested Class Summary
static class MinConGenLin.ConstraintsInconsistentException
          The equality constraints are inconsistent.
static class MinConGenLin.ConstraintsNotSatisfiedException
          No vector x satisfies all of the constraints.
static class MinConGenLin.EqualityConstraintsException
          the variables are determined by the equality constraints.
static interface MinConGenLin.Function
          Public interface for the user-supplied function to evaluate the function to be minimized.
static interface MinConGenLin.Gradient
          Public interface for the user-supplied function to compute the gradient.
static class MinConGenLin.VarBoundsInconsistentException
          The equality constraints and the bounds on the variables are found to be inconsistent.
 
Constructor Summary
MinConGenLin(MinConGenLin.Function fcn, int nvar, int ncon, int neq, double[] a, double[] b, double[] lowerBound, double[] upperBound)
          Constructor for MinConGenLin.
 
Method Summary
 int[] getFinalActiveConstraints()
          Returns the indices of the final active constraints.
 int getFinalActiveConstraintsNum()
          Returns the final number of active constraints.
 double[] getLagrangeMultiplierEst()
          Returns the Lagrange multiplier estimates of the final active constraints.
 double getObjectiveValue()
          Returns the value of the objective function.
 double[] getSolution()
          Returns the computed solution.
 void setGuess(double[] guess)
          Sets an initial guess of the solution.
 void setTolerance(double tolerance)
          Sets the nonnegative tolerance on the first order conditions at the calculated solution.
 void solve()
          Minimizes a general objective function subject to linear equality/inequality constraints.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

MinConGenLin

public MinConGenLin(MinConGenLin.Function fcn,
                    int nvar,
                    int ncon,
                    int neq,
                    double[] a,
                    double[] b,
                    double[] lowerBound,
                    double[] upperBound)
Constructor for MinConGenLin.

Parameters:
fcn - A Function object, user-supplied function to evaluate the function to be minimized.
nvar - A int scalar containing the number of variables.
ncon - A int scalar containing the number of linear constraints (excluding simple bounds).
neq - A int scalar containing the number of linear equality constraints.
a - A double array containing the equality constraint gradients in the first neq rows followed by the inequality constraint gradients. a.length = ncon * nvar
b - A double array containing the right-hand sides of the linear constraints.
lowerBound - A double array containing the lower bounds on the variables. Choose a very large negative value if a component should be unbounded below or set lowerBound[i] = upperBound[i] to freeze the i-th variable. lowerBound.length = nvar
upperBound - A double array containing the upper bounds on the variables. Choose a very large positive value if a component should be unbounded above. upperBound.length = nvar
Throws:
IllegalArgumentException - is thrown if the dimensions of nvar, ncon, neq, a.length , b.length, lowerBound.length and upperBound.length are not consistent.
Method Detail

getFinalActiveConstraints

public int[] getFinalActiveConstraints()
Returns the indices of the final active constraints.

Returns:
a int array containing the indices of the final active constraints.

getFinalActiveConstraintsNum

public int getFinalActiveConstraintsNum()
Returns the final number of active constraints.

Returns:
a int scalar containing the final number of active constraints.

getLagrangeMultiplierEst

public double[] getLagrangeMultiplierEst()
Returns the Lagrange multiplier estimates of the final active constraints.

Returns:
a double array containing the Lagrange multiplier estimates of the final active constraints.

getObjectiveValue

public double getObjectiveValue()
Returns the value of the objective function.

Returns:
a double scalar containing the value of the objective function.

getSolution

public double[] getSolution()
Returns the computed solution.

Returns:
a double array containing the computed solution.

setGuess

public void setGuess(double[] guess)
Sets an initial guess of the solution.

Parameters:
guess - a double array containing an initial guess.

setTolerance

public void setTolerance(double tolerance)
Sets the nonnegative tolerance on the first order conditions at the calculated solution.

Parameters:
tolerance - a double scalar containing the tolerance.

solve

public final void solve()
                 throws MinConGenLin.ConstraintsInconsistentException,
                        MinConGenLin.VarBoundsInconsistentException,
                        MinConGenLin.ConstraintsNotSatisfiedException,
                        MinConGenLin.EqualityConstraintsException
Minimizes a general objective function subject to linear equality/inequality constraints.

Throws:
MinConGenLin.ConstraintsInconsistentException
MinConGenLin.VarBoundsInconsistentException
MinConGenLin.ConstraintsNotSatisfiedException
MinConGenLin.EqualityConstraintsException

JMSLTM Numerical Library 4.0

Copyright 1970-2006 Visual Numerics, Inc.
Built June 1 2006.