第6讲非线性规划基本知识

非线性规划基本概念（1学时）一维搜索（1学时）重点：下降迭代算法、黄金分割法、二次插值法。难点：下降迭代算法构造基本要求：了解非线性规划的分类，掌握梯度的计算和性质，会用海赛阵判断凸规划，掌握用黄金分割法、二次插值法。第4讲非线性规划及一维搜索（第3章）非线性规划基本概念（3.1）)X(fminq,,1j,0)X(g.jp,,1i,0)X(hinEXXf),(min1非线性规划模型分类一般无约束极值形式为：一般有约束极值问题形式为：例1在层次分析（AnalyticHierarchyProcess,简记为AHP）中，为了进行多属性的综合评价，需要确定每个属性的相对重要性，即它们各自的权重。为此，将各属性进行两两比较可得如下判断矩阵：nnnnaaaaJ1111其中：是第个属性与第个属性的重要性之比。现需要从判断矩阵求出各属性的权重，为使求出的权重向量在最小二乘意义上能最好地反映判断矩阵的估计，建立数学模型：211)()(minijninjijwwawf11niiw0iw有约束极值问题2321)(tttfnttt,...,,21)(tf),(),...,(),(21ntftftf321,,223211321)tt)t(f(),,(sminini例2模型参数识别问题设已知某问题的数学模型为试验测得在时刻时的值为试用其估计参数。建立问题为的数学模型采用最小二乘法问题转化为求解无约束极值问题2多元函数的极值问题（1）梯度及Hesse矩阵梯度Hesse矩阵TxXfxXfxXfnXf),,,()()()()(212222122222212212212212)()()()()()()()()())(()(nnnnnxXfxxXfxxXfxxXfxXfxxXfxxXfxxXfxXfXfXH例3：求下列函数的梯度：①222112312334fXxxxxxxx解：2122312131224.24fXfXxxxxxxxxxx312321223121312331264.24,,2464TfXxxxxxxxxfXfXfXfXxxxxxxxxxx12121212223222121122322221212142.12242,122xxxxTxxxxfXfXxxexxxexxfXfXxxefXxxxxxe②1223124xxfXxxe解：例4求目标函数f（X）=的梯度和Hesse矩阵。解：则又因为：故Hesse阵为：22212312233xxx2xx2xx3x21122xxxXf2132222fXxxxx323223fXxxx122133222,222,223TfXxxxxxxx2,2,20,2,2232322222312212212xfxxfxfxxfxxfxf2202220222Xf（2）局部极值和全局极值极小点局部极小点全局极小点严格局部极小点非严格局部极小点非严格全局极小点严格全局极小点1*X2*Xab0Xf例如：图中一元函数f定义在区间[ab]上为严格局部极小点，非严格局部极小点1*X2*Xa为严格全局极小点凸（凹）函数定义:设函数在凸集上有定义,如果对任意和属于及任何实数（）则称是上的凸函数.（3）凸函数、凹函数及凸规划凸（凹）函数二阶判别定理：设是非空开凸集上的二阶连续可微函数，则为凸函数的充分必要条件是在上半正（负）定。)(XfR)1(X)2(X01)(XfRR)()1()()())1(()2()1()2()1(XfXfXXf)(Xf)(XfR)(XH凸规划min..0.1~jfXstgXjm)(Xf若为凸函数为凹函数，则该非线性规划为凸规划。定义：)(Xgj凸规划性质：设是凸规划问题的一个局部最优解，则是全局最优解。如果是严格凸函数，则是唯一全局最优解。证明：反证法设是凸规划的局部最优解但不是全局最优解，则存在可行解满足由可行域为凸集，则为可行解由是凸函数即在的任意小邻域内存在函数值小于的可行解与是局部极小点矛盾。证毕。*X*X*)(Xf*X*X*X)(Xf)(XfY)(*)(YfXf*)(*)()1(*)()()1(*)())1(*(XfXfXfYfXfYXf)1,0(,)1(*YX（4）多元函数的泰勒公式多元函数Taylor展开式在最优化理论中十分重要。许多方法及其收敛性的证明都是从它出发的。下面就给出多元函数Taylor展开式：的二阶泰勒展开))(()(!21)()()()()0()0(2)0()0()0()0(XXXfXXXXXfXfXfTT例5用泰勒公式将函数在点,823)(122213231xxxxxXfTX)1,1()0(解：给出极小点的一个初始估计值()fX(0)X令(1)()()(1)kkkkXXP0k设其中：为一个方向向量，为一个实数（称为步长）()kPk1kk依次用（1）式计算得一个点列()kX若有：(0)(1)(2)()()()()...()...kfXfXfXfX则称（1）为下降迭代算法1）定义：4下降迭代算法令例6试求目标函数在点处的负梯度方向，并求沿这个方向移动一个单位长度后新点的目标函数值。解：由于则函数在处的负梯度方向是12121264,42fXfXxxxxxx(0)0,1TX1212112(0)0121021644422xxxxfXxxxPfXxxfXx2221212143,xxxxxxf(0)0,1TX这个方向上的单位向量是：(0)(0)224252514255fXefX新的点为：(1)(0)225505511151555XXe1(1)2211222634|250.75XfXxxxx(0)(0)22112234|1XfXxxxx（2）确定最佳步长：在已知的情况下求（1）确定搜索方向：不同的搜索方向对应不同的算法()kP()()min()kkfXP()kP()kXkk定理：式（1）中按最佳步长得到的新的点处的梯度和其搜索方向正交。即(1)kX(1)()()0kTkfXP证明：1212()()()()()()()()1122(1)(1)(1)(1)(1)(1)()()()12(1)(1)(1)()()()()()(,,...,)(,,...,)()()()()...()0nnkkkkkkkknnkkkkkkkkknkkkkkTkfXPfxpxpxpfxxxfXfXfXpppxxxfXPP得即为最佳步长例7：试求目标函数在点处的负梯度方向，并求沿这个方向移动最佳步长后新点的目标函数值。解：由于则函数在处的负梯度方向是12121264,42fXfXxxxxxx(0)0,1TX1212112(0)(0)0121021644422xxxxfXxxxPfXxxfXx2221212143,xxxxxxf(0)0,1TX(1)(0)(0)044(())1212XXfX(1)0.67fX(0)(0)22112234|1XfXxxxx(1)2()84201fX05()0410(1)0420/41121/41X2)收敛性：若其中为极小点。则称该算法是有效的()*lim0kkXX*X()kX下降算法得到的点列不一定收敛到极小点，它依赖于初始点的选择。例显然为极小点()fxx*0X()()(1)()()1(1)1,121,12kkkkkxxxxx初始点选(0)()1,1kxx()kx不可能收敛于*x初始点选(0)()1,0kkxx3)收敛速度：设收敛于若存在与迭代次数无关的数和使得从开始都有*X0()kX00k(1)()()*kkkXXXX则称为阶收敛。()kX线性收敛，101超线性收敛，2二阶收敛。4)计算机迭代时终止计算的准则(1)()3()(1)()4()()()()kkkkkkXXXfXfXfX(1)()1(1)()2()()kkkkXXfXfX（1）绝对误差（2）相对误差(3)根据目标函数梯度(1)4()kfX2(1)4()korfX一维搜索本节讨论的主要问题是解决这个问题的方法称为一维搜索。这种方法不仅对于解决一维最优化本身具有实际意义，而且也是解多维最优化问题的重要支柱。在微积分中解的方法限于方程可以直接求解出来的情况。本节介绍的方法对不作严格要求，它可以很复杂，其导数可能不存在或者很难求出。当然对于可以求导数的情况，相应的方法也会简单些。)(mintRtRR:)(mint0)(t（1）黄金分割法：适用于一般的函数。（试探法）（2）二次插值法：（3）Newton切线法：适用于的一阶导数和二阶导数都可求出的情况。（函数逼近法）)(t本章将介绍以下几种直线搜索方法：1搜索区间的确定定义1：设，t*是在L上的全局极小点。如果对于L上任取的两点和且均有≤t*，当≥t*时，则称是区间L上的单谷函数。以下假设一元函数是单谷函数。11:RRL)(t11()()11()())(t)(t0tt*t*t11111111..11定义2：，t*是在L上的全局极小点。若找到,则称此区间为的极小点的一个搜索区间，。单谷函数的性质：设是单谷函数极小点的一个搜索区间。在上任取两点，使,若则是极小点的一个搜索区间；若，则是极小点的一个搜索区间。11()())(t1111,,*LLt使)(t[,]ab11()()1[,]a)(t11()()1[,]b)(t....ab11()()11:RRL1111[,][,]ab11[,]11单谷函数的这一性质可用来将搜索区间无限缩小，以至求到极小点。本章下面就介绍一维搜索法.1[,]a11()()1[,]b)(t11()()证明：利用反证法证明。对于后一种情况，即若不是搜索区间即的极小点必在中。此时有,矛盾。根据单谷函数定义知：故是搜索区间，同样可证前种情形*11t1[,]b25101112（负值舍去）试探点的公式为：左试点右试点0.382()0.618()