Package com.imsl.math

Class MinConGenLin

java.lang.Object
com.imsl.math.MinConGenLin
All Implemented Interfaces:
Serializable, Cloneable
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_2x\le b_2$$

$$x_l \le x\le 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 f\left( {x^k } \right) + d^T \nabla \,f\left( {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)^T\nabla f(x^k)$$

and

$$(d^k)^T\nabla f(x^k +\alpha ^kd^k) \ge 0.7 (d^k)^T\nabla 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 f\left( {x^k + \alpha ^k d^k } \right) - \nabla f\left( {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:

  • Constructor Details

    • 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 - An int scalar containing the number of variables.
      ncon - An int scalar containing the number of linear constraints (excluding simple bounds).
      neq - An 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 Details

    • setNumberOfThreads

      public void setNumberOfThreads(int numberOfThreads)
      Sets the number of java.lang.Thread instances to be used for parallel processing.
      Parameters:
      numberOfThreads - an int specifying the number of java.lang.Thread instances to be used for parallel processing. If numberOfThreads is greater than 1, then interface Function.f is evaluated in parallel and Function.f must be thread-safe. Otherwise, unexpected behavior can occur.

      Default: numberOfThreads = 1.

    • getNumberOfThreads

      public int getNumberOfThreads()
      Returns the number of java.lang.Thread instances used for parallel processing.
      Returns:
      an int containing the number of java.lang.Thread instances used for parallel processing.

    • 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

    • getLagrangeMultiplerEst

      public double[] getLagrangeMultiplerEst()
      Deprecated.
      Method name misspelled. Use getLagrangeMultiplierEst() instead.
      Returns the Lagrange multiplier estimates of the final active constraints.
      Returns:
      a double array containing the Lagrange multiplier estimates of the final 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.

    • 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.

    • getFinalActiveConstraintsNum

      public int getFinalActiveConstraintsNum()
      Returns the final number of active constraints.
      Returns:
      an int scalar containing the final number of active constraints.

    • getSolution

      public double[] getSolution()
      Returns the computed solution.
      Returns:
      a double array containing the computed solution.

    • getFinalActiveConstraints

      public int[] getFinalActiveConstraints()
      Returns the indices of the final active constraints.
      Returns:
      an int array containing the indices of the final active constraints.

    • setGuess

      public void setGuess(double[] guess)
      Sets an initial guess of the solution.
      Parameters:
      guess - a double array containing an initial guess.