🤔 数学中的优化方法
本科阶段学了几门课程都是与优化相关的, 主要讲优化的有最优化算法、运筹学、计算智能、最优控制. 其他有一些课程也又涉及到的, 比如, 数学分析中的求极值和零点、数据分析中求回归方程的最小二乘, 还有模糊数学、数值分析和数学建模等都有涉及. 撰写此文无外乎对所学的优化知识做一个总结.
鉴于都是属于概括性的学了一遍, 总结出来的内容算不得全面, 用词也算不得十分准确, 权当一个记忆备份.
优化问题
优化问题的描述分为两部分:目标函数和约束函数. 函数在此用来作一般性的描述, 具体问题的形式未必是函数, 也可以是集合.
优化问题从抽象出来的数学描述来看, 可以分为两个大类:离散问题和连续问题. 连续和不连续通常是通过变量来确定(此处不确定, 毕竟主要所做过的主要还是连续的). 所学的最优化算法和最优控制主要就是解决的连续问题. 运筹学中描述了解决一些离散问题的方法, 比如0-1规划和整数规划.
对于连续问题, 从问题性质来区分, 仍然可以分为两大类:凸问题和非凸问题. 所谓凸问题是指目标函数和约束函数(或可行域)都是凸的, 而函数或集合是否为凸需要诉诸凸集的概念阐述. 非凸问题是图问题的反面. 计算智能通常用非凸问题测试算法的好坏, 由此也有一些比较出名的测试问题.
另外, 从问题的条件来区分, 可以分为约束问题和无约束问题.
从最优化算法中主要学到的是解决二次型问题的方法;最优控制的优化问题是微积分一类的, 此类问题比较难, 和控制关系紧密;运筹学为规划问题一类, 路径优化和规划方面的问题可在其中找到方法;计算智能比较偏计算机, 解决一些非凸问题或离散问题.
优化方法
通过计算机求解的问题, 大多都是通过迭代逐步逼近最优解. 计算机求解分为两类:数值求解和符号求解(逻辑推理).
问题的转换
方法本身存在解决问题的范围限制, 所以, 可以通过改变问题的形式来适应方法.
非凸问转换成凸问题. 这样可以保证从初始点收敛到唯一最优解. 比如, 对于一个单变量的, 并且有多个极值点的目标函数, 可以通过拟合一个近似的凸的目标函数来求解其近似解.
约束问题转换成无约束问题. 实际上, 最后要解决的问题都是无约束的问题. 简单的约束可以通过在迭代中作映射确保在可行域内迭代. 更一般的做法是将约束条件和目标函数整合在一起, 增广Lagrange就是此类一种比较常用的方法.
离散问题转换连续问题. 通过把离散问题转化为连续问题, 能够帮助分析问题的性质, 并且可以使用求解连续优化问题的方法来求解. 但这种方法也并不是对于任何离散问题都行之有效, 最终得到的解可能会和真实解偏差较大, 问题转换时应当考虑此因素.
关于优化问题转换还有一些其他内容, 比如, 运筹学中转换为对偶问题和极大化问题转换为极小化问题等等. 这些问题的转换的方法, 有的是必须的, 有的是可选择的, 其中的根本原则是保持问题转换前后的一致性.
一些具体的方法
这里主要以最优化算法中所学来描述. 所谓方法, 通常是指几种方法结合在一起形成一个解决问题的方案. 涉及到的要素主要有初始点的选取、下降的方向、迭代步长、停止条件. 联系走路做一个类比, 初始点相当于出发点;下降方向相当于迈出每个步子时的方向选择策略;迭代步长相当于每一步走多远;停止条件则决定什么时候停止继续前进. 这里忽略初始点的选取不作描述.
下降方向. 梯度法、牛顿法、拟牛顿法. 梯度法, 以目标函数的梯度作为下降方向, 一阶方法, 优点是只要求目标函数的一阶导数, 方便应用;缺点是它在接近最优点时会出现锯齿现象(迭代轨迹抖动). 牛顿法, 二阶方法, 优点是收敛速度快, 缺点是需要二阶导数, 这样的要求就使得它的应用范围受限制. 拟牛顿法, 介于梯度法和牛顿法之间, 类似于求解非线性方程时割线法介于二分法和牛顿法之间. 此法的基本思想是得到近似于牛顿法那样的Hessian矩阵, 这类方法比较著名的有BFGS(Broyden, Fletcher, Goldfarb, Shanno).
迭代步长. 步长可分为固定步长和动态步长. 固定步长每次迭代都不变, 虽然简单, 但鉴于其效果, 一般不采用. 动态步长每次迭代都会更新, 获得步长的方法又分为精确的和非精确的. 精确的方法期望能获得尽量大的步长, 比如黄金分割法(或称0. 618法), 此类方法在步长求取上比较耗时. 非精确的方法则期望获得一个合适的步长, 从而在整体迭代相对于精确方法消耗时间要少, Armijo就属于此类方法. 精确方法虽然每步都强调求得尽量大的步长, 但是在消耗时间上劣势使得算法在整体性能上不如非精确方法. 获得步长的方法通常也是通过迭代求得, 要么从大的步长迭代向小的步长, 要么从小的步长迭代向较大的步长. 另外, 在做自适应重启加速梯度法的时候, 是通过每次迭代估计Lipchitz常数来获得步长的, 效率也比较高.
停止准则. 迭代次数、迭代时间、目标函数精度、迭代值精度(变量的精度). 停止迭代的限制条件关键在于目标函数精度和迭代值精度. 精度限制分为绝对精度和相对精度, 相对精度有更好的适应性, 相对绝对精度而言, 它能够使得一个解决方案应用于更多的问题. 另外, 对于一般的问题, 实际上并没有一个一般的精度标准, 即便是相对精度也有限制, 因此也有研究概率停止条件的.
判断方法的优劣
通过不同方法计算同一个问题, 在实验时, 对比的指标包括计算时间、迭代次数、目标函数精度、迭代值精度.
复杂度. 复杂度包括时间复杂度和空间复杂度. 以计算机计算来看, 表现出来的就是计算时间和内存占用. 在资源不足的情况下, 需要两者之间的协调. 利用时间换空间, 或者利用空间换时间.
精度. 尽管都是趋向最优解(局部或者全局), 但不同的方法得到的解的质量不尽相同.
其他
计算智能本质上描述的是仿生物算法, 比如遗传算法、蚁群算法、神经网络算法等等. 以遗传算法为例, 其基本思想是模仿生物优胜劣汰的进化过程. 通过变量编码表述为个体(染色体), 修改(或不修改)目标函数得到的适应度函数表述适应性. 在迭代过程中通过遗传算子和变异算子体现遗传和变异.
结语
优化这个概念涵盖内容很广, 这里略提一二. 但优化问题有其共性, 比如, 通过转化问题来简化问题, 保持总体上的优化而不是每个细节都苛刻.
打算写这么一篇总结也有好些时日了, 现在算是了却了一桩心头事.