一、优化问题及标准形式

1. 概念

我们称

为优化问题。

优化变量：$x \in \mathbb{R}^n$

目标函数（费用函数）：$f_0:\mathbb{R}^n \rightarrow \mathbb{R}$

不等式约束：$f_i(x) \leq 0$，不等式约束函数：$f_i : \mathbb{R}^n \rightarrow \mathbb{R}$

等式约束：$h_i(x) = 0$，等式约束函数：$h_i:\mathbb{R}^n \rightarrow \mathbb{R}$

如果没有约束，即$m = p = 0$，则称该问题为无约束问题。

定义域：$\mathcal{D} = \bigcap_{i = 1}^m \text{dom}f_i \cap \bigcap_{i = 1}^p \text{dom} h_i$

当点$x \in \mathcal{D}$满足所有约束时，$x$是可行的，当问题至少有一个可行点时，我们称问题是可行的，否则为不可行。所有可行点的集合称为可行集或约束集。

优化问题的最优值$p^*$定义为

如果问题不可行，我们有$p^* = \infty$（空集的下确界为$\infty$）。如果存在可行解$x_k$满足：当$k \rightarrow \infty$时，$f_0(x_k) \rightarrow -\infty$，那么$p^* = -\infty$，并且我们称问题无下界。

2. 最优点与局部最优点

如果$x^*$是可行的并且$f_0(x^*) = p^*$，那么我们称$x^*$为最优点，所有最优点的集合称为最优集，记为：

如果问题存在最优解，我们称最优值是可得的或可达的，称问题可解。

满足$f_0(x)\leq p^* + \epsilon$（其中$\epsilon > 0$）的可行解$x$称为$\epsilon -$次优。所有$\epsilon-$次优解的集合称为优化问题的$\epsilon-$次优集

我们称可行解$x$为局部最优，如果存在$R > 0$使得

或换而言之，$x$是关于$z$的优化问题

的解。

这部分可以理解为，确定好一个$x$，如果存在$R > 0$，使得对于满足$\|z - x \| \leq R$且$z \in \mathcal{D}$的$z$而言，我们恒有$f_0(x) \leq f_0(z)$，则称$x$为局部最优。或者说，$x$是区间$[x - R, x + R]$上的最优解。

如果$x$可行且$f_i(x) = 0$，我们称约束$f_i(x) \leq 0$的第$i$个不等式在$x$处起作用。如果$f_i(x) < 0$，则约束$f_i(x) \leq 0$不起作用。

如果某个约束去掉后不改变可行集，我们称它是冗余的。

例子：

1. $f_0(x) = \frac{1}{x}, \text{dom} f_0 = \mathbb{R}_{++}: p^* = 0$，但是不可达
2. $f_0(x) = -\log x, \text{dom} f_0 = \mathbb{R}_{++}: p^* = -\infty$，问题无下界
3. $f_0(x) = x \log x, \text{dom} f_0 = \mathbb{R}_{++}: p^* = -\frac{1}{e}$，在$x = \frac{1}{e}$处取到
4. $f_0(x) = x^3 - 3x:$在$x = 1$时取到局部最小值，$p^* = -\infty$，无下界

3. 可行性问题

如果目标函数恒为零，那么其最优值要么是零（如果可行集非空），要么是$\infty$（如果可行集是空集）。我们称其为可行性问题，写作：

因此可行性问题可以用来判断约束是否一致。

4. 极大化问题

极大化问题

可以通过在同样的约束下极小化$-f_0$求解。

其中关于极大化问题的最优值定义为：

并且可行解$x$是$\epsilon-$次优的，如果$f_0(x) \geq p^* - \epsilon$。当考虑极大化问题时，目标函数有时又称效用或满意度。

二、等价问题

如果从一个问题的解，很容易得到另一个问题的解，并且反之亦然，我们称两个问题是等价的。以下是常见的等价变换：

1. 变量变换

设$\phi: \mathbb{R}^n \rightarrow \mathbb{R}^n$是一一映射，其象包含了问题的定义域$\mathcal{D}$，即$\phi(\text{dom} \phi) \supe \mathcal{D}$。我们定义函数$\tilde{f_i}$和$\tilde{h_i}$为

下面考虑关于$z$的问题

我们称该问题与$x$的优化问题通过变量变换或变量代换$x = \phi(z)$所联系。

如果$x$解决了优化问题，那么$z = \phi^{-1}(x)$也求解了$z$的优化问题；如果$z$解决了优化问题，那么$x = \phi(z)$也解决了$x$的优化问题。

注意：$\phi$需要是一个一一映射的函数，这个确保了它的反函数存在。

2. 目标函数和约束函数变换

设$\psi_0 : \mathbb{R} \rightarrow \mathbb{R}$单增；$\psi_1, \cdots, \psi_m : \mathbb{R} \rightarrow \mathbb{R}$满足：当且仅当$u \leq 0$时，$\psi_i(u) \leq 0$；$\psi_{m + 1}, \cdots, \psi_{m + p}: \mathbb{R} \rightarrow \mathbb{R}$满足：当且仅当$u = 0$时，$\psi_{i}(u) = 0$。我们定义函数$\tilde{f_i}$和$\tilde{h_i}$为复合函数

显然问题

与标准形式问题等价；事实上，其可行集相同，最优解也相同。

$\psi$的定义时给出的条件本质上就是保证了

$$f_i(x) \leq 0 \Leftrightarrow \psi(f_i(x)) \leq 0 \quad h_i(x) = 0 \Leftrightarrow \psi(h_i(x)) = 0$$

3. 松弛变量

对于$f_i(x) \leq 0$等价存在一个$s_i \geq 0$满足$f_i(x) + s_i = 0$。利用这个变换，我们可以得到问题

新的变量$s_i$称为对应原不等式约束$f_i(x) \leq 0$的松弛变量。通过引入松弛变量，可以将每个不等式约束替换为一个等式和一个非负约束。

事实上，如果$(x, s)$对该问题是可行的，那么$x$是原问题的可行解，因为$s_i = -f(x) \geq 0$。反之，如果$x$是原问题的可行解，那么$(x, s)$是该问题的可行解，其中我们取$s_i = -f_i(x)$。类似地，$x$是原问题的最优解，当且仅当$(x, s)$是该问题的最优解，其中$s_i = -f_i(x)$。

对于这个变换，只要取$s_i = -f_i(x)$，本问题就能转化为$x$的优化问题

4. 消除等式约束

如果我们可以用一些参数$z \in \mathbb{R}^k$来显式地参数化等式约束

的解，那么我们可以从原问题中消除等式约束，如下所示。设函数$\phi: \mathbb{R}^k \rightarrow \mathbb{R}^n$是这样的函数：$x$满足式（8）等价于存在一些$z \in \mathbb{R}^k$使得$x = \phi(z)$。那么优化问题

与原问题等价。如果$z$是转换问题的最优解，那么$x = \phi(z)$是原问题的最优解。反之，如果$x$是原问题的最优解，那么存在至少一个$z$使得$x = \phi(z)$。任意这样的$z$均是转换后的问题的最优解。

对于$\phi(z)$的进一步理解：

通过等式约束$h_i(x) = 0$定义了一个可行流形：$\mathcal{M} = \{x \in \mathbb{R}^n | h(x) = 0 \}$。我们要去找一个满射的映射$\phi: \mathbb{R}^k \rightarrow \mathcal{M}$，使得对任意满足$h_i(x) = 0$的$x$，存在某个$z$满足$x = \phi(z)$。相当于一次性描述所有等式约束共同成立时$x$的参数化形式。

也有：

$$\{\phi(z) | z \in \mathbb{R}^k \} \supe \{x | h_i(x) = 0, i = 1, \dots, p \}.$$

5. 消除线性等式约束

6. 引入等式约束

我们考虑一个新的问题：

那么显然，该问题是与下列问题等价的

可以留意到，这里的目标函数和等式约束是独立的，包含着不同的优化变量。

7. 优化部分变量

我们总有

其中$\tilde{f}(x) = \inf_y f(x, y)$。换言之，我们总可以通过先优化一部分变量再优化另一部分变量来达到优化一个函数的目的。

我们考虑一个新的问题：

其约束相互独立，也就是说每个约束函数只与$x_1$或$x_2$相关。我们首先优化$x_2$，定义

则原问题等价于

证明：$\inf_{x, y}f(x, y) = \inf_x \inf_y f(x, y)$

由于$\inf_{x, y}f(x, y)$是在$x, y$上的最小，因此有

$$\inf_{x, y}f(x, y) \leq \inf_x \inf_y f(x, y)$$

由于$f(x, y)$连续，因此对于$\epsilon > 0$，$\exists f(x_0, y_0) \leq \inf_{x, y} f(x, y) + \epsilon$ .

因为$\inf_y f(x_0, y) \leq f(x_0, y_0)$，且$\inf_x \inf_y f(x, y) \leq inf_y f(x_0, y_0)$。

因此有：

$$\inf_x \inf_y f(x, y) \leq \inf_{x, y} f(x, y) + \epsilon$$

因此$\epsilon$是任意的，故$\inf_x \inf_y f(x, y) \leq \inf_{x, y} f(x, y)$.

8. 上镜图问题形式

标准问题的上镜图形式为：

其优化变量为$x \in \mathbb{R}^n$及$t \in \mathbb{R}$。容易看出这个问题与原问题是等价的：$(x ,t)$是问题的最优解当且仅当$x$是原优化问题的最优解，且$t = f_0(x)$。