运筹学第4章非线性规划

运筹帷幄之中决胜千里之外第4章

非线性规划Non-linearProgramming§4.1基本概念§4.2凸函数和凸规划§4.3一维搜索方法§4.4无约束最优化方法§4.5约束最优化方法第4章

非线性规划1.非线性规划问题例4.1.1

曲线的最优拟合问题§4.1基本概念例2构件容积问题§4.1基本概念1.非线性规划问题数学规划约束集或可行域MP中目标函数和约束函数中至少有一个不是x的线性函数，称(MP)为非线性规划§4.1基本概念MP的可行解或可行点向量化表示当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。否则，称为约束非线性规划或者约束最优化问题。§4.1基本概念最优解和极小点§4.1基本概念最优解和极小点§4.1基本概念例：非线性规划的图解法2)(=xfAB2.非线性规划方法概述：§4.1基本概念线搜索框架下的迭代算法基本迭代格式§4.1基本概念第1步

选取初始点0x，k:=0;

第2步

构造搜索方向kp；

第3步

根据kp，确定步长kt；

第4步

令kkkkptxx+=+1，

若1+kx已满足某种终止条件，停止迭代，输出

近似解1+kx；否则令k:=k+1，转回第2步。

§4.2凸函数和凸规划1.凸函数的定义(a)凸函数(b)凹函数§4.2凸函数和凸规划§4.2凸函数和凸规划2.凸函数的一些基本性质注：一般来说上述定理的逆是不成立的。§4.2凸函数和凸规划2.凸函数的一些基本性质§4.2凸函数和凸规划2.凸函数的一些基本性质各阶主子式负正相间（第一个为负）3.凸规划的定义约束集如果(MP)的约束集X是凸集，目标函数f是X上的凸函数，则(MP)叫做非线性凸规划，或简称为凸规划。§4.2凸函数和凸规划定理4.2.6

凸规划的任一局部最优解都是它的整体最优解。§4.2凸函数和凸规划4.凸规划的性质：本节练习1.

验证

§4.3一维搜索方法精确一维搜索方法：0.618法，Newton法非精确一维搜索方法：

Goldstein法，

Armijo法1.0.618法（近似黄金分割法）§4.3一维搜索方法2.Newton法§4.3一维搜索方法第1步

给定初始点1t，0>e，1:=k；

第2步

如果ej<¢)(kt，停止迭代，输出kt。否则，当0)(=¢¢ktj时，停止，

解题失败；当0)(¹¢¢ktj时，转下一步；

第3步

计算)()(1kkkkttttjj¢¢¢-=+，如果e<-+kktt1，停止迭代，输出1+kt。否则1:+=kk，转第2步。

3.Goldstein法§4.3一维搜索方法Goldstein法步骤:§4.3一维搜索方法4.Armijo法§4.3一维搜索方法取定Mm<<<10，用一下两个式子限定kt不太大也不太小：

)0()0()(jjj¢+£kkmtt

)0()0()(jjj¢+>kkmMtMt

§4.4无约束最优化方法无约束问题的最优性条件最速下降法共轭方向法1、无约束问题的最优化条件§4.4无约束最优化方法§4.4无约束最优化方法1、无约束问题的最优化条件2.最速下降法（又称梯度法）§4.4无约束最优化方法§4.4无约束最优化方法最速下降法的计算步骤：3.共轭方向法§4.4无约束最优化方法§4.4无约束最优化方法3.共轭方向法F-R法步骤§4.4无约束最优化方法§4.5约束最优化方法约束最优化问题的最优化条件简约梯度法惩罚函数法其中(MP)1.约束最优化问题的最优化条件§4.5约束最优化方法Kuhn-Tucker条件（K-T条件）：§4.5约束最优化方法注：凡是满足K-T条件的点叫K-T点§4.5约束最优化方法简约梯度法(4.5.12)Wolfe法步骤惩罚函数法思想：利用问题中的约束函数做出适当的带有参数的惩罚函数，然后在原来的目标函数上加上惩罚函数构造出带参数的增广目标函数，把(MP)问题的求解转换为求解一系列无约束非线性规划问题。罚函数法障碍函数法罚函数法设法适当地加大不可行点处对应的目标函数值，使不可行点不能成为相应无约束极小化问题的最优解。罚函数实际应用中，选取一个