DefineOptimization

New to Analytica 4.3

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

Defines an optimization problem, in which Analytica Optimizer should find a set of values for the indicated decisions variables that satisfies all the indicated constraints and, if an objective is also specified, maximizes or minimizes the objective. The function is used for defining Linear Programs (LPs), Quadratic Programs (QPs), Quadratically Constrained Programs (QCPs), and Non-Linear Programs (NLPs).

DefineOptimization has a long list of optional parameters, but typically the core parameters («decisions», «minimize» or «maximize», and «constraints») suffice to define the optimization problem definition, with attributes within your model filling in the necessary details about each decision and constraint. You should generally use a named-parameter syntax when calling DefineOptimization, by spelling out the name of each parameter followed by a colon, and then followed by argument(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.

Many problems also specify constraints that 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. You may specify any number of constraints, each being an equality or inequality expression. Each constraint may be array-valued, which in effect specifies a collection of constraints that must be satisfied.

The «type» parameter is optional, but may be explicitly specified as 'LP', 'QP', 'QCP', 'CQCP', 'NCQCP', 'NLP', or 'NSP'. (Linear, Quadratic, Quadratically constrained, Convex Quadratically Constrained, Non-convex Quadratically Constrained, Non-Linear, or Non-Smooth). When this is omitted, Analytica will automatically analyze the model to determine the problem type, and will select the solver engine that is appropriate for that type of problem. When you explicitly specify «type», an error will be reported if the problem is found to be outside of that problem class. To utilize a linear or quadratic solver, your model must contain only linear (or quadratic) relationships.

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. The DefineOptimization function supercedes the older LpDefine, QpDefine and NlpDefine functions that were used in Analytica 3.1 through Analytica 4.2, although these older functions are still available to be used in the cases where they are more convenient.

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, but it does not actually solve for the solution. Once a problem has been defined, its solution is obtained using the OptSolution function. A series of additional functions access other aspects 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. Given a solution object, the OptInfo function can be used to explore the internals of the problem specification. For example, you can use OptInfo to explore how your Analytica model was converted into linear or quadratic coefficients.

DefineOptimization will typically evaluate your model between one and three times in order to deduce the problem type and dimensionalities of decisions and constraints. The bulk of the solving time is incurred when OptStatusText, OptSolution, or other solution function is called, when the problem is actually solved.

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 allowed 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. 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

The key "components" of a 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 bounds for variables if you plan to use the Evolutionary solver engine.

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 OptDimensions attribute provides you full control when specifying the dimensionality of a decision variable. If you leave OptDimensions 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 OptDimensions attribute from the object window of a decision node.

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 (occassionally 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.

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 OptDimensions unspecified, Analytica will attempt to infer which extra dimensions should be assimilated or abstracted.

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.

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.

Engine Settings

You may need to select a particular solver engine, or to tune the search control settings for the search.

DefineOptimization will automatically select a solver engine that is appropriate for your problem type if you don't explicitly select the engine. However, when you wish to use a particular solver engine, specify the engine name in the «engine» parameter, e.g.:

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

Four solver engines ship with Analytica Optimizer: "LP/Quadratic", "SOCP Barrier", "GRG Nonlinear", and "Evolutionary". You may also specify the name of an add-on solver engine if you have it installed.

Each solver engine exposes settings that control its termination conditions, algorithm methods, etc. These are set using the «parameter» and «settings» parameters of DefineOptimization. If you wish to change only a single setting, the following method is convenient:

DefineOptimization(.., parameter:"Multistart", setting:1 )

To set more than one, create a 1-D array where the index labels contain the setting name and the array cells contain the setting value, and then pass the array to the «setting» parameter.

To see a list of the settings for the "Evolutionary" engine, evaluate:

OptEngineInfo("Evolutionary", "Defaults")