- 开设于本科三年级上学期，作为全方向的选修课程。
- 使用课本：
- 填空题10分（每小题2分，5个小题）
- 判断题10分（每小题2分，5个小题）
- 计算题7到8个题（教材中例题，写过的练习题等）
-
第一章 最优化简介
- 最优化问题的一般形式
3页 - 全局和局部最优解
16页 - 优化算法常用的收敛准则，收敛速度
17—20页
- 最优化问题的一般形式
-
第二章 基础知识
- 梯度海瑟矩阵
28-29页 - 凸集仿射集
36页 - 半正定矩阵
39页 - 凸函数：
42页- 例题 2.5
45页
- 例题 2.5
- 次梯度次微分：
51页- 例题 2.10 — 2.12
55页
- 例题 2.10 — 2.12
- 梯度海瑟矩阵
-
第三章 典型优化问题
- 线性规划：
62-63页- 习题 3.1 3.2
78页
- 习题 3.1 3.2
- 半定规划：
70—72页- 习题 3.9 79页
- 线性规划：
-
第四章最优性理论
- 下降方向：
85页- 线性化可行方向
- LICQ
- Slater条件等
- 无约束可微问题的一阶必要条件，二阶最优性条件：
85—87页- 例题
87页 - 习题 4.5
115页
- 例题
- 无约束不可微问题的最优性理论：
89——91页 - 对偶理论 例题
96-100页- 习题 4.7
115页 - 习题 4.13
116页
- 习题 4.7
- 一般约束优化问题的最优性理论：
- 例题
107页 - 习题 4.10
116页
- 例题
- 凸优化问题最优性理论：
- 例题
111页 - 习题 4.11(a)，4.6(b)
116页
- 例题
- 下降方向：
-
第五章 无约束优化算法
- 线搜索准则：
- Armijo 准则
121页 - Wolfe 准则
123页
- Armijo 准则
- 梯度法迭代计算
128页- 定理 5.2
- 习题 5.2
179页
- 步长：
- 精确线性搜索；
- BB 梯度法
- BB 梯度法的两种迭代格式推理
132页
- 牛顿类算法：
- 牛顿方程 牛顿方向 经典牛顿法迭代格式
141页
- 牛顿方程 牛顿方向 经典牛顿法迭代格式
- 牛顿法的具体迭代计算：
- 搜索方向 ：
- 步长：1（即经典牛顿法）
- 精确线性搜索
- 搜索方向 ：
- 拟牛顿类算法：
- 割线方程
148页 - 拟牛顿矩阵更新公式推理；
- SR1公式 5.5.9
150页 - BFGS公式推理5.5.12
151页
- SR1公式 5.5.9
- 割线方程
- 线搜索准则：
-
第六章约束优化算法
- 罚函数法：
- 二次罚函数法
- 对数罚函数法
- 等式约束优化问题
- 增广拉格朗日函数法
- 罚函数法：
- 最优化问题的一般形式
3页 - 全局和局部最优解
16页 - 优化算法常用的收敛准则，收敛速度
17—20页
最优化问题一般可以描述为: $$ \min \space f(x), \tag{1.1.1} \ s.t.\space x \in \chi $$ 其中:
-
$x=(x_{1}, x_{2}, \cdots, x_{n})^{T}\in \mathbb{R}^{n}$ 是决策变量. -
$f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ 是目标函数. -
$\chi \subseteq \mathbb{R}^{n}$ 是约束集合或可行域.- 可行域包含的点称为可行解或可行点.
- 记号
s.t.是 “subject to”的缩写，专指约束条件. - 当 $ \chi = R^{n} $ 时，问题（1.1.1）称为无约束优化问题.
- 集合
$\chi$ 通常可以由约束函数 $ c_{i}(x): \mathbb{R}^{n} \rightarrow \mathbb{R}, i=1, 2, \cdots, m+l$表达成如下形式： $ $ \begin{align} \chi = { x \in \mathbb{R}^{n} \mid c_{i}(x) & \leq 0, i = 1, 2, \cdots, m, \notag \ c_{i}(x) & = 0, i = m+1, m+2, \cdots, m+l }. \notag \end{align} $$ - 在所有满足上述约束条件的决策变量中，
- 使目标函数
$f(x)$ 取最小值的变量 $x^$ 称为优化问题（1.1.1）的最优解，即对于任意 $x \in X$ 都有 $f(x) \geq f(x^)$. - 如果我们求解在约束集合
$X$ 上目标函数$f(x)$ 的最大值，则问题（1.1.1）中的 “ $ \min $ ” 应相应地替换为 “ $ \max $ ” .
- 使目标函数
- 注意到在集合
$X$ 上，函数$f$ 的最小（最大）值不一定存在，但是其下（上）确界 “$\inf f(\sup f)$ ” 总是存在的.- 当目标函数的最小（最大）值不存在时，我们便关心其下（上）确界，即将问题（1.1.1）中的 “ $ \min (\max) $ ” 改为 “ $ \inf (\sup) $ ” .
- 为了叙述简便，问题（1.1.1）中的
$x$ 为$\mathbb{R}^n$ 空间中的向量. - 实际上，根据具体应用和需求，$x$ 还可以是矩阵、多维数组或张量等，本书介绍的很多理论和算法可以相应推广.
在求解最优化问题之前，先介绍最小化问题(1.1.1)的最优解的定义．
定义1.1（最优解）对于可行点
- 如果
$f(\bar{x}) \le f(x), \forall x \in X$ ，那么称$\bar{x}$ 为问题（1.1.1）的 全局极小解（点），有时也称为（全局）最优解或最小值点； - 如果存在
$\bar{x}$ 的一个$\varepsilon$ 邻域$N_{\varepsilon}(\bar{x})$ 使得$f(\bar{x}) \le f(x), \forall x \in N_{\varepsilon}(\bar{x}) \cap X$ ，那么称$\bar{x}$ 为问题（1.1.1）的 局部极小解（点），有时也称为局部最优解； - 进一步地，如果有
$f(\bar{x}) < f(x), \forall x \in N_{\varepsilon}(\bar{x}) \cap X, x \neq \bar{x}$ 成立，则称$\bar{x}$ 为问题（1.1.1）的 严格局部极小解（点）。 - 如果一个点是局部极小解，但不是严格局部极小解，我们称之为非严格局部极小解（点）．
-
迭代算法产生原因
- 在给定优化问题之后，我们要考虑如何求解．根据优化问题的不同形式，其求解的困难程度可能会有很大差别．
- 对于一个优化问题，如果我们能用代数表达式给出其最优解，那么这个解称为显式解，对应的问题往往比较简单．
- 例如二次函数在有界区间上的极小化问题，我们可以通过比较其在对称轴上和区间两个端点处的值得到最优解，这个解可以显式地写出．
- 但实际问题往往是没有办法显式求解的，因此常采用迭代算法．
-
迭代算法的基本思想
- 从一个初始点
$x^0$ 出发，按照某种给定的规则进行迭代，得到一个序列${x^k}$ ： - 如果迭代在有限步内终止，那么希望最后一个点就是优化问题的解.
- 如果迭代点列是无穷集合，那么希望该序列的极限点（或者聚点）则为优化问题的解．
- 从一个初始点
-
收敛准则
- 为了使算法能在有限步内终止，我们一般会通过一些收敛准则来保证迭代停在问题的一定精度逼近解上．
- 对于无约束优化问题，常用的收敛准则有
$$
\frac{f(x^{k}) - f^}{\max { |f^|, 1 }} \leq \varepsilon_{1},
\quad ||
\nabla f(x^{k})|| \leq \varepsilon_{2} \tag{1.4.1}
$$
- 其中
$\varepsilon _{1}, \varepsilon _{2}$ 为给定的很小的正数. -
$||\cdot ||$ 表示某种范数- 这里可以简单理解为
$l_{2}$ 范数：$\displaystyle||x||_{2}=(\sum {i=1}^{n}x{i}^{2})^{1/2}$，第二章将会给出范数的一般定义）.
- 这里可以简单理解为
-
$f^*$ 为函数$f$ 的最小值（假设已知或者以某种方式估计得到）. -
$\nabla f(x^{k})$ 表示函数$f$ 在点$x$ 处的梯度（光滑函数在局部最优点处梯度为零向量，第四章中会给出更多介绍）.
- 其中
- 对于约束优化问题，还需要考虑约束违反度。具体地，要求最后得到的点满足
$$
\begin{align}
c_{i}(x^{k}) & \le \varepsilon {3}, i=1, 2, \cdots, m, \notag \
| c{i}(x^{k})| & \le \varepsilon _{4}, i=m+1, m+2, \cdots, m+l, \notag
\end{align}
$$
- 其中
$\varepsilon _{3}, \varepsilon _{4}$ 为很小的正数，用来刻画$x^{k}$ 的可行性.
- 其中
-
解的最优性
- 除了约束违反度之外，我们也要考虑
$x^{k}$ 与最优解之间的距离.- 如 (1.4.1)式中给出的函数值与最优值的相对误差.
- 由于一般情况下事先并不知道最优解，在最优解唯一的情形下一般使用某种基准算法来得到
$x^*$ 的一个估计，之后计算其与$x^{k}$ 的距离以评价算法的性能. - 因为约束的存在，我们不能简单地用目标函数的梯度来判断最优性.
- 实际中采用的判别准则是点的最优性条件的违反度（关于约束优化的最优性条件，会在第四章中给出）.
- 除了约束违反度之外，我们也要考虑
-
停机准则
- 对于一个具体的算法，根据其设计的出发点，我们不一定能得到一个高精度的逼近解.
- 此时，为了避免无用的计算开销，我们还需要一些停机准则来及时停止算法的进行。常用的停机准则有： $$ \frac{||x^{k+1}-x^{k}||}{\max { ||x^{k}||, 1}}\le \varepsilon _{5}, \space \frac{|f(x^{k+1})-f(x^{k})|}{\max { |f(x^{k})|, 1}}\le \varepsilon _{6}, $$
- 这里的各个
$\varepsilon$ 一般互不相等. - 上面的准则分别表示相邻迭代点和其对应目标函数值的相对误差很小.
- 在算法设计中，这两个条件往往只能反映迭代点列接近收敛，但不能代表收敛到优化问题的最优解.
-
依点列收敛
- 在算法设计中，一个重要的标准是算法产生的点列是否收敛到优化问题的解．
- 对于问题(1.1.1)，其可能有很多局部极小解和全局极小解，但所有全局极小解对应的目标函数值，即优化问题的最小值
$f^*$ 是一样的． - 考虑无约束的情形，对于一个算法：
给定初始点$x^{0}$，记其迭代产生的点列为${x^{k}}$ ，如果${x^{k}}$ 在某种范数$||\cdot ||$ 的意义下满足： $$ \lim _{k\rightarrow \infty}||x^{k}-x^{}||=0 $$ 且收敛的点 $x^$ 为一个局部（全局）极小解，那么我们称该点列收敛到局部（全局）极小解， 相应的算法称为是依点列收敛到局部（全局）极小解的. - 对于带约束的情形：
给定初始点$x^{0}$ ，算法产生的点列${x^{k}}$ 不一定是可行的（即$x^{k}\in \chi$ 未必对任意$k$ 成立）.- 考虑到约束违反的情形，我们需要保证
${x^{k}}$ 在收敛到$x^*$ 的时候，其违反度是可接受的. - 除此要求之外，算法的收敛性的定义和无约束情形相同.
- 考虑到约束违反的情形，我们需要保证
-
依函数值收敛
- 在算法的收敛分析中，初始迭代点
$x^{0}$ 的选取也尤为重要。- 比如一般的牛顿法，只有在初始点足够接近局部（全局）最优解时，才能收敛。
- 但是这样的初始点的选取往往比较困难，此时我们更想要的是一个从任何初始点出发都能收敛的算法。
- 因此优化算法的研究包括如何设计全局化策略
- 将已有的可能发散的优化算法修改得到一个新的全局收敛到局部（全局）最优解的算法。
- 比如通过采用合适的全局化策略，我们可以修正一般的牛顿法使得修改后的算法是全局收敛到局部（全局）最优解的。
- 进一步地，如果从任意初始点
$x^{0}$ 出发，算法都是依点列收敛到局部（全局）极小解的，我们称该算法是全局依点列收敛到局部（全局）极小解的。- 相应地，如果记对应的函数值序列为
${f(x^{k})}$ ，我们还可以定义算法的 （全局）依函数值收敛到局部（全局）极小值 的概念。
- 相应地，如果记对应的函数值序列为
- 对于凸优化问题，因为其任何局部最优解都为全局最优解，算法的收敛性都是相对于其全局极小而言的。
- 除了点列和函数值的收敛外，实际中常用的还有每个迭代点的最优性条件（如无约束优化问题中的梯度范数，约束优化问题中的最优性条件违反度等等）的收敛。
- 在算法的收敛分析中，初始迭代点
-
收敛速度
-
Q-收敛速度
对于同一个优化问题，其求解算法可以有很多.
在设计和比较不同的算法时，另一个重要的指标是算法的渐进收敛速度.
我们以点列的 Q-收敛速度 （Q 的含义为 “quotient” ）为例:
（函数值的 Q-收敛速度 可以类似地定义）
设${x^{k}}$ 为算法产生的迭代点列且收敛于$x^*$ ，- 若对充分大的
$k$ 有 $$ \frac{||x^{k+1}-x^{}||}{||x^{k}-x^{}||}\le a, \space a\in (0, 1), $$ 则称算法（点列）是 Q-线性收敛的； - 若满足 $$ \lim _{k\rightarrow \infty}\frac{||x^{k+1}-x^{}||}{||x^{k}-x^{}||}=0, $$ 称算法（点列）是 Q-超线性收敛的；
- 若满足 $$ \lim _{k\rightarrow \infty}\frac{||x^{k+1}-x^{}||}{||x^{k}-x^{}||}=1, $$ 称算法（点列）是Q-次线性收敛的；
- 若对充分大的
$k$ 满足 $$ \frac{||x^{k+1}-x^{}||}{||x^{k}-x^{}||^{2}}\le a, \space a>0, $$ 则称算法（点列）是 Q-二次收敛 的. - 类似地，也可定义更一般的 Q-r 次收敛
$(r>1)$ .
- 若对充分大的
-
R-收敛速度
除 Q-收敛速度外，另一常用概念是 R-收敛速度（R 的含义为“root”）.
以点列为例：
设${x^{k}}$ 为算法产生的迭代点且收敛于$x^*$ ，- 若存在 Q-线性收敛 于 0 的非负序列
$t_{k}$ 并且对任意的$k$ 有 $$ ||x^{k}-x^{*}||\le t_{k} $$ 成立，则称算法（点列）是 R-线性收敛 的. - 类似地，可定义 R-超线性收敛 和 R-二次收敛 等收敛速度.
- 从 R-收敛速度的定义可以看出序列
${||x^{k}-x^{*}||}$ 被另一趋于 0 的序列${t_{k}}$ 控制. - 当知道
$t_{k}$ 的形式时，我们也称算法（点列）的收敛速度为$\mathcal{O}(t_{k})$ .
- 若存在 Q-线性收敛 于 0 的非负序列
-
-
复杂度
- 与收敛速度密切相关的概念是优化算法的 复杂度
$N(\varepsilon)$ - 即计算出给定精度
$\varepsilon$ 的解所需的迭代次数或浮点运算次数.
- 即计算出给定精度
- 在实际应用中，这两种定义复杂度的方式均很常见.
- 如果能较准确地估计每次迭代的运算量，则可以由算法所需迭代次数推出所需浮点运算次数.
- 我们用具体的例子来进一步解释算法复杂度：
设某一算法产生的迭代序列${x^{k}}$ 满足: $$ f(x^{k})-f(x^{*})\le \frac{c}{\sqrt{k}}, \space \forall k>0, $$- 其中
$c>0$ 为常数，$x^*$ 为全局极小点. - 如果需要计算算法满足精度
$f(x^{k})-f(x^*)\le \varepsilon$ 所需的迭代次数:- 只需令
$\frac{c}{\sqrt{k}}\le \varepsilon$ - 则得到
$k\ge \frac{c^{2}}{\varepsilon ^{2}}$ - 因此该优化算法对应的（迭代次数）复杂度为
$N(\varepsilon)=\mathcal{O}(\frac{1}{\varepsilon ^{2}})$ .
- 只需令
- 其中
- 注意：
- 渐进收敛速度更多的是考虑迭代次数充分大的情形.
- 而复杂度给出了算法迭代有限步之后产生的解与最优解之间的定量关系.
- 与收敛速度密切相关的概念是优化算法的 复杂度
- 梯度海瑟矩阵
28-29页 - 凸集仿射集
36页 - 半正定矩阵
39页 - 凸函数：
42页- 例题 2.5
45页
- 例题 2.5
- 次梯度次微分：
51页- 例题 2.10 — 2.12
55页
- 例题 2.10 — 2.12
-
向量范数
定义2.1（范数）称一个从向量空间
$\mathbb{R}^{n}$ 到实数域$\mathbb{R}$ 的非负函数$||\cdot ||$ 为 范数，如果它满足：- (1) 正定性：对于所有的
$v \in \mathbb{R}^{n}$ ，有$||v|| \ge 0$ ，且$||v|| = 0$ 当且仅当$v = 0$ ； - (2) 齐次性：对于所有的
$v \in \mathbb{R}^{n}$ 和$\alpha \in \mathbb{R}$ ，有$||\alpha v|| = |\alpha| \cdot ||v||$ ； - (3) 三角不等式：对于所有的
$v, w \in \mathbb{R}^{n}$ ，有$||v + w|| \le ||v|| + ||w||$ .
- (1) 正定性：对于所有的
-
最常用的向量范数为
$l_{p}$ 范数($p \ge 1$ ): $$ ||v||{p} = (|v{1}|^{p} + |v_{2}|^{p} + \cdots + |v_{n}|^{p})^{\frac{1}{p}}; $$- 当
$p = \infty$ 时，$l_{\infty}$ 范数定义为 $$ ||v||{\infty} = \max_i |v{i}|. $$ - 其中
$p=1, 2, \infty$ 的情形最重要，分别记为 $||\cdot ||{1}$, $||\cdot ||{2}$ 和$||\cdot ||_{\infty}$ . - 在不引起歧义的情况下，我们有时省略
$l_{2}$ 范数的角标，记为$||\cdot ||$ .
- 当
-
正定矩阵诱导范数
在最优化问题算法构造和分析中，也常常遇到由正定矩阵$A$ 诱导的范数， 即$||x||_{A}\xlongequal{{def}}\sqrt{x^{T}Ax}$ .- 根据正定矩阵的定义，很容易验证
$||\cdot ||_{A}$ 定义了一个范数.
- 根据正定矩阵的定义，很容易验证
-
柯西不等式
对向量的$l_{2}$ 范数，我们有常用的柯西（Cauchy）不等式：命题2.1（柯西不等式）设
$a, b \in \mathbb{R}^{n}$ ，则 $$ |a^{T}b|\le ||a||{2}||b||{2}, $$ 等号成立当且仅当$a$ 与$b$ 线性相关.
和向量范数类似，矩阵范数是定义在矩阵空间上的非负函数，并且满足正定性、齐次性和三角不等式。
-
矩阵范数
向量的$l_{p}$ 范数可以比较容易地推广到矩阵的$l_{p}$ 范数，本书常用$p=1,2$ 的情形。- 当
$p=1$ 时，矩阵$A \in \mathbb{R}^{m \times n}$ 的$l_{1}$ 范数定义为 $$ ||A||_{1} = \sum {i=1}^{m}\sum {j=1}^{n}|a{ij}|, $$ 即 $||A||{1}$ 为$A$ 中所有元素绝对值的和。 - 当
$p=2$ 时，此时得到的是矩阵的 Frobenius 范数（下称$F$ 范数），记为 $||A||{F}$。它可以看成是向量的 $l{2}$ 范数的推广，即所有元素平方和开根号： $$ ||A||_{F} = \sqrt{Tr(AA^{T})} = \sqrt{\sum {ij} a{ij}^{2}} (2.1.1) $$-
$Tr(X)$ 表示方阵$X$ 的迹。 - 矩阵的
$F$ 范数具有正交不变性: 即对于任意的正交矩阵$U \in \mathbb{R}^{m \times m}, V \in \mathbb{R}^{n \times n}$ ，我们有 $$ \begin{matrix} \begin{align} ||UAV||{F}^{2} &= Tr(UAVV^{T}A^{T}U^{T}) &= Tr(UAA^{T}U^{T}) \ &= Tr(AA^{T}U^{T}U) &= Tr(AA^{T}) = ||A||{F}^{2} \end{align} \end{matrix} $$ 其中第三个等号成立是因为$Tr(AB) = Tr(BA)$ 。
-
- 当
-
算子范数
- 给定矩阵
$A \in \mathbb{R}^{m \times n}$ ，以及$m$ 维和$n$ 维空间的向量范数 $||\cdot ||{(m)}$ 和 $||\cdot ||{(n)}$，其诱导的矩阵范数定义如下： $$ ||A||{(m, n)} = \max {x \in R^{n}, ||x||{(n)}=1} ||Ax||{(m)}, $$- 容易验证
$||\cdot ||_{(m, n)}$ 满足范数的定义。
- 容易验证
- 如果将 $||\cdot ||{(m)}$ 和 $||\cdot ||{(n)}$ 都取为相应向量空间的
$l_p$ 范数，我们可以得到矩阵的$p$ 范数。- 本书经常用到的是矩阵的 2 范数，即 $$ ||A||{2} = \max {x \in R^{n}, ||x||{2}=1} ||Ax||{2}. $$ 容易验证（见习题 2.1），矩阵的 2 范数是该矩阵的最大奇异值。
- 给定矩阵
-
算子范数的相容性
根据算子范数的定义，所有算子范数都满足如下性质： $$ ||Ax||{(m)} \le ||A||{(m, n)} ||x||_{(n)}. \tag{2.1.2} $$- 例如
当$m=n=2$ 时，$||Ax||{2} \le ||A||{2} ||x||_{2}$。 - 性质 (2.1.2) 又被称为矩阵范数的 相容性
即 $||\cdot ||{(m, n)}$ 与 $||\cdot ||{(m)}$ 和$||\cdot ||_{(n)}$ 是相容的。 - 并非所有矩阵范数都与给定的向量范数相容，在今后的应用中读者需要注意这一问题。
[!tip|label:注2-1] 和矩阵 2 范数类似，向量的
$l_1$ 范数以及$l_{\infty}$ 范数均可诱导出相应的矩阵范数（分别为矩阵的 1 范数和无穷范数）
在多数数值代数教材中将它们记为 $||\cdot ||{1}$ 和 $||\cdot ||{\infty}$。
然而本书较少涉及这两个范数，因此我们将$||A||_{1}$ 定义为矩阵$A$ 中所有元素绝对值的和。
读者应当注意它和其他数值代数教材中定义的不同。 - 例如
-
除了矩阵 2 范数以外，另一个常用的矩阵范数为 核范数。
- 给定矩阵
$A \in \mathbb{R}^{m \times n}$ ，其核范数定义为 $$ ||A||_{*} = \sum _{i=1}^{r} \sigma _{i}, $$-
$\sigma _{i}, i=1, 2, \cdots, r$ 为$A$ 的所有非零奇异值 $r = \text{rank}(A)$
-
- 类似于向量的
$l_1$ 范数的保稀疏性，我们也经常通过限制矩阵的核范数来保证矩阵的低秩性。 - 同时，根据范数的三角不等式（下文中的凸性），相应的优化问题可以有效求解。
- 给定矩阵
-
Frobenius 内积
- 对于矩阵空间
$\mathbb{R}^{n \times n}$ 的两个矩阵$A$ 和$B$ ，除了定义它们各自的范数以外，我们还可以定义它们之间的内积。 - 范数一般用来衡量矩阵的模的大小，而内积一般用来表征两个矩阵（或其张成的空间）之间的夹角。
- 这里，我们介绍一种常用的内积——Frobenius 内积。$m \times n$ 矩阵
$A$ 和$B$ 的 Frobenius 内积定义为 $$ \langle A, B \rangle = \text{Tr}(AB^T) = \sum_{i=1}^m \sum_{j=1}^n a_{ij} b_{ij}. $$ 易知其为两个矩阵逐分量相乘的和，因而满足内积的定义。 - 当
$A = B$ 时，$\langle A, B \rangle$ 等于矩阵$A$ 的$F$ 范数的平方。
- 对于矩阵空间
-
柯西不等式
和向量范数相似，我们也有矩阵范数对应的柯西不等式：命题 2.2（矩阵范数的柯西不等式）设
$A, B \in \mathbb{R}^{m \times n}$ ，则 $$ |\langle A, B \rangle| \le ||A||{F} ||B||{F}, $$ 等号成立当且仅当$A$ 和$B$ 线性相关。
-
梯度的定义
定义 2.2（梯度）给定函数
$f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ ，且$f$ 在点$x$ 的一个邻域内有意义，若存在向量$g \in \mathbb{R}^{n}$ 满足 $$ \lim _{p \to 0} \frac{f(x+p) - f(x) - g^{T} p}{||p||} = 0, \tag{2.2.1} $$- 其中
$||\cdot ||$ 是任意的向量范数 - 就称
$f$ 在点$x$ 处 可微（或 Fr'echet 可微）。- 此时
$g$ 称为$f$ 在点$x$ 处的 梯度，记作$\nabla f(x)$ 。
- 此时
- 如果对区域
$D$ 上的每一个点$x$ 都有$\nabla f(x)$ 存在，则称$f$ 在$D$ 上可微。
- 其中
-
梯度的算子记号
-
若
$f$ 在点$x$ 处的梯度存在，在 (2.2.1) 式中令$p = \varepsilon e_{i}$ ，$e_{i}$ 是第$i$ 个分量为 1 的单位向量，可知$\nabla f(x)$ 的第$i$ 个分量为$\frac{\partial f(x)}{\partial x_{i}}$ 。 -
即 $$ \nabla f(x) = \left[ \frac{\partial f(x)}{\partial x_{1}}, \frac{\partial f(x)}{\partial x_{2}}, \cdots, \frac{\partial f(x)}{\partial x_{n}} \right]^{T}. $$
-
如果只关心对一部分变量的梯度，可以通过对
$\nabla$ 加下标来表示。- 例如，
$\nabla _{x}f(x, y)$ 表示将$y$ 视为常数时$f$ 关于$x$ 的梯度。
- 例如，
-
-
海瑟矩阵的定义
- 对应于一元函数的二阶导数，对于多元函数我们可以定义其海瑟矩阵。
定义 2.3（海瑟矩阵）
如果函数$f(x): \mathbb{R}^{n} \rightarrow \mathbb{R}$ 在点$x$ 处的二阶偏导数$\frac{\partial ^2 f(x)}{\partial x_{i} \partial x_{j}}$ ，$i, j = 1, 2, \cdots, n$ 都存在，则 $$ \nabla ^2 f(x) = \begin{bmatrix} \frac{\partial ^2 f(x)}{\partial x_1^2} & \frac{\partial ^2 f(x)}{\partial x_1 \partial x_2} & \frac{\partial ^2 f(x)}{\partial x_1 \partial x_3} & \cdots & \frac{\partial ^2 f(x)}{\partial x_1 \partial x_n} \ \frac{\partial ^2 f(x)}{\partial x_2 \partial x_1} & \frac{\partial ^2 f(x)}{\partial x_2^2} & \frac{\partial ^2 f(x)}{\partial x_2 \partial x_3} & \cdots & \frac{\partial ^2 f(x)}{\partial x_2 \partial x_n} \ \vdots & \vdots & \vdots & \ddots & \vdots \ \frac{\partial ^2 f(x)}{\partial x_n \partial x_1} & \frac{\partial ^2 f(x)}{\partial x_n \partial x_2} & \frac{\partial ^2 f(x)}{\partial x_n \partial x_3} & \cdots & \frac{\partial ^2 f(x)}{\partial x_n^2} \end{bmatrix} $$ 称为$f$ 在点$x$ 处的海瑟矩阵。- 当
$\nabla ^{2} f(x)$ 在区域$D$ 上的每个点$x$ 处都存在时，称$f$ 在$D$ 上二阶可微。 - 若
$\nabla ^{2} f(x)$ 在$D$ 上还连续，则称$f$ 在$D$ 上二阶连续可微，可以证明此时海瑟矩阵是一个对称矩阵。
-
雅可比矩阵
当$f: \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$ 是向量值函数时，我们可以定义它的雅可比（Jacobi）矩阵$J(x) \in \mathbb{R}^{m \times n}$ ，它的第$i$ 行是分量$f_{i}(x)$ 梯度的转置，即 $$ J(x) = \begin{bmatrix} \frac{\partial f_{1}(x)}{\partial x_{1}} & \frac{\partial f_{1}(x)}{\partial x_{2}} & \cdots & \frac{\partial f_{1}(x)}{\partial x_{n}} \ \frac{\partial f_{2}(x)}{\partial x_{1}} & \frac{\partial f_{2}(x)}{\partial x_{2}} & \cdots & \frac{\partial f_{2}(x)}{\partial x_{n}} \ \vdots & \vdots & \ddots & \vdots \ \frac{\partial f_{m}(x)}{\partial x_{1}} & \frac{\partial f_{m}(x)}{\partial x_{2}} & \cdots & \frac{\partial f_{m}(x)}{\partial x_{n}} \end{bmatrix} $$ 此外容易看出，梯度$\nabla f(x)$ 的雅可比矩阵就是$f(x)$ 的海瑟矩阵。 -
泰勒展开
- 类似于一元函数的泰勒展开，
- 对于多元函数，我们不加证明地给出如下形式的泰勒展开：
定理2.1
设$f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ 是连续可微的，$p \in \mathbb{R}^{n}$ 为向量，那么 $$ f(x+p) = f(x) + \nabla f(x+tp)^T p, $$ 其中$0 < t < 1$ .- 进一步地，如果
$f$ 是二阶连续可微的，则 $$ \nabla f(x+p) = \nabla f(x) + \int_{0}^{1} $$
- 进一步地，如果
-
梯度利普希茨(Lipschitz) 连续的函数
-
定义2.4（梯度利普希茨连续）
给定可微函数$f$ ，若存在$L > 0$ ，对任意的$x, y \in \textbf{dom} f$ 有 $$ ||\nabla f(x) - \nabla f(y)|| \leq L ||x - y||,\tag{2.2.2} $$ 则称$f$ 是梯度利普希茨连续的- 相应利普希茨常数为
$L$ 。 - 有时也简记为梯度
$L$ -利普希茨连续或$L$ -光滑。
- 相应利普希茨常数为
- 梯度利普希茨连续表明
$\nabla f(x)$ 的变化可以被自变量$x$ 的变化所控制， 满足该性质的函数具有很多好的性质，一个重要的性质是其具有二次上界。
-
定义2.4（梯度利普希茨连续）
-
二次上界
-
引理2.1（二次上界）
设可微函数$f(x)$ 的定义域$\text{dom} f = \mathbb{R}^{n}$ ，且为梯度$L$ -利普希茨连续的，则函数$f(x)$ 有二次上界： $$ f(y) \leq f(x) + \nabla f(x)^T(y - x) + \frac{L}{2} ||y - x||^2, \quad \forall x, y \in \text{dom} f. \tag{2.2.3} $$ - 引理 2.1 实际上指的是
$f(x)$ 可被一个二次函数上界所控制- 即要求
$f(x)$ 的增长速度不超过二次。 - 实际上，该引理对
$f(x)$ 定义域的要求可减弱为$\text{dom} f$ 是凸集（见定义 2.13）- 此条件的作用是保证证明中的
$g(t)$ 当$t \in [0, 1]$ 时是有定义的。
- 此条件的作用是保证证明中的
- 即要求
- 若
$f$ 是梯度利普希茨连续的，且有一个全局极小点 $x^$，一个重要的推论就是我们能够利用二次上界 (2.2.3) 来估计 $f(x) - f(x^)$ 的大小，其中$x$ 可以是定义域中的任意一点。 -
推论 2.1
设可微函数$f(x)$ 的定义域为$\mathbb{R}^{n}$ 且存在一个全局极小点 $x^$， 若 $f(x)$ 为梯度 $L$-利普希茨连续的，则对任意的 $x$ 有 $$ \frac{1}{2L} ||\nabla f(x)||^2 \leq f(x) - f(x^). \tag{2.2.5} $$
-
引理2.1（二次上界）
- Fréchet可微
- Gâteaux可微
-
直线、线段
- 对于
$\mathbb{R}^n$ 中的两个点$x_1 \neq x_2$ ，
形如 $$ y = \theta x_1 + (1 - \theta) x_2 $$ 的点形成了过点$x_1$ 和$x_2$ 的直线。 - 当
$0 \leq \theta \leq 1$ 时，这样的点形成了连接点$x_1$ 与$x_2$ 的线段。
- 对于
-
仿射集、凸集
-
定义2.12（仿射集）
如果过集合$C$ 中任意两点的直线都在$C$ 内，则称$C$ 为仿射集，即 $$ x_1, x_2 \in C \Rightarrow \theta x_1 + (1 - \theta) x_2 \in C, \quad \forall \theta \in \mathbb{R}. $$[!note] 线性方程组
$Ax = b$ 的解集是仿射集（充要条件） -
定义2.13（凸集）
如果连接集合$C$ 中任意两点的线段都在$C$ 内，则称$C$ 为凸集，即 $$ x_1, x_2 \in C \Rightarrow \theta x_1 + (1 - \theta) x_2 \in C, \quad \forall 0 \leq \theta \leq 1. $$[!note] 从仿射集的定义容易看出仿射集都是凸集。
-
定义2.12（仿射集）
-
凸组合、凸包
- 从凸集可以引出凸组合和凸包等概念。形如
$$
x = \theta_{1} x_{1} + \theta_{2} x_{2} + \cdots + \theta_{k} x_{k}, \
1 = \theta_{1} + \theta_{2} + \cdots + \theta_{k}, \
\theta_{i} \geq 0, \quad i = 1, 2, \cdots, k
$$
的点称为
$x_{1}, x_{2}, \cdots, x_{k}$ 的凸组合。 - 集合
$S$ 中点所有可能的凸组合构成的集合称作$S$ 的凸包，记作$\textbf{conv}(S)$ 。
[!note] 实际上，$\textbf{conv}(S)$ 是包含
$S$ 的最小的凸集。 - 从凸集可以引出凸组合和凸包等概念。形如
$$
x = \theta_{1} x_{1} + \theta_{2} x_{2} + \cdots + \theta_{k} x_{k}, \
1 = \theta_{1} + \theta_{2} + \cdots + \theta_{k}, \
\theta_{i} \geq 0, \quad i = 1, 2, \cdots, k
$$
的点称为
-
仿射包
- 若在凸组合的定义中去掉
$\theta_{i} \geq 0$ 的限制，我们可以得到仿射包的概念。 -
定义2.14（仿射包）
设$S$ 为$\mathbb{R}^n$ 的子集，称如下集合为$S$ 的仿射包： $$ {x | x = \theta_{1} x_{1} + \theta_{2} x_{2} + \cdots + \theta_{k} x_{k}, \quad x_{1}, x_{2}, \cdots, x_{k} \in S, \quad \theta_{1} + \theta_{2} + \cdots + \theta_{k} = 1}, $$ 记为$\textbf{affine}(S)$ 。
[!note] 一般而言，一个集合的仿射包实际上是包含该集合的最小的仿射集。
- 若在凸组合的定义中去掉
-
锥组合、凸锥
-
锥组合
形如 $$ x = \theta_{1} x_{1} + \theta_{2} x_{2}, \quad \theta_{1} > 0, \quad \theta_{2} > 0 $$ 的点称为点$x_{1}, x_{2}$ 的锥组合。 -
凸锥
若集合
$S$ 中任意点的锥组合都在$S$ 中，则称$S$ 为凸锥.
-
锥组合
- 超平面、半空间
- 超平面是仿射集和凸集
- 半空间是凸集但不是仿射集
- 球、椭球、锥
- (欧几里得)球
- 椭球
- 范数球
- 范数锥
- 二次锥
- 范数球和范数锥都是凸集．
- 多面体
- （半）正定锥
-
证明集合
$C$ 为凸集：- 第一种：
定义：
$$
x_{1}, x_{2} \in C, \quad 0 \leq \theta \leq 1 \Rightarrow \theta x_{1} + (1 - \theta) x_{2} \in C
$$
来证明集合
$C$ 是凸集。 - 第二种方法是说明集合
$C$ 可由简单的凸集（超平面、半空间、范数球等）经过保凸的运算后得到。
- 第一种：
定义：
$$
x_{1}, x_{2} \in C, \quad 0 \leq \theta \leq 1 \Rightarrow \theta x_{1} + (1 - \theta) x_{2} \in C
$$
来证明集合
- 一些常见的保凸运算
- 任意多个凸集的交以及仿射变换都是保凸的。
- 注意到缩放、平移和投影变换都是仿射变换，因此凸集经过缩放、平移或投影的像仍是凸集。
- 利用仿射变换保凸的性质，可以证明
- 线性矩阵不等式的解集
${x | x_{1}A_{1} + x_{2}A_{2} + \cdots + x_{m}A_{m} \leq B}$ 是凸集$(A_{i}, i=1, 2, \cdots, m, B \in S^{p})$， - 双曲锥
${x | x^{T}Px \leq (c^{T}x)^{2}, c^{T}x \geq 0} (P \in S_{+}^{n})$ 是凸集。
- 线性矩阵不等式的解集
- 定理2.3(分离超平面定理)
- 定理2.4(严格分离定理)
- 定义2.15(支撑超平面)
- 定理2.5(支撑超平面定理)
-
定义2.16
- 凸函数
设函数 ( f ) 为适当函数，如果 (\text{dom} f) 是凸集，且 $$ f(\theta x + (1 - \theta) y) \le \theta f(x) + (1 - \theta) f(y) $$ 对所有 ( x, y \in \text{dom}, 0 \leq \theta \leq 1 ) 都成立，则称 ( f ) 是凸函数。[!tip] 直观地来看，连接凸函数的图像上任意两点的线段都在函数图像上方。
- 凹函数：若
$-f$ 是凸函数，则称$f$ 是凹函数。- 只要改变一下符号，很多凸函数的性质都可以直接应用到凹函数上.
- 凸函数
-
严格凸函数
如果$\text{dom} f$ 是凸集，且 $$ f(\theta x + (1 - \theta) y) < \theta f(x) + (1 - \theta) f(y) $$ 对所有的$x, y \in \text{dom}, x \neq y, 0 < \theta < 1$ 成立，则称$f$ 是严格凸函数。 -
强凸函数
-
定义2.17（强凸函数）
若存在常数 ( m > 0 )，使得 [ g(x) = f(x) - \frac{m}{2} ||x||^{2} ] 为凸函数，则称 ( f(x) ) 为 强凸函数，其中 ( m ) 为 强凸参数。 为了方便我们也称 ( f(x) ) 为 ( m )-强凸函数。 - 通过直接对 ( g(x) = f(x) - \frac{m}{2} ||x||^{2} ) 应用凸函数的定义，我们可得到另一个常用的强凸函数定义。
-
定义2.18（强凸函数的等价定义）
若存在常数 ( m > 0 )，使得对任意 ( x, y \in \text{dom} f ) 以及 ( \theta \in (0, 1) )，有 $$ f(\theta x + (1 - \theta) y) \le \theta f(x) + (1 - \theta) f(y) - \frac{m}{2} \theta (1 - \theta) ||x - y||^{2}, $$ 则称 ( f(x) ) 为强凸函数，其中 ( m ) 为强凸参数。 - 强凸函数的两种定义侧重点不同：
- 从定义2.17可以看出，强凸函数减去一个正定二次函数仍然是凸的；
- 从定义2.18可以看出，强凸函数一定是严格凸函数，当m=0时退化成凸函数．
[!tip] 无论从哪个定义出发，容易看出和凸函数相比，强凸函数有更好的性质． 在后面很多算法的理论分析中，为了得到点列的收敛性以及更快的收敛速度，我们都要加上强凸这一条件．
- 此外，根据强凸函数的等价定义容易得出下面的结论：
-
命题2.3
设 ( f ) 为强凸函数且存在最小值，则 ( f ) 的最小值点唯一。 -
注2.2
- 命题2.3中 ( f ) 存在最小值前提
- 强凸函数 ( f ) 的全局极小点不一定存在。
-
命题2.3
-
定义2.17（强凸函数）
-
凸函数的判定方式：
- 先将其限制在任意直线上，然后判断对应的一维函数是否是凸的。
- 一个函数是凸函数当且仅当将函数限制在任意直线在定义域内的部分上时仍是凸的。
-
定理2.6
$ f(x) $ 是凸函数当且仅当对任意的 $ x \in \text{dom} f, v \in \mathbb{R}^n, g: \mathbb{R} \rightarrow \mathbb{R}$， $ $ g(t) = f(x + tv), \quad \text{dom } g = { t | x + tv \in \text{dom} f } $$ 是凸函数。
-
判断可微函数凸性的一阶条件
-
定理2.7（一阶条件）
对于定义在凸集上的可微函数 ( f )，( f ) 是凸函数当且仅当 $$ f(y) \ge f(x) + \nabla f(x)^T (y - x), \quad \forall x, y \in \text{dom} f. $$- 定理2.7说明可微凸函数 ( f ) 的图形始终在其任一点处切线的上方.
- 因此，用可微凸函数 ( f ) 在任意一点处的一阶近似可以得到 ( f ) 的一个全局下界。
- 定理2.8（梯度单调性） 设 ( f ) 为可微函数，则 ( f ) 为凸函数当且仅当 ( \textbf{dom} f ) 为凸集且 ( \nabla f ) 为单调映射，即 $$ (\nabla f(x) - \nabla f(y))^T (x - y) \ge 0, \quad \forall x, y \in \textbf{dom} f. $$
-
定理2.7（一阶条件）
-
判断可微函数凸性的二阶条件
- 进一步地，如果函数二阶连续可微，我们可以得到下面的二阶条件：
定理2.9（二阶条件）
设$f$ 为定义在凸集上的二阶连续可微函数:-
$f$ 是凸函数当且仅当 $$ \nabla ^2f(x)\ge 0, \space \forall x\in domf. $$ - 若更进一步有： $$ \nabla ^{2}f(x)>0, \forall x\in \textbf{dom}f $$ 则$f$是严格凸函数
-
- 当函数二阶连续可微时，利用二阶条件判断凸性通常更为方便.
- 进一步地，如果函数二阶连续可微，我们可以得到下面的二阶条件：
-
使用上方图来判断函数凸性
定理2.10
函数f(x)为凸函数当且仅当其上方图$\textbf{epi}f$是凸集.
Note
下面的定理说明非负加权和、与仿射函数的复合、逐点取最大值等运算，是不改变函数的凸性的．
-
定理2.11
- 若$f$是凸函数，则$\alpha f$是凸函数，其中$\alpha \geq 0$.
- 若$f_{1}$，$f_{2}$是凸函数，则$f_{1}+f_{2}$是凸函数.
- 若$f$是凸函数，则$f(Ax + b)$是凸函数.
- 若$f_{1}, f_{2}, \cdots, f_{m}$是凸函数，则$f(x) = \max{f_{1}(x), f_{2}(x), \cdots, f_{m}(x)}$ 是凸函数.
- 若对每个$y \in A$，$f(x, y)$关于$x$是凸函数，则 $$ g(x) = \sup_{y \in A} f(x, y) $$ 是凸函数.
- 给定函数$g: \mathbb{R}^{n} \rightarrow \mathbb{R}$和$h: \mathbb{R} \rightarrow \mathbb{R}$，
令$f(x) = h(g(x))$.
若$g$是凸函数，$h$是凸函数且单调不减，那么$f$是凸函数；
若$g$是凹函数，$h$是凸函数且单调不增，那么$f$是凸函数. - 若$f(x, y)$关于$(x, y)$整体是凸函数，$C$是凸集，则 $$ g(x) = \inf_{y \in C} f(x, y) $$ 是凸函数.
- 凸下水平集
- 二次下界
-
定义 2.21（次梯度、次微分）
设
$f$ 为适当凸函数，x 为定义域$\textbf{dom}f$ 中的一点.- 若向量$g\in \mathbb{R}^{n}$满足
$$
f(y)\ge f(x)+g^{T}(y-x), \forall y\in f,
$$
则称
$g$ 为函数$f$ 在点 x 处的一个次梯度. - 进一步地，称集合
$$
\partial f(x)={g |g\in \mathbb{R}^{n}, f(y)\ge f(x)+g^{T}(y-x), \forall y\in \textbf{dom}f}
$$
为
$f$ 在点 x 处的次微分.
- 若向量$g\in \mathbb{R}^{n}$满足
$$
f(y)\ge f(x)+g^{T}(y-x), \forall y\in f,
$$
则称
-
推论
- 若
$g$ 是$f(x)$ 在$x_0$ 处的次梯度，则函数 $$ l(x)\xlongequal{{def}}f(x_{0})+g^{T}(x-x_{0}) $$ 为凸函数f(x)的一个全局下界. - 次梯度
$g$ 可以诱导出上方图$\textbf{epi}f$ 在点 $(^x,f^(x))$ 处的一个支撑超平面:
对$\textbf{epi}f$ 中的任意点 (y,t),有 $$ \left [\begin{matrix} g\-1\end{matrix} \right ]^{T} (\left [\begin{matrix} y\t\end{matrix} \right ] -\left [\begin{matrix} x\f(x)\end{matrix} \right]) \le 0, \space \forall (y, t)\in epif. $$
- 若
Note
下面的定理说明次微分$\partial f(x)$在一定条件下分别为闭凸集和非空有界集.
-
定理2.13
设f是凸函数，则$\partial f(x)$有如下性质：- (1)对任何$x\in \textbf{dom}$,$\partial f(x)$是一个闭凸集（可能为空集）；
- (2)如果$x\in \textbf{intdom}$，则$\partial f(x)$非空有界集.
[!tip]
$\textbf{intdom}f$ 是集合$\textbf{dom}f$ 的所有内点。 - 当凸函数f(x)在某点处可微时，$\nabla f(x)$就是f(x)在该点处唯一的次梯度.
-
命题2.6
设*f(x)*在$x_{0}\in \textbf{intdom}f$ 处可微，则 $$ \partial f(x_{0})={ \bigtriangledown f(x_{0})}. $$ -
定理2.14（次梯度的单调性）
设$f: \mathbb{R}^{n}\rightarrow \mathbb{R}$为凸函数，$x, y\in domf$， 则 $$ (u-v)^{T}(x-y)\ge 0, $$ 其中$u\in \partial f(x), v\in \partial f(y).$
- 基本规则
- 两个函数之和的次梯度
- 函数族的上确界
- 线性规划：
62-63页- 习题 3.1 3.2
78页
- 习题 3.1 3.2
- 半定规划：
70—72页- 习题 3.9 79页
-
一般形式 线性规划问题的一般形式如下： $$ \begin{align} \min _{x\in \mathbb{R}^n} \quad & c^{T}x, \notag \ \text{s.t.}\quad & Ax=b, \notag \ & Gx \le e, \notag \end{align} $$
- 其中 $ c \in \mathbb{R}^{n}, A\in \mathbb{R}^{m\times n}, b\in \mathbb{R}^{m}, $
- 而
$G\in \mathbb{R}^{p\times n}和e\in \mathbb{R}^{p}$ 是给定的矩阵和向量， -
$x\in \mathbb{R}^{n}$ 是决策变量.
-
标准形
（等式约束和决策变量非负）$$ \begin{align} \min _{x\in \mathbb{R}^n} \quad & c^{T}x, \notag \ \text{s.t.}\quad & Ax=b, \notag \ & x \ge 0, \notag \end{align} $$ -
不等式型 $$ \begin{align} \min _{x\in \mathbb{R}^n} \quad & c^{T}x, \notag \ \text{s.t.}\quad & Ax \le b, \notag \ \end{align} $$
- 问题形式： 基追踪问题是压缩感知中的一个基本问题，可以写为 $$ \begin{align} \min \limits {x\in R^{n}} \quad & ||x||{1}, \notag\ \text{s.t.} \quad & Ax=b. \notag \end{align}\tag{3.1.4} $$
-
解法
-
解法一：
对每个$|x_i|$引入一个新的变量zi,可以将问题(3.1.4)转化为 $$ \begin{align} \min \limits {z\in R^{n}} \quad & \sum \limits {i=1}^{n}z{i},\notag \ \text{s.t.} \quad & Ax=b, \notag\ & z{i}\le x_{i}\le z_{i}, i=1, 2, \cdots, n, \notag \end{align} $$ 这是一个线性规划问题. -
解法二:
可以引入xi的正部和负部$x_{i}^{+}, x_{i}^{-}\ge 0$,
利用$x_{i}=x_{i}^{+}-x_{i}^{-}, |x_{i}|=x_{i}^{+}+x_{i}^{-}$ 得出**问题(3.1.4)**的另外一种等价的线性规划: $$ \begin{align} \min \limits {x^{+}, x^{-}\in R^{n}} \quad & \sum \limits {i=1}^{n}(x{i}^{+}+x{i}^{-}), \ \text{s.t.} \quad & Ax^{+}-Ax^{-}=b, \ & x^{+}, x^{-}\ge 0. \end{align} $$
-
解法一：
-
问题形式
- 最小$l_{1}$范数模型 $$ \min {x\in \mathbb{R}^{n}}||Ax-b||{1}, \tag{3.1.5} $$
- 最小$l_{\infty}$范数模型。 $$ \min {x\in \mathbb{R}^{n}}||Ax-b||{\infty}. \tag{3.1.6} $$ 这两个问题都可以转化为线性规划的形式。
-
解法
- 对于最小$l_{1}$范数模型:
通过引入变量$y=Ax-b$ ，可以得到如下等价问题： $$ \min {x, y\in \mathbb{R}^{n}}||y||{1},\ \text{s.t.} \space y=Ax-b. $$ 利用基追踪问题中类似的技巧，我们可以将上述绝对值优化问题转化成线性规划问题。 - 对于最小$l_{\infty}$范数模型:
令 $t=||Ax-b||{\infty}$，则得到等价问题 $$ \min {x\in R^{n}, t\in R}t,\ \text{s.t.} \space ||Ax-b||{\infty}\le t. $$ 利用$l{\infty}$范数的定义，可以进一步写为 $$ \min _{x\in R^{n}, t\in R}t, \ \text{s.t.} \space -t\textbf{1}\le Ax-b\le t\textbf{1}, $$
- 对于最小$l_{1}$范数模型:
- 半定规划（semidefinite programming，SDP）是线性规划在矩阵空间中的一种推广。
- 它的目标函数和等式约束都是关于矩阵的线性函数，
- 但与线性规划不同的是，其自变量取值于半正定矩阵空间。
-
一般形式：
$$ \begin{align} \min \quad & c^T x, \notag \ \text{s.t.} \quad & x_1 A_1 + x_2 A_2 + \cdots + x_n A_n + B \leq 0, \notag \ & Gx = h, \notag \end{align}\tag{3.5.1} $$- 其中 $ c \in \mathbb{R}^n $, $ A_i \in S^m (i=1, 2, \cdots, n)$, $ B \in S^m $
-
$G \in \mathbb{R}^{p \times n}$ ,$h \in \mathbb{R}^p$ 为已知的向量和矩阵 -
$x = (x_1, x_2, \cdots, x_n) \in \mathbb{R}^n$ 是自变量。 这里，如果矩阵$A_i$ ,$B$ 是对角的，那么问题(3.5.1)退化为线性规划问题。
-
标准形式： $$ \begin{align} \min \quad & \langle C, X \rangle, \notag \ \text{s.t.} \space \langle A_1, X \rangle &= b_1,\notag \ & ...\notag \ \langle A_n, X \rangle &= b_n,\notag \ X & \geq 0,\notag \end{align}\tag{3.5.2} $$
-
不等式形式： $$ \begin{align} \min \quad & C^Tx, \notag \ \text{s.t.} \quad & x_1 A_1 + x_2 A_2 + \cdots + x_n A_n + B \leq 0, \notag \end{align} \tag{3.5.3} $$
- 形如 (3.5.1)式 的优化问题都可以转化成 (3.5.2)式 或者 (3.5.3)式 的形式。
-
二次约束二次规划问题的半定规划松弛
- 考虑二次约束二次规划问题
$$
\begin{align}
\min {x\in R^{n}}\quad & x^{T}A{0}x+2b_{0}^{T}x+c_{0}, \
\text{s.t.} \quad & x^{T}A_{i}x+2b_{i}^{T}x+c_{i}\le 0, i=1, 2,\cdots, m, \
\end{align}\tag {3.5.4}
$$
- 其中
$A_{i}$ 为$n \times n$ 对称矩阵. - 当部分
$A_{i}$ 为对称不定矩阵时，问题(3.5.4) 是 NP 难的 非凸优化 问题.
- 其中
- 现在我们写出 问题(3.5.4) 的 半定规划松弛 问题.
[!tip] 对任意 $x \in R^{n} $ 以及.
$A\in S^{n}$ ,有恒等式 $$ x^{T}Ax=Tr(x^{T}Ax)=Tr(Axx^{T})=\langle A, xx^{T}\rangle, $$- 因此 问题(3.5.4) 中所有的二次项均可用下面的方式进行等价刻画： $$ x^{T}A_{i}x+2b_{i}^{T}x+c_{i}=\langle A_{i}, xx^{T}\rangle +2b_{i}^{T}x+c_{i}. $$
- 则原始问题等价于 $$ \begin{align} \min {x\in R^{n}} \quad &\langle A{0}, X\rangle +2b_{0}^{T}x+c_{0} \notag\ \text{s.t.} \quad & <A_{i}, X>+2b_{i}^{T}x+c_{i}\le 0, i=1, 2,\cdots, m \notag \ & X=xx^{T} \notag \end{align} \tag{3.5.5} $$
- 进一步地， $$ \begin{align} x^TA_ix+2b_i^Tx+c_i & = \langle \left (\begin{matrix} A_i & b_i \ b_i^T & c_i \end{matrix}\right ), \left (\begin{matrix} X & x \ x^T & 1 \end{matrix} \right ) \rangle, \notag \ & \xlongequal{{def}} \langle \overline{A}_i, \overline{X}\rangle, i=0,1,\cdots,m. \notag \end{align} $$
- 接下来将等价问题（3.5.5）松弛为半定规划问题。
- 在问题（3.5.5）中，唯一的非线性部分是约束
$X=xx^T$ ，我们将其松弛成半正定约束$X\geqslant xx^T$ 。 - 可以证明，$\overline{X}\geqslant 0$与$X\geqslant xx^T$是等价的。
- 因此这个问题的半定规划松弛可以写成
$$
\begin{align}
\min \quad & \langle \overline{A}_{0}, \overline{X}\rangle \notag\
\text{s.t.} \quad & \langle \overline{A}i, \overline{X}\rangle \leq 0, i=1,2,\cdots, m, \notag \
\quad & \overline{X}\geqslant 0, \notag \
\quad & \overline{X}{n+1, n+1}=1.
\end{align}
$$
- 其中“松弛”来源于我们将
$X=xx^T$ 替换成了$X\geqslant xx^T$
- 其中“松弛”来源于我们将
- 在问题（3.5.5）中，唯一的非线性部分是约束
- 考虑二次约束二次规划问题
$$
\begin{align}
\min {x\in R^{n}}\quad & x^{T}A{0}x+2b_{0}^{T}x+c_{0}, \
\text{s.t.} \quad & x^{T}A_{i}x+2b_{i}^{T}x+c_{i}\le 0, i=1, 2,\cdots, m, \
\end{align}\tag {3.5.4}
$$
-
最大割问题的半定规划松弛(略)
- 下降方向：
85页- 线性化可行方向
- LICQ
- Slater条件等
- 无约束可微问题的一阶必要条件，二阶最优性条件：
85—87页- 例题
87页 - 习题 4.5
115页
- 例题
- 无约束不可微问题的最优性理论：
89——91页 - 对偶理论 例题
96-100页- 习题 4.7
115页 - 习题 4.13
116页
- 习题 4.7
- 一般约束优化问题的最优性理论：
- 例题
107页 - 习题 4.10
116页
- 例题
- 凸优化问题最优性理论：
- 例题
111页 - 习题 4.11(a)，4.6(b)
116页
- 例题
-
考虑优化问题(1.1.1)
$$ \begin{matrix} \min & f(x), \ \text{s.t.} & x\in X, \end{matrix}\tag{4.1.1} $$ 其中$X\subseteq R^{n}$为可行域.
对于问题（4.1.1），首先要考虑的是最优解的存在性，然后考虑如何求出其最优解。[!tip] 在数学分析课程中，我们学习过Weierstrass 定理，即定义在紧集上的连续函数一定存在最大（最小）值点. 而在许多实际问题中，定义域可能不是紧的，目标函数也不一定连续， 因此需要将此定理推广来保证最优化问题解的存在性.
-
定理4.1（Weierstrass定理）
- 考虑一个适当且闭的函数$f:X\rightarrow (-\infty, +\infty )$，
假设下面三个条件中任意一个成立：- 有$\displaystyle \underset{{x}\in X}{\textbf{dom}} ; f \xlongequal{def}{x\in X:f(x)<+\infty}$是有界的；
- 存在一个常数
$\gamma$ 使得下水平集 $$ C_{\gamma}\xlongequal{def}{x\in X:f(x)\le \gamma } $$ 是非空且有界的； - f 是强制的:
即对于任一满足$||x^{k}||\to \infty$的点列$ {x^{k}}\subset X$，都有 $$ \lim _{k\to \infty}f(x^{k})=+\infty, $$ 那么，问题(4.1.1) 的最小值点集${x\in X|f(x)\le f(y),\forall y\in X}$是非空且紧的。
[!note] 定理4.1的三个条件在本质上都是保证
$f(x)$ 的最小值不能在无穷远处取到，
因此我们可以仅在一个有界的下水平集中考虑$f(x)$ 的最小值．
同时要求$f(x)$ 为适当且闭的函数，并不需要$f(x)$ 的连续性．
因此定理4.1比数学分析中的 Weierstrass 定理应用范围更广. - 考虑一个适当且闭的函数$f:X\rightarrow (-\infty, +\infty )$，
一阶最优性条件是利用梯度（一阶）信息来判断给定点的最优性．
-
定义 4.1（下降方向）
对于可微函数 f 和点$x\in R^{n}$，如果存在向量 d 满足
$$
\nabla f(x)^{T}d<0,
$$
那么称
$d$ 为$f$ 在点$x$ 处的一个下降方向。[!note] 由下降方向的定义，容易验证：
如果$f$ 在点$x$ 处存在一个下降方向$d$ ，那么对于任意的$T>0$ ，存在$t\in (0,T]$ ， 使得$f(x+td)<f(x)$ .
因此，在局部最优点处不能有下降方向. -
定理 4.2（一阶必要条件）
假设$f$ 在全空间$R^{n}$ 可微，如果 $x^{}$ 是一个局部极小点，那么 $$ \nabla f(x^{})=0. $$
[!attention|label:注意]
- 上面的条件仅仅是必要的。
- 对于$f(x)=x^{2}, x\in \mathbb{R}$，我们知道满足$f^{\prime}(x)=0$的点为$x^{\ast}=0$，并且其也是全局最优解。
- 对于$f(x)=x^{3}, x\in \mathbb{R}$，满足$f^{\prime}(x)=0$的点为$x^{\ast}=0$，但其不是一个局部最优解。
- 实际上，我们称满足$\nabla f(x)=0$的点$x$为$f$的稳定点（有时也称为驻点或临界点）。
- 可以看出，除了一阶必要条件，还需要对函数加一些额外的限制条件，才能保证最优解的充分性。
-
定理4.3
假设$f$ 在点$x^*$ 的一个开邻域内是二阶连续可微的，则以下最优性条件成立：-
二阶必要条件
如果$x^*$ 是 f 的一个局部极小点，那么 $$ \nabla f(x^{\ast}) = 0, \quad \nabla^2 f(x^{\ast}) \geq 0; $$ -
二阶充分条件
如果在点 $x^$ 处有
$$
\nabla f(x^{\ast}) = 0, \quad
\nabla^2 f(x^{\ast}) > 0;
$$
成立，那么 $x^$ 为
$f$ 的一个局部极小点.
-
二阶必要条件
-
推论：
- 由定理4.3有如下结论：
设点
$\bar{x}$ 满足一阶最优性条件（即$\nabla f(\bar{x})=0$ ）， 且该点处的海瑟矩阵$\nabla ^{2}f(\bar{x})$ 不是半正定的， 那么$\bar{x}$ 不是一个局部极小点. - 进一步地:
如果海瑟矩阵
$abla ^{2}f(\bar{x})$ 既有正特征值又有负特征值， 我们称稳定点$\bar{x}$ 为一个 鞍点. - 事实上:
记
$d_{1},d_{2}$ 为其正负特征值对应的特征向量，
那么对于任意充分小的$t>0$,
我们都有$f(\bar{x}+td_{1})>f(\bar{x})$ 且$f(\bar{x}+td_{2})<f(\bar{x})$ .
- 由定理4.3有如下结论：
设点
[!attention|label:注意]
- 二阶最优性条件给出的仍然是关于局部最优性的判断.
- 对于给定点的全局最优性判断，我们还需要借助实际问题的性质：
- 比如目标函数是凸的、非线性最小二乘问题中目标函数值为0等.
-
定理4.4
假设$f$ 是适当且凸的函数，则 $x^$ 为问题(4.2.1)的一个全局极小点
当且仅当 $$ 0 \in \partial f(x^) $$ - 定理4.4说明条件 $0 \in \partial f(x^)$ 是 $x^$ 为全局最优解的充要条件．
- 这个结论比定理4.2要强，其原因是凸问题有非常好的性质，它的稳定点中不存在鞍点．
- 因此，可以通过计算凸函数的次梯度集合来求解其对应的全局极小点．
- 考虑一般的约束优化问题
$$
\begin{align}
\min_{x\in \mathbb{R}^{n}} & f(x),\notag \
\text{s.t.} \quad & c_{i}(x)\le 0, i\in I,\notag \
& c_{i}(x)=0, i\in \varepsilon, \notag
\end{align}
$$
- 其中
$c_i$ 为定义在$\mathbb{R}^n$ 或其子集上的实值函数 -
$I$ 和$\varepsilon$ 分别表示不等式约束和等式约束对应的下标集合且各下标互相不同。
- 其中
- 这个问题的可行域定义为 $$ X={x \in \mathbb{R}^n | c_{i}(x)\le 0, i\in I \text{ 且 } c_{i}(x)=0, i\in \varepsilon }. $$
-
拉格朗日乘子
- 研究**问题(4.4.1)**的重要工具之一是拉格朗日函数，
- 它的基本思想是给该问题中的每一个约束指定一个拉格朗日乘子，
- 以乘子为加权系数将约束增加到目标函数中。
- 令
$\lambda_i$ 为对应于第$i$ 个不等式约束的拉格朗日乘子，$v_i$ 为对应于第$i$ 个等式约束的拉格朗日乘子。 - 为了构造合适的对偶问题，基本原则：
- 对拉格朗日乘子添加合适的约束条件
- 使得$f(x)$在问题(4.4.1)的任意可行点$x$处大于或等于相应拉格朗日函数值。
- 根据这个原则，我们要求
$\lambda \geq 0$ 。
- 根据这个原则，我们要求
- 研究**问题(4.4.1)**的重要工具之一是拉格朗日函数，
-
拉格朗日函数
- 记 $ m=|I|, p=|\varepsilon|$ ， 则 拉格朗日函数 的具体形式 $L: \mathbb{R}^{n}\times \mathbb{R}{+}^{m}\times \mathbb{R}^{p}\rightarrow \mathbb{R}$ 定义为 $$ L(x, \lambda, v)=f(x)+\sum{i\in I}\lambda_i c_i(x)+\sum_{i\in \varepsilon}v_i c_i(x). \tag{4.4.2} $$
[!tip] **函数（4.4.2）**中的加号也可以修改为减号，同时调整相应乘子的约束条件使得上述下界原则满足即可。
-
拉格朗日对偶函数
- 对拉格朗日函数$L(x, \lambda, v)$中的$x$取下确界可定义拉格朗日对偶函数
- 这一函数将在对偶理论中起到很关键的作用。
-
定义4.2
拉格朗日对偶函数 $g: \mathbb{R}{+}^{m}\times \mathbb{R}{-}^{p}\rightarrow [-\infty, +\infty )$ 是拉格朗日函数$L(x, \lambda, v)$ 对于$\lambda \in \mathbb{R}{+}^{m}, v\in \mathbb{R}{-}^{p}$ 关于$x$ 取的下确界： $$ g(\lambda, \upsilon )=\underset{x\in R^{n}}{inf}L(x, \lambda, \upsilon ). (4.4.3) $$ - 固定
$(\lambda, \upsilon)$ ，如果拉格朗日函数关于$x$ 无界， 那么对偶函数在（$\lambda$，$\upsilon$）处的值为$-\infty$.- 因为拉格朗日对偶函数是逐点定义的一族关于
$(\lambda , \upsilon)$ 的仿射函数的下确界.
- 因为拉格朗日对偶函数是逐点定义的一族关于
[!note] 根据 定理2.11 (5) 可知 拉格朗日对偶函数为凹函数 （无论原始问题是否为凸问题）。 这个性质是十分重要的，它能帮助我们推导出许多拥有良好性质的算法。
- 对拉格朗日函数$L(x, \lambda, v)$中的$x$取下确界可定义拉格朗日对偶函数
-
弱对偶原理
-
引理4.1（弱对偶原理）
对于任意的$\lambda \geq 0$ 和$v$ ，拉格朗日对偶函数给出了**优化问题(4.4.1)**最优值的一个下界，即 $$ g(\lambda, u )\leq p^{*}, \space \lambda \geq 0. $$
[!note] 无论选择什么样的拉格朗日乘子$\lambda$和$v$， 拉格朗日对偶函数
$g(\lambda, v)$ 总是不会超过原优化问题(4.4.1)的最优值$p^*$ 。 -
引理4.1（弱对偶原理）
-
拉格朗日对偶问题：
-
形式：
$$
\max _{\lambda \ge 0,v} ; g(\lambda, v)
=\max _{\lambda \ge 0,v}\inf _{x\in R^{n}}L(x,\lambda, v).\tag{4.4.8}
$$
- 向量
$\lambda$ 和$\upsilon$ 称为问题（4.4.1）的对偶变量或者拉格朗日乘子向量.
- 向量
- 由于其目标函数的凹性和约束集合的凸性，拉格朗日对偶问题是一个凸优化问题（见注1.1）.
- 当
$g(\lambda, v)=-\infty$ 时，对偶函数提供的$p^{*}$ 的下界变得没有实际意义. - 只有当
$g(\lambda, u)>-\infty$ 时，对偶函数生成的关于原始问题最优解$p^{*}$ 的下界才是非凡的.
- 当
- 因此规定定义域 $$ \textbf{dom} g={ (\lambda, v)|\lambda \ge 0, g(\lambda, v)>-\infty }. $$
-
形式：
$$
\max _{\lambda \ge 0,v} ; g(\lambda, v)
=\max _{\lambda \ge 0,v}\inf _{x\in R^{n}}L(x,\lambda, v).\tag{4.4.8}
$$
-
对偶可行解、对偶间隙、对偶最优解
- 当
$(\lambda, u )\in domg$ 时，称其为 对偶可行解.- 记对偶问题的最优值为
$q^{*}$ .
- 记对偶问题的最优值为
- 称 $P^{}-q^{}(\ge 0)$ 为对偶间隙.
- 如果对偶间隙为$0(p^{}=q^{})$，称强对偶原理成立.
- 假设（$\lambda ^{} , u ^{}$）是使得对偶问题取得最优值的解，称其为对偶最优解或者最优拉格朗日乘子.
- 当
[!attention] 拉格朗日对偶问题的写法并不唯一
- 线搜索准则：
- Armijo 准则
121页 - Wolfe 准则
123页
- Armijo 准则
- 梯度法迭代计算
128页- 定理 5.2
- 习题 5.2
179页
- 步长：
- 精确线性搜索；
- BB 梯度法
- BB 梯度法的两种迭代格式推理
132页
- 牛顿类算法：
- 牛顿方程 牛顿方向 经典牛顿法迭代格式
141页
- 牛顿方程 牛顿方向 经典牛顿法迭代格式
- 牛顿法的具体迭代计算：
- 搜索方向 ：
- 步长：1（即经典牛顿法）
- 精确线性搜索
- 搜索方向 ：
- 拟牛顿类算法：
- 割线方程
148页 - 拟牛顿矩阵更新公式推理；
- SR1公式 5.5.9
150页 - BFGS公式推理5.5.12
151页
- SR1公式 5.5.9
- 割线方程
- 罚函数法：
- 二次罚函数法
- 对数罚函数法
- 等式约束优化问题
- 增广拉格朗日函数法