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

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