1.3Continuous optimization problems: general form

As explained before, this course focuses exclusively on continuous optimization problems, where the variables belong to continuous spaces (e.g., $\mathbb{X} = \mathbb{R}^n$), and where tools from calculus and convex analysis are applicable. Throughout, we adopt the presentation and terminology of Boyd & Vandenberghe (2004), which is widespread in the optimization literature.

A general continuous optimization problem can be formulated as

This notation describes the problem of finding a vector $x$ that minimizes the objective function $f_0(x)$ among those satisfying $f_i(x) \leq 0$, $i=1, \ldots,$ and $h_i(x) = 0$, $i=1, \ldots, p$.

Terminology: objective, constraints, domain and feasible set¶

• $x \in \mathbb{R}^n$: the decision variable, or vector of optimization parameters.

• $f_0: \mathbb{R}^n \to \mathbb{R}$: the objective function, which assigns a scalar cost to each possible choice of $x$.

• $f_i(x) \leq 0, i=1, \ldots, m$: the inequality constraints, where each $f_i: \mathbb{R}^n \to \mathbb{R}$ is a function that restricts the feasible region to one side of a surface in $\mathbb{R}^n$.

• $h_i(x) = 0, i=1, \ldots, p$: the equality constraints, where each $h_i: \mathbb{R}^n \to \mathbb{R}$ enforces a strict condition that must be satisfied exactly.

• the domain $\mathcal{D}$ of the optimization problem (1) corresponds to the set of points in $\mathbb{R}^n$ for which the functions (objectives or constraints) are well defined. For instance, Formally, it is the intersection of the domains of all functions involved, i.e.,

  $$\mathcal{D} = \bigcap_{i=0}^m \dom f_i \;\cap\; \bigcap_{j=1}^p \text{dom}\, h_j$$

  (2)

  For instance, for a function $x \mapsto f(x)=\log(x)$, the domain is $\dom f = \mathbb{R}_{+}^*$.

• The set of all $x \in \mathcal{D}$ that satisfy the constraints is called the feasible set:

if $\Omega = \emptyset$, there are no feasible point and we say the problem is infeasible. Otherwise, if there is at least one feasbile point, the problem is said to be feasible.

Optimal value and optimal points¶

An optimization problem seeks to find the optimal value of the objective function over the feasible set. Formally, the optimal value $p^\star$ is defined as:

where $\Omega$ is the feasible set defined in (3). Depending on the problem, three situations may arise:

• if the problem is infeasible (i.e., $\Omega = \emptyset$) we set by convention $p^\star = +\infty$.
• if there exists a sequence of feasible points $x_k$ such that $f_0(x_k) \to -\infty$ as $k\to + \infty$, then $p^\star = -\infty$ and we say the problem is unbounded below.
• if $p^\star$ is finite, then we have to distinguish between two situations:
  • there exists a feasible $x^\star$ such that $f(x^\star) = p^\star$. In this case, we say $x^\star$ is optimal and the optimal value is attained. We also say the problem (1) has a solution $x^\star$ with optimal value $p^\star$. Note that they might be more than one $x^\star$ that attains the optimal value!
  • the optimal value $p^\star$ is never attained, i.e., there is no $x^\star$ such solves the problem.

In the next section, we will see the notion of global and local optima.

About notations and terminology¶

Many names are used in the literature to refer to the field of optimization, including:

• mathematical programming
• mathematical optimization
• numerical optimization

All these terms refer to the study of optimization problems and are used interchangeably.

How to write an optimization problem?¶

In the literature, you will encounter several equivalent notations for expressing the same optimization problem. In this lecture, we adopt the notation of Boyd & Vandenberghe (2004), which uses the minimize and subject to keywords, for example:

In more mathematical or theoretical contexts, the same problem is often written as:

Some classical textbooks (e.g., Nocedal & Wright, 2006) use the more compact notation:

which is widely accepted, even though technically the minimum may not exist (e.g., if the problem is unbounded below).

To emphasize interest in actual solutions of the optimization problem, one often writes:

a notation frequently encountered in fields like signal processing.