约束问题的线性化方法.ppt

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