运筹学-第3版-课件-第4章-非线性规划

1、第4章 非线性规划,Non-linear Programming,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 基本概念,向量化表示,4.1 基本概念,最优解和极小点,4.1 基本概念,最优解和极小点,4.1 基本概念,2. 非线性规划方法概述：,4.1 基本概念,基本迭代格

2、式,4.1 基本概念,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.凸规划的性质：,4.3 一维搜索方法,精确一

3、维搜索方法： 0.618法， Newton法 非精确一维搜索方法： Goldstein法， Armijo法,1. 0.618法（近似黄金分割法）,4.3 一维搜索方法,2. Newton法,4.3 一维搜索方法,3. Goldstein法,4.3 一维搜索方法,Goldstein法步骤:,4.3 一维搜索方法,4. Armijo法,4.3 一维搜索方法,4.4 无约束最优化方法,无约束问题的最优性条件 最速下降法 共轭方向法,1、无约束问题的最优化条件,4.4 无约束最优化方法,4.4 无约束最优化方法,1、无约束问题的最优化条件,2. 最速下降法（又称梯度法）,4.4 无约束最优化方法,4.

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