2023-07-06 《数值优化方法》-庞丽萍，肖现涛-无约束最优化（一）
数值优化方法Matlab优化概述形如
的问题称为无约束最优化问题，注意到上述问题是定义在
上且
为实值函数。
对于上述优化问题首先需要明确的是最优解的概念。
定义 1.1 若对任意
，不等式
成立，则称
是优化问题的全局极小解（或全局最优解）。进一步地，若对任意的
，不等式严格成立，则称
为优化问题的严格全局极小解（或严格全局最优解）。
相应的可以定义局部最优解的概念。
若存在实数
，以及
的
领域
, 使得对任意
, 不等式
成立，则称为
为优化问题的局部极小解 (或局部最优解). 当不等式严格成立的时候，则称为严格局部极小解 (或严格局部最优解).
下面给出多元函数的二阶泰勒展开公式
其中
为
在
处的梯度向量，
为
在
处的黑塞 (Hesse) 矩阵.
下面的一些凸优化的基本概念在泛函分析和非线性最优化基础中都有详细的介绍。
定义 1.2 设
是
的子集，若对任意
和任意
, 有
则称
为凸集。
注意该定义中
，而在大部分的教材（凸优化 boyd）中，该定义为
. 此外, 当
时，称
是仿射的.
定义 1.3 设
是凸集, 
, 若对任意的
和任意的
, 不等式
成立，则称
是
上的凸函数，当
且不等号严格成立的时候，称为
是
上的严格凸函数.
同样的，一般的定义中
. 严格凸函数的定义为当
及
. 《非线性最优化基础》(林贵华), 《凸优化》(Boyd)
定理 1.1 (凸函数判别定理) 若
, 则下面三个结论是等价的：
(1) 
是凸函数；
(2) 
;
(3) 
是半正定的，记作
.
这里简单总结证明思路
(1) 
(2) 只需要带入凸函数定义并转成形式
, 然后两边取极限
.
(2) 
(3) 对
进行二阶泰勒展开然后取
可得到.
(3) 
(1) 令
， 然后对其二阶泰勒展开得到
然后整理可得。
定理 1.2 设
，则有
(1) 若对任意
, 
是正定的，则
是严格凸函数；
(2) 若
是严格凸函数，则
是半正定的。
下面讨论凸函数的最优解的性质。
定义 1.4 设
, 
, 
, 且
. 若存在
, 使得
则称向量
是
在
处的下降方向。
定理 1.3 (必要条件) 设
在
处可微，若
为无约束优化问题的局部最优解，则
.
证明：由一阶泰勒展开式
立即可得。
定理 1.4 (充分条件) 设
在
处二阶可微，若
, 
为正定矩阵，则
为无约束优化问题的严格局部最优解。
证明：在
附近做二阶泰勒展开可得。
定理 1.5 (充要条件) 设函数
是可微凸函数，则
是无约束优化问题的全局最优解的充要条件是
, 即
是稳定点。
证明：由定理 1.3 和定理 1.1 可得。（只需注意到凸函数的局部最优解同时也是全局最优解，这里只需要带入凸函数定义即可）
下面给出迭代法的基本概念和收敛速度的定义。
下降迭代法产生的新的迭代点的目标函数值比前一个迭代点的目标函数值小。（我们知道很多迭代法并不满足这个性质，但是依然收敛）
下降算法的基本框架：
Step 1. (初始化) 选取初始点
, 给出算法参数和计算精度，置
.
Step 2. (确定搜索方向) 选取一个搜索方向
, 使目标函数下降或至少不增..
Step 3. （线搜索）确定步长
, 其满足
, 令
.
Step 4. （停止准则）给出算法的终止条件，若新的迭代点满足停止条件，则输出当前迭代解.
Step 5. (循环) 否则，
并回到Step 2.
定义 1.5 若从任意的初始点出发，都能保证算法产生的点列（或子列）收敛到最优点，则称算法具有全局收敛性。若算法只有在初始点和最优点具有某种程度的接近时，才能保证算法产生的迭代点列的收敛性，则称该算法具有局部收敛性。
*注意子列收敛也是一种全局收敛性。
定义 1.6 设由算法产生的迭代点列
收敛于
, 即有
若存在实数
及一个与迭代点次数
无关的常数
, 使
则称算法产生的迭代点列具有
阶收敛速度。几种特殊情况a. 若
, 
, 则称算法是线性收敛的。b. 若
或
时，则称算法是超线性收敛的.c. 若
, 则称算法是二阶收敛的.
定理 1.6 若点列
超线性收敛于
，则
证明：带入超线性收敛的定义并进行不等式缩放即可。
当算法是超线性收敛时，可以用
作为终止条件。