规划数学非线性规划基本知识

关于规划数学非线性规划基本知识第1页，讲稿共38页，2023年5月2日，星期三非线性规划基本概念（3.1）1非线性规划模型分类

一般无约束极值形式为：一般有约束极值问题形式为：第2页，讲稿共38页，2023年5月2日，星期三例1在层次分析（AnalyticHierarchyProcess,简记为AHP）中，为了进行多属性的综合评价，需要确定每个属性的相对重要性，即它们各自的权重。为此，将各属性进行两两比较可得如下判断矩阵：

其中：是第个属性与第个属性的重要性之比。现需要从判断矩阵求出各属性的权重，为使求出的权重向量在最小二乘意义上能最好地反映判断矩阵的估计，建立数学模型：有约束极值问题第3页，讲稿共38页，2023年5月2日，星期三例2模型参数识别问题

设已知某问题的数学模型为

试验测得在时刻时

的值为试用其估计参数。建立问题为的数学模型采用最小二乘法问题转化为求解无约束极值问题第4页，讲稿共38页，2023年5月2日，星期三2多元函数的极值问题（1）梯度及Hesse矩阵梯度Hesse矩阵第5页，讲稿共38页，2023年5月2日，星期三

例3：求下列函数的梯度：①解：第6页，讲稿共38页，2023年5月2日，星期三②解：第7页，讲稿共38页，2023年5月2日，星期三例4求目标函数f（X）=的梯度和Hesse矩阵。解：

则

又因为：

故Hesse阵为：

第8页，讲稿共38页，2023年5月2日，星期三

（2）局部极值和全局极值极小点局部极小点全局极小点严格局部极小点非严格局部极小点非严格全局极小点严格全局极小点例如：图中一元函数f定义在区间[ab]上为严格局部极小点，非严格局部极小点a为严格全局极小点第9页，讲稿共38页，2023年5月2日，星期三凸（凹）函数定义:

设函数在凸集上有定义,如果对任意和属于及任何实数（）则称是上的凸函数.

（3）凸函数、凹函数及凸规划凸（凹）函数二阶判别定理：

设是非空开凸集上的二阶连续可微函数，则为凸函数的充分必要条件是在上半正（负）定。

第10页，讲稿共38页，2023年5月2日，星期三第11页，讲稿共38页，2023年5月2日，星期三凸规划若为凸函数为凹函数，则该非线性规划为凸规划。定义：第12页，讲稿共38页，2023年5月2日，星期三凸规划性质：设是凸规划问题的一个局部最优解，则是全局最优解。如果是严格凸函数，则是唯一全局最优解。证明：反证法设是凸规划的局部最优解但不是全局最优解，则存在可行解满足由可行域为凸集，则为可行解由是凸函数即在的任意小邻域内存在函数值小于的可行解与是局部极小点矛盾。证毕。第13页，讲稿共38页，2023年5月2日，星期三

（4）多元函数的泰勒公式

多元函数Taylor展开式在最优化理论中十分重要。许多方法及其收敛性的证明都是从它出发的。下面就给出多元函数Taylor展开式：的二阶泰勒展开例5用泰勒公式将函数在点解：第14页，讲稿共38页，2023年5月2日，星期三给出极小点的一个初始估计值令设其中：为一个方向向量，为一个实数（称为步长）

依次用（1）式计算得一个点列若有：则称（1）为下降迭代算法1）定义：4下降迭代算法令第15页，讲稿共38页，2023年5月2日，星期三例6

试求目标函数在点处的负梯度方向，并求沿这个方向移动一个单位长度后新点的目标函数值。解：由于则函数在处的负梯度方向是这个方向上的单位向量是：新的点为：第16页，讲稿共38页，2023年5月2日，星期三

（2）确定最佳步长：在已知的情况下求（1）确定搜索方向：不同的搜索方向对应不同的算法定理：式（1）中按最佳步长得到的新的点处的梯度和其搜索方向正交。即证明：得即为最佳步长第17页，讲稿共38页，2023年5月2日，星期三例7：试求目标函数在点处的负梯度方向，并求沿这个方向移动最佳步长后新点的目标函数值。解：由于则函数在处的负梯度方向是第18页，讲稿共38页，2023年5月2日，星期三2)收敛性：若其中为极小点。则称该算法是有效的下降算法得到的点列不一定收敛到极小点，它依赖于初始点的选择。例显然为极小点初始点选不可能收敛于初始点选第19页，讲稿共38页，2023年5月2日，星期三3)收敛速度：设收敛于若存在与迭代次数无关的数和使得从开始都有

则称为阶收敛。

线性收敛，超线性收敛，二阶收敛。第20页，讲稿共38页，2023年5月2日，星期三

4)计算机迭代时终止计算的准则（1）绝对误差（2）相对误差(3)根据目标函数梯度第21页，讲稿共38页，2023年5月2日，星期三一维搜索

本节讨论的主要问题是

解决这个问题的方法称为一维搜索。这种方法不仅对于解决一维最优化本身具有实际意义，而且也是解多维最优化问题的重要支柱。在微积分中解的方法限于方程可以直接求解出来的情况。本节介绍的方法对不作严格要求，它可以很复杂，其导数可能不存在或者很难求出。当然对于可以求导数的情况，相应的方法也会简单些。第22页，讲稿共38页，2023年5月2日，星期三

（1）黄金分割法：适用于一般的函数。（试探法）（2）二次插值法：（3）Newton切线法：适用于的一阶导数和二阶导数都可求出的情况。（函数逼近法）本章将介绍以下几种直线搜索方法：第23页，讲稿共38页，2023年5月2日，星期三1搜索区间的确定

定义1：设，t*是在L上的全局极小点。如果对于L上任取的两点和且<均有≤t*，当≥t*时，则称是区间L上的单谷函数。以下假设一元函数是单谷函数。

0tt*t*t..第24页，讲稿共38页，2023年5月2日，星期三定义2：，t*是在L上的全局极小点。若找到,则称此区间为的极小点的一个搜索区间，。单谷函数的性质：设是单谷函数极小点的一个搜索区间。在上任取两点，使,若则是极小点的一个搜索区间；若，则是极小点的一个搜索区间。....ab第25页，讲稿共38页，2023年5月2日，星期三

单谷函数的这一性质可用来将搜索区间无限缩小，以至求到极小点。本章下面就介绍一维搜索法.证明：利用反证法证明。对于后一种情况，即若不是搜索区间即的极小点必在中。此时有

,矛盾。根据单谷函数定义知：故是搜索区间，同样可证前种情形第26页，讲稿共38页，2023年5月2日，星期三第27页，讲稿共38页，2023年5月2日，星期三（负值舍去）第28页，讲稿共38页，2023年5月2日，星期三试探点的公式为：左试点右试点为了算法描述方便我们记试点如下：第29页，讲稿共38页，2023年5月2日，星期三步骤：1给出初始区间及精度，计算试探点及函数值令k=12若停止计算，中任意一点均可作为所求极小点的近似。否则当时转3，当时转4；3置计算转5；4置计算转5；

5令k=k+1返回2第30页，讲稿共38页，2023年5月2日，星期三例8用0.618法求解下列问题初始区间为计算结果列于下表：1-11-0.2360.236

-0.653-1.1252-0.2361

0.2360.528-1.125-0.970.-1.10....3-0.236

0.528

0.056

0.236-1.050

-1.125

40.0560.5280.2360.348-1.125-1.106

560.1680.3480.2360.279-1.125-1.12370.1680.2790.0560.3480.1680.236-1.112-1.125第31页，讲稿共38页，2023年5月2日，星期三3二次插值法考虑问题

二次插值法是以目标函数的二次插值函数的极小点作为新的中间插值点，进行一维搜索的方法。

假设初始区间函数值呈现“两端大中间小”的3个点所确定的区间，三个点为，对应的函数值为。令

，过这三个点，可确定二次插值函数

（1）（2）第32页，讲稿共38页，2023年5月2日，星期三

（3）将式（2）和式（3）联立解得将区间内的3个点及其函数值分别代入式(2),得到含三个未知数的方程组：（4）第33页，讲稿共38页，2023年5月2日，星期三第34页，讲稿共38页，2023年5月