[latexpage]
Functional form
An optimization problem is a problem of the form
$$ p^* := \displaystyle\min_x : f_0(x) \mbox{ subject to } f_i(x) \le 0, \;\; i=1,\ldots, m , $$
where
- $x \in {\mathbb{R}}^n$ is the decision variable;
- $f_0 : {\mathbb{R}}^n \rightarrow {\mathbb{R}}$ is the objective function, or cost;
- $f_i : {\mathbb{R}}^n \rightarrow {\mathbb{R}}, i=1,\ldots,m$ represent the constraints;
- $p^*$ is the optimal value.
In the above, the term ‘‘subject to’’ is sometimes replaced with the shorthand colon notation.
Often the above is referred to as a ‘‘mathematical program’’. The term “programming” (or “program”) does not refer to a computer code. It is used mainly for historical purposes. We will use the more rigorous (but less popular) term “optimization problem”.
Example: An optimization problem in two variables.
Epigraph form
In optimization, we can always assume that the objective is a linear function of the variables. This can be done via the epigraph representation of the problem, which is based on adding a new scalar variable $t$:
$$ p^* = \displaystyle\min_{x,t} : t \mbox{ subject to } f_0(x)-t\le 0, \;\; f_i(x) \le 0, \;\; i=1,\ldots, m . $$
At optimum, $t=p^*$. In the above, the objective function is $\tilde{f} : \mathbb{R}^{n+1} \rightarrow \mathbb{R}$, with values $\tilde{f}_0 (x,t) = t$.
We can picture this as follows. Consider the sub-level sets of the objective function, which are of the form $\{ x : t \ge f_0(x) \}$ for some $t \in \mathbb{R}$. The problem amounts to finding the smallest $t$ for which the corresponding sub-level set intersects the set of points that satisfy the constraints.
Example: Geometric view of the optimization problem in two variables.
Other standard forms
Sometimes we single out equality constraints, if any:
$$\min_x : f_0(x) \mbox{ subject to } h_i(x) = 0, \;\; i=1,\ldots,p, \;\; f_i(x) \le 0, \;\; i=1,\ldots, m,$$
where $h_i$’s are given. Of course, we may reduce the above problem to the standard form above, representing each equality constraint by a pair of inequalities.
Sometimes, the constraints are described abstractly via a set condition, of the form $x \in \mathbf{X}$ for some subset $\mathbf{X}$ of $\mathbb{R}^n$. The corresponding notation is
$$\displaystyle\min_{x \in \mathbf{X}} : f_0(x)$$
Some problems come in the form of maximization problems. Such problems are readily cast in standard form via the expression
$$\displaystyle\max_{x \in \mathbf{X}} : f_0(x) = -\displaystyle\min_{x \in {\cal X}} : g_0(x),$$
where $g_0 := -f_0$.
