Theory of constrained optimization - Mines Nancy

In this chapter, we will introduce tools to characterize (and sometimes, solve) general constrained optimization problems of the form

\begin{array}{lll} \text{minimize} & f_0(x) & \\ \text{subject to} & f_i(x) \leq 0 & i = 1, \ldots, m\\ & h_i(x) = 0 & i = 1, \ldots, p \end{array}

(1)

This problem is not necessarily convex. However, as we will see, certain tools rely on the assuming that (1) is a convex problem. This will be clearly stated in the text.

Recall from Chapter 1 some important notions. The constraint set of (1) is given by

\Omega = \left\lbrace x \in \mathbb{R}^n \mid f_i(x) \leq 0, \: i = 1, \ldots, m, \quad h_i(x) = 0, \: i = 1, \ldots,p\right\rbrace

(2)

whereas its domain is

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

(3)

The feasible set is then

\mathcal{F} = \mathcal{D} \cap \Omega = \{ x \in \mathcal{D} \mid f_i(x) \leq 0, i=1, \ldots, m,\; h_j(x) = 0, j=1, \ldots, p \}.

(4)

Recall that the optimal value of the problem (1) is given by

p^\star = \inf_{x \in \mathcal{F}} f_0(x)

(5)

and $p^\star = + \infty$ whenever the problem is unfeasible, i.e., $\mathcal{F} = \emptyset$ . See also this page in Chapter 1 for a review of the vocabulary.

For convex problems, the constraint set $\Omega$ is defined by

\Omega = \left\lbrace x \in \mathbb{R}^n \mid f_i(x) \leq 0, \: i = 1, \ldots, m, \quad a_i^\top x = b_i, \: i = 1, \ldots,p\right\rbrace

(6)

where

the inequality constraints are such that the functions $f_i$ , $i=1, \ldots, m$ are convex functions
the equality constraints $h_i(x) = a_i^\top x - b_i$ are affine functions.

References¶

Boyd, S. P., & Vandenberghe, L. (2004). Convex optimization. Cambridge University Press.

7 Theory of constrained optimization