Nomenclature

Alicia Y. Tsai; Authors: Laurent EI Ghaoui; Contributors: Phan Hoang, Tony Tin, Ha To Tam, Nguyen Van Kep, Le Dinh Nam, Juliette Decugis, Nguyen Quoc Cuong.; Giuseppe C. Calafiore

Nomenclature

Consider the optimization problem

$(P) \quad \min_x f_0(x): f_i(x) \leq 0, \quad i=1, \ldots, m.$

Feasible set

The feasible set of problem $(P)$ is defined as

$\mathbf{X}:=\left\{x \in \mathbb{R}^n: f_i(x) \leq 0, \quad i=1, \ldots, m\right\} .$

A point $x$ is said to be feasible for problem $(P)$ if it belongs to the feasible set $X$ , that is, it satisfies the constraints.

Example: In the toy optimization problem, the feasible set is the ‘‘box’’ in $\mathbb{R}^2$ , described by $-1 \leq x_1 \leq 2,0 \leq x_2 \leq 3$ .

The feasible set may be empty if the constraints cannot be satisfied simultaneously. In this case, the problem is said to be infeasible.

What is a solution?

In an optimization problem, we are usually interested in computing the optimal value of the objective function, and also often a minimizer, which is a vector that achieves that value, if any.

Feasibility problems

Sometimes an objective function is not provided. This means that we are just interested in finding a feasible point or determining that the problem is infeasible. By convention, we set $f_0$ to be a constant in that case, to reflect the fact that we are indifferent to the choice of a point $x$ as long as it is feasible.

Optimal value

The optimal value of the problem is the value of the objective at optimum, and we denote it by $p^*$ :

$p^*:=\min_x f_0(x): f_i(x) \leq 0, \quad i=1, \ldots, m .$

Example: In the toy optimization problem, the optimal value is $p^*=-10.2667$ .

Optimal set

The optimal set (or the set of solutions) of the problem $(P)$ is defined as the set of feasible points for which the objective function achieves the optimal value:

$\mathbf{X}^{\text{opt}}:=\left\{x \in \mathbb{R}^n: f_0(x)=p^*, \quad f_i(x) \leq 0, \quad i=1, \ldots, m\right\} .$

We take the convention that the optimal set is empty if the problem is not feasible.

A standard notation for the optimal set is via the $\arg\min$ notation:

$\mathbf{X}^{\text{opt}}=\arg\min_{x \in \mathbf{X}} f_0(x) .$

A point $x$ is said to be optimal if it belongs to the optimal set. Optimal points may not exist, and the optimal set may be empty. This can be due to the fact that the problem is infeasible. Or it may be due to the fact that the optimal value is only attained in the limit.

Example: The problem

$\min_x e^{-x}$

has no optimal points, as the optimal value $p^*=0$ is only attained in the limit $x \rightarrow +\infty$ .

If the optimal set is not empty, we say that the problem is attained.

Suboptimality

The $\epsilon-$ suboptimal set is defined as

$\mathbf{X}_e:=\left\{x \in \mathbb{R}^n: f_i(x) \leq 0, \quad i=1, \ldots, m, \quad f_0(x) \leq p^*+c\right\} .$

(With our notation, $\mathbf{X}_0=\mathbf{X}_{\text {opt }}$ .) Any point in the $\epsilon-$ suboptimal set is termed $\epsilon-$ suboptimal.

This set allows characterizing points that are close to being optimal (when $\epsilon$ is small). Usually, practical algorithms are only able to compute suboptimal solutions, and never reach true optimality.

Example: Nomenclature of the two-dimensional toy problem.

Local vs. global optimal points

A point $z$ is locally optimal if there is a value $R>0$ such that is optimal for the problem

$\min_x f_0(x): f_i(x) \leq 0, \quad i=1, \ldots, m, \quad \| z-x\|_2 \leq R$

In other words, a local minimizer $x$ minimizes $f_0$ , but only for nearby points on the feasible set. Then the value of the objective function is not necessarily the optimal value of the problem.

The term globally optimal (or, optimal for short) is used to distinguish points in the optimal set from local minima.

Example: a function with local minima.

Many optimization algorithms may get trapped in local minima; a situation often described as a major challenge in optimization problems.

License

Icon for the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License