Standard forms

Functional form
Epigraph form
Other standard forms

Functional form

An optimization problem is a problem of the form

$p^ast := displaystylemin_x : f_0(x) mbox{ subject to } f_i(x) le 0, ;; i=1,ldots, m ,$

where

$x in mbox{bf R}^n$ is the decision variable;
$f_0 : mbox{bf R}^n rightarrow mbox{bf R}$ is the objective function, or cost;
$f_i : mbox{bf R}^n rightarrow mbox{bf R}$ , represent the constraints;
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 :

$p^ast = displaystylemin_{x,t} : t mbox{ subject to } f_0(x)-tle 0, ;; f_i(x) le 0, ;; i=1,ldots, m .$

At optimum, t=p^ast . In the above, the objective function is $tilde{f} : mathbf{R}^{n+1} rightarrow mathbf{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 mathbf{R} . The problem amounts to finding the smallest 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 of $mathbf{R}^n$ . The corresponding notation is

$displaystylemin_{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

$displaystylemax_{x in mathbf{X}} : f_0(x) = -displaystylemin_{x in {cal X}} : g_0(x),$

where g_0 := -f_0 .