11.3.4广义既约梯度(GRG)方法
推广约化梯度方法到一般的非线性优化 问题 GRG基本思想：等式约束可以通过消元 的办法化为无约束问题
将等式约束线化 消元 化为无约束形式
应用无约)方法
首先考虑等式约束问题，目标函数和约 束都是非线性的：
基本GRG算法
( )
勋f x 0
( )
c
约束标准型：
相对收益： 最优解可能不在顶点， 非基本变量可能不为0 线性搜索 最优化准则： 最优化准则： % c³ 0 基本解： 相对收益：
凸单纯形算法
凸单纯形算法
11.3.3既约(Reduced)梯度方法
类似于无约束优化的梯度算法（Cauchy 算法）。搜索方向d 为梯度的负方向 约化梯度为 ，即凸单纯形算法中非基 本量的相对收益。可以证明，它实际上 是在约束条件(m个)下的以非基本变量为 独立变量(n-m)的梯度： % ¶ f
?f ¶x
称为约化梯度，是在非基本变量子空间中 的梯度。
11.3.3既约(Reduced)梯度方法
确 定 搜 索 方 向 基本量的 ： 非基本量子空间 中的搜索方向： 中的搜索方向：
x
：
11.3.3既约(Reduced)梯度方法
11.3.3既约(Reduced)梯度方法
约化梯度方法的加速
共轭梯度 准牛顿方法
1、约束的线化 、
2、选择独立变量，即分解为基本量与非基本变量 、选择独立变量， 基本量，即非 独立变量的系 数矩阵： 非基本量，即 独立变量的系 独立变量 数矩阵：
基本GRG算法
3、以非基本变量为独立变量，在线化的约束中解出基本量，实现消元 、以非基本变量为独立变量，在线化的约束中解出基本量，
4、计算目标函数的梯度（独立变量为非基本变量为），即线性规划中的相对收益 、计算目标函数的梯度（独立变量为非基本变量为），即线性规划中的相对收益 ），
惩罚逐次线性规划算法
例：惩罚逐次线性规划方法
限制步长求解
线化
例：惩罚逐次线性规划方法
x(1)点的惩罚函数计算
点线化求解： 在x(1)点线化求解：
例：惩罚逐次线性规划方法
点线化求解： 在x(2)点线化求解：
点线化求解： 在x(3)点线化求解：
…
11.2可分离规划：分段线性近似
分段线性逼近
单变量分段线性近似
解决办法：将 解决办法
往约束曲面上投影，在投影上进行线性搜索：
具体方法： 具体方法： （1）给定α，解出
（2）调变α，使f(x)最速下降
完整GRG算法
完整GRG算法
11.3.5 最一般情形的GRG算法
包含不等式约束，定义域有上下界
定义域边界处理：两种方法
① 将其作为不等式约束 ② 在基本GRG算法过程中对边界特殊处理
5、梯度为0即是最优化的必要条件，可作为收敛准则 、梯度为 即是最优化的必要条件 即是最优化的必要条件， ≤
基本GRG算法
6、确定搜索方向 、
7、在搜索方向上线性搜索 、
返回4 返回
基本GRG算法修正
问题：搜索方向d具有下降的性质，这是由于 是下降的，而 问题 一般不具有这个性质，因此会导致在d方向上搜索会违反约束
单纯形方法求解： 单纯形方法求解：
精确解
总结
逐次线性逼近算法
步长限制，惩罚函数 适用于非线性不强的问题
分段线性逼近算法
精度随格点数增加而增加 要求函数可分离
11.3搜索方向的线性化生成
11.3.1可行方向算法
可行方向算法
例：可行方向算法
例：可行方向算法
例：可行方向算法
…
可行方向算法修正
不等式约束的处理：两种方法
① 加入松弛变量，化为等式约束 ② 在基本GRG算法过程中对边界特殊处理
11 约束问题的线性化方法
非线性约束问题求解策略
1. 转化为无约束问题
Lagrange乘子法 惩罚函数法
2. 线性化 3. 直接搜索等其它方法
线化方法：Taylor展开
11.1线性逐次逼近算法
线性约束问题 非线性约束问题
11.1.1线性约束问题
在初始点x0线化
线性约束问题算法
例：三级压缩机优化设计
目标：选择中间级大力，最大限度节能
例：三级压缩机优化设计
11.1.2非线性约束问题
在点x(t)线化
例：弱非线性问题的逐次线化求解
线化
应用线性规划算法求解
例：弱非线性问题的逐次线化求解
…
11.1.2非线性约束问题
对于较强的非线性问题，逐次线化方法 会导致发散，解决办法：
① 限制步长：区域越小线性近似越准确 ② 使用惩罚函数
ε微扰法 Topkis–Veinott方法
11.3.2单纯形方法推广
单纯形方法回顾
约束标准型：
基本解： 相对收益： 基本变量的 选取与替换： 最优化准则： 所有非基本 变量的相对收益 大于或等于0
新的可行基本解：
单纯形方法推广到线性约束问题：凸单纯形方法 凸单纯形方法
m inimize Ñ f x 0 x
多变量可分离规划
前提：函数可分离
多变量可分离规划
例：多变量函数线性近似
% f2 (x 2 ) = L
例：可分离规划求解
例：可分离规划求解
x1的网格点选取： 的网格点选取： 的网格点选取
函数的分段线性近似： 函数的分段线性近似：
例：可分离规划求解
线化之后的线性规划标准形式： 线化之后的线性规划标准形式：