DefineOptimization

DefineOptimization(decisions, maximize/minimize, constraints, type,...)

Defines an optimization problem to find a solution for the decision variables that maximizes (or minimizes) an objective and satisfies some constraints. Any optimization must have at least one decision variable -- otherwise it has nothing to optimize. If it has no objective, it tries to find any solution that satisfies the constraints. If it has an objective, the constraints are optional. Analytica automatically discovers the type of problem and selects the appropriate solver engine, according to whether the problem is a Linear Program (LP), Quadratic Program (QP), Quadratically Constrained Program (QCP), or Non-Linear Program (NLP).

The key parameters for DefineOptimization are «decisions», «minimize» or «maximize», and «constraints». For example, if your has two decision variables, X and Y, this formulates a linear program to find values of X and Y that maximize the expression subject to two linear constraints:

DefineOptimization(

Decisions: X, Y,

Maximize: 3*X + 2*Y,

Constraints: 5*X + 2*Y <= 900,

8*X + 10*Y <= 2800)

It is best to use named-parameter syntax with DefineOptimization, spelling out the name of each parameter followed by a colon, and the value(s) for that parameter.

A problem definition always specifies one or more decision variables (i.e., there must be at least one thing to solve for or optimize). Decisions define the search space for the optimization. These are typically decision nodes in your model (the green rectangle nodes), although local variables may also be used as decision variables. Each decision variable may be scalar or array-valued. For example, when solving for an optimal portfolio allocation, the allocation decision would typically be dimensioned by an investment index.

Many problems include an objective, which is an expression passed to either the «minimize» or «maximize» parameter, such that the expression depends directly or indirectly on the decision variables. To simply solve a system of equations and inequalities to find a feasible solution, the objective is omitted. When specified, the objective is a standard Analytica expression, typically one that computes a scalar result when the decision variables are set to a candidate solution.

Constraints are expressions that specify an equality or inequality, which must be satisfied by any solution. A problem with no constraints is referred to as an unconstrained optimization problem and must have an objective function. Each constraint may be an array, which specifies a collection of constraints to satisfy.

The Optimizer analyzes your model to discover automatically what type of optimization Program it is, and so which solver engine to use. But, you can also specify the «type» parameter as one of: 'LP', 'QP', 'QCP', 'CQCP', 'NCQCP', 'NLP', or 'NSP'. (Linear , Quadratic, Quadratically constrained, Convex Quadratically Constrained, Non-convex Quadratically Constrained, Non-Linear, or Non-Smooth Program). If you specify the type, it will flag an error if it finds that the actual problem is outside that class -- for example, if you have specified it is an "LP" or linear program and it finds a non-linear relationship.

All problems types (linear, quadratic, or non-linear) are formulated in the same way, using the structure of an Analytica model, and all formulated using DefineOptimization.

Examples

Suppose your model has two decision node variables, X and Y. The following specifies a linear program:

DefineOptimization(

Decisions: X, Y,

Maximize: 3*X + 2*Y,

Constraints: 5*X + 2*Y <= 900,

8*X + 10*Y <= 2800)

Local variables may also be used for the decision variables:

Var X := 0;

Var Y := 0;

DefineOptimization(

Decisions: X, Y,

Maximize: X + 4*Y,

Constraints:

4*X >= Y-2

2*X <= Y+1)

Obtaining the Solution

DefineOptimization defines a problem to be solved or optimized, and analyzes the structure of the problem -- for example to determine it is linear, quadratic, or nonlinear, etc. It does not actually solve for the solution. The first evaluation of OptSolution will trigger finding a solution, as will any related function for accessing an aspect of the solution: OptStatusNum, OptStatusText, OptObjective, OptSlack, OptShadow, OptReducedCost, OptObjectiveSa, OptRhsSa.

When DefineOptimization is evaluated, it returns a special object, which displays as: «LP», «QP», «QCP», «CQCP», «NCQCP», «NLP», or «NSP», depending on the type of problem. This object contains an encoding of the problem definition, and is passed to any of the solution functions mentioned above. You can double-click on the result cell containing «LP» (etc) or evaluate the OptInfo function to explore the internals of the problem specification. For example, you can use OptInfo to see the tables of linear or quadratic coefficients extracted from your model.

DefineOptimization will typically evaluate your model one to three times to discover the problem type and the dimensionalities of decisions and constraints. The bulk of the solving time is incurred when it actually solves the problem, triggered by evaluating OptSolution, OptStatusText, or another solution function.

Variable/Node Classes

In most cases, constraints and objectives are encoded within Analytica variables as part of a larger model. When so doing, the variable (or node) class becomes relevant, where the following distinguished variable classes are used for the respective components of the optimization problem:

For example, the expression to be maximized (or minimized) is placed in the definition of an objective node, and any equality or inequality constraints are placed directly in definitions of constraint nodes.

The use of variable nodes in a model allows you to structure your optimization model in the form of an influence diagram, break up the computation into many steps, splitting among many variable nodes and organizing into submodules. It also allows you to use your model outside of an optimization context, for example, when exploring the solution space manually or via parametric analysis. And it allows further specification of each component within the model nodes themselves. So, for example, if a certain decision variable is integer-valued with special bounds, those can be indicated directly in the decision variable. If certain decisions or constraints incorporate (assimilate) indexes as part of the optimization problem, these can be indicated directly in the decision or constraint node. Thus, most of the problem specification exists within the Analytica model structure, rather than in the parameters to DefineOptimization. Once a model is defined (including decision, constraint and objective nodes), the specific optimization to be solved is defined using DefineOptimization.

Decision Variables

Decision variables define the search space for the optimization, and the set of decision variables to be used is specified in the «decisions» parameter of DefineOptimization. For example:

DefineOptimization(decisions: X, Y, Z, ...)

The variables, X, Y, and Z, may be either identifiers of variables in your model, or may be local variable identifiers.

You can also specify that every decision node in the model should be included by specifying:

DefineOptimization(decisions: All, ...)

Or that all decisions in one or more selected modules using the syntax:

DefineOptimization(decisions: All in Module_A, All in Module_B, ...)

When using All in «module», any decision nodes, aliases or input/output nodes for a decision node that is contained in the indicated module, or in any of its submodules, is included in the optimization except for those decisions that are descendants of the variable being defined with the DefineOptimization function.

An advantage of using the All or All in «module» syntax is that your optimization formulation automatically adapts as decisions are added or subtracted from your model. However, when using this, you must take care not to utilize a decision node for a different purpose.

The key "components" of each decision variable are:

• Its domain, which includes:
  • Its integer type: Continuous, Integer, Binary, Grouped Integer, or an explicit set of Discrete possible values.
  • Its bounds
• Its dimensionality (the indexes that a solution will be indexed by)
• An initial guess

You have full control over these aspects through the attributes of a decision variable node.

The Domain Attribute allows you to select the integer-type and bounds. In most cases, you can use the pulldown and enter simple scalar values for bounds. For more complex domains, where some aspect of the domain is computed, or where the integer type or bounds vary along some index, a computed expression can be specified for the domain. If you use a computed expression for the domain, it should not depend on other decision variables -- the domain remains constant while any given problem space is being solved. When bounds depend on other decision variables, constraints are used (see below). If you don't set the domain of a decision, the variable is treated as continuous. You can also override the domain specified in the decision using the optional «domain» parameter of DefineOptimization. You must set both upper and lower bounds for variables if you plan to use the Evolutionary solver engine.

The decision variable's domain can be computed, but should never depend upon another decision variable in the optimization. If the domain is influenced by another decision variable, the actual domain (integer type and variable bounds) are determined statically from the definitions of the other decision variables and do not change during the optimization search. For example, suppose you have:

Definition of X := 5;

Domain of Y := Continuous(lb: X)

optDef := DefineOptimization(decisions: X, Y,...)

This formulation encodes the bound that Y >= 5, and not a constraint that Y >= X. To enforce Y >= X, use a constraint.

Decision variables are often array-valued -- that is, they may contain one, two or more dimensions even when there is only a single optimization to be solved. The Intrinsic Indexes attribute in the Object Window provides you full control when specifying the dimensionality of a decision variable. If you leave Intrinsic Indexes unspecified, Analytica will attempt to infer the intended dimensionality of each decision variable. Even though it may be able to guess the dimensionality correctly, it is preferred style to explicitly indicate the dimensionality, even if there are no dimensions (in which case we say it has a scalar dimensionality). To specify the dimensionality, press the Indexes button in the Intrinsic Indexes attribute from the object window of a decision node.

When using a local variable as a decision variable, the intrinsic indexes are specified by including parentheses after the variable name, e.g.:

Var x [Segment, Time] := ...

Finally, in certainly non-linear problems, the initial guess may influence both the time required to find the solution, and the actual solution found. Because non-linear problems may contain local optima, the starting point for the search may influence which local optima is discovered, or even whether any feasible solution is found at all. The Initial Guess attribute on a decision node can be used to specify an initial guess, or even an array of initial guesses (occasionally you may want to try solving the same problem from a set of different initial guesses). If you don't specify the Initial Guess attribute, DefineOptimization will attempt to utilize values contained in the Definition for the initial guess, with some limitations. In general, you will probably want to utilize the Definition of decision variables for uses of your model outside of optimization, such as simple evaluation, Parametric Analysis, sensitivity analysis, etc. It is for this reason that DefineOptimization prefers you to use the Initial Guess attribute for specifying initial guesses. Note that when your problem is linear (or even convex quadratic), the initial guess is irrelevant. You can also override the particular initial guess encoded in a decision node by specifying the optional «guess» parameter to DefineOptimization.

Constraints

Constraints specify relationships between quantities in your model that must be satisfied in any feasible solution. Constraints should depend directly or indirectly on decision variables. A constraint specification consists of two items of information:

• An equality or inequality expression.
• A list of intrinsic (assimilated) indexes

A constraint can be specified directly to the «constraints» parameter as an equality or inequality expression, or it can be placed within a constraint node with the definition consisting of an equality or inequality expression. The equality or inequality expression must be the top-level operation in the definition. When using constraint nodes, list the constraint identifiers in the «constraints» parameter of DefineOptimization.

You can also specify All or All in «module» as a constraint to indicate that all constraint nodes located in (or with aliases located in) the given module or any of its submodules are to be included in the optimization.

The following illustrates the various ways that constraints can be specified:

DefineOptimization(

decisions: All,

Constraints:

Closed_system_constraint,

No_loss_constraint,

X + Y <= Z,

X <= Y,

All in Module_A,

All in Module_B,

...)

A single constraint expression will generally encode a collection of constraints when inputs to the constraint expression are array-valued. These dimensions may either be intrinsic to your problem, or abstracted. Intrinsic dimensions result in multiple constraints within a single optimization problem. Abstracted dimensions result in multiple separate optimization problems. In a constraint node, use the OptDimensions attribute to list intrinsic dimensions of your problem. By pressing the Indexes button, you can select the intrinsic indexes, or select none when no extra dimensions should be assimilated into the optimization problem. If you leave the Intrinsic Indexes unspecified, Analytica will attempt to infer which extra dimensions should be assimilated or abstracted.

See also Display of constraint results.

Objective

When you wish simply to find a solution to a set of equations and inequalities, the objective need not be specified. Otherwise, the expression is specified using either the «maximize» or «minimize» parameter of DefineOptimization. The expression parameter accepts an Analytica expression that evaluates to a single number within a single optimization problem. E.g.:

DefineOptimization(

decisions: All,

minimize: Cost)

It is a stylistic convention to place objective expressions within an objective node, so that the objective is visually distinguished when viewing an influence diagram depiction of your model. With an objective node, simply place the identifier in the «maximize» or «minimize» parameter of DefineOptimization. If you are maximizing or minimizing a statistical quality such as the Mean, then it is nicer to set the «maximize» parameter to the expression Mean(MyObjective), rather than including the call to Mean within the node's definition.

Problem Type

Most solver engines can only solve some problem types. So you, the modeler, need to figure out ahead of time what type of problem you are trying to solve, according to whether the objective and constraints are linear, quadratic, or other nonlinear functions of the decision variables, and so select the appropriate engine. The Analytica Optimizer can usually figure out the problem type itself. It then automatically chooses the appropriate solver engine. These are the problem types it can handle:

• LP: Linear objective and linear constraints
• QP: Quadratic objective and linear constraints
• QCP: Linear or quadratic objective and quadratic constraints. This is further sub-categorized as:
  • CQCP: Convex quadratic
  • NCQCP: Non-convex quadratic
• NLP: (Smooth) Non-linear objective and constraints
• NSP: Non-smooth (hence non-linear) objective and constraints

Parts of your model that do not depend on decision variables can be of any functional form without impacting the problem type.

If DefineOptimization finds that all constraints and the objective are linear functions of the decision variables, it automatically sets the problem type to «LP», infers all the linear coefficients, and selects the "LP/Quadratic" solver engine. Or if it finds that some relationships are quadratic, it automatically selects that problem type, computes the quadratic coefficient matrices, and selects the appropriate engine . It may not discover the convexity or non-convexity of a set of quadratic constraints until it starts to solve the problem; but if a non-convexity is detected, it changes the problem type to NCQCP and and uses the "GRG Nonlinear" solver engine.

You always have the option of setting the problem type yourself using the «type» parameter, rather than rely on Analytica to infer it. This may eliminate the need for some aspects model analysis by DefineOptimization, which could reduce computation time slightly. Also, if you specify the «type», DefineOptimization issue an error if the relationships in the model are not consistent with that problem type. This is often useful when you expect the model to be linear (or quadratic), and want to be notified if you have accidentally introduced some relation that is not linear (or not quadratic).

You can also specify any problem type as:

• continuous - every decision variables is continuous
• integer -- every decision variable is boolean, integer, or discrete with explicit values, or
• mixed-integer some decisions are continuous and some are integer.

The integer-ness or otherwise of each decision variable is taken directly from its Domain.

Solver Engines

Analytica Optimizer ships with four solver engines: "LP/Quadratic", "SOCP Barrier", "GRG Nonlinear", and "Evolutionary". Normally, DefineOptimization automatically chooses the most appropriate solver based on how the problem is formulated. But, sometimes you may want to tell it which engine to use, specify the «engine» parameter, e.g.:

DefineOptimization(.., Engine: "GRG Nonlinear")

You can also purchase a range of more powerful add-on solver engines for challenging applications with large numbers of decision variables and constraints. See [1] to purchase one. See information Examining Engine Capabilities to learn the numbers of decisions and constraints handled by each engine type.

If you have installed an add-on engine, you may specify its use by setting the «engine» parameter.

Engine settings

Each solver engine has settings that control its Termination Controls, algorithm methods, and so on. You can see the full list of settings relevant to a specified engine using this function:

OptEngineInfo(«Engine», "SettingNames")

You can see the default settings with:

OptEngineInfo(«Engine», "Defaults")

You can change one engine setting using the «settingName» and «settingValue» parameters, like this:

DefineOptimization(..., settingName: "Multistart", settingValue: 1)

If you want to specify several engine settings, it is easier to create a 1-D array where the index labels each contain a setting name and the array cells contain the corresponding values. You then pass the array to the «settingValue» parameter.

Debugging Problem Formulations

Debugging an optimization model can be very difficult. Many nasty complications appear in non-linear models in particular, such as local minima and maxima, and unusual surfaces with gradients pointing off in unexpected directions, and singularities that result in INF or NaN values, which may thwart successful convergence to a solution. Identifying which constraints to blame when no feasible solution exists is seldom obvious. And mistakes with dimensionality may create a problem formation different from that which you expected.

No feasible solution

A big advantage of linear over nonlinear optimization is that you can use special tools to diagnose which constraint(s) are to responsible for the absence of any feasible solution. The OptFindIIS function identifies the minimal set of constraints in your problem that form a contradiction -- i.e. cannot be satisfied simultaneously.

For quadratic and non-linear problems, debugging the no feasible solution problem requires more ingenuity. The best strategy is to relax constraints that you expect might be the hardest to satisfy. For example, maybe it would be easy to find a feasible solution when you are not limited by budget; so, you might start by removing the budget constraint from the «constraints» parameter, or simply increase the available budget amount. Once you obtain a formulation with a feasible solution, you may gain further insight into the nature of your problem.

For non-linear problems, it may help to study the trace file. For additional hints on diagnosing non-feasible formulations, see no feasible solution warning.

Trace File (NLPs)

When solving an NLP (or when using the "GRG Nonlinear" or "Evolutionary" engine on an LP or QP), you can generate a trace file log of the points explored during the solution process. To do this, specify a file name for the trace file in the «traceFile» parameter, thus:

DefineOptimization(..,engine: "GRG Nonlinear", traceFile: "C:\Temp\trace.log")

Once the solve is attempted, load the indicated file into a text editor such as NotePad or TextPad. Each point searched is logged, along with the values of the objective and constraints, with violated constraints flagged with a (!). Many mysteries are solved quickly when viewing the trace file -- it often becomes quite obvious why the solver engine did what it did.

Examining internals of problem specification

DefineOptimization returns an object that displays as «LP», «NLP», etc. When this displays in a result table, you can double click on it to view the internals. Double clicking on it brings up the same result obtained when you evaluate OptInfo(def, "All").

You can access individual parts of the formulation more directly using other options of the OptInfo function. The OptInfo function returns information about the internals of an optimization problem instance. For example, to see exactly what decision variables and constraints are present and how intrinsic dimensions were "flattened", view the result of each of these expressions:

OptInfo(probDef, "Variables")

OptInfo(probDef, "Constraints")

Numerous other components can be viewed using OptInfo, including bounds and linear/quadratic coefficients, which may help establish whether the problem formation was interpreted as you intended.

Array Abstraction Control

When an extra dimension is identified in the objective, a constraint, initial guess, a variable's domain, or an optional parameter of DefineOptimization, which is otherwise not determined to be intrinsic to the optimization problem itself, Analytica's standard intelligent array mechanism will array abstract over that index to produce multiple problem instances, where each problem instance shall be solved separately, and where each instance varies in its formation accordingly. Hence, a single DefineOptimization call may define an array of optimization problems, each to be solved separately.

When you want to force array abstraction over a particular index or indexes, you can list these indexes in the «over» parameter of DefineOptimization. For example:

DefineOptimization(..., over: Plant)

indicates that a separate optimization should be solved for each Plant.

Linear and quadratic optimization problems array abstract pretty seamlessly, such that if you introduce new indexes into your model in the future, the principles of array abstraction kick in and automatically generalize to an array of independent optimizations. The same can also be said of non-linear optimizations defined via DefineOptimization, except that certain substantial inefficiencies may arise when non-linear models are array abstracted. In most cases, you can circumvent these with some model modification and appropriate use of the «SetContext» parameter. Without circumventing these inefficiencies, the non-linear optimizations will array abstract in a functionally correct fashion, so that you can evaluate and view the results, but you may find excessive computation times, especially as your abstracted indexes grow in length.

The potential inefficiency with abstracted NLPs results because your constraints, objective, and intermediate variables within your model may be computing array-valued results along the abstracted index, even when the optimization problem actively being solved corresponds to only a single position along that index. To eliminate this inefficiency, you must refine your model so that all children of the index can continue to successfully evaluate when the list definition of the index is replaced by a single value (for example, Tables must be replaced by DetermTables). Once this is the case, you can list the index in the «SetContext» parameter. As any single NLP is being solved, the indicated context variable will be replaced with the single value. See Using SetContext to efficiently solve NLPs.

Optional Parameters

Overriding Integer type and bounds

DefineOptimization has a large number of additional optional parameters, mostly esoteric.

The «Domain» parameter can be used to override the domain appearing in decision variable nodes, or to provide an integer type or bounds for local decision variables. The «Domain» parameter accepts expressions composed of Domain Specification Functions, and is a repeated parameter where the expressions are placed in positional correspondence with the list of decision variables in the «decisions» parameter. For example:

DefineOptimization(

decisions: X, Y1, Y2, U, Z,

domain: Continuous(-1, 1), GroupedInteger("G1"), GroupedInteger("G1"), Null, Boolean(),

... )

In the above, X is treated as continuous, bounded by -1 ≤ X ≤ 1, Y1 and Y2 are grouped integer variables belonging to the same group, and Z is a boolean integer. U's domain is not overriden.

Overriding Initial Guess

The initial guess for each variable can likewise be specified as a parameter, overriding the Initial Guess attribute or other inferred initial value. Like «Domain», the «Guess» attribute is a repeated parameter in positional correspondence with the variables listed in the «decisions» parameter.

DefineOptimization(

decisions: X, Y1, Y2, U, Z,

guess: 0.5, null, null, 0, 1,

...)

In the example, initial values for X, U, and Z are provided. The initial guess for Y1 and Y2 are not overridden.

Preserving values

DefineOptimization, and the solution process for an NLP, conduct a series of WhatIf type evaluations on the model. Previously computed values are preserved by default, meaning that they are returned once the solution process completes.

You can set the optional parameter «preserve» to false to turn this off. Doing so eliminates the memory overhead required to save all the previously computed values, but will require all those values to be recomputed if they are viewed again later. If you are having trouble completing your solution within available memory, this switch may help a little; otherwise, there is little reason to use it.

Indexes of local decision variables and constraint expressions

Whereas structured optimization models include explicit objects in the model for decisions and constraints, some code (often in User-Defined Functions) defines and solves an optimization in an expression that stands on its own, without external decision and constraint objects. Without the objects, you don't have the attributes such as Intrinsic Indexes and Domain for specifying information about the decisions and constraints.

In stand-alone problems, local variables are used for decision variables, and expressions for constraints and objective are specified as expressions. For example:

Local x := 0;
Local opt := DefineOptimization( Decisions: x, Constraints: x^2 = Exp(x) );
OptSolution(opt,x)

If you need to explicitly specify intrinsic indexes for decision variables, you do so by specifying the indexes in the local declaration. If you need to explicitly specify intrinsic indexes for any of the constraints, use the optional «InstrinsicIndexes» parameter (which requires Analytica 5.0). For example:

Local pt[Dim] := target_point;   { Uses the local as the decision variable }
OptSolution(
	DefineOptimization( 
		Decisions: pt,
		Minimize: Sum( (pt-target_point)^2, Dim ) ,
		Constraints: Sum( (pt-circle_center)^2, Dim)) <= Circle_radii^2,
		IntrinsicIndexes: Circle_index
	)
)

The above example is found in the "NLP with Jacobian" model (with partial derivative specification not shown here), and the closest point target_point that is also inside all specified circles (or spheres or hyper-spheres when the Dim index has more than 2 elements. The declaration of x specifies that x has the Dim index (i.e., it is a point in IndexLength(Dim)-dimensional space). DefineOptimization uses is usual heuristics to infer the dimensionality of decisions and constraints from all the items in the problem definition, but in this case, without specifying Circle_index in the «IntrinsicIndexes», it will infer that you want to solve a separate optimization problem for each circle (i.e., that Circle_index is extrinsic.

When one or more indexes are listed in «IntrinsicIndexes», these apply to any constraints whose evaluation has those indexes when the decisions are evaluated with their dimensionality. It applies to all constraints where those indexes appear, including global constraint objects, even if they also specify the Intrinsic Indexes parameter.

History

DefineOptimization was introduced in Analytica 4.3 to replace the older LpDefine, QpDefine and NlpDefine functions. These older functions are still available for backward compatibility.

See Also

• Specifying Settings
• Primary Optimization Functions
• NlpDefine
• Formulations that Preserve Linearity for Optimization
• Using SetContext to efficiently solve NLPs
• Using a Solver Add-on Engine
• Solving and the solution: OptSolution, OptStatusText, OptObjective
• Viewing internals: OptInfo, OptEngineInfo
• Display of constraint results