NlpDefine

Defines a non-linear programming problem.

Requires Analytica Optimizer, Analytica Power Player with Optimizer, or ADE with Optimizer.

NlpDefine accepts a large number of optional parameters, allowing many variations in the formulation of NLPs. See the Parameters section below.

What is a non-linear program?

A non-linear program is an optimization problem where you wish to find a vector for the decision variables that minimizes (or maximizes) an objective function subject to a set of constraints and variable bounds. Special cases also include unconstrained optimization and finding a solution to a system of non-linear equations. Decision variables may be continuous or mixed-integer.

Linear and quadratic optimization problems can be formulated as NLPs, but when it is possible, you are much better off encoding these as linear or quadratic programs using LpDefine or QpDefine. Linear and quadratic formulations more readily array abstract and suffer from fewer numeric convergence issues.

Structuring an NLP

To encode an NLP in an Analyica model, you begin by identifying a decision variable in your model, which will be set to candidate solutions during the optimization search. This decision variable is nominally a one-dimensional vector, so that there will be an index associated with it, as in the following:

Index V := ['x1','x2','x3']
Variable X := Table(V)

You can also use a self-indexed table for X, in which X serves as both the index and the decision variable.

Using the values of V, your model will compute an objective variable, let's suppose it is named Y. You may have a very complex model, with large numbers of variables between X and Y, utilizing arbitrary Analytica expressions. Y is the objective. For an unconstrained optimization problem, these provide the essential pieces.

It is also possible to use a local variable for X, defined using Var..Do. X may then appear in the expression provided to NlpDefine's parameters obj, lhs, gradient, jacobian, or hessian. This is often used when an NLP is defined inside a User-Defined Function.

Unconstrained Optimization

An unconstrained minimization problem can be defined using:

NlpDefine( Vars: V, X:X, Obj:Y )

Evaluation of NlpDefine this returns an NLP object, which displays as <<NLP>> in the result table. This is a problem definition, from which various pieces of information can be extracted, including the solution.

To solve the NLP, use the LpSolution function, which returns a vector, indexed by V (the index provided as the first parameter, Vars), with the solution found. However, it is also important that you check the status using LpStatusText or LpStatusNum to determine why the search terminated and whether a solution was successfully found. Thus, you may have variables such as the following:

Variable My_Nlp := NlpDefine( Vars: V, X:X, Obj: Y )
Variable NlpStatus := LpStatusText(My_Nlp)
Variable X_opt := LpSolution(My_Nlp)

Note that after the search completes, the optimal solution is in X_opt, rather than in X. It is common to use a button with a script such as: (X := X_opt), where the surrounding parens are necessary, when you want X to be set.

Goal Seek

A further special case of unconstrained optimization occurs when the decision variable is a scalar, e.g., find scalar X that minimizes Y, or that minimizes (Y-g)^2. In this case, the Vars index is not necessary, and a simple problem can be defined as:

NlpDefine( X:X, Obj:Y )

Since so many of the parameters of NlpDefine are optional, it is standard to used a named-parameter syntax.

There is also a GoalSeek function in a library included with Analytica, with does not require Analyica Optimizer. The GoalSeek function uses a very simple Newton-Rapson descent algorithm that may be sufficient in many cases, but provides fewer options for diagnosing and addressing convergence problems on hard optimization problems. In general, NlpDefine provides higher quality algorithms.

Constrained Optimization

In constrained optimization, which typically is associated with NLPs, we also have one or more non-linear constraints. Here we have constraints of the form

g_j(X,V) = b_j

Let's look at an example with a single non-linear constraint. Suppose we want to minimize surface area of a cylinder that is constrained to have a volume of 1, where surface_area and volume are computed in variables of those names. The NLP with one constraint can be defined as

NlpDefine( Vars:V, X:X, obj:surface_area, lhs:volume, sense:'=', rhs:1, lb:0 )

In this formulation, the constraint is encoded using the three parameters lhs, sense, and rhs. Of these, only the lhs can depend on X. The other two, sense and rhs, do not vary during the optimization search. We also include a variable bound here, lb, so that the dimensions (elements of X) are constrained to be non-negative. Note that the obj or lhs could be an expression referencing X directly.

When we have two or more constraints, we must also create a constraint index, to index the set of constraints. Generally the constraint index is defined as a list of labels, with each label providing a meaningful name for the constraint. It is easiest to set up the left-hand side in a table, in its own variable. (Here we've changed the volume constraint from an equality to a minimum required volume).

Index Constraints := ['min volume','taller than wide']
Variable lhs := Table(constraints)(volume-1,h-w)
Variable my_Nlp := NlpDefine( Vars:V,Constraints:constraints,obj:surface_area,
                              Lhs:lhs, sense:'>',rhs:0, lb:0 )

Parameters

NlpDefine accepts a large number of optional parameters. Because of this, it is best to use a named-parameter syntax rather than relying on parameter position. Here are parameters that are possible:

Vars: optional index. If your solution is vector-valued (anything other than a scalar), an index corresponding to the set of scalar decision variables is required.

Constraints: optional index: If you have two or more constraints, this index is required to index these constraints. Often defined as a list of labels.

X: Identifies a variable that holds the candidate solution at each iteration of the search. A local variable identifier or a standard variable identifier may be supplied here. The value there initially is used as the starting point for the search, unless the guess parameter is supplied.

Obj: optional expression. The objective function. This should depend on X, and is re-evaluated at each iteration of the search.

Lhs: optional expression. The left-hand sides of all constraints. These should depend on X, and if there is more than one constraint, should be indexed by the Constraints index. This expression is re-evaluated at each iteration of the search. This may be omitted in an unconstrained optimization problem.

Rhs: optional. The right-hand side of constraints. This is evaluated when the problem is defined and is not re-evaluated at each iteration. It should not depend on X -- you should move any terms depending on X to the left-hand side. When the rhs is different for different constraints, this should be indexed by Constraints.

Sense: optional. One of "<", "=", or ">", or "L", "E", "G". The inequalities are non-strict, so "<" means that the lhs is constrained to be less than or greater than the rhs. Defaults to "<". If the sense is different for different constraints, then this should be indexed by Constraints.

maximize: optional boolean. When omitted, a minimization problem is defined. When Maximize:True is specified, the object is maximized.

lb, ub: optional. Lower and upper bounds on the decision variables. If unspecified, the variables are unconstrained from -INF to INF. If different bounds exist for different decision variables, these should be indexed by Vars.

Ctype: optional, one of "C","B","I","G". Specifies whether the solution variables are continuous or integer values. "C" (default)=continuous, "B"=binary 0/1 valued, "I"=integer valued, "G"=group valued (see Group). For mixed-integer, where some variables are continuous and others integer, Ctype will be indexed by Vars.

ObjNl, LhsNl: optional, one of "L","N","D". Specifies whether the dependence of the objective, or lhs, is linear (L), non-linear continuous (N), or discontinuous (D). This information is used by the algorithms to select the most appropriate techniques for the problem and may speed search. ObjNl may be indexed by Vars if the objective is linearly dependent on some decision variables but non-linearly dependent on others. Likewise, LhsNl may be indexed by Vars and Contraints in general.

Guess: optional. An initial guess, used as the starting point for the search. When omitted, the current value of X is used. Guess is usually indexed by Vars. If you include another index here, you'll define multiple NLPs starting from different starting positions, which provides one mechanism for dealing with the problem of local minima by using multiple starting points.

Gradient,Jacobian,hessian,lhsHessian: optional expressions. These are all expressions that depend on X and compute the gradient or hessian of the objective function, or the jacobian and hessian of the constraint lhs. When correctly supplied to NlpDefine, these can speed up the search by eliminating extra evaluations otherwise carried out to estimate these derivatives numerically, and may help with numeric "noise" that is often present in numeric estimations of derivatives. The Hessians are not used by the engines supplied with Analytica Optimizer, but may be used by some add-on engines.

Group: optional. Used with group-integer variables. When N variables belong to the same group, a solution requires each in the gruop to have a value from 1..N, with each having a different value. This parameter specifies the group number for each variable. If variables are partitioned into multiple groups, then this parameter would be indexed by Vars, with some having the value 1, other the value 2, etc., indicating which variables belong to the first group, second group, etc.

Engine: optional. Specifies which engine is to be used to solve the problem. The standard Analytica Optimizer license allows "GRG Nonlinear" or "Evolutionary". If you have a license for an add-on engine, this may be something else, such as "Knitro", etc. To see possible values, evaluate: SolverInfo("Availengines")

Parameter,Setting: optional. A value or values of search-control parameters, used to control aspects of the search. See the section on Specifying Search Control parameters below.

TraceFile: The name of a filename. When the algorithm runs, a trace of the search is written to this file, which is often useful for debugging convergence problems. The file can be viewed in any text editor. Relative filenames are interpreted relative to the CurrentDataDirectory.

SetContext: Optional list of variables. Zero or more context variables that are to be array abstracted over, so that a separate optimization is to be carried out for each variable. See Getting NLPs to Array Abstract.

Over: optional list of indexes. Specifies that a separate optimization is to be carried out over each index that is listed. See Getting NLPs to Array Abstract.

Specifying Search Control Settings

In order to get acceptable results on hard optimization problems, it is sometimes necessary to adjust the settings of the optimizer engine. This may include adjustments to numeric precision, population size, time limits or other termination criteria, etc.

Search control settings are specified via the Parameter and Setting parameters of NlpDefine. For example, when using the Evoluationary solver, you may want to set the mutation rate, which would be done as follows:

NlpDefine( ..., Engine:"Evolutionary", Parameter:"MutationRate", Setting: 0.15 )

In order to change a setting you must know the setting name and the value you wish to use. The possible settings names depend on which engine is used, but the possible settings for any engine can be accessed using the SolverInfo function. To see the set of parameters and their default values and allowed ranges for the evolutionary solver, use:

SolverInfo( Engine:"Evolutionary", Item:["MinSetting","MaxSetting","Defaults"] )

The above example sets a single setting, but in general you may need to specify multiple search settings. To do this, Parameter and Setting must have a common index. A common way to do this is to define a self-indexed table, filling in the setting names as index labels and the table body cells with the settings. When set up in this fashion, specify only the Setting parameter, omitting Parameter, and Analytica will automatically find the parameter names in the index labels.