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

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 } f\left( 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:

• 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 \(l_i \le g_i \left( x \right) \le u_i\) 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 \texttt{violationBound} $$ $$ ||\lambda^-||_\infty \le \texttt{multiplierError} $$ $$ ||\nabla L(x,\mu,\lambda)|| \le \epsilon_x(1+||\nabla f(x)||) $$ $$ |\lambda^T g(x)| \le \texttt{violationBound}\times\texttt{multiplierError}\times M $$ where \(L(x,\mu,\lambda) = f(x) - \lambda^T g(x)\), 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. $$ d \le \epsilon_x (||x||+\epsilon_x) $$ $$ ||\nabla L(x,\mu,\lambda)|| \le \epsilon_x(1+||\nabla f(x)||) $$ $$ ||g(x)^-||_1 \le \texttt{violationBound} $$ $$ ||\lambda^-||_\infty \le \texttt{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. $$ D \Phi(x;d) \ge -100 (|\Phi(x)|+1) \epsilon_x $$ where \(\Phi\) is the current penalty function, and \(D\Phi\) is the directional derivative of \(\Phi\). 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

Nested Classes

Modifier and Type	Class and Description
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 Deprecated. Use IMSLFormatter instead.
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.

Constructor Summary

Constructors

Constructor and Description
MinConNLP(int mTotalConstraints, int mEqualityConstraints, int nVariables) Nonlinear programming solver constructor.

Method Summary

Modifier and Type	Method and Description
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.
int	getNumberOfThreads() Returns the number of java.lang.Thread instances used for parallel processing.
double	getOptimalValue() Returns the value of the objective function.
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	setNumberOfThreads(int numberOfThreads) Sets the number of java.lang.Thread instances to be used for parallel processing.
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

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

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.

getOptimalValue

public double getOptimalValue()

Returns the value of the objective function.

Returns:

a double, the value of the objective function.

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

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

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 -Double.MAX_VALUE. If variable i has no lower bound, set xlb[i] = -Double.MAX_VALUE.

Parameters:

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

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 Double.MAX_VALUE. If variable i has no upper bound, set xub[i] = Double.MAX_VALUE.

Parameters:

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

setGradientPrecision

public void setGradientPrecision(double epsdif)

Set the relative precision in gradients. If this member function is not called, epsdif is set to machine precision.

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

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 machine precision.

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

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

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.1\left(\mbox{epsfcn}^{1/2}\right) \) componentwise relative. This is the default value used.
2	Use the symmetric difference quotient with discretization stepsize \( 0.1\left(\mbox{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.01\left(\mbox{epsfcn}^{1/7}\right) \)

Throws:

IllegalArgumentException - is thrown if idtype is less than or equal to 0 or greater than or equal to 4.

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

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

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^{2\log \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

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

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

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

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.

getTolerance

public double getTolerance()

Returns the desired precision of the solution.

Returns:

a double that is the desired precision of the solution.

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.

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 value is -1 (no time limit).

getIterations

public int getIterations()

Returns the actual number of iterations used.

Returns:

the number of iterations used.

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 conditions

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

getLagrangeMultiplierEst

public double[] getLagrangeMultiplierEst()

Returns the Lagrange multiplier estimates of the constraints.

Returns:

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

getConstraintResiduals

public double[] getConstraintResiduals()

Returns the constraint residuals.

Returns:

a double array containing the constraint residuals.

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.