Optimization Characteristics

Introduction

Although the material in this chapter is not specific to Analytica, it should give users a foundation of knowledge sufficient to understand the basic characteristics of an optimization problem and to understand the mathematical characteristics that define different optimization types.

Parts of an Optimization Problem: General Description

The first step in performing an optimization is to formulate the problem appropriately. An optimization problem is defined by four parts: a set of decision variables, an objective function, bounds on the decision variables, and constraints. The formulation looks like this.

Decision variables

A vector (one-dimensional array) of the variables whose values we can change to find an optimal solution. A solution is a set of values assigned to these decision variables.

Objective

A function of the decision variables that gives a single number evaluating a solution. By default, the Optimizer tries to find the value of the decision variables that minimizes the value of objective. If you set the optional parameter Maximize to True, it instead tries to maximize the objective. For a linear program (LP), the objective is defined by a set of coefficients or weights that apply to the decision variables. For a nonlinear program (NLP), the objective can be any expression or variable that depends on the decision variables.

Bounds

A range on the decision variables, defining what values are allowed. These bounds define the set of possible solutions, called the search space. Each decision variable can have a lower bound and/or an upper bound. If not specified, the lower and upper bounds are -INF and +INF — that is, there are no bounds.

Constraints

The constraints, e.g., , are bounds on functions of the decision variables. They define which solutions are feasible.

Identifying the type of optimization

A critical issue in formulating an optimization problem is determining whether it is linear, quadratic, or nonlinear. Although Analytica can automatically determine class of optimization, it is important for the user should have a basic understanding of what these classes mean.

For a linear program (LP), the objective must be a linear function of the decision variables. For a quadratic program (QP), the objective is a quadratic function and the constraints must be linear functions of the decision variables. For a quadratically-constrained program (QCP), the objective and constraints must all be linear or quadratic functions of decision variables. The problem is a nonlinear program (NLP) if the objective or any of the constraints are non-quadratic in any of the decision variables.

Linear and convex quadratic optimization problems are often relatively fast to compute. But general nonlinear optimization is a computationally difficult problem. Many of the most famous and notoriously difficult computation problems can be cast as optimization programs, from the traveling salesman to the solution (or non-solution) of Fermat’s last “theorem.” It is, therefore, unreasonable to expect the Optimizer engine to succeed on any possible nonlinear problem you can formulate. While the Frontline Solver engine used in the Analytica Optimizer is among the best of the general-purpose optimization engines available, success with hard optimization problems depends on your ability to formulate the problem effectively, provide appropriate hints for the Optimizer, and adjust the search control settings.

There are often several ways to formulate the same problem. Linear and quadratic formulations are faster and more flexible, so it is worth careful thought to see if it is possible to reformulate a nonlinear optimization into a linear or quadratic optimization. Often a simple transformation, combination, or disaggregation of the decision variables can turn an apparently nonlinear problem into a linear or quadratic problem.

Specific Optimization Characteristics

The general description of optimization problems on page 16 applied to all problem types. The following sections offer more specific mathematical descriptions for each type of optimization:

Parts of a Linear Program (LP)

A linear optimization problem has the following standard formulation. In this standard form, all decision variables, xi, are real-valued and unconstrained, rang-ing from -INF to +INF – ( ∞ t o∞ ).

Linear programs generally solve quickly, although large models can be computationally complex. Solutions to linear problems always represent a global maximum or minimum. This means that you always be assured of finding the absolute optimum solution.