MinConNLP (JMSL Numerical Library)

Overview

Package

Class

Tree

Index

Help

JMSL^TM Numerical Library 5.0.1

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

com.imsl.math
Class MinConNLP

java.lang.Object
  com.imsl.math.MinConNLP

All Implemented Interfaces:: Serializable, Cloneable

public class MinConNLP
extends Object
implements Serializable, Cloneable
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}$

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:

A good initial starting point is very problem specific and should be provided by the calling program whenever possible. See method setGuess.
Gradient approximation methods can have an effect on the success of MinConNLP. Selecting a higher order approximation method may be necessary for some problems. See method setDifferentiationType.
If a two sided constraint is transformed into two constraints, $g_{2i} left( x right) ge 0$ and $g_{2i+1} left( x right) ge 0$ , then choose $del0 lt 1/2 left( u_i-l_i right)/max left{ 1,|nabla g_i left( x right) | right}$ , or at least try to provide an estimate for that value. This will increase the efficiency of the algorithm. See method setBindingThreshold.
The parameter ierr provided in the interface to the user supplied function FCN can be very useful in cases when evaluation is requested at a point that is not possible or reasonable. For example, if evaluation at the requested point would result in a floating point exception, then setting ierr to true and returning without performing the evaluation will avoid the exception. MinConNLP will then reduce the stepsize and try the step again. Note, if ierr is set to true for the initial guess, then an error is issued.

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.

Termination condition 10: Kuhn-Tucker conditions are satisfied.
$||g(x)^-||_1 le mbox{tt violationBound}$

$||lambda^-||_infty le mbox{tt multiplierError}$

$|lambda^T g(x)| le mbox{tt violationBound}timesmbox{tt multiplierError}times M$
where , M is the number of constraints, and $epsilon_x = 10^{-5}$ . The notation $y^{-}$ means a vector whose negative elements are the same as the vector y, but with zeros in place of y's positive values.
Termination condition 11: Computed correction is small.

$||g(x)^-||_1 le mbox{tt violationBound}$

$||lambda^-||_infty le mbox{tt multiplierError}$
where d is the computed correction for the current solution x.
Termination condition 12: x is almost feasible, directional derivative is very small. Further progress cannot be expected.
where is the current penalty function, and is the directional derivative of . This usually occurs as a termination condition for ill-conditioned problems.

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:

Level	Output
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 last computed 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.
Throws:: IllegalArgumentException

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 last computed 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.

idtype	Action
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 . 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

, and

respectively. If this member function is not called, delmin is set to

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