第4章非线性规化

第4章 非线性规划初论

在数学模型中:

有一个或几个函数是变量X的非线性函数, 则称这种最优化问题为非线性规划. 本章介绍非线性规划问题的基本概念和 一些基本的求解方法。

4.1非线性规划的数学模型4.1.1非线性规划的种类 1、二次规划：约束为线性，而目标函数 为二次型或二次函数

4.1非线性规划的数学模型2、几何规划：约束不等式及目标函数具有多 元多项式. 几何规划数学模型的一般形式为：

4.1非线性规划的数学模型3、最小二乘问题 ：对目标函数具有变量平方和形 式f (x) n

i 1

xi

2

的问题极小化，即求

m in f ( x )

[ F ( x )]i i 1

n

2

的极小值问题。 最小二乘问题的主要工程应用之一有曲线拟合问 题。

4.1非线性规划的数学模型最小二乘问题的数学模型为：

4.1非线性规划的数学模型4.1.2最优解的特点 1、最优解X*可能在约束集合的边界上，也可 能在可行域的内部。此种情况出现在约束为 线性，目标函数为非线性的求解问题中。如 图：

4.1非线性规划的数学模型2、最优解不一定在可行域的定点，也有可能 在可行域边界中的某点。此种情况也多出现 在约束条件为线性、目标函数为非线性时。

4.1非线性规划的数学模型3、可能存在多个极值点。此种情况常为约束 条件和目标函数均为非线性函数时。

4.2库恩-图克定理4.2.1不等式约束问题极值条件定理：对于不等式约束非线性最优化问题

g 若 f ( X ),

i

( X ) 均可微，则其极值点存在的必要条件是：

此种不等式约束非线性规划极值点的必要条件称为之为库-图定理。

4.2库恩-图克定理证明：首先，化不等式约束为等式约束，

引入一个非负标量或叫松弛变量 即使得

.

Si 0

并构造一个拉格朗日函数

4.2库恩-图克定理于是：

4.2库恩-图克定理4.2.2库-图定理的几何解释

将库-图定理中极值点必要条件1)、2)写成：

由此可表明： 目标函数负梯度可以表示为各约束函数梯度 g i ( X ) 的线性组合。即目标函数负梯度在任何可行方 向的投影为零，或者说目标函数负梯度一定在 各约束函数梯度 g ( X ) 组成的锥体内。x

4.2库恩-图克定理这种几何解释可从以下 具体情况给予证实： 1、无约束时在这种情况下，如图 极值点： f ( X ) 0

f ( X ) 0

gi i 1

m

i

(X ) 0

gi i 1

m

i

(X ) 0

这时，

i

0,

f xi

0

4.2库恩-图克定理2、只有一个不等式约束时如图，此种情况下 A点：不是最优点，因为 沿可行方向不为零； B点：为最优点，因为 f ( X 与 共线(共向),既有) g(X ) f ( X ) xi

g ( X ) x j f ( X )

j=1,2,3

f ( X ) g ( X )

4.2库恩-图克定理3、有两个不等式约束时若极小点在可行域内部，则同情况1; 若极小点在可行域边界上，则同情况2; 若极值点在两个约束的交点上，即 f ( X )

此时，有两种可能： 当 f ( X ) 在 g 1 ( X ) 与 g 2 ( X ) 之内时，则 A点为极值点，如上图。 当 f ( X )在 g ( X ) 与 g 2 ( X ) 之夹角范围 之外时，则A点部为极值点，如下图。1