数学建模 非线性规划(xin)

数学建模 非线性规划(xin)

非线性规划 (Nonlinear Programming)第一章 一般的非线性规划问题§1.1 问题概论

(模型) min s .t

f (x)

g i ( x ) 0, i 1,..., m h j ( x ) 0, j 1,..., n1

数学建模 非线性规划(xin)

(两类问题)无约束极值问题与约束极值问题

(一些基本定义)梯度

df df T f ( x) ( ,..., ) dx1 dxn

Hesse矩阵

H ( x)

f11 f m1

f1n f mn

Jaccobi矩阵

f1T F ( x ) f T n 2

数学建模 非线性规划(xin)

§ 1.2 最优解分类 (注：不一定存在)

定义1.2.1 整体(全局)最优解 定义1.2.2 局部最优解 (已有算法基本都是求局部 最优解的)§ 1.3 凸集与凸函数 定义1.3.1 凸集 定义1.3.2 (严格)凸函数 称定义在凸集K上的实值 ，有： 函数f (x)为凸函数，若 x1,x2 K及 01 f ( x1 (1 ) x2 ) f ( x1 ) (1 ) f ( x2 ) 定义1.3.3 凹函数3

数学建模 非线性规划(xin)

定义1.3.4 凸规划(图集上凸函数的极小化问题)

K 定理1.3.1 设 K1 、 2 均为凸集，则K1 K2 也是凸 集 ，对任意实数ß, K1 是凸集。 (证明)(推广)定理1.3.2 有限个凸集的交集必是凸集

y 定理1.3.3 (分离定理)K为闭凸集， K 则

p 0,p y min p x / x K T T

定理1.3.4 (支撑超平面定理)4

数学建模 非线性规划(xin)

定理1.3.5 若

i 0,(i=1, , r )

f1 ( x), ,fr ( x)

均为凸集K上的凸函数，则

i 1

r

i

f i ( x)

也是K上的凸函数。

(请证明)

定理1.3.6 设f (x)是凸集K上的凸函数，则

{x k / f ( x) C}必为凸集。 (请证明)

实数C,水平集

定理1.3.7 若f (x) 在开集K 中可微，则f 是K上的(严格) 凸函数当且仅当

x, y K , 均有 f ( x) f ( y) f ( x)T ( x y)5

数学建模 非线性规划(xin)

证明(充分性) x, y K 任取 0,1 ,记 z x (1 ) y, 则z K 由条件， T T

f ( x) f ( z) f ( z) ( x z) f ( z) (1 ) f ( z) ( x y)

f ( y) f ( z) f ( z)T ( y z) f ( z) f ( z)T ( x y)

第一式乘以 ,第二式乘以( ),相加得 1 f ( x) (1 ) f ( y) f ( z ) f ( x (1 ) y) 故f ( x)为凸函数(必要性)

x, y K , (0,1),由f ( x)凸，可得 f ( x (1 ) y ) f ( x) (1 ) f ( y ) f ( y ) ( f ( x) f ( y )) 故 f ( x (1 ) y ) f ( y ) f ( x) f ( y )6

数学建模 非线性规划(xin)

0 , 得: f ( x)T ( x y) f ( x) f ( y) 令 此即需证。 若 f (x) 两阶可微，则有以下的定理：定理1.3.8 设f (x)在开凸集K中二阶连续可微，f 为凸函数的 充要条件为： x K , f ( x)在x处的Hesse矩阵H(x)在Rn中半正定，即

y H ( x) y 0T

x K , y Rn

证明：(充分性) x

, y K ,由f ( x)的二阶可微性得1 f ( x) f ( y ) f ( y )T ( x y ) ( x y )T H ( y ( x y ))( x y ) 27

数学建模 非线性规划(xin)

此处 (0,1),因为K为凸集，故有y ( x y) K 从而，H ( y ( x y)) 在R n中半正定，故：f ( x) f ( y) f ( y)T ( x y)

(必要性) n 任取 x K , z R ,因为K是开集，故存在 0,

使当 (0, )时，x z K ) 将 f ( x z在 x 处展开 ：f ( x z ) f ( x) f ( x)T z

22

z T H ( x ) z o( 2 )

数学建模 非线性规划(xin)

f ( x) f ( x)T z

2

2 zT H ( x) z 0 令 0 得 定理1.3.9

z T H ( x ) z o ( 2 )

f ( x)在开凸集中二阶连续可微，若 x K , Hesse 矩阵在Rn上正定，则f ( x)是严格凸函数。 x, y K , x y,由假设

证明

1 f ( x) f ( y ) f ( y )T ( x y ) ( x y )T H ( y ( x y ))( x y ) 2 f ( y ) f ( y ) T ( x y )9

数学建模 非线性规划(xin)

此即说明f 是严格凸函数。 定理1.3.10 f ( x)是凸集K 上的凸函数，则f ( x)在K中的

任一局部最优解都是它的整体最优解。证明

x*是一局部最优解但非整体最优解，则 x R, 使 f ( x ) f ( x* ) 0, ( 1),由于f ( x)是凸函数，可得： f ( x (1 ) x* ) f ( x) (1 ) f ( x* ) f ( x* )

* 当 充分小时 x (1 ) x 在

盾，证毕

x

*

的邻域中，从而导出矛

数学建模 非线性规划(xin)

§1.4 最优性条件 无约束极小化问题(模型) min f ( x ) s .t x Rn(1.4.1)*

定理1.4.1 (一阶必要条件)若 f ( x) 是可微函数，x 是问题(1.4.1) 的一个局部最小点的必要条件为： f ( x) 0 (无约束极小化问题求解)等价于(方程组求解)

hp ( x ) 0, p 1, , t*

min hp x p 1

t

2

定理1.4.2 (二阶必要条件)设

Rn f ( x) 为

中的二阶连续可微函

数，如果 x* 是 f ( x) 的一个局部极小点，则11

数学建模 非线性规划(xin)

f ( x* ) 0 y T H ( x* ) y 0证明：由定理1.4.1, f ( x* ) 0 。对任意的

y Rn , 根据泰勒公式有f ( x* y ) f ( x * )

22

y T H ( x* ) y o( 2 )

x*是局部极小点，故对于充分小的 必有 由于f ( x* ) f ( x* y)yT H ( x* ) y ,证毕。 0 此式成立必须有

数学建模 非线性规划(xin)

定理1.4.3 (二阶充分条件)设 f ( x) 两阶可微，若 x 满足 f ( x ) 0且yT F ( x ) y 0, y Rn , y 0则点 x 是f ( x) 的一个严格局部极小点，这里F ( x) 是 f ( x)的两阶 Hesse矩阵 f ( x) 两阶连续可微，若 x 满足 定理1.4.4(两阶充分条件)设

f ( x ) 0, 且存在x 的一个邻域V ( x ),使得 y Rn , x V ( x )有

yT H ( x) y 0, 则x 必为f ( x)的局部极小点。1 x V ( x ),

由f ( x) f ( x ) ( x x )T H ( x ( x x ))( x x ) 证明：任取 2

f 显然， ( x x ) V ( x ) 由假设， ( x) f ( x ),由 x性，x 是

x

的任意

f ( x)的局部极小点，证毕。13

数学建模 非线性规划(xin)

定理1.4.5

若f ( x)是Rn上的凸函数，则f ( x)的任意局部极小点均为整体最小解

证: 设x 是f ( x)的任意局部极小点， x R n ,由凸函数性质 f ( x) f ( x ) f ( x )T ( x x ) 0, 此即说明 x 是f ( x)的整体极小点。证毕

数学建模 非线性规划(xin)

具有等式与不等式约束的极小化问题 (NP) min f ( x) s .t

g ( x) 0 h( x ) 0

定义 1.4.1 设x是满足(NP)约束条件的点，记

I ( x) i g i ( x) 0, i 1, , m

称I 为x处不等式约束中的积极约束的下标集合 定义1.4.2 (积极约束) 称约束 为x处的积极约束

gi ( x) 0, i I ( x); hp ( x) 0, p 1 , t

定义1.4.3 (正则点)若向量组 gi ( x) 0, i I ( x); hp ( x) 0, p 1 , t 线性无关，则称x为约束条件的一个正则点。15

数学建模 非线性规划(xin)

定理1.4.5 (Kuhn-Tucker条件)设

x

是(NP)的局部极小点且T

x 是约束的正则点，则必存在乘子矢量 1, ,n ) 和 u (u1 , , u n )T ( 其中 0, 使得 x , 和 u 满足

f ( x) i gi ( x) u p hp ( x) 0i 1 p 1

m

t

i gi ( x) 0, i 1, , m i 0, i 1, , mgi ( x) 0, i 1, , m hp ( x) 0, p 1, , t

数学建模 非线性规划(xin)

例 求下面问题的 K-T 点min s .t2 x12 x2 6x1 6x2 18

x1 x2 4

x1 0, x2 0

解：本问题的 K-T条件为

2 x1 6 1 2 0 2 x2 6 1 3 0

1 ( x1 x2 4) 0 2 x1 0, 3 x2 0x1 x2 4

1 , 2 , 3 0;x1 , x2 017

数学建模 非线性规划(xin)

(1) x1 0, 则上述条件化为

1 2 6 1 3 6 2 x2 1 ( x2 4) 0, 3 x2 0 0 x2 4; 1 , 2 , 3 0若 若

x2 4 3 0 1 2 (舍去)0 x2 4 1 0 2 6 (舍去)

(2)x2 0 1 0 2 6

(舍去)

(3) x1 0且 x2 0, K T 条件化为

数学建模 非线性规划(xin)

2 3 02 1 (2 1 ) 0 2 1 6 x1 x2 3

1

x (2, 2)T 故有 1 2 x1 x2 2 求得

数学建模 非线性规划(xin)

§1.5迭代算法

迭代算法及收敛速度

记满足要求的点集为 (如 K-T 点集，最优解集等)。算法一般 采用迭代方法，即：任给一个初始点 0

x , 令k : 0

步1 步2

若xk 停 ； 否则,求一改进点 xk 1 A( xk )

k : k 1, 返回步1

定义1.5.1 (全局收敛性)设A是求解问题的一个算法，若对任意初始 点 x 0 在用算法A进行迭代时，或能在有限

步求得最优解，或求 得一无穷点列 x k , k 1, ,该点列的任意聚点均为需求的点。

数学建模 非线性规划(xin)

例1 求解问题 min s .t

xn x 1A( x) 1 ( x 1) 2

算法 迭代点列

x

0

x k 1

例2 求解 min

x , x E

1 k 1 1 1 1 ( x 1) k 1 k 1 1 1 2 2 2 2 2

算法

1 2 ( x 1), 当x 1 A( x) 1 x , 当x 1 2 21

本文来源：https://www.bwwdw.com/article/2ai4.html