系数排列成一个矩阵
a11 a12
A
a21 an1
a22 an2
a1n a2n ann
二次型矩阵
因为aij ajiA是一个对称矩阵.
二次型矩阵都是对称矩阵
令 x(x1,x2,,xn)T
二次型就可以用矩阵的乘积表示出来
nn
f ( x 1 , x 2 , , x n )
，
g1(
x（1）)＝
1 0
，
g
2
(
x（1）)＝
－1
1
设
－04－w1
10－w2
－1
1
0 0
解此方程组，得w1＝－4，w2＝0。
由于w1 0,故不是KKT点。
再 验 证 x ( 2 ) , 在 这 一 点 ， g 1 ( x ) 0 ， g 2 ( x ) 0 都 是 起 作 用 约 束 目 标 函 数 和 约 束 函 数 的 梯 度 分 别 是 :
,
2
f'(x
(2)）＝02
0 2
2
f'(x
(3)）＝
2 0
0 2
,
2
f'(x
(4)）＝02
0 2
由于2f'(x(1)）, 2f'(x(3)）,2f'(x(4)）不定或负定，仅2f'(x(2) )正定，
故x(2)=
1 2
是局部极小点。
设 f(x ) x 1 2 x 3 2 2 x 3 2 2 x 2x 3 x 2 x 3
二次型 f(x1,x2,,xn)如果对于任意一组不全为零的 实数 c1,c2,,cn都有 f(c1,c2, ,cn)0 就称为正定的.
A是一个实对称矩阵, 如果 实二次型
xT Ax
是正定的, 则A称为正定矩阵.
设f(x1,x2,,xn)是一个实二次型, 如果对于任意一
组不全为零的实数 c1,c2,,cn, 都有 f(c1,c2, ,cn)0
三元二次型
二次型的矩阵表示
令 aij aji(ij)因为 xixj xjxi
二次型可以写成
f (x1, x2, , xn) a11x121 a12x1x2 a1nx1xn
a21x2x1 a22x22 a2nx2xn an1xnx1
an2xnx2 annxn2
nn
aijxi xj
i1 j1
就称 f(x1,x2,,xn)是负定的.
如果对于任意一组实数c1,c2,,cn, 都有
f(c1,c2, ,cn)0, 就称f(x1,x2,,xn)是半正定的.
如果对于任意一组实数 c1,c2,,cn, 都有 f(c1,c2, ,cn)0, 就称 f(x1,x2,,xn)是半负定的.
如果 f(x1,x2,,xn)即不是半正定的, 也不是半负定 的, 就称它是不定的.
a ij x i x j
i1 j1
n
a1jx j
j1
n
x1, x2 ,
,xn
a2jx j
j1
n
a
nj
x
j
j1
a11 a12
x1, x2, , xn aa 2n11
a22 an2
xT Ax
a1n x1 a2n x2 a nnxn
即为 f(x1,x2, ,xn)xTAx
L ( x , w , v ) x 1 w [ 3 ( x 1 3 ) 2 x 2 ] v [ ( x 1 3 ) 2 x 2 2 1 0 ]
Lagrange函数关于x的Hessian矩阵是
2xL6w02v
0 2v
检查x(1) : 是可行点，且两约束都是起作用约束。
f
(
x(1)
)
1 0,g
解： 先求平稳点
f
(x)
44xx21
8 4
0
平稳点为 x*＝[2, 1]T
Hesse矩阵为
2
f
(x*)
4 0
0 4
x*＝[2, 1]T是f(x)的严格极小点，f(x*)=10
例：利用极值条件解下列问题
mf( i x ) n ( x 1 2 1 ) 2 x 1 2 x 2 2 2 x 1
解：先求驻点， 由于
设A是实对称矩阵, 如果二次型xT Ax 是负定 的, 就称A是负定的；
如果xT Ax是半正定的或半负定的, 就称A是 半正定的或半负定的.
二次函数
二次函数
q(x) 1 xT Gx bT x c 2
1 2
i,
n
xi
j 1
Gij
x
j
n i1
bi x j
c
其中
G11 G12 G G21 G22
第一章习题课
二次型
n个变量的二次齐次多项式
f(x 1 ,x 2 , ,x n ) a 1x 1 2 2 a 1x 2 1 x 2 2 a 1 n x 1 x n a 2x 2 2 2 2 a 2 n x 2 x n a nx n n 2
称为一个n元二次型, 简称二次型
x 1 2 2 x 1 x 2 3 x 1 x 3 x 2 2 5 x 2 x 3 2 x 3 2
(
x(1)
)
－6
1
,
h( x (1)
)
－2 －6
按照KKT条件，设
10－w －16
v
－2 －6
0
w
3 19
.v
1 38
不存在使w 0的解，故它不是KKT点.
检 查 x(2) : 是 可 行 点 ， 且 两 约 束 都 是 起 作 用 约 束 。
f
( x (2) )
1 0
,
g
(
x
(
2
)
Gn1 Gn2
G1n
G2n
Gnn
在代数学中将特殊的二次函数 f (x) 1xTGx称为二次型
2
Hesse矩阵
设f(x1,x2,,xn)所有的二阶导数都存在, 那么f 的 Hesse矩阵即
2 f
x12
2 f
H
(
f
)
x 2 x1
2 f
x
n
x1
2 f
x1x2
2 f
x
2 2
)
6 1
,
h
(
x
(1
)
)
2
－
6
按 照 KKT条 件 ， 设
1 0
－
w
6 1
2
v
－
6
0
w
3 .v 19
1 38
故 它 是 KKT点 ,此 点 Lagrange函 数 的 Hessian矩 阵 为 ：
1
2 x
L
(
x
(
2
)
,
w
,
v
)
0
0
1
19
2f x32
62x1
所以
2f(x)12x122x12x2 2x3
2x1 12x2
4
2x3 4
62x1
即为Hesse矩阵
f (x*) 0 以及 2 f (x*) 是正定(负定)的，
则x*是f(x) 的一个严格的局部最小(大)点。
例 求f(x1,x2)=2x12－8x1+2x22－4x2+20的极值点及极值
f(x （ 2 ） ) ＝ － 2 2 ， g 1 (x （ 2 ） ) ＝ 1 2 ， g 2 (x （ 2 ） ) ＝ － 1 1
设
－22－w1
－12－w2
－1
1
0 0
解此方程组，得w1＝0，w2＝2。
故它是KKT点。
例 考虑下列非线性规划问题 min x1 s.t.3( x1 3)2 x2 0 ( x1 3)2 x22 10 0
目标函数和约束函数的梯度是
f
(
x )＝
2( x1 2 x2
2
)
，
g1
(
x )＝
1 － 2
x2
，
g
2
(
x )＝
－1
1
先 验 证 x (1) .在 这 一 点 ，g1 ( x) 0， g 2 ( x) 0都 是 起 作 用 约 束
目标函数和约束函数的梯度分别是
f
(
x（1）)＝
－ 4
0
f x1
4x13
2x1
2, f x2
2x2
令f'(x)=0,即4x13 2x1 2 0，2x2＝0
解得驻点x*=(1,0)
又Hessian阵2f'(x）＝12x102－2
0 2
2f'(x*）＝100
0 2
正定，故x*=(1,0) 是局部极小点。
利用极值条件解下列问题：
min f(x)1 3x1 31 3x2 3x2 2x1
解：先求驻点， 由于
f x1
x12
1, f x2
x22
2x2
令f'(x)=0,即12 1＝0, x22 2x2 0
解得驻点x(1)=10 , x(2)=12 , x(3)=-01 ,x(4)=-21
又Hessian阵2
f'(x）＝
2x1 0
0 2x2－2
2f'(x(1)）＝02
0 2
检验以下各点是否为局部最优解
x (1 ) 2 3 ,x (2 ) 4 3 ,x (3 ) 3 0 1 0 x (4 ) 3 0 1 0
记目标函数和约束函数分别为f(x),g(x),h(x),他们在 点x处的梯度分别是 f(x ) 1 0 , g (x ) 6 (x 1 1 3 ) , h (x ) 2 (x 2 1 x 2 3 ) Lagrange函数是