非线性规划
非线性规划的一般形式
基本概念
-
邻域:开球
-
局部最优解:能找到一个邻域使得该点是邻域与可行域交集中的最优解,退化到一维模型就是极值点。
-
全局最优解:整个可行域中的最优解,退化到一维模型就是最小值点。
-
严格局部最优解和严格全局最优解:上述定义中的换成。
-
梯度(标量函数):多元函数对每一个自变量分量求偏导,结果是列向量。
-
梯度(向量函数)
-
海塞矩阵
-
求导法则:与一元函数基本一致
(1)对向量函数的点积求偏导(2)对常数矩阵和向量函数的乘积求偏导
(3)对二次函数求偏导 -
泰勒展开
(1)一元函数(假设存在连续的二阶导数)
(2)多元函数 (沿着某个方向的泰勒展开,实际上就是一元函数)
凸函数和凹函数
- 凸函数:凸组合的函数小于等于函数的凸组合。退化到一维模型中就是函数上任意两点的连线在函数曲线的上方。
- 一元凸函数的判定。
(1) 定义法。
(2) 一阶导数:切线在连线下方
(3)二阶导数:一阶导数单调递增
-
多元凸(凹)函数的判定:
(1)任意方向上的一元函数都是凸函数。方向和原点都是任意取的。
(2)一阶导数
(3)二阶导数
凸规化
-
凸规化的定义:可行域是凸集,目标函数是连续凸函数。
- 凸规划的性质:任意一个局部最优解就是全局最优解。
- 可行下降方向:既可行又能下降的方向。
- 求解非线性规划的基本途径是迭代。
(1)确定初始可行解。
(2)确定可行下降方向。
(3)一维搜索求。
(4)将作为新的的可行解,重复步骤(2)~(3),直到不存在可行下降方向。
一维搜索
- 问题的提出:在求凸规划问题的过程中,假设我们已知了一个初始解和可行下降方向,那么如何在该方向上找到一个更优的点呢?(即目标函数值更小)
- 一维精确搜索:寻找一元函数的最小值。
- 一维非精确搜索:找一个比当前的结果好一点的点,并不要求是最优。
- 一维精确搜索的性质:新找到的点和梯度与搜索方向正交。
- 精确搜素的基本途径。
(1)确定初始区间(单谷区间)。
(2)压缩区间,直到区间长度小于给定阈值。 - 区间压缩原理:比较区间内两点的函数值。
- 0.618法:每次压缩区间变成原来的0.618倍。
注意:
(1)除了第一步,每次只需计算一个新增点和其函数值(第一步需要两次)。
(2)迭代停止后最优解的选取:区间的中点。 - Fibonacci法:设是斐波那契数列的第n项,恰好是某个区间长度。则通过计算n点的函数值,能将该区间压缩到一个单位长度。
- 利用导数的精确搜索:区间对分。
我们求的最小值实际上就是该函数的极小值,即导数为0的点。确定了初始的单谷区间后,两个端点的导数一定是异号的,压缩比是0.5。 - 利用二阶导数的精确搜索:牛顿法。
无约束优化:
- 基本假设:目标函数具有二阶导数
- 无约束优化的局部最优性条件
(1)必要条件(是极值点):
(2)充分条件(是极小值点): - 基本方法:下降方向法
(1)任取
(2)如果在X处最优(即找不到下降方向),则停止。否则,确定下降方向
(3)利用一维精确搜索的方法在方向D上寻找最小值,即求解下面的优化问题:
(4)用替换X,返回(2)继续迭代。
于是问题的关键在于如何寻找下降方向D? - 梯度下降法:
(1)下降方向:该点的负梯度方向,在小邻域中的下降方向是最好的。
(2)缺点:寻优速度太慢。
(3)特点:相邻两点的寻优方向正交。
(4)改进思路:改进寻优方向。