优化理论-框架 Nov 1, 2019 · 优化理论 · 分享到: 优化理论框架 优化理论解的存在性 无约束数值优化条件 无约束优化一阶条件 无约束优化二阶条件 无约束数值优化方法 方向确定 步长确定-精确搜索与不精确搜索 线性搜索法 信任法（信赖域）——Levenberg-Marquardt方法 有约束数值优化条件 有约束数值优化一阶条件 KKT点 有约束数值优化二阶条件 有约束数值优化方法 转换为无约束优化——拉格朗日法 Barrier methods 惩罚函数 收敛速度 优化理论解的存在性 解的存在性： 维尔斯特拉斯极值定理：若函数\(f\)在n维有界闭区域\(S\)上连续，那么\(f\)在\(S\)上一定有全局最小值； 若函数\(f\)在n维闭区域\(S\)上连续并且向正无穷发散(coercive，即\(lim||x||⇒∞,f(x)=+∞\))，那么\(f\)在\(S\)上一定有全局最小值。 以上定理只能保证最小值存在，没有建立最小值和极小值之间的关系。但是，对于一类特殊的函数，它在一定区域内的极小值一定是最小值，这类函数即凸函数。凸函数为定义在凸区间上的一种函数，它满足任意两点的连线位于抽象的函数曲面之下；而凸区间则满足任意两点连线仍然在区间中。定义在凸区间内的严格凸函数有唯一的极小值，该极小值为该函数在该区间上的最小值。 无约束数值优化条件 参见笔记——《最优化条件：无约束问题最优化条件》 无约束优化一阶条件 无约束优化二阶条件 无约束数值优化方法 线搜索和信任域（信赖域），两者主要区别是计算步长和搜索方向的步骤相反。线搜索的思路是先选择搜索方向,然后才是长度。信任域的思路是先选择长度（信任域半径），然后选择方向及其长度。 对于搜索方向的选择，我们又有最速下降、牛顿、拟牛顿、非线性共轭梯度等方法。主要基础理论就是泰勒定理和矩阵相关知识。 方向确定 梯度法（最速下降法） 牛顿法 拟牛顿法 DFP算法 BFGS算法 L-BFGS算法 步长确定-精确搜索与不精确搜索 两个常用的步长控制算法是线搜索和信赖域方法。在一个线搜索方法中，模型函数给出一个步骤方向，然后沿着这个方向搜索以找到一个可以达到收敛的适当的点。在信赖域方法中，每一步要更新一个距离，而在这个距离内模型函数是被信任的。如果模型步骤位于该距离之内，则可以被使用；否则，模型函数在信赖域边界上的极小值将被使用。一般来说，信赖域方法更稳健，但是它们需要更多的数值线性代数运算。 线性搜索法 线搜索技术是多变量函数优化的基础，它包括精确线搜索技术和非精确线搜索技术。常见的精确线搜索技术可分为分割方法和插值方法两大类：分割方法有二分法、黄金分割法、斐波那契法等；插值方法有一点二次插值法（牛顿法）、二点二次插值法（包括割线法）、三点二次插值法、二点三次插值法等。非精确线搜索技术基于非精确线搜索准则，常用的准则有 Armijo-Goldstein 准则、Wolfe-Powell 准则、强 Wolfe-Powell 准则和简单准则。这里特别指出精确与非精确是指对步长搜索的精确性。 什么是线搜索呢？我们知道最优化算法的基本框架就是依据迭代公式\(\vec x_{k+1}=\vec x_k+\alpha_k\vec d_k\)不断产生下一个迭代点，直到满足某些终止条件。迭代公式的确定涉及搜索方向\(\vec d_k\)和搜索步长\(\alpha_k\)的确定，其中\(\alpha_k\)的确定过程就是所谓线搜索的过程。 精确线搜索的精确有两种理解。第一，对于分割法，精确搜索每次使得搜索空间有固定比例的缩小。例如\(l_k\)是第\(k\)次搜索空间大小，则第\(k+1\)次搜索空间就是\(\alpha l_k(\alpha ∈ (0,1))\)，第二，对于插值法，求使得近似（多项式）函数\(p(\vec x_k+\alpha_k\vec d_k)\)取到最小值时对应的\(\alpha\)，换句话说：精确线搜索求使得目标函数沿搜索方向\(\vec d_k\)下降最多的搜索步长。其他精确线搜索还有共轭梯度法conjugate gradient method。 非精确线搜索没有找出导数为零的点,而是使f(x)有一个充分的下降(sufficient descent)，即只求使得目标函数沿搜索方向\(\vec d_k\)有一定下降的搜索步长，这个步长选择不好甚至可能会导致偏离搜索目标（比如梯度下降法中学习率过大的情况）。非精确搜索方法的基础是backtracking，如果能够收敛，则需要考虑以下几种条件。 wolfe conditions Curvature condition Armijo conditions goldstein conditions 需要指出的是，非精确搜索和精确搜索不是完全互斥的，一些精确搜索方法也满足非精确线搜索准则。 实际计算中，通常采用非精确线搜索技术，这是因为精确线搜索技术耗费大量的计算资源，而且对于多变量函数的优化，许多算法的收敛速度并不取决于是否采用精确线搜索技术。 信任法（信赖域）——Levenberg-Marquardt方法 有约束数值优化条件 参见笔记——《最优化条件：有约束问题最优化条件》 有约束数值优化一阶条件 KKT点 有约束数值优化二阶条件 有约束数值优化方法 转换为无约束优化——拉格朗日法 Barrier methods 惩罚函数 收敛速度 如果我们假设了算法产生的迭代点列\(\{ {x_k}\}\)是在某种范数下收敛的, 即\(\lim\limits_{k→∞}||x_k–x^\ast||=0\), 那么考察收敛速度的话, Q-收敛速度较为常用是这么定义的: 若存在实数\(\alpha > 0\)及一个与迭代次数\(k\)无关的常数\(q > 0\), 使得 \[\lim_{k→∞}\frac{||x_{k+1}–x^\ast||}{||x_k–x^\ast||^\alpha} = q\] 线性收敛速度: \(\alpha = 1,q > 0\) 超线性收敛速度: \(1 < \alpha < 2,q > 0\)或者\(\alpha = 1,q = 0\) 二阶收敛速度: \(\alpha = 2\) 注: 还有其他的一些收敛速度的定义, 但并不常用。