第11章约束问题的线性化方法

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前提：函数可分离多变量可分离规划例：多变量函数线性近似()22f x=%L例：可分离规划求解例：可分离规划求解x1的网格点选取：的网格点选取：函数的分段线性近似：函数的分段线性近似：例：可分离规划求解线化之后的线性规划标准形式：线化之后的线性规划标准形式：单纯形方法求解：单纯形方法求解：精确解总结n逐次线性逼近算法n步长限制，惩罚函数n适用于非线性不强的问题n分段线性逼近算法n精度随格点数增加而增加n要求函数可分离11.3搜索方向的线性化生成11.3.1可行方向算法可行方向算法例：可行方向算法例：可行方向算法例：可行方向算法可行方向算法修正n微扰法nTopkisVeinott方法11.3.2单纯形方法推广单纯形方法回顾单纯形方法回顾约束标准型：基本解：相对收益：基本变量的选取与替换：新的可行基本解：最优化准则：所有非基本变量的相对收益大于或等于0单纯形方法推广到线性约束问题：凸单纯形方法凸单纯形方法相对收益：最优化准则：最优解可能不在顶点，非基本变量可能不为0()0m i ni m i zef xx约束标准型：基本解：相对收益：()0f xc勋最优化准则：0c%线性搜索凸单纯形算法凸单纯形算法11.3.3既约(Reduced)梯度方法n类似于无约束优化的梯度算法（Cauchy算法）。搜索方向d 为梯度的负方向n约化梯度为 ，即凸单纯形算法中非基本量的相对收益。可以证明，它实际上是在约束条件(m个)下的以非基本变量为独立变量(n-m)的梯度：称为约化梯度，是在非基本变量子空间中的梯度。ffx=%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包含不等式约束，定义域有上下界n定义域边界处理：两种方法 将其作为不等式约束 在基本GRG算法过程中对边界特殊处理n不等式约束的处理：两种方法 加入松弛变量，化为等式约束 在基本GRG算法过程中对边界特殊处理