约束问题的线性化方法

《约束问题的线性化方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、11约束问题的线性化方法非线性约束问题求解策略转化为无约束问题Lagrange乘子法惩罚函数法线性化直接搜索等其它方法线化方法：Taylor展开11.1线性逐次逼近算法线性约束问题非线性约束问题11.1.1线性约束问题在初始点x0线化线性约束问题算法例：三级压缩机优化设计目标：选择中间级大力，最大限度节能例：三级压缩机优化设计11.1.2非线性约束问题在点x(t)线化例：弱非线性问题的逐次线化求解线化应用线性规划算法求解例：弱非线性问题的逐次线化求解…11.1.2非线性约束问题对于较强的非线性问题，逐次线化方法会导致发散，解决办法：限制步长：区域越小线性近似越准确

2、使用惩罚函数惩罚逐次线性规划算法例：惩罚逐次线性规划方法限制步长求解线化例：惩罚逐次线性规划方法x(1)点的惩罚函数计算在x(1)点线化求解：例：惩罚逐次线性规划方法在x(2)点线化求解：在x(3)点线化求解：…11.2可分离规划：分段线性近似分段线性逼近单变量分段线性近似多变量可分离规划前提：函数可分离多变量可分离规划例：多变量函数线性近似例：可分离规划求解例：可分离规划求解x1的网格点选取：函数的分段线性近似：例：可分离规划求解线化之后的线性规划标准形式：单纯形方法求解：精确解总结逐次线性逼近算法步长限制，惩罚函数适用于非线性不强的问题分段线性逼近算法精度随格

3、点数增加而增加要求函数可分离11.3搜索方向的线性化生成11.3.1可行方向算法可行方向算法例：可行方向算法例：可行方向算法例：可行方向算法…可行方向算法修正ε微扰法Topkis–Veinott方法11.3.2单纯形方法推广单纯形方法回顾约束标准型：基本解：相对收益：基本变量的选取与替换：新的可行基本解：最优化准则：所有非基本变量的相对收益大于或等于0单纯形方法推广到线性约束问题：凸单纯形方法相对收益：最优化准则：最优解可能不在顶点，非基本变量可能不为0约束标准型：基本解：相对收益：最优化准则：线性搜索凸单纯形算法凸单纯形算法11.3.3既约(Reduced)梯度

4、方法类似于无约束优化的梯度算法（Cauchy算法）。搜索方向d为梯度的负方向约化梯度为，即凸单纯形算法中非基本量的相对收益。可以证明，它实际上是在约束条件(m个)下的以非基本变量为独立变量(n-m)的梯度：称为约化梯度，是在非基本变量子空间中的梯度。11.3.3既约(Reduced)梯度方法基本量的变化：非基本量子空间中的搜索方向：保证x在定义域内：确定搜索方向11.3.3既约(Reduced)梯度方法11.3.3既约(Reduced)梯度方法约化梯度方法的加速共轭梯度准牛顿方法11.3.4广义既约梯度(GRG)方法推广约化梯度方法到一般的非线性优化问题GRG基本

5、思想：等式约束可以通过消元的办法化为无约束问题将等式约束线化消元化为无约束形式应用无约束的基于梯度算法11.3.4广义既约梯度(GRG)方法首先考虑等式约束问题，目标函数和约束都是非线性的：基本GRG算法1、约束的线化2、选择独立变量，即分解为基本量与非基本变量基本量，即非独立变量的系数矩阵：非基本量，即独立变量的系数矩阵：基本GRG算法3、以非基本变量为独立变量，在线化的约束中解出基本量，实现消元4、计算目标函数的梯度（独立变量为非基本变量为），即线性规划中的相对收益5、梯度为0即是最优化的必要条件，可作为收敛准则≤基本GRG算法6、确定搜索方向7、在搜索方向上

6、线性搜索返回4基本GRG算法修正问题：搜索方向d具有下降的性质，这是由于是下降的，而一般不具有这个性质，因此会导致在d方向上搜索会违反约束解决办法：将往约束曲面上投影，在投影上进行线性搜索：具体方法：（1）给定α，解出（2）调变α，使f(x)最速下降完整GRG算法完整GRG算法11.3.5最一般情形的GRG算法包含不等式约束，定义域有上下界定义域边界处理：两种方法将其作为不等式约束在基本GRG算法过程中对边界特殊处理不等式约束的处理：两种方法加入松弛变量，化为等式约束在基本GRG算法过程中对边界特殊处理