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

关于规划数学非线性规划基本知识非线性规划基本概念（3.1）1非线性规划模型分类

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

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

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

试验测得在时刻时

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

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

则

又因为：

故Hesse阵为：

第8页,共38页，星期六，2024年，5月

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

设函数在凸集上有定义,如果对任意和属于及任何实数

（）则称是上的凸函数.

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

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

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

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

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

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

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

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

则称为阶收敛。

线性收敛，超线性收敛，二阶收敛。第20页,共38页，星期六，2024年，5月

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

本节讨论的主要问题是

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

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

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

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

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

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

5令k=k+1返回2第30页,共38页，星期六，2024年，5月例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页，星期六，2024年，5月3二次插值法考虑问题

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

假设初始区间函