Mathematische Optimization: Theory
Overview
Formulating and solving optimization problems \( \min f(x), x \in D\) requires the application of various fields of applied mathematics and is a versatile endeavor.
Modeling real-world problems in mathematical language is a creative task that draws on probability theory and linear algebra. The resulting optimization problems can be analyzed for their structural properties; depending on the objective function \(f\) and constraints \(D\), theoretically provable guarantees about the solvability and complexity of the problem can be derived. The ultimate solution of the optimization problem falls within the domain of numerical analysis, where mathematics, computer science, and programming challenges converge.
Modelling
Real-world phenomena are characterized by complexity, nonlinear relationships, and uncertainties. Their accurate representation requires a detailed examination of the variables describing the phenomenon and any causal relationships.
These can be simple (e.g., the relationship between production costs and profit), complex (e.g., the relationship between acceleration and position), or stochastic (e.g., the relationship between investment duration and return). Often, modeling requires data analysis to quantify the interactions between various variables, introducing another source of uncertainty into the modeling process. This uncertainty must be quantified and constrained using stochastic methods.
The transformation into an abstract mathematical model is further complicated by the fact that only a restrictive class of models can be reliably solved within the framework of mathematical optimization. Therefore, details irrelevant to the central relationships must be reduced as much as possible for later use—a conflict with the original goal of a truthful mathematical representation of a real-world phenomenon. Cycles of model formulation, analysis, and evaluation are the standard [1, p. 13]. In short: models are simple, modeling is hard.
Analysis
Whether and how an optimization problem \( \min f(x), x \in D\) can be solved depends on the properties of the objective function \(f\) and the constraints \(D\). For some combinations, solution guarantees can be provided, while others resist any attempt to find the optimum.
A crucial property is convexity. If an optimization problem is convex, then \(f\) has only one local optimum, and every line segment between two points \(x_1, x_2 \in D\) lies entirely within \(D\) [2, p. 138]. Consequently, the search for a global optimum reduces to finding the single local optimum. The use of gradient-based methods is sufficient to generate a sequence of successively better points converging to the global optimum.
Convex optimization problems also have a systematically constructible lower bound for their optimal values \( \min f(x), x \in D\). These bounds are themselves solutions to an optimization problem, known as the dual problem [2, p. 216]. These secondary problems reveal much about the original optimization problem, allowing for diagnostics on the sensitivity of the optimal value to changes in the constraints or providing solvability guarantees.
Solution
If the optimization problem is convex, then it is essentially solvable. Using vectors and matrices, local slopes and curvatures are quantified. These are used in an iterative process to generate a sequence of points that improve in terms of their function value, converging towards the global optimum.
In doing so, mathematical considerations must be carefully balanced against memory requirements, computational intensity, and interpretability of the method. All this makes solving a general convex optimization problem a complex matter. However, if the objective function and constraints are linear, powerful algorithms exist. This also applies when quadratic terms and cone conditions arise. In these cases, thanks to the availability of open-source solvers, little difficult work is required, and the optimization problem can be solved according to automated rules [3, pp. 155–210].
Outlook
On the subordinate pages, you will find information on convexity, duality theory, and the modeling of uncertainty. Some basic aspects of the numerical solution of convex problems are described.
Sources
[1] Meyer, W. J. (2012). Concepts of Mathematical Modeling. New York: Courier Corporation.
[2] Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge: Cambridge University Press.
[3] Liberti, L., & Maculan, N. (2006). Global Optimization: From Theory to Implementation. Berlin Heidelberg: Springer Science & Business Media.
