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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,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,算法,包含不等式约束，定义域有上下界,定义域边界处理：两种方法,将其作为不等式约束,在基本,GRG,算法过程中对边界特殊处理,不等式约束的处理：两种方法,加入松弛变量，化为等式约束,在基本,GRG,算法过程中对边界特殊处理,