5约束优化的数学基础

约束优化的数学基础本章内容•优化问题分单变量和多变量，有约束和无约束，线性和非线性问题。•无约束优化就是数学上的无条件极值，约束优化就是数学上的条件极值。•我们常见的是非线性规划问题。•本章是回顾相关的数学基础，讨论约束最优化的条件等问题多元函数的极小值充分必要条件**120Tnxffffxxxx*22221121222*22122222212nnnnnxfffxxxxxfffGxxxxxxfffxxxxx正定约束优化的模型：),,2,1(0,,,),,2,1(0,,,..,,,min212121lkxxxhxhmjxxxgxgtsxxxfxfnkknjjn　第一节等式约束优化的极值条件minfx求解等式约束优化问题：需要导出极值存在的条件，这是求解等式约束优化问题的理论基础。对这一问题在数学上有两种处理方法：消元法（降维法）和拉格朗日乘子法（升维法），现分别予以介绍。　　　),,2,1(0..lkxhtsk为了便于理解，先讨论二元函数只有一个等式约束的简单情况，即从约束条件得带入目标函数可消去一个变量消元法（降维法）12min,fxx12..,0sthxx12xx消元法（降维法）对于n维情况12min,,nfxxx12..,,1,2,,knsthxxxkl由个约束方程将n个变量中的前个变量用其余个变量表示，即有：带入目标函数可以消去个设计变量llnl1112221212,,,,,,llnllnllllnxxxxxxxxxxxxl拉格朗日乘子法拉格朗日乘子法通过增加变量将等式约束优化问题变成无约束优化问题，所以又称升维法。0)(0)(],[0,..),(min12211***2211*21**2121dxxhdxxhSxhxhSxdxxfdxxfSxfdxdxSxxxxhtsxxfTkT　　　　　　的梯度垂直：需要与需要满足约束条件，即另外，　　　　　　，需要：如果不想使函数值增加附近的一切微小位移　，对于在设约束最优点为　　　　　　　　问题：　个等式约束的二维优化对于具有　和　值点联立方程可解得约束极　　再加上　　　　　　　即：　　　　由上式，令　　即：　　　　　　　　　　　　　　　*2*1*21221122112121122211*212211*210,000)(0,..0)(),(minxxXxxhxhxfxhxfxhxfxhxfxhxhxfxfdxdxdxxhdxxhSxhxxhtsdxxfdxxfSxfxxfTkT0)(0)(],,,[),,2,1(0,,,..),,,(min1***1*21**2121iniikTkkiniiTnnkkndxxhSxhxhSxdxxfSxfdxdxdxSxxlkxxxhxhtsxxxfl　　　　　　的梯度垂直：需要与需要满足约束条件，即另外，　　　　　　，需要：如果不想使函数值增加附近的一切微小位移　，对于在设最优点为　　　　　　　　　：　个等式约束的优化问题对于具有，得：再加上乘以个把0011iniikiniikdxxfdxxhl31212310nlliiiiiiihhhhfdxxxxxx可以通过其中的前l个方程3121230lliiiiihhhhfxxxxx31212310nlljjljjjjjhhhhfdxxxxxx：的系数为０，方程变为，使得上面方程中来求解lldxdxdx,,,,,,2121但应是任意的量，则应有12,,,llndxdxdx3121230lljjjjjhhhhfxxxxx1,2,,jlln，得：再加上乘以个把0011iniikiniikdxxfdxxhl31212310nlliiiiiiihhhhfdxxxxxxli1综合起来即为：再加上等式约束就是无约束优化问题F的极值条件：01,2,,khxkl121201,2,,nniiiihhhfinxxxx1,lkkkFxfxhx),,2,1(0),,2,1(0lkFnixFki　　　　设，目标函数是，约束条件是的个等式约束方程。为了求出的可能的极值点，引入非零拉格朗日乘子，并构成一个新的目标函数12Tnxxxxfx01,2,,khxkllfx****12Tnxxxx1,2,,kkl1,lkkkFxfxhx3)3,5(080420102)()(),(08)(..60410)(min211222112121212221，可解得：　　　　　　　　　　则：　　令：　　　　　　　例题：　TxxxFxxxFxxxFxhxfxFxxxhtsxxxxxxxfmjjmjjjnilkkijmjjjlkkkjjnilkkinilkkiFxgxhxFZxgxhxfxFmjxgxhxFFxFZ12122112221111221122)()())(()()(),,(),,2,1(0)(　　，则可引入：若问题含有非等式约束　：可以构造一个新的函数计算，接寻优的方法进行迭代为便于在计算机上用直第二节不等式约束优化的极值条件工程上大多数问题都是不等式约束优化问题.一元函数在一定区间的优化问题:引入松弛变量12min..00fxstgxaxgxxb22111112221211,0,0hxagxaaxahxbgxbxbb)00(2121、、和两个拉格朗日乘子得到拉格朗日方程-111211112211221121,,,,,,Fxabfxhxahxbfxaxaxbb1212120dgdgFdfdfxdxdxdxdx1112112020FaaFbb211111221212,0,0FhxagxaFhxbgxb分析可知，此时不是，就是。当时，，约束起作用，即为的情况。当时，，约束不起作用，即为的情况。这个分析结果可表示为110a110,0a110,0a110,0a10gxaxxa110,0a10gxaxxa110,00,0gxxagxxa为起作用的约束，即为不起作用约束，即这说明对于和，二者至少必有一个需要取零值，因此可将的条件写成。11gx110a110gx可将的条件写成。210b220gx121211221200,00,0dgdgdfdxdxdxgxgx1212120dgdgdfdfdxdxdxdx分析极值点在区间中所处的位置，将会出现三种可能的情况：*x,ab1）当时，因为此时，则极值条件为*axb120*0dfxdx2）当时，因为此时，则极值条件为，即。*xa120,010dfdx*0dfxdx3）当时，因为此时，则极值条件为，即。*xb120,020dfdx*0dfxdx这和如下图所示的从几何概念分析的结果完全一致。三个极值条件的几何表示第六节库恩—塔克条件将上述一元函数推广到多元函数，可以得到著名的库恩—塔克条件可以得到拉格朗日函数minfx..01,2,,jstgxjm（其中设计变量为n维向量，它受到有m个不等式约束的限制）12Tinxxxxx21,,mjjnjjFxxfxgxx拉格朗日函数的极值条件从一元函数类推可以得到库恩—塔克条件101,2,,mjjiiiigFfinxxx201,2,,jnjnjFxjmx201,2,,jnjjFgxxjm**1*01,2,,01,2,,01,2,,mjjiiijjjfxgxinxxgxjmjm即：库恩-塔克条件的几何意义是：在约束极小点处函数的负梯度一定能够表示成所有起作用的约束在该点梯度的非负线性组合。**0jjjJfxgx令J表示起作用的约束下标集合，则库恩—塔克条件为：JjJjxgnixxgxxfjjijJjji０　　　　　　　　　　　　　　　　　　　　　0,,2,10***图2-12两个起作用的约束*1122kkfxgxgx图2-13库恩—塔克条件的几何意义a）负梯度位于锥角区之内b）负梯度位于锥角区之外K-T条件关于仅含不等式约束的二维问题的几何解释作业：1、minf(x,y)=4x*x+5y*ys.t.h(x,y)=2x+3y-6=0使用消元法求解2、使用拉格朗日乘子法求解上面问题3、用K-T条件求证minf(x,y)=(x-7)*(x-7)+(y-3)*(y-3)s.t.g1(x,y)=x*x+y*y-10=0g2(x,y)=x+y-4=0g3(x,y)=-y=0在点(3,1)处是否为极值点作业：4、maxf(x,y)=8x+12y-x*x-y*ys.t.g1(x,y)=3x+2y-6=0g2(x,y)=-x=0g3(x,y)=-y=0用K-T条件求约束极值点提示：分８种情况联立下面方程组求解00***xgxxgxxfjijJjji　　　