16.3.4  Solving general nonlinear programming problems

The nlpsolve command computes the optimum of a multivariate objective function subject to equality and/or inequality constraints with continuous and/or integer variables.

• nlpsolve takes the following arguments:
  • obj or fname, an expression to optimize or a string containing the path to a problem file.
  • Optionally, constr, a list of equality and inequality constraints. Double-bounded constraints in form a≤ f(x)≤ b can be entered as f(x)=a..b instead of two inequalities.
  • Optionally, bd, a sequence of variable boundaries x=a..b where a∈ℝ∪{−∞} and b∈ℝ∪{+∞}, b≥ a. If several variables have the same upper and lower bounds, one can enter [x,y,...]=a..b. If the bounds are stored in a two-column matrix, consider using the conversion routine box_constraints (see Section 6.6.9).
  • Optionally, opt, a sequence of options in which each option may be one of:
    • maximize=bool or nlp_maximize=bool, where bool can be true or false. Just maximize or nlp_maximize is equivalent to maximize=true. (By default, maximize=false, i.e. the objective is minimized.)
    • nlp_initialpoint=pt, where pt is a starting point for the solver or a list of starting points, each of which is given in the form [x=x₀,y=y₀,…]. Alternatively, pt may be an initial search rectangle specified by [x=x_min..x_max,y=y_min..y_max,…] which serves as a frame for automatic generation of starting points.
    • nlp_method=meth, which is a string or a list specifying the method of optimization. Available methods are:
      • nelder-mead or nm, the simplex method of Nelder and Mead, modified so that it can handle variable bounds and (in)equality constraints; see Luersen, Riche, and Guyon (2003).
      • differential-evolution or de, the method of differential evolution, modified so it can handle bounds, (in)equalities and integrality constraints; see Lampinen and Zelinka (2000).
      • interior-point or ipt, the interior-point method which requires the objective and constraint derivatives, and can handle (mixed) integer nonlinear problems. If GSL routines are available, then unconstrained problems are solved by BGFS method which is faster.
      • cobyla or cbl, the (derivative-free) COBYLA algorithm.
      Note that these names must be entered with double quotes, i.e. as strings. Some parameters can be set for individual methods; to do so, meth should be a list in which the leading element is the method specification, followed by one or more entries of the form "param"=value, where param can be one of the following (see below for detailed explanations on values):
      • cross-probability, which specifies the probability of mutation in differential evolution, where value=p∈⟨ 0,1⟩ (by default, p=0.5).
      • scale, which specifies the scaling factor for differential evolution (by default, it is computed automatically from cross-probability by using the formula of Zaharie (2002)).
      • reflect-ratio, which specifies the simplex reflection factor in Nelder-Mead method (by default 1).
      • expand-ratio, which specifies the simplex expansion factor in Nelder-Mead method (by default 2).
      • contract-ratio, which specifies the simplex contraction factor in Nelder-Mead method (by default 0.5).
      • shrink-ratio, which specifies the simplex shrinking factor in Nelder-Mead method (by default 0.5).
      • size, which specifies the initial simplex size for Nelder-Mead method (by default, it is computed automatically by using the variable bounds).
      • step, which specifies initial step for BGFS method or adaptive penalty step for Nelder-Mead method (by default, it is set to 1 for BGFS and to 0.01 for Nelder-Mead).
      • search-points, which specifies the number of agents in differential evolution (by default 10n, where n is the number of variables) or the number of points for determining PDH clusters (by default 1000√n).
      • postprocess, which specifies whether the result obtained by differential evolution or Nelder-Mead method should be refined by a local method, where value is a boolean value (by default, value=true).
      The optimization method is determined automatically if meth is not set (see below).
    • nlp_precision=ε for some ε>0, which sets the optimality tolerance for the solver (by default, ε=epsilon()^2/3).
    • nlp_tolerance=δ for some δ>0, which sets the feasibility tolerance for the solver (by default, δ=10⁻⁵).
    • nlp_presolve=bool, where bool can be either true or false. This option enables/disables the preprocessing step which attempts to reduce the number of decision variables by solving subsets of equality constraints which are all linear in certain subsets of variables, substituting the results, and repeating the process until no further reduction can be made. (In particular, fixed variables are removed.) After solving the presolved problem, the removed variables are substituted back to the solution. (By default, nlp_presolve=true.)
    • border=bool, where bool is a boolean value. This enables or disables finding variable bounds automatically. (By default, border=true.)
    • nlp_integervariables=lst, where lst is a list of problem variables that are supposed to take integral values (empty by default).
    • nlp_binaryvariables=lst, where lst is a list of problem variables that are supposed to take binary (0-1) values (empty by default).
    • nlp_iterationlimit=N for a positive integer N, which sets the maximum number of iterations allowed for the solver (by default, N=250).
    • nlp_verbose=v, where v is an integer specifying the verbosity level: 0 – no messages, 1 – only errors, 2 – errors and warnings, 3 – all messages (by default, v=1).
    • cluster=k or bool, where k≥ 2 is an integer and bool is either true or false, which specifies whether the initial points should be determined by k-means clustering a large number of random points at which the objective Hessian is positive definite (this works only if the interior-point method is used), called PDH (Positive Definite Hessian) points. The number of generated points can be specified by setting the search-points parameter. If cluster=true, the number of clusters is determined automatically using the Hartigan criterion. If k is set, then k clusters are generated. Cluster centers are subsequently used as the initial points. (By default, cluster=false.)
    • convex or convex=bool, where bool can be either true or false. This specifies whether the input problem should be treated as being convex. If this option is set, then the convexity check is not performed, speeding up the execution. (By default, convexity check is performed only if it is relevant for choosing a suitable optimization method.)
    • assume=asmp, where asmp may be one of the following:
      • nlp_nonnegative, which restricts all variables to nonnegative values (existing positive lower bounds are kept, however),
      • nlp_nonnegint or nonnegint, which makes all variables take nonnegative integer values,
      • nlp_integer or integer, which forces all variables to take integer values,
      • nlp_binary, which forces all variables to take 0-1 values.
• nlpsolve(obj ⟨,constr,bd,opt ⟩) returns a list [optobj,optdec], where optobj is the optimal value of obj and optdec is a list of of optimal values of the decision variables. If the optimization fails, then optobj is the error message and optdec is the last point on the path the solver takes in attempt to find the optimal objective value. If the problem is infeasible or if the solver fails to find a feasible point, then an error is returned.
• nlpsolve(fname ⟨,opt ⟩) solves the problem written in the file pointed to by fname, which must be written in the AMPL modeling language (file extension .mod). nlpsolve contains a very basic parser for such files and is able to read problem variables, objective and constraints (this works with problems from MINLPLib). Solver parameters can be specified in opt.

Automatic selection of the optimization method.

If objective and constraints are twice differentiable, then interior-point method is used. If no initial point is provided and there are only box constraints, then differential evolution is applied first to find a good starting point. In the non-differentiable case, nlpsolve applies the Nelder-Mead method and switches to differential evolution in the case of failure. In case of integrality constraints, as well as in the case of a box-constrained problem without additional constraints and initial point(s), differential evolution is selected. Linear problems are solved by the lpsolve command, while univariate optimization on a segment is performed by using Brent’s algorithm.

Local vs. global optimization.

When an initial point is provided, nlpsolve acts like a local optimizer. Without initial point(s), it uses a multistart technique in attempt to find the global minimum: starting points are automatically generated by using the probabilistic restart technique described by Luersen, Riche, and Guyon (2003) until the maximum number of iterations is reached. This technique avoids previously generated points and also the points of convergence, while keeping relatively close to them; thus, the search space is examined in a probabilistic but systematic way. An exception is the method of differential evolution, which is a “global” method by design (however not a true one); the initial population is generated uniformly if the search space is compact.

Automatic detection of variable bounds.

If the constraint derivatives are available, nlpsolve determines rough bounds of the decision variables, and is thus able to detect whether the search domain is compact. In particular, this information is used by the probabilistic restart technique.

(Mixed) integer optimization.

When integrality constraints are provided, nlpsolve applies a suitable method for finding integer-feasible solutions. For differentiable input, the branch&bound method is used, unless the problem is convex, in which case the outer-approximation method is used. In the non-differentiable case, differential evolution is applied.

Examples

The continuous function f defined by

has a unique global minimum in [−5,5] at x=−1, with f(−1)=1.005.

Minimize z=x₁ x₄ (x₁+x₂+x₃)+x₃ subject to

where 1≤ x_i≤ 5, i=1,2,3,4.

Minimize z=(x₁−1)²+(x₁−x₂)²+(x₃−1)²+(x₄−1)⁴+(x₅−1)⁶ subject to

Maximize z=3x₁ x₂−x₁+6x₂ subject to 5x₁ x₂−4x₁−4.5x₂≤ 32, where 1≤ x₁,x₂≤ 5 are integers.

Maximize z=2x₁+3x₂+6x₃−2x₁ x₂−x₁ x₃−4x₂ x₃ where all variables are binary.

Minimize z=5y−2ln(x+1) subject to

where x∈[0,2] and y∈[1,3] is integer.

Minimize z=x₁²+x₂²+3x₃²+4x₄²+2x₅²−8x₁−2x₂−3x₃−x₄−2x₅ subject to

where 0≤ x_i≤ 99 are integers for i=1,…,5.

Minimize the function

for 0≤ x₁,x₂≤ 10 and a=2.

With the following program compiled in Xcas:

input:

Since f is programmatic, it cannot be differentiated symbolically in Xcas. Differential evolution is thus selected for minimization since the problem is box-constrained and no initial points are provided. Because f has three input arguments, the first argument in nlpsolve has to be quoted in order to fix the parameter a to 2. This technique should be used for “black box” objectives possibly requiring parameter specifications.

To see a contour plot of f, enter: