Standard forms

L. El Ghaoui

Standard forms

Functional form
Epigraph form
Other standard forms

Functional form
An optimization problem is a problem of the form

$p^*:=\min _x f_0(x) \text { subject to } f_i(x) \leq 0, \quad i=1, \ldots, m,$

where
– $x \in \mathbf{R}^n$ is the decision variable;
– $f_0: \mathbf{R}^n \rightarrow \mathbf{R}$ is the objective function, or cost
– $f_i: \mathbf{R}^n \rightarrow \mathbf{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.
Example: An optimization problem in two variables.
Epigraph form

$p^*=\min _{x, t} t \text { subject to } f_0(x)-t \leq 0, \quad f_i(x) \leq 0, \quad i=1, \ldots, m .$

At optimum, $t=p^*$ . In the above, the objective function is $\tilde{f}: \mathbf{R}^{n+1} \rightarrow \mathbf{R}$ , with values $\tilde{f}_0(x, t)=t$ . 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) \text { subject to } h_i(x)=0, \quad i=1, \ldots, p, \quad f_i(x) \leq 0, \quad 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 $\mathbf{R}^n$ . The corresponding notation is

$\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

$\begin{aligned} & \max _{x \in \mathbf{X}} f_0(x)=-\min _{x \in \mathcal{X}} g_0(x), \\ & \text { where } g_0:=-f_0 \end{aligned}$

Standard forms

License

Share This Book