学习笔记：数值最优和模型预测控制(二)最优化的基础

上一章传送门：

善道：学习笔记：数值最优和模型预测控制(一)概述77 赞同 · 2 评论文章

本章先开始探究静态最优问题的基本概念。

2.1局部/全局最小和容许集

定义2.1 局部/全局最小: 给定函数 [公式] 有映射关系 [公式] 且有最优点 [公式] 。
1.一个局部最小：如果足够小的邻域内的任意 [公式] 有 [公式] 
2.一个严格局部最小：如果足够小的邻域内的任意 [公式] 有 [公式]
3.一个全局(绝对)最小：如果 [公式] 有 [公式]
4.一个严格全局(绝对)最小：如果 [公式] 有 [公式]

按照定义可知，一个全局最小总是局部最小，由下图可知

图1 局部全局最小值
定义2.2 容许集: 给定集合 [公式]

[公式] 都可视为容许的点，满足约束条件，于是最优化也可以简写为

(2.1) [公式]

所以无约束问题有 [公式] 。在上一章中由约束条件围成的区域即容许集。易知，容许集非空，为保证这一点，独立等式约束条件数 [公式] 不能超过最优变量 [公式] 的个数 [公式] 。

Weierstrass定理: 如果映射 [公式] 连续，且容许集 [公式] 紧致而非空那么最优问题总有至少一个在最优点处 [公式] 的最小值。

若非紧致开集定义的容许集则不适用。比如 [公式]

2.2 梯度和Hesse矩阵

一个代价函数的一阶二阶导数是最优化的根本。因为不连续函数或不连续导数经常有很多问题，所以经常假定，所有最优问题的函数都是连续且足够可微的。

定义2.2 梯度: 如果映射 [公式] 连续可微，那么 [公式] 在 [公式] 处的梯度可以定义为
(2.2) [公式]

负的梯度对于求解最优问题至关重要，因为它对应了 [公式] 处代价函数变化率的最速下降方向。

图2 曲线的梯度图示
定义2.3 Hesse矩阵: 如果映射 [公式] 二次连续可微，那么 [公式] 在 [公式] 处的Hesse矩阵可以定义为
(2.3) [公式]

根据Schwarz定理，由于二次偏导的连续性，存在偏导的可交换性，即 [公式]，这也就是说Hesse矩阵式对称阵( [公式] )，并且总有实的特征值。这样如果Hesse矩阵是(半)正定的，那么最优化是有意义的。

定义2.4 正/负定性: 一个对称矩阵 [公式] 的定性有以下条件刻画
[公式]

矩阵 [公式] 特征值为等式 [公式] 的解；顺序主子式为如下形式的行列式：

[公式]

想要确定矩阵的定性，使用条件①②③足矣，至于条件③也被称为Slyvester判据，只适用于正定负定的矩阵。

2.3 凸性

凸的性质是最优问题的根本，也使得数值求解变得简单。对于命题最优问题的解的唯一性来说，凸性至关重要。凸性既可以用在集合上，也可以用在函数以及最优问题上。

2.3.1凸集

定义2.5 凸集: 一个集合 [公式] 被称为凸集，当任意元素向量 [公式] 满足
[公式]

凸集的几何解释是：一个集合恰为凸集，当且仅当任意两点连线完全包含于集合之中。下列图例展示了这个性质，前两张图都是凸集，而后两张都不是。

图3 凸集的图示

凸集的一个性质就是，它的交集也是凸集。

2.3.2 凸函数

定义2.6 凹凸函数: 一个凸集 [公式] ，在上面映射函数 [公式] 也是凸的，如果满足 [公式] 同时也有
[公式] 
函数若严格凸，则去掉等号且 [公式] 取开区间；类似的有，函数 [公式] 为(严格)凹，当且仅当 [公式] 是(严格)凸的。

函数的凹凸性也可同样图示解释，函数是凸(凹)的，如果函数值 [公式] 落在两端 [公式] 连线之下(上)。至于一次函数同时是凹凸性的。

图4 (a)严格凸(b)凸(c)凹(d)非凸非凹

凸函数保有一些有趣的性质：

  • 若有凸函数 [公式] ，以及系数 [公式] ，和函数 [公式] 也为凸函数。
  • 有凸函数 [公式]那么集合 [公式] 也一直凸。
图5 凸集S是凸函数f(x)和切平面f(x)=k的交集平面
  • 连续可微函数 [公式] 在 [公式] 上凸，则 [公式] 有 [公式]。这个性质也可以作为定义2.6的替代，通过下图展示。几何含义为，凸函数在任意点都存在所谓的支撑超平面，如此 [公式] 便可以停在上面。
图6 凸函数的支撑超平面(标量形式为支撑切线)

例2.3 给定函数

(2.4) [公式]

易知函数在容许集 [公式] 上非凸，这可以通过等高线看出——其定义恰为平面和凸函数的交集，可以看到一些非凸的等高线，即该函数非凸。

图7 函数等高线的投影

函数的凹凸性同样可以通过Hesse矩阵的定性来判断。

定理2.3 如果 [公式] 凸，且 [公式] 二次连续可微，那么
1.函数 [公式] 为凸，如果 [公式] 对 [公式] 半正定
2.函数 [公式] 为严格凸，如果 [公式] 对 [公式] 正定
3.函数 [公式] 为凹，如果 [公式] 对 [公式] 半负定
4.函数 [公式] 为严格凹，如果 [公式] 对 [公式] 负定

值得注意的是，严格凸函数不能保证其Hesse矩阵的半正定性。比如，严格凸函数 [公式]其在 [公式] 处的二次导数 [公式] 。

2.3.3 凸优化问题

定义2.7 若容许集 [公式] 凸且代价函数 [公式] (严格)凸，静态最优问题 [公式] (严格)凸。
定理2.4 如果约束函数 [公式] 是线性的，而 [公式] ，[公式] 是凸的，那么容许集 [公式] 凸。

定理2.4很好理解，即两个凸集的交集也为凸集。容许集即若干约束集的交集。这样就充分保证了静态优化问题的凸性。

定理2.5 静态最优问题 [公式] 是一个(严格)凸优化，如果满足
a) 约束函数 [公式] 是线性的
b) 约束函数 [公式] 是凸的，
c) 代价函数 [公式] 在容许集 [公式] 上(严格)凸。

凸优化的重要性质有 1)每个局部最小都是全局最小 2）如果严格局部最小存在，那么它唯一且为全局最小 3) 一个严格凸优化问题不能有多于一个解，若存在一个局部最小，那么它就为唯一的全局最小。

一个优化问题的严格凸性不意味着一定存在解，就如同之前提到的例子 [公式]。其代价函数 [公式] 二阶导数恒大于零对于 [公式]。所以这个优化问题是个凸优化，但是不存在最小值。

综上可知，凸性对最优问题的分析极大简化了。所以很多的理论求解最优问题以及收敛性质的数值方法基于这个假设，因为大多数数值方法都能收敛于一个局部最优，这意味着(严格)凸性自动推出了(唯一的)全局解。

参考文献：

Numerische Optimierung und modellprädiktive Regelung (WS 2019/2020), A. Völz, K. Graichen, Lehrstuhl für Regelungstechnik, Friedrich-Alexander-Universität Erlangen-Nürnberg