Optimization Problems (numerical methods)¶
Definition¶
An optimization problem can be mathematically expressed as a problem for which an input determines an output of extreme value (minimum or maximum) on a given domain.
More formally, given a function \(f: \mathbb{R}^{n} \to \mathbb{R}\), and a set \(S \subseteq \mathbb{R}^{n}\), we see an \(\mathbf{x}^{*} \in S\) such that
\(\mathbf{x}^{*}\) is called the minimizer, since it's the argument that produces an output that is the global minima.
- Note that a maximum of \(f\) is the minimum of \(-f\), so we only need to consider minimization.
The objective function \(f\) may be linear or non-linear, but is usually assumed to be differentiable.
The set \(S\) is defined by a set of equations and inequalities and any point \(\mathbf{x} \in S\) - ie. points that satisfy the given constrants - is called a feasible point, and \(S\) is the feasible set.
A general continuous optimization problem has the form
where \(f:\mathbb{R}^{n} \to \mathbb{R}\), \(\mathbf{g} : \mathbb{R}^{n} \to \mathbb{R}^{m}\), \(\mathbf{h}:\mathbb{R}^{n} \to \mathbb{R}^{p}\).
\(\mathbf{g}\) are vector functions that represent equality constraints, whilst \(\mathbf{h}\) are vector functions that represent inequality constraints. Both of these types of constraints are required to properly model an optimization problem, and both constraints are unique in their own way.
If all of \(f, \mathbf{g}, \mathbf{h}\) are linear, then this is a linear problem. If either one of the functions are non-linear, then it becomes a non-linear problem.
We need to note that finding global minima is generally very difficult, and we use local methods like derivatives and taylor expansions to find local minima, which are significantly easier to find.
{ width="400" }
Optimization Methods¶
Optimization in One Dimension (numerical methods)