Sophisticated Optimization

Linear problems are characterized by a linear mathematical relationship between the input decision variables and all constraints, as well as with the output. For example, if an input goes up by x, then the output goes down by 2x, subject to a similarly simple constraint. Scheduling the shortest route (assuming straight lines and constant speed) to stop at a given number of destinations is a common example of a linear optimization problem.

Nonlinear problems are a bit more advanced and feature at least one nonlinear relationship between decision variables and a constraint or the output. For example, if an input goes up by x, then the output goes up by some value to the power of x. Maximizing return on an investment portfolio subject to constraints on risk is an example of a common nonlinear optimization problem.

Most practical optimization problems involve constraints of some kind – real-life limitations such as budget ceilings, schedules, or resource availability. These are called constrained optimization models. Sometimes, however, unconstrained optimization techniques arise, especially as a way to revisit a constrained model. Often, a constrained optimization analysis may not produce results that are good enough, and so the “ideal” constraints must be removed or relaxed, and the model reconsidered. When this happens, constraints can be replaced by penalty functions which allow the formerly “illegal” values to be considered, but apply some kind of “penalty,” such as an additional cost, when they occur. In this way, more realistic situations and options can be modeled.

In some optimization models, the variables in question lend themselves to a defined, limited set of possible values – often integers. You can only select full integers of people for a production schedule, for example. These are discrete optimization models. Other models contain variables that can take on any value. For instance, you could invest any amount of dollars and cents in a given asset class of a portfolio. These are continuous optimization models. Continuous optimization problems tend to be easier to solve than discrete optimization problems because the availability of so many values enable algorithms to better infer data about other, better possible solutions. However, improvements in algorithms and computing technology have made even complex discrete optimization problems more solvable than ever.

Most optimization problems have a single goal (or objective function) to solve – minimize a cost, or maximize a return, for example. However, there are cases when optimization models have no objective function. In feasibility problems, the goal is to find values for the variables that satisfy the constraints of a model with no particular objective to optimize. By contrast, multi-objective optimization problems arise as well, in fields such as engineering, economics, and logistics. In these cases, optimal decisions need to be made while considering trade-offs between two or more conflicting objectives. For example, developing a new industrial component might involve minimizing weight while maximizing strength, or choosing a financial portfolio might involve maximizing the expected return while minimizing risk. These problems are modeled in optimization software as single objective models by either creating a weighted combination of the different objectives or by replacing some of the objectives with constraints.

In deterministic optimization, it is assumed that all the data for the given model are known with certainty. However, for many actual problems, the data cannot be known accurately because they represent unknown information about the future (for example, product demand or price for a future time period). In stochastic optimization, or optimization under uncertainty, such uncertainty is incorporated into the model. Probability distributions describing the unknown data can be estimated, and then a Monte Carlo simulation is run for each trial solution the optimization algorithm selects. In this way, a statistic of the simulated solution is optimized – for instance, you may want to minimize the standard deviation of the results to reduce risk. The goal is to find some policy that is feasible for all (or almost all) the possible outcomes and optimizes the expected performance of the model.