第四章 非线性规划及其应用

二、基本数学概念
2 f ( x1 , x 2 ) = 2 x12 − 8 x1 + 2 x 2 − 4 x 2 + 20 例3-1：试求 ：
极值和极值点。 极值和极值点。
二、基本数学概念
凸函数和凹函数： 凸函数和凹函数： 几何意义：函数f(X)图形上任意两点的连线都在函数图 几何意义：函数 图形上任意两点的连线都在函数图 形的上方，图形下凸， 凸函数；反之，若都在下方， 形的上方，图形下凸，为凸函数；反之，若都在下方， 图形上凸， 凹函数。 图形上凸，为凹函数。 线性函数 判定：海森矩阵正定、半正定，为凸函数； 判定：海森矩阵正定、半正定，为凸函数； 海森矩阵负定、半负定，为凹函数。 海森矩阵负定、半负定，为凹函数。
2 MinF( X ) = x12 + x2 − 4 x1 + 4
g1 ( X ) = x1 − x 2 + 2 ≥ 0
g 2 ( X ) = − x12 + x 2 − 1 ≥ 0
g 3 ( X ) = x1 ≥ 0
g 4 ( X ) = x2 ≥ 0
第二节 无约束条件的非线性规划问题
对于函数关系比较简单的非线性规划问题， 对于函数关系比较简单的非线性规划问题，可按极值 存在的必要条件和充分条件， 微分法求解 求解， 存在的必要条件和充分条件，按微分法求解，对函数 搜索法。 关系比较复杂的问题，常作搜索法 关系比较复杂的问题，常作搜索法。 直接法：爬山法、一维搜索法 直接法：爬山法、一维搜索法(0.618法)、座标轮换法 法、 解析法：梯度法、牛顿法、拟牛顿法、 解析法：梯度法、牛顿法、拟牛顿法、共轭梯度法
只有等式约束的非线性规划问题通常可用消元法、 只有等式约束的非线性规划问题通常可用消元法、拉 消元法 格朗日乘子法或罚函数法，将其化为无约束问题求解。 格朗日乘子法或罚函数法，将其化为无约束问题求解。
一、消元法
适用：易于实现消元的显函数。 适用：易于实现消元的显函数。 例3-5：设某最优化问题为： ：设某最优化问题为：
第四章 非线性规划及其应用
第一节 概述
定义：一个规划问题， 定义：一个规划问题，当其目标函数或约束条 件方程中含有一个或多个有自变量的非线性函数 时，就形成了非线性规划问题。 就形成了非线性规划问题。
第一节 概述
例：南方某圩区，地势平坦低洼，易遭涝灾，拟修建 南方某圩区，地势平坦低洼，易遭涝灾， 除涝工程。除涝工程由两种工程措施组成， 除涝工程。除涝工程由两种工程措施组成，一是利用 当地原有湖泊水库蓄存涝水， 当地原有湖泊水库蓄存涝水，即修建一定规模的湖堤 使涝水在其中蓄存某一深度； 使涝水在其中蓄存某一深度；二是在原有泵站的基础 上扩大规模，增加该地区涝水向外河排泄的能力。 上扩大规模，增加该地区涝水向外河排泄的能力。要 求决策出投资最少的除涝工程规模。 求决策出投资最少的除涝工程规模。 除涝工程规模：蓄涝湖泊面积 除涝工程规模：蓄涝湖泊面积x1(km2)、泵站装机容量 、 x2(103kw)、湖泊蓄涝水深 3(m)。 、湖泊蓄涝水深x 。
二、基本数学概念
凸集： 凸集： 维欧式空间E 设R是n维欧式空间 n的点集，若集合 中任意两点的 是 维欧式空间 的点集，若集合R中任意两点的 属于R，则称R是凸集 是凸集。 连线均 属于 ，则称 是凸集。
二、基本数学概念
梯度、海森矩阵及函数极值条件： 梯度、海森矩阵及函数极值条件： 梯度： 处可微， 梯度：若f(X)在X处可微，则f(X)对X各分量的偏导数组 在 处可微 对 各分量的偏导数组 成的n维向量称为 维向量称为~。 成的 维向量称为 。 即：
一、0.618法（黄金分割法）
基本原理 方法 结论 只要第一个点取在原始区间的0.618处，第二点在 只要第一个点取在原始区间的 处 它的对称位置上，就能保证在经多次舍弃后， 它的对称位置上，就能保证在经多次舍弃后，保留的 点始终在新区间的0.618处，区间缩短率 点始终在新区间的 处 区间缩短率E=0.618。 。
MinF ( X )
X ∈ R ⊂ En
R = {X g i ( X ) ≥ 0, i = 1,2,L, P}
假定F(X)为凸函数，gi(X)为凹函数，或-gi(X)为凸函 为凸函数， 为凹函数， 假定 为凸函数 为凹函数 为凸函 就称其为凸规划。 数，就称其为凸规划。
二、基本数学概念
凸规划 定义：非线性规划问题， 定义：非线性规划问题，若约束条件构成的可行域为 凸集，目标函数为凸函数求极小值或凹函数求极大值， 凸集，目标函数为凸函数求极小值或凹函数求极大值， 称为凸规划。 称为凸规划。
二、基本数学概念
局部最优和全局最优解： 局部最优和全局最优解： 局部最优解： 局部最优解：一部分可行域上的极值点 全局最优解： 全局最优解：整个可行域上的极值点
二、基本数学概念
凸规划 定义：非线性规划问题， 定义：非线性规划问题，若约束条件构成的可行域为 凸集，目标函数为凸函数求极小值或凹函数求极大值， 凸集，目标函数为凸函数求极小值或凹函数求极大值， 称为凸规划。 称为凸规划。
f ( xk + λk d k ) < f ( xk )
返回② ⑤ 令 xk +1 = xk + λk d k ，然后置 k = k + 1，返回②.
二、梯度法 （最陡下降法steepest descent method ）
在下降迭代算法中，搜索方向起着关键的作用， 在下降迭代算法中，搜索方向起着关键的作用， 起着关键的作用 而当搜索方向确定后，步长又是决定算法好坏的重要 而当搜索方向确定后，步长又是决定算法好坏的重要 因素. 非线性规划只含一个变量， 因素 非线性规划只含一个变量，即一维非线性规划可 以用一维搜索方法求得最优解，对于二维非线性规划， 以用一维搜索方法求得最优解，对于二维非线性规划， 可以像解线性规划那样用图形求解，也可用搜索法， 可以像解线性规划那样用图形求解，也可用搜索法， 使用搜索方法要用到梯度的概念， 使用搜索方法要用到梯度的概念，最常用的搜索方法 就是最速下降法. 就是最速下降法
，设f(X)二次连续可微。
二、梯度法 （最陡下降法steepest descent method ）
迭代法的基本步骤如下： 迭代法的基本步骤如下： ① 适当选取初始点 x0 ，令 k = 0 .
是否满足停止迭代的条件，如是， ② 检验 xk 是否满足停止迭代的条件，如是，则停 止迭代，用 xk 来近似问题的最优解，否则转至③. 止迭代， 来近似问题的最优解，否则转至③ 处的搜索方向. ③ 按某种规则确定 xk 处的搜索方向. 出发， ④ 从 xk 出发， 沿方向 d k ， 按某种方法确定步长 λk ， 使得： 使得：
∂f ( X ) ∂f ( X ) ∂f ( X ) T ∇f ( X ) = ( , ,L, ) ∂x1 ∂x 2 ∂x n
二、基本数学概念
海森矩阵：若f(X)二阶连续可微，则海森矩阵是二阶偏 海森矩阵： 二阶连续可微， 二阶连续可微 导数的对称矩阵。 导数的对称矩阵。即：
∂2 f (X ) ∂2 f (X ) ∂2 f (X ) , ,L, 2 ∂x1∂x 2 ∂x1∂x n ∂x 1 2 h11 , h12 ,L , h1n 2 2 ∂ f ( X ) , ∂ f ( X ) ,L, ∂ f ( X ) h , h ,L, h 21 22 2n 2 H ( X ) = ∂x 2 ∂x1 ∂x 2 ∂x n = ∂x 2 L L h , h ,L, h nn n1 n 2 ∂2 f (X ) ∂2 f (X ) ∂2 f (X ) ∂x ∂x , ∂x ∂x , L, ∂x 2 n 2 n n 1
二、基本数学概念
多元函数极值点存在条件： 多元函数极值点存在条件： 必要条件： 必要条件： ∇f ( X ) = 0,
∂f ( X ) ∂f ( X ) ∂f ( X ) = =L= =0 ∂x1 ∂x2 ∂xn
充分条件： 充分条件： 极小点： ①极小点： ∇f ( X ) = 0, 且H ( X )正定或半正定 ②极大点： ∇f ( X ) = 0, 且H ( X )负定或半负定 极大点：
一、0.618法（黄金分割法）
f ( x) = x 4 − 4 x 3 − 6 x 2 − 16 x + 4 例3-3：求函数 ：
在区间[-1， 上的极小点 上的极小点， 在区间 ，6]上的极小点，误差
ξ < 0.05
。
二、梯度法 （最陡下降法steepest descent method ）
梯度法：又称最陡下降法，搜索最陡梯度的方法。 梯度法：又称最陡下降法，搜索最陡梯度的方法。 设无约束条件的多变量函数最优化问题是： 设无约束条件的多变量函数最优化问题是：
二、梯度法 （最陡下降法steepest descent method ）
最速下降法（ 最速下降法（steepest descent method） ） 由法国数学家Cauchy于1847年首先提出。在每次迭代 年首先提出。 由法国数学家 于 年首先提出 沿最速下降方向（负梯度方向）进行搜索， 中，沿最速下降方向（负梯度方向）进行搜索，每步 沿负梯度方向取最优步长，因此这种方法称为最优梯 沿负梯度方向取最优步长，因此这种方法称为最优梯 度法。 度法。
MinF ( X )
X ∈ R ⊂ En
R = {X g i ( X ) ≥ 0, i = 1,2,L, P}
假定F(X)为凸函数，gi(X)为凹函数，或-gi(X)为凸函 为凸函数， 为凹函数， 假定 为凸函数 为凹函数 为凸函 就称其为凸规划。 数，就称其为凸规划。
二、基本数学概念
例3-2：验证下述规划为凸规划 ：
MaxZ = 10 x + x2 + 60
S.t