非线性规划的理论与算法

第五章第五章 非线性规划 理论和算法非线性规划 理论和算法 5 55 5 约束优化约束优化 我们现在继续讨论更一般的有约束的线性优化问题 特别的 我们考虑一个具有非线性 目标函数和 或者 非线性约束的优化问题 我们可以将这种问题表示为下面的一般形式 5 10 ixg ixg xf i i x 0 0 min 在本节的末尾 我们假设和 全部是连续可微的 f i g i 拉格朗日函数是研究有约束的优化问题的一个重要工具 为了定义这个函数 我们结 合每个约束的乘子 称作拉格朗日乘子 对于问题 5 10 拉格朗日函数如下定义 i 5 11 i ii xgxfxL 本质上 我们考虑的是目标函数违反了可行约束时的惩罚函数 选择合适的 最小 i 化无约束函数等价于求解约束问题 5 10 这就是我们对拉格朗日函数感兴趣 L x 的最根本的原因 与这个问题相关的最重要问题之一是求解最优问题的充要条件 总之 这些条件称为 最优性条件 也是本节的目的 在给出问题 5 10 最优性条件之前 我们先讨论一个叫做正则性的条件 由下面的 定义给出 定义定义 5 15 1 设向量满足和 设是使得 x ixgi 0 ixgi 0 J 等号成立的指标集 是问题 5 10 约束条件的正则点 如果梯度向量 0 xgi x 相互线性无关 xgi iJ 在上述定义中与对应的约束 即满足的约束称为在点处的有效约束 J 0 xgi x 我们讨论第一章提到的两个优化的概念 局部和全局 回顾 5 10 的全局最优解向 量 它是可行的而且满足对于所有的都成立 相比之下 局部最优解 x xfxf x 是可行的而且满足对于 成立 因此局部解一 x xfxf xxx 0 定是它邻域的可行点中最优的 下面我们考虑的最优性条件仅仅判别局部解 则可能是全 局最优解 也可能不是 幸运的是 这里存在一类局部最优解和全局解一致的问题 凸 优化问题 附录 A 中讨论的就是基于凸集的凸优化问题 定理定理 5 15 1 一阶必要条件 一阶必要条件 设是问题 5 10 的局部最小值 假设是这个问题 x x 的约束的正则点 则存在 使得 i i 0 i ii xgxf 5 12 i i 0 5 13 ixgi i 0 5 14 注意 5 12 左边表达的意思是拉格朗日函数对每个变量的梯度 一阶条 L x x 件在局部最小值 局部最大值及鞍点处满足 当目标函数和约束函数是二次连续可微的时 候 可以用函数的曲率排除最大值和鞍点 根据定理 5 1 我们考虑拉格朗日函数 和这个函数对每个变量的海森矩阵 来计算目标函数和约束函数在当前点处的 L x x 曲率 定理定理 5 25 2 二阶必要条件 二阶必要条件 假设函数和 都是二次连续可微的 假设 f i g i 是问题 5 10 局部最小值而且是这个问题的约束正则点 则存在 满足 x i i 5 12 5 14 及下面的条件 5 15 i ii xgxf 2 2 在处有效约束的切线子空间处是半正定的 x 定理后半部分可以改写为含有效约束的雅阁比矩阵的形式 设表示处有效约 xA x 束的雅阁比矩阵 设表示基于的零空间 则定理的最后一个条件等价于下面 xN xA 的条件 5 16 2 2 xNxgxfxN i ii T 是半正定的 二阶必要条件并非常常保证给出的解的局部最优性 局部最优性的充分条件更加严格 和复杂 因为要考虑到退化的可能性 定理定理 5 35 3 二阶充分条件 二阶充分条件 假设函数和 都是连续二次可微的 同时假 f i g i 设是问题 5 10 可行点而且是这个问题的约束正则点 设表示处有效约束 x xA x 的雅阁比矩阵 设表示基于的零空间 如果存在 满足 5 12 xN xA i i 5 14 及下面的条件 暗示 5 17 ixgi 0 0 i 和 5 18 2 2 xNxgxfxN i ii T 是正定的 则是问题 5 10 的局部最小值 x 定理 5 1 5 2 和 5 3 中列出的条件称作 Karush Kuhn Tucker KKT 条件 以它们的 发明者命名的 一些求解约束优化问题的方法表达成一系列简单的可以用一般迭代步骤求出解的简单 优化问题 这些 简单 的问题可以是无约束的 此时可以应用我们前面章节介绍的方法 求解 我们在 5 5 1 中考虑这些策略 在其他情况下 这些简单的问题是二次规划且可以 应用第七章中的方法求解 这个策略的典型例子是 5 5 2 中讨论的连续二次规划问题 5 5 1 广义简约梯度法广义简约梯度法 在本节中 我们介绍一种求解有约束的非线性规划的方法 这种方法建立在前文讨论 的无约束优化法之最速下降法的基础上的 这种方法的思想是利用约束减少变量的个数 然后用最速下降法去求解简化的无约束的问题 线性等式约束线性等式约束 首先我们讨论一个约束是线性方程组的例子 22 1234 11234 21234 min 4440 2220 f xxxxx g xxxxx gxxxxx 在其他变量给定情况下 很容易求解只有两个变量的约束方程 给定 令 1 x 4 x 和 214 388xxx 314 33xxx 把这些变量代入目标函数 然后得到下面简化的形式 2 2 14114144 min 38833f x xxxxxxx 这个简化形式是无约束的 因此可以利用 5 4 1 节的最速下降法求解 例 1 用最速下降法求 min f x f 2 2 4 2 Matlab 程序 M 文件 function R n steel x0 y0 eps syms x syms y f x 2 4 exp x 2 x 2 y 2 v x y j jacobian f v T subs j 1 x x0 subs j 2 y y0 temp sqrt T 1 2 T 2 2 x1 x0 y1 y0 n 0 syms kk while temp eps d T f1 x1 kk d 1 f2 y1 kk d 2 fT subs j 1 x f1 subs j 2 y f2 fun sqrt fT 1 2 fT 2 2 Mini Gold fun 0 1 0 00001 x0 x1 Mini d 1 y0 y1 Mini d 2 T subs j 1 x x0 subs j 2 y y0 temp sqrt T 1 2 T 2 2 x1 x0 y1 y0 n n 1 end R x0 y0 调用黄金分割法 M 文件 function Mini Gold f a0 b0 eps syms x format long syms kk u a0 0 382 b0 a0 v a0 0 618 b0 a0 k 0 a a0 b b0 array k 1 1 a array k 1 2 b while b a b0 a0 eps Fu subs f kk u Fv subs f kk v if FuFv a u u v v a 0 618 b a k k 1 end array k 1 1 a array k 1 2 b end Mini a b 2 输入 R n steel 0 1 0 0001 R 1 99999413667642 3 99999120501463 n 1 非线性等式约束非线性等式约束 现在考虑用一个线性方程去逼近一个拥有非线性约束问题的可能性 而线性问题就可 以像上面的例子那样解决 要了解如何工作的 考虑下面的例子 它和前面提到的例子类 似 但是它的约束是非线性的 22 1234 2 11234 2 21234 min 4440 2220 f xxxxx g xxxxx gxxxxx 在当前点我们用 Taylor 级数逼近约束方程 x T g xg xg xxx 于是 0 4 442 4 4 1 2 444 2 143211 44 33 22 11 143211 xxxxxx xx xx xx xx xxxxxxg 和 0 2 2 2 4443212 xxxxxxxg 广义简约梯度法 GRG 的思想是求解一系列子问题 每个子问题可以利用约束的线 性逼近 在算法的每一步迭代中 利用先前获得的点重新计算线性化约束的点 一般来说 即使约束是线性逼近的 但每一步迭代获得值也是逐步逼近最优点的 线性化的一个性质 是在最优点 线性化的问题和原问题有相同的解 使用 GRG 的第一步是选择一个初值 假设我们开始设 而这个值恰 0 0 8 3 0 x 好逼近公式 我们构造的首个逼近问题如下 22 1234 1234 2123 min 4440 220 f xxxxx g xxxx gxxxx 程序思路与例 1 相似 具体参考例 1 程序 5 5 约束优化约束优化 现在我们这个逼近问题的等式约束 用其他变量表示其中的两个变量 不妨选择 和 即得 2 x 3 x 和 214 248xxx 314 1 23 2 xxx 把这些表达式代入目标函数 获得简化的问题 2 2 14114144 1 min 248 23 2 f x xxxxxxx 求解这个无约束的最小化问题 得到再代入上面表达式 14 0 375 0 96875xx 得 因此 GRG 方法的第一步迭代产生了一个新点 23 4 875 1 25xx 1 0 375 4 875 1 25 0 96875 X 继续这个求解过程 在新点上我们重新线性化约束函数 利用获得的线性方程组 把 其中两个变量用其他变量表示 然后代入目标函数 就可以得到新的简化问题 求解这个 新的简化问题得到新的点 依此类推 利用停止准则其中 2 X 1kk XXT 0 0025T 我们得到结果如下表 5 7 把这个结果同最优解比较 其目标值是 0 500 4 825 1 534 0 610 x 1 612 观察表 5 7 注意到当或时 函数的值有时比最小值小 这是怎么回事1k 2k k f x 呢 原因是通过 GRG 方法计算获得的点通常不满足约束条件 它们只对这些约束条件 k x 的线性逼近可行 现在我们讨论如何在一个不可行的点使用 GRG 方法 第一阶段问题是构建一个满足 约束条件的点 第一阶段的目标函数是违反约束的绝对值总和 而第一阶段问题的约束都 是不违反约束的 假设我们在点开始计算 这个点不满足第一个约束 但满 0 1 1 0 1x 足第二个约束 所以第一阶段问题是 2 1234 2 1234 min444 2220 xxxx xxxx 一旦通过解决第一阶段问题获得一个适宜的解 那么上面阐述的方法就可以用来求最 优解 线性不等式约束线性不等式约束 最后 我们讨论 GRG 是怎样像解决等式问题那样解决有不等式约束的问题 在每次迭 代中 只有严格满足不等式约束的量才能进入线性方程组 以消除变量 这些不等式约束 通常被认为是有效的 这个过程是复杂的 由于为了得到好的结果 在当前点的每一个不 等式约束都有被舍弃的可能 我们在下面的例子中说明了这一点 22 1212 12 1 2 2 15 min 22 0 0 0 2 f x xxx xx x x x 图图 5 5 广义简约梯度算法的过程广义简约梯度算法的过程 这个问题的可行集合显示在图 5 5 中 图中的可行箭头表示由每个约束指向的可行的 超平面 假设我们从开始 这一点满足所有约束条件 从图 5 5 可以看出 0 1 0 x 三个约束条件是无效的 而约束是有效的 我们必须决 12 0 xx 1 0 x 2 2x 2 0 x 定是否应该留在它的下界还是允许它离开边界 2 x 000 12 21 251 5f xxx 这表明如果我们沿方向 移动 减少的最多 即减少增大 00 1 5df x f 1 x 因为这个方向朝向可行区域内部 我们决定从边界释放 新的点变成 2 x 2 x 其中 这个约束引入了的一个上限 也就是 0 0 8333 接 1000 xxd 0 0 0 下来我们通过线性搜索来确定 0 在这个范围之内的最优值 结果是 0 0 8333 从而 1 0 8333 0 8333x 参见图 5 5 现在 我们重复这个过程 约束 12 0 xx 开始起作用 其他约束失效 因为活动约 束不是一个简单的上下限约束 我们引入一个剩余变量 3 x 然后将其中之一用其余变量 表示 代入 1 23 xxx 我们得到如下化简的优化问题 22 23232 2 3 15 min 22 02 0 f x xxxx x x 在 1 23 0 8333 0 x x 简约梯度为 2323223 22125 221 2 667 0 667 f xxxxxxx 因此f 在 2 667 0 667 方向降幅最大 也就是要增大 2 x 并减小 3 x 但是 3 x已 经到达其下界 我们无法再减小它 因此我们保持 3 x在它的下界处 即我们沿方向 1 2 667 0d 到达新的点 2111 2323 x xx xd 沿这个方向的线性搜索给出 1 0 25 2 23 1 5 0 x x 接下来仍然是该约束有效 所以我们仍然在 2 x和 3 x的空 间中 在 2 23 1 5 0 x x 处的梯度 23 0 2f x x 与当前解 2 X的边界线垂直 且 指向可行区域的外部 因而f不可能进一步减小 于是我们找到了最优解 对应于最初的 变量空间 这个最优解就是 1 1 5x 和 2 1 5x 这就是一些广泛使用的非线性规划求解方法 例如 Excel 的 SOLVER GINO CONOPT GRG2 以及一些其他的方法用来求解非线性规划问题的方法 具体求解时只需附 加一些额外细节 例如线性搜索时的 Newton Raphson 方向等 同线性规划相比 能够在 一个合理的计算时间内解决的问题通常规模比较小 并且求得的结果也可能不是特别精确 另外 可行集合或目标函数潜在的非凸性会导致求解结果是局部最优的而远非全局解 因 此在解释非线性规划的结果时需要更加小心 5 5 2 序列二次规划序列二次规划 考虑一般的非线性最优化问题 ixg ixg xf i i x 0 0 min 5 20 为了解决这个问题 有人试图利用可得到的较好的算法解决更有条理 更简单的二次 规划 参见第七章 这是连续二次方程背后的思想 在当前可行点 k x 问题 5 20 是由 一个二次规划来近似的 拉格朗日函数的近似二次方程可以像近似的线性约束一样计算 可以得到如下的二次方程规划问题 1 min 2 0 5 21 0 T kTkkk k kTkk ii kTkk ii f xxxxxBxx g xxxg xi g xxxg xi 其中 2 kkk xx BL x 是拉格朗日函数 5 11 的海森矩阵 k 为当前估计的拉 格朗日乘数 这个问题可以用解决二次方程规划问题的一种特殊算法来解 例如我们在第七章讨论 的内点方法 二次规划的最优解是用来确定搜索方向 那么线性搜索或信赖域程序是为了 确定下一个迭代 也许思考序列二次规划的最好方式是将其作为求解有约束条件问题的牛顿法的优化版 的扩展 回想一下 牛顿方法的优化版使用目标函数的二次逼近 定义这个逼近的最小值 作为下一次迭代值 这很像我们描述的 SQP 方法 的确 对于一个无约束问题 二次规划 与牛顿法是相同的 对于约束问题 在解决 SQP 时的二次规划问题的最优性条件相当于在 当前迭代下牛顿法直接指向的原来问题的最优化条件 序列二次规划迭代直到该问题收敛 就像牛顿法一样 二次规划方法是非常强大 尤 其是当运用线性搜索或信赖域方法来处理非线性和非凸性 我们推荐读者翻阅 Boggs and Tolle 14 和 Nocedal and Wright 55 来进一步了解二次规划方法 5 6 非光滑优化 次梯度方法非光滑优化 次梯度方法 在这一部分 我们考虑无约束非线性规划的形式 min f x 当 12 n xx xx 并且 f是一个不可微的凸函数 由于在此情况下没有定义梯度 所以无法获得基于梯度的最优 条件 然而 梯度的概念可被推广如下 f在 x点的次梯度是向量 12 n ss ss 使 x sxf xf x 对任意x都成立 当函数f是可微的 次梯度和梯度是相同的 当函数f在x点处不可微 通常在x处 有许多次梯度 例如 考虑含有一个变量的凸函数 max 1 11f xx xx 从图 5 6 可明显看出这个函数在1x 处是不可