JMSLTM Numerical Library 4.0

com.imsl.math
Class MinConNLP

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

public class MinConNLP
extends Object
implements Serializable, Cloneable

General nonlinear programming solver.

MinConNLP is based on the FORTRAN subroutine, DONLP2, by Peter Spellucci and licensed from TU Darmstadt. MinConNLP uses a sequential equality constrained quadratic programming method with an active set technique, and an alternative usage of a fully regularized mixed constrained subproblem in case of nonregular constraints (i.e. linear dependent gradients in the "working sets"). It uses a slightly modified version of the Pantoja-Mayne update for the Hessian of the Lagrangian, variable dual scaling and an improved Armjijo-type stepsize algorithm. Bounds on the variables are treated in a gradient-projection like fashion. Details may be found in the following two papers:

P. Spellucci: An SQP method for general nonlinear programs using only equality constrained subproblems. Math. Prog. 82, (1998), 413-448.

P. Spellucci: A new technique for inconsistent problems in the SQP method. Math. Meth. of Oper. Res. 47, (1998), 355-500. (published by Physica Verlag, Heidelberg, Germany).

The problem is stated as follows:

mathop {min }limits_{x; in ;R^n }
  fleft( x right)

subject to

{rm{ }}g_j left( x right) = 0, {rm{for}} ,, j
  = 1,; ldots ,;m_e

g_j left( x right) ge 0, rm{for} ,,
  {j = m_e  + 1,; ldots ,;m}

x_l  le x le x_u

where all problem functions are assumed to be continuously differentiable. Although default values are provided for optional input arguments, it may be necessary to adjust these values for some problems. Through the use of member functions, MinConNLP allows for several parameters of the algorithm to be adjusted to account for specific characteristics of problems. The DONLP2 Users Guide provides detailed descriptions of these parameters as well as strategies for maximizing the performance of the algorithm. In addition, the following are a number of guidelines to consider when using MinConNLP:

The solver terminates if there is an error or if one of the following three terminations conditions is satisfied. The method getTerminationCondition returns the termination condition index.

Note that one can use the JDK 1.4 JAVA Logging API to generate intermediate output for the solver. Accumulated levels of detail correspond to JAVA's CONFIG, FINE, FINER, and FINEST logging levels with CONFIG yielding the smallest amount of information and FINEST yielding the most. The levels of output yield the following:

LevelOutput
CONFIG One line of intermediate results is printed with each iteration. A summary report is printed upon completion.
FINE Lines of intermediate results giving the most important data for each step are printed after each step. A summary report is printed upon completion.
FINER Lines of detailed intermediate results showing all primal and dual variables, the relevant values from the working set, progress in the backtracking, etc. are printed. A summary report is printed upon completion.
FINEST Lines of detailed intermediate results showing all primal and dual variables, the relevant values from the working set, progress in the backtracking, the gradients in the working set, the quasi-Newton updated, etc. are printed. A summary report is printed upon completion.

See Also:
Finite-difference Example, Gradient Example, Logging Example, Serialized Form

Nested Class Summary
static class MinConNLP.BadInitialGuessException
          Penalty function point infeasible for original problem.
static class MinConNLP.ConstraintEvaluationException
          Constraint evaluation returns an error with current point.
static class MinConNLP.Formatter
          Simple formatter for MinConNLP logging
static interface MinConNLP.Function
          Public interface for the user supplied function to the MinConNLP object.
static interface MinConNLP.Gradient
          Public interface for the user supplied function to compute the gradient for MinConNLP object.
static class MinConNLP.IllConditionedException
          Problem is singular or ill-conditioned.
static class MinConNLP.LimitingAccuracyException
          Limiting accuracy reached for a singular problem.
static class MinConNLP.LinearlyDependentGradientsException
          Working set gradients are linearly dependent.
static class MinConNLP.NoAcceptableStepsizeException
          No acceptable stepsize in [SIGMA,SIGLA].
static class MinConNLP.ObjectiveEvaluationException
          Objective evaluation returns an error with current point.
static class MinConNLP.PenaltyFunctionPointInfeasibleException
          Penalty function point infeasible.
static class MinConNLP.QPInfeasibleException
          QP problem seemingly infeasible.
static class MinConNLP.SingularException
          Problem is singular.
static class MinConNLP.TerminationCriteriaNotSatisfiedException
          Termination criteria are not satisfied.
static class MinConNLP.TooManyIterationsException
          Maximum number of iterations exceeded.
static class MinConNLP.TooMuchTimeException
          Maximum time allowed for solve exceeded.
static class MinConNLP.WorkingSetSingularException
          Working set is singular in dual extended QP.
 
Field Summary
static long serialVersionUID
           
 
Constructor Summary
MinConNLP(int mTotalConstraints, int mEqualityConstraints, int nVariables)
          Nonlinear programming solver constructor.
 
Method Summary
 double[] getConstraintResiduals()
          Returns the constraint residuals.
 int getIterations()
          Returns the actual number of iterations used.
 double[] getLagrangeMultiplierEst()
          Returns the Lagrange multiplier estimates of the constraints.
 Logger getLogger()
          Returns the logger object.
 long getMaximumTime()
          Returns the maximum time allowed for the solve step.
 double[] getSolution()
          Returns the solution.
 int getTerminationCriterion()
          Returns the reason the solve step terminated.
 double getTolerance()
          Returns the desired precision of the solution.
 void setBindingThreshold(double del0)
          Set the binding threshold for constraints.
 void setBoundViolationBound(double taubnd)
          Set the amount by which bounds may be violated during numerical differentiation.
 void setDifferentiationType(int idtype)
          Set the type of numerical differentiation to be used.
 void setFunctionPrecision(double epsfcn)
          Set the relative precision of the function evaluation routine.
 void setGradientPrecision(double epsdif)
          Set the relative precision in gradients.
 void setGuess(double[] xguess)
          Set the initial guess of the minimum point of the input function.
 void setMaximumTime(long maximumTime)
          Sets the maximum time allowed for the solve step.
 void setMaxIterations(int maxIterations)
          Set the maximum number of iterations allowed.
 void setMultiplierError(double smallw)
          Set the error allowed in the multipliers.
 void setPenaltyBound(double tau0)
          Set the universal bound for describing how much the unscaled penalty-term may deviate from zero.
 void setScalingBound(double scbnd)
          Set the scaling bound for the internal automatic scaling of the objective function.
 void setTolerance(double epsx)
          Set the desired precision of the solution.
 void setViolationBound(double delmin)
          Set the scalar which defines allowable constraint violations of the final accepted result.
 void setXlowerBound(double[] xlb)
          Set the lower bounds on the variables.
 void setXscale(double[] xscale)
          Set the internal scaling of the variables.
 void setXupperBound(double[] xub)
          Set the upper bounds on the variables.
 double[] solve(MinConNLP.Function F)
          Solve a general nonlinear programming problem using the successive quadratic programming algorithm with a finite-difference gradient or with a user-supplied gradient.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

serialVersionUID

public static final long serialVersionUID
See Also:
Constant Field Values
Constructor Detail

MinConNLP

public MinConNLP(int mTotalConstraints,
                 int mEqualityConstraints,
                 int nVariables)
          throws IllegalArgumentException
Nonlinear programming solver constructor.

Parameters:
mTotalConstraints - An int scalar value which defines the total number of constraints
mEqualityConstraints - An int scalar value which defines the number of equality constraints
nVariables - An int scalar value which defines the number of variables.
Method Detail

getConstraintResiduals

public double[] getConstraintResiduals()
Returns the constraint residuals.

Returns:
a double array containing the constraint residuals.

getIterations

public int getIterations()
Returns the actual number of iterations used.

Returns:
the number of iterations used.

getLagrangeMultiplierEst

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

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

getLogger

public Logger getLogger()
Returns the logger object. Logger support requires JDK1.4. Use with earlier versions returns null.

Returns:
the logger object, if present, or null.

getMaximumTime

public long getMaximumTime()
Returns the maximum time allowed for the solve step.

Returns:
the maximum time, in milliseconds, to be allowed for the solve step. If less than or equal to zero then no time limit is imposed. The default valus is -1 (no time limit).

getSolution

public double[] getSolution()
Returns the solution. This is the same solution as returned by the solve method.

Returns:
a double array containing the solution.

getTerminationCriterion

public int getTerminationCriterion()
Returns the reason the solve step terminated.

Returns:
an int that indicates the reason the solve method terminated.
See Also:
List of termination condtions

getTolerance

public double getTolerance()
Returns the desired precision of the solution.

Returns:
a double that is the the desired precision of the solution.

setBindingThreshold

public void setBindingThreshold(double del0)
Set the binding threshold for constraints. In the initial phase of minimization a constraint is considered binding if frac{g_i left( x right)}{max left( 1,|nabla g_i left( x right) | right)} leq mbox{it del0}       i=M_e + 1,dots,M

Good values are between .01 and 1.0. If del0 is chosen too small then identification of the correct set of binding constraints may be delayed. Contrary, if del0 is too large, then the method will often escape to the full regularized SQP method, using individual slack variables for any active constraint, which is quite costly. For well scaled problems del0 = 1.0 is reasonable. If this member function is not called, del0 is set to .5 * tau0.

Parameters:
del0 - a double scalar value specifying the binding threshold for constraints.
Throws:
IllegalArgumentException - is thrown if del0 is less than or equal to 0.0

setBoundViolationBound

public void setBoundViolationBound(double taubnd)
Set the amount by which bounds may be violated during numerical differentiation. If this member function is not called, taubnd is set to 1.0.

Parameters:
taubnd - a double scalar value specifying the amount by which bounds may be violated during numerical differentiation.
Throws:
IllegalArgumentException - is thrown if taubnd is less than or equal to 0.0

setDifferentiationType

public void setDifferentiationType(int idtype)
Set the type of numerical differentiation to be used.

Parameters:
idtype - an int scalar value specifying the type of numerical differentiation to be used. If this member function is not called, idtype is set to 1.
idtypeAction
1 Use a forward difference quotient with discretization stepsize 0.1left( mbox{it epsfcn}^{1/2}right) componentwise relative. This is the default value used.
2 Use the symmetric difference quotient with discretization stepsize 0.1left( mbox{it epsfcn}^{1/3}right) componentwise relative.
3 Use the sixth order approximation computing a Richardson extrapolation of three symmetric difference quotient values. This uses a discretization stepsize 0.01left( mbox{it epsfcn}^{1/7}right)
Throws:
IllegalArgumentException - is thrown if idtype is less than or equal to 0 or greater than or equal to 4.

setFunctionPrecision

public void setFunctionPrecision(double epsfcn)
Set the relative precision of the function evaluation routine. If this member function is not called, epsfcn is set to 2.2e-16.

Parameters:
epsfcn - a double scalar value specifying the relative precision of the function evaluation routine.
Throws:
IllegalArgumentException - is thrown if epsfcn is less than or equal to 0.0

setGradientPrecision

public void setGradientPrecision(double epsdif)
Set the relative precision in gradients. If this member function is not called, epsdif is set to 2.2e-16.

Parameters:
epsdif - a double scalar value specifying the relative precision in gradients.
Throws:
IllegalArgumentException - is thrown if epsdif is less than or equal to 0.0

setGuess

public void setGuess(double[] xguess)
Set the initial guess of the minimum point of the input function. If this member function is not called, the elements of this array are set to x, (with the smallest value of left| {x} right|_2) that satisfies the bounds.

Parameters:
xguess - a double array specifying the initial guess of the minimum point of the input function

setMaximumTime

public void setMaximumTime(long maximumTime)
Sets the maximum time allowed for the solve step.

Parameters:
maximumTime - is the maximum time, in milliseconds, to be allowed for the solve step. If less than or equal to zero then no time limit is imposed.

setMaxIterations

public void setMaxIterations(int maxIterations)
Set the maximum number of iterations allowed. If this member function is not called, the maximum number of iterations is set to 200.

Parameters:
maxIterations - an int specifying the maximum number of iterations allowed
Throws:
IllegalArgumentException - is thrown if maxIterations is less than or equal to 0

setMultiplierError

public void setMultiplierError(double smallw)
Set the error allowed in the multipliers. A negative multiplier of an inequality constraint is accepted (as zero) if its absolute value is less than smallw. If this member function is not called, it is set to e^{2log epsilon/3}.

Parameters:
smallw - a double scalar value specifying the error allowed in the multipliers.
Throws:
IllegalArgumentException - is thrown if smallw is less than or equal to 0.0

setPenaltyBound

public void setPenaltyBound(double tau0)
Set the universal bound for describing how much the unscaled penalty-term may deviate from zero. A small tau0 diminishes the efficiency of the solver because the iterates then will follow the boundary of the feasible set closely. Conversely, a large tau0 may degrade the reliability of the code. If this member function is not called, tau0 is set to 1.0.

Parameters:
tau0 - a double scalar value specifying the universal bound for describing how much the unscaled penalty-term may deviate from zero.
Throws:
IllegalArgumentException - is thrown if tau0 is less than or equal to 0.0

setScalingBound

public void setScalingBound(double scbnd)
Set the scaling bound for the internal automatic scaling of the objective function. If this member function is not called, scbnd is set to 1.0e4.

Parameters:
scbnd - a double scalar value specifying the scaling variable for the problem function.
Throws:
IllegalArgumentException - is thrown if scbnd is less than or equal to 0.0

setTolerance

public void setTolerance(double epsx)
Set the desired precision of the solution.

Parameters:
epsx - is the the desired precision of the solution. For a well scaled and well-conditioned problem it essentially specifies a desired relative precision in the solution. It should never be chosen less than the square root of the machine precision since the control of progress in the method is based on the comparison of function values usually taken from the constraining manifold where the objective function varies like O(||x^k-x^*||^2). Even this requirement may be too strong. The default value of 1.0e-5 is approximately the third root of the machine precision. The user should be aware of the fact that the precision requirement is automatically relaxed if the solver considers a problem "singular". If the precision seems to be too poor in such a case a decrease of epsx might help. Default: 1.0e-5.

setViolationBound

public void setViolationBound(double delmin)
Set the scalar which defines allowable constraint violations of the final accepted result. Constraints are satisfied if left| g_i (x) right| leq delmin, and g_i (x) geq -delmin   respectively. If this member function is not called, delmin is set to min(del0/10, max(epsdif, min(del0/10,max((1.e-6)del0, small_w))).

Parameters:
delmin - a double scalar value specifying the allowable constraint violations of the final accepted result.
Throws:
IllegalArgumentException - is thrown if delmin is less than or equal to 0.0

setXlowerBound

public void setXlowerBound(double[] xlb)
Set the lower bounds on the variables. If this member function is not called, the elements of this array are set to -1.79e308.

Parameters:
xlb - a double array specifying the lower bounds on the variables

setXscale

public void setXscale(double[] xscale)
Set the internal scaling of the variables. The initial value given and the objective function and gradient evaluations, however, are always given in the original unscaled variables. The first internal variable is obtained by dividing the values x[i] by xscale[i]. If this member function is not called, xscale[i] is set to 1.0.

Parameters:
xscale - a double array specifying the internal scaling of the variables.
Throws:
IllegalArgumentException - is thrown if xscale is less than or equal to 0.0

setXupperBound

public void setXupperBound(double[] xub)
Set the upper bounds on the variables. If this member function is not called, the elements of this array are set to 1.79e308.

Parameters:
xub - a double array specifying the upper bounds on the variables

solve

public double[] solve(MinConNLP.Function F)
               throws MinConNLP.ConstraintEvaluationException,
                      MinConNLP.ObjectiveEvaluationException,
                      MinConNLP.WorkingSetSingularException,
                      MinConNLP.QPInfeasibleException,
                      MinConNLP.PenaltyFunctionPointInfeasibleException,
                      MinConNLP.LimitingAccuracyException,
                      MinConNLP.TooManyIterationsException,
                      MinConNLP.BadInitialGuessException,
                      MinConNLP.IllConditionedException,
                      MinConNLP.SingularException,
                      MinConNLP.LinearlyDependentGradientsException,
                      MinConNLP.NoAcceptableStepsizeException,
                      MinConNLP.TerminationCriteriaNotSatisfiedException
Solve a general nonlinear programming problem using the successive quadratic programming algorithm with a finite-difference gradient or with a user-supplied gradient.

Parameters:
F - defines the user-supplied function to evaluate the function at a given point. F can be used to supply a gradient of the function. If F implements Gradient the user-supplied gradient is used. Otherwise,an attempt to solve the problem is made using a finite-difference gradient.
Returns:
a double array containing the solution of the nonlinear programming problem.
Throws:
MinConNLP.ConstraintEvaluationException
MinConNLP.ObjectiveEvaluationException
MinConNLP.WorkingSetSingularException
MinConNLP.QPInfeasibleException
MinConNLP.PenaltyFunctionPointInfeasibleException
MinConNLP.LimitingAccuracyException
MinConNLP.TooManyIterationsException
MinConNLP.BadInitialGuessException
MinConNLP.IllConditionedException
MinConNLP.SingularException
MinConNLP.LinearlyDependentGradientsException
MinConNLP.NoAcceptableStepsizeException
MinConNLP.TerminationCriteriaNotSatisfiedException

JMSLTM Numerical Library 4.0

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