Chance constrained programming

Last updated August 10, 2024

Chance Constrained Programming (CCP) is a mathematical optimization approach used to handle problems under uncertainty. It was first introduced by Charnes and Cooper in 1959 and further developed by Miller and Wagner in 1965.^[1]^[2] CCP is widely used in various fields, including finance, engineering, and operations research, to optimize decision-making processes where certain constraints need to be satisfied with a specified probability.

Theoretical Background

Chance Constrained Programming involves the use of probability and confidence levels to handle uncertainty in optimization problems. It distinguishes between single and joint chance constraints:

Single Chance Constraints: These constraints ensure that each individual constraint is satisfied with a certain probability.
Joint Chance Constraints: These constraints ensure that all constraints are satisfied simultaneously with a certain probability.^[3]

Mathematical Formulation

A general chance constrained optimization problem can be formulated as follows:

$\min f(x,u,\xi ){\text{s.t. }}g(x,u,\xi )=0,\Pr\{h(x,u,\xi )\geq 0\}\geq \alpha$

Here, $f$ is the objective function, $g$ represents the equality constraints, $h$ represents the inequality constraints, $x$ represents the state variables, $u$ represents the control variables, $\xi$ represents the uncertain parameters, and $\alpha$ is the confidence level.

Common objective functions in CCP involve minimizing the expected value of a cost function, possibly combined with minimizing the variance of the cost function.^[3]

Solution Approaches

To solve CCP problems, the stochastic optimization problem is often relaxed into an equivalent deterministic problem. There are different approaches depending on the nature of the problem:

Linear CCP: For linear systems, the feasible region is typically convex, and the problem can be solved using linear programming techniques.
Nonlinear CCP: For nonlinear systems, the main challenge lies in computing the probabilities and their gradients. These problems often require nonlinear programming solvers.
Dynamic Systems: Dynamic systems involve time-dependent uncertainties, and the solution approach must account for the propagation of uncertainty over time.^[3]

Practical Applications

Chance constrained programming is used in engineering for process optimisation under uncertainty and production planning and in finance for portfolio selection.^[3] It has been applied to renewable energy integration,^[4] generating flight trajectory for UAVs,^[5] and robotic space exploration.^[6]

Process Optimization Under Uncertainty

CCP is used in chemical and process engineering to optimize operations considering uncertainties in operating conditions and model parameters. For example, in optimizing the design and operation of chemical plants, CCP helps in achieving desired performance levels while accounting for uncertainties in feedstock quality, demand, and environmental conditions.^[3]

Production Planning and Operations

In production planning, CCP can optimize production schedules and resource allocation under demand uncertainty. A typical problem formulation involves maximizing profit while ensuring that production constraints are satisfied with a certain probability.^[3]

Chance-Constrained Portfolio Selection

Chance-constrained portfolio selection is an approach to portfolio selection under loss aversion which is based on CCP. The goal is to maximize expected returns while ensuring that the portfolio's risk (e.g., variance or downside risk) stays within acceptable levels with a certain probability. This approach allows investors to consider the uncertainty in asset returns and make more informed investment decisions.^[3]

Related Research Articles

Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize a multivariate quadratic function subject to linear constraints on the variables. Quadratic programming is a type of nonlinear programming.

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

In the field of mathematical optimization, stochastic programming is a framework for modeling optimization problems that involve uncertainty. A stochastic program is an optimization problem in which some or all problem parameters are uncertain, but follow known probability distributions. This framework contrasts with deterministic optimization, in which all problem parameters are assumed to be known exactly. The goal of stochastic programming is to find a decision which both optimizes some criteria chosen by the decision maker, and appropriately accounts for the uncertainty of the problem parameters. Because many real-world decisions involve uncertainty, stochastic programming has found applications in a broad range of areas ranging from finance to transportation to energy optimization.

Multi-disciplinary design optimization (MDO) is a field of engineering that uses optimization methods to solve design problems incorporating a number of disciplines. It is also known as multidisciplinary system design optimization (MSDO), and multidisciplinary design analysis and optimization (MDAO).

Curve fitting is the process of constructing a curve, or mathematical function, that has the best fit to a series of data points, possibly subject to constraints. Curve fitting can involve either interpolation, where an exact fit to the data is required, or smoothing, in which a "smooth" function is constructed that approximately fits the data. A related topic is regression analysis, which focuses more on questions of statistical inference such as how much uncertainty is present in a curve that is fitted to data observed with random errors. Fitted curves can be used as an aid for data visualization, to infer values of a function where no data are available, and to summarize the relationships among two or more variables. Extrapolation refers to the use of a fitted curve beyond the range of the observed data, and is subject to a degree of uncertainty since it may reflect the method used to construct the curve as much as it reflects the observed data.

In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints are not linear equalities or the objective function is not a linear function. An optimization problem is one of calculation of the extrema of an objective function over a set of unknown real variables and conditional to the satisfaction of a system of equalities and inequalities, collectively termed constraints. It is the sub-field of mathematical optimization that deals with problems that are not linear.

Model predictive control (MPC) is an advanced method of process control that is used to control a process while satisfying a set of constraints. It has been in use in the process industries in chemical plants and oil refineries since the 1980s. In recent years it has also been used in power system balancing models and in power electronics. Model predictive controllers rely on dynamic models of the process, most often linear empirical models obtained by system identification. The main advantage of MPC is the fact that it allows the current timeslot to be optimized, while keeping future timeslots in account. This is achieved by optimizing a finite time-horizon, but only implementing the current timeslot and then optimizing again, repeatedly, thus differing from a linear–quadratic regulator (LQR). Also MPC has the ability to anticipate future events and can take control actions accordingly. PID controllers do not have this predictive ability. MPC is nearly universally implemented as a digital control, although there is research into achieving faster response times with specially designed analog circuitry.

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.

Bayesian experimental design provides a general probability-theoretical framework from which other theories on experimental design can be derived. It is based on Bayesian inference to interpret the observations/data acquired during the experiment. This allows accounting for both any prior knowledge on the parameters to be determined as well as uncertainties in observations.

In mathematics, constraint counting is counting the number of constraints in order to compare it with the number of variables, parameters, etc. that are free to be determined, the idea being that in most cases the number of independent choices that can be made is the excess of the latter over the former.

In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. If the primal is a minimization problem then the dual is a maximization problem. Any feasible solution to the primal (minimization) problem is at least as large as any feasible solution to the dual (maximization) problem. Therefore, the solution to the primal is an upper bound to the solution of the dual, and the solution of the dual is a lower bound to the solution of the primal. This fact is called weak duality.

In mathematical optimization, constrained optimization is the process of optimizing an objective function with respect to some variables in the presence of constraints on those variables. The objective function is either a cost function or energy function, which is to be minimized, or a reward function or utility function, which is to be maximized. Constraints can be either hard constraints, which set conditions for the variables that are required to be satisfied, or soft constraints, which have some variable values that are penalized in the objective function if, and based on the extent that, the conditions on the variables are not satisfied.

In mathematics, a constraint is a condition of an optimization problem that the solution must satisfy. There are several types of constraints—primarily equality constraints, inequality constraints, and integer constraints. The set of candidate solutions that satisfy all constraints is called the feasible set.

Penalty methods are a certain class of algorithms for solving constrained optimization problems.

Robust optimization is a field of mathematical optimization theory that deals with optimization problems in which a certain measure of robustness is sought against uncertainty that can be represented as deterministic variability in the value of the parameters of the problem itself and/or its solution. It is related to, but often distinguished from, probabilistic optimization methods such as chance-constrained optimization.

The scenario approach or scenario optimization approach is a technique for obtaining solutions to robust optimization and chance-constrained optimization problems based on a sample of the constraints. It also relates to inductive reasoning in modeling and decision-making. The technique has existed for decades as a heuristic approach and has more recently been given a systematic theoretical foundation.

The GEKKO Python package solves large-scale mixed-integer and differential algebraic equations with nonlinear programming solvers. Modes of operation include machine learning, data reconciliation, real-time optimization, dynamic simulation, and nonlinear model predictive control. In addition, the package solves Linear programming (LP), Quadratic programming (QP), Quadratically constrained quadratic program (QCQP), Nonlinear programming (NLP), Mixed integer programming (MIP), and Mixed integer linear programming (MILP). GEKKO is available in Python and installed with pip from PyPI of the Python Software Foundation.

Dynamic discrete choice (DDC) models, also known as discrete choice models of dynamic programming, model an agent's choices over discrete options that have future implications. Rather than assuming observed choices are the result of static utility maximization, observed choices in DDC models are assumed to result from an agent's maximization of the present value of utility, generalizing the utility theory upon which discrete choice models are based.

Chance-constrained portfolio selection is an approach to portfolio selection under loss aversion. The formulation assumes that (i) investor's preferences are representable by the expected utility of final wealth, and that (ii) they require that the probability of their final wealth falling below a survival or safety level must to be acceptably low. The chance-constrained portfolio problem is then to find:

References

↑ Charnes, Abraham; Cooper, William W. (1959). "Chance-Constrained Programming". Management Science. 6 (1): 73–79. doi:10.1287/mnsc.6.1.73.
↑ Miller, L. R.; Wagner, H. M. (1965). "Chance-constrained programming with joint constraints". Operations Research. 13 (6): 930–945. doi:10.1287/opre.13.6.930.
1 2 3 4 5 6 7 Pu, Pu; Arellano-Garcia, Harvey; Wozny, Günter (2008). "Chance constrained programming approach to process optimization under uncertainty". Computers and Chemical Engineering. 32 (1–2): 25–45. doi:10.1016/j.compchemeng.2007.05.009.
↑ Zhang, Ning; Kang, Chongqing; Du, Ershun; Wang, Yi (2019). Analytics and Optimization for Renewable Energy Integration. CRC Press. p. 180. ISBN 9780429847707.
↑ Chai, Runqi (2023). Advanced Trajectory Optimization, Guidance and Control Strategies for Aerospace Vehicles. Springer Nature Singapore. p. 131. ISBN 9789819943111.
↑ Ono, Masahiro; Pavone, Marco; Kuwata, Yoshiaki; Balaram, J. (2015). "Chance-constrained dynamic programming with application to risk-aware robotic space exploration". Autonomous Robots. 39: 555–571. doi:10.1007/s10514-015-9467-7.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Charnes, Abraham; Cooper, William W. (1959). "Chance-Constrained Programming". Management Science. 6 (1): 73–79. doi:10.1287/mnsc.6.1.73.

[2] Miller, L. R.; Wagner, H. M. (1965). "Chance-constrained programming with joint constraints". Operations Research. 13 (6): 930–945. doi:10.1287/opre.13.6.930.

[pu-3] 1 2 3 4 5 6 7 Pu, Pu; Arellano-Garcia, Harvey; Wozny, Günter (2008). "Chance constrained programming approach to process optimization under uncertainty". Computers and Chemical Engineering. 32 (1–2): 25–45. doi:10.1016/j.compchemeng.2007.05.009.

[4] Zhang, Ning; Kang, Chongqing; Du, Ershun; Wang, Yi (2019). Analytics and Optimization for Renewable Energy Integration. CRC Press. p. 180. ISBN 9780429847707.

[5] Chai, Runqi (2023). Advanced Trajectory Optimization, Guidance and Control Strategies for Aerospace Vehicles. Springer Nature Singapore. p. 131. ISBN 9789819943111.

[6] Ono, Masahiro; Pavone, Marco; Kuwata, Yoshiaki; Balaram, J. (2015). "Chance-constrained dynamic programming with application to risk-aware robotic space exploration". Autonomous Robots. 39: 555–571. doi:10.1007/s10514-015-9467-7.

[1]

[2]

[3]

[4]

[5]

[6]