9299.net
大学生考试网 让学习变简单
当前位置:首页 >> >>

第2章 优化设计的数学基础_图文

第2章 优化设计的数学基础_图文

第2章

优化设计的 数学基础

Ⅱ Math Foundation of Optimal Design

第2章

优化设计的数学基础
内容简介

优化设计是以数学规划论为理论基础,以计算机为工具的一 种现代设计方法。优化设计问题大多是多变量有约束的非线性规 划问题,其数学本质是求解多变量非线性函数的极值问题。 因此,本章将介绍与此有关的一些数学基础知识。主要介绍 的内容如下:
■ 二次型与正定矩阵

■ 函数的方向导数与梯度
■ 函数的泰勒近似展开式和黑塞矩阵 ■ 无约束优化问题的极值条件 ■ 凸函数与凸规划 ■

约束优化问题的极值条件

2.1 二次型与正定矩阵
在介绍优化方法时,常常是将二次型函数作为对象。其原因除了 二次型函数在工程优化问题中有较多的应用且比较简单之外,还因为 任何一个复杂的多元函数都可采用泰勒二次展开式做局部逼近,使复 杂函数简化为二次函数。因此,需要讨论有关二次型函数的问题。

1. 二次型函数
所谓二次型函数是指含有 n 个实变量 x1,x2,…,xn的一个二次 齐次多项式函数,其表达式为
2 f ( X ) ? a11 x12 ? a12 x1 x2 ? ? ? a1n x1 xn ? a21 x2 x1 ? a22 x2 ? ? ? a2 n x2 xn ? n n

? ? an1 xn x1 ? an 2 xn x2 ? ? ? a x ? ?? aij xi x j
2 nn n i ?1 j ?1

(2-1)

式中,aij (i,j = 1, 2, …, n)——给定的实常数,称为二次型的系数。

上式经化简,可写成矩阵形式
f ( X ) ? x1 (a11 x1 ? a12 x2 ? ? ? a1n xn ) ? x2 (a21 x1 ? a22 x2 ? ? ? a2 n xn ) ? ? ? xn (an1 x1 ? an 2 x2 ? ? ? ann xn ) ? a11 a12 ? a1n ? ? xi ? ?a a ? a ? ? x ? 2n ? ? i ? ? ? x1 , x2 , ?, xn ? ? 21 22 ? ? ? ? ? ? ?? ? ? ? ? ?? ? ? an1 an 2 ? ann ? ? xi ?
? xi ? ?x ? ? ? X ? ? i ?, ?? ? ? xi ? ? ?
? a11 a12 ? a1n ? ?a a ? a ? 2n ? A ? ? 21 22 ?? ? ? ? ? ? ? an1 an 2 ? ann ? ?

(2-2a)

若令

则式(2-2a)可简记为
f ( X ) ? X T AX

(2-2b)

式中,矩阵A 是由函数 f (X) 中各项所含系数所组成的 n×n 阶矩阵。 若式中 aij = aji ( i, j = 1, 2, …, n)为常系数,则称式(2-1)和式(22a)为二次型函数或简称实二次型。

A 称为二次型矩阵,因为 aij = aji ,所以 A =AT,称为对称矩阵,
因此二次型矩阵都是对称矩阵。

2. 正定矩阵
在采用泰勒二次近似展开式讨论函数的极值时,常要分析二次型 函数是否正定或负定。二次型的正定与负定的定义简述如下: 如果对于任意的非零向量 X = [x1, x2, …,xn]T,即x1,x2,…,xn 不全为零,若有 XTAX > 0,则称此二次型 f (X)=XTAX 是正定二次 型, 其对应的矩阵A 称为正定矩阵; 若有 XTAX ≥0,则称此二次型 f (X) = XTAX 为半正定二次型,并称 其相应的矩阵A为半正定矩阵; 若有XTAX < 0,则称此二次型 f (X)=XTAX 为负定二次型,其对应 的矩阵A为负定矩阵。 矩阵A的正定与负定的判别,可用矩阵A的各阶顺序主子式的正负 来判别。矩阵A的正定条件是:

a11 a12 ? a1n a11 ? 0, a11 a12 a21 a22 ? 0, ?, a21 a22 ? a2 n ? ? ? ? an1 an 2 ? ann ?0

即矩阵A的各阶主子式均大于零。当矩阵A为正定时,其对应的二次型 为正定二次型。 如果实二次型 XTAX 中的矩阵A的各阶主子式负、正相间(即所 有奇数阶主子式小于零,而所有偶数阶主子式大于零),即
a11 a12 a21 a22 a11 a12 a13 ? 0, a21 a22 a23 ? 0, (-1) n a31 a32 a33 a11 a12 ? a1n a21 a22 ? a2 n ? ? ? ? an1 an 2 ? ann ?0

a11 ? 0,

则该矩阵 A为负定矩阵,其对应的二次型为负定二次型。

2.2 函数的方向导数与梯度
目标函数的等值线(或面)仅从几何方面定性直观的表示出函数 的变化规律。这种表示方法虽然直观,但不能定量表示,且多数只限 于二元函数。为了能够定量地表明函数特别是多元函数在某一点的变 化形态,需要引出函数的方向导数及梯度的概念。

1. 函数的方向导数
由多元函数的微分学可知,对于一个连续可微函数 f (X)在某一点 X (k)的一阶偏导数为
?f ( X ( k ) ) ?f ( X ( k ) ) ?f ( X ( k ) ) , , ?, ?x1 ?x2 ?xn

(2-3)

可简记为

?f ( X ( k ) ) , ?xi

i ? 1, 2,?n

它描述了该函数 f (X)在 X (k) 沿各坐标轴这一特定方向的变化率。 现以二元函数 f (x1,x2) 为例,求其沿任一方向 S(它与各坐标 轴之间的夹角为α1,α2,见图2-1)的函数变化率。 设该二元函数由 X ( k ) ? [ x( k ) , x( k ) ] 1 2 沿方向 S 变化到点
( ( X ( k ?1) ? [ x1 k ) ? ?x1, x2k ) ? ?x2 ] ,

则当 X (k) 至 X (k+1) 的距离
2 X ( k ) X ( k ?1) ? ? ? ?X ? (?x12 ? ?x2 )1/ 2

图2-1

函数的变化率

为无限小时,函数的增量与 X ( k ) X ( k ?1) 的比值,称为该二元函数 f (x1, x2) 在 点 X (k) 沿方向 S 的方向导数,记为

?f ( X ( k ) ) f ( X ( k ?1) ) ? f ( X ( k ) ) ? lim ? ?0 ?S ? ? lim
? ?0
( ( f ( x1( k ) ? ?x1 , x2k ) ? ?x2 ) ? f ( x1( k ) , x2k ) )

?

( ( f ( x1( k ) ? ?x1 , x2k ) ? ?x2 ) ? f ( x1( k ) , x2k ) ? ?x2 ) ?x1 ? lim [ ? ?x1 ?0 ?x1 ? ?x ? 0
2

( ( f ( x1( k ) , x2k ) ? ?x2 ) ? f ( x1( k ) , x2k ) ) ?x2 ? ? ] ?x2 ?

?f ( X ( k ) ) ?f ( X ( k ) ) ? ? cos ?1 ? ? cos ? 2 ?x1 ?x2


?f ( X ( k ) ) ?f ( X ( k ) ) ?f ( X ( k ) ) ? ? cos ?1 ? ? cos ? 2 ?S ?x1 ?x2

(2-5)

对于n 维函数,可以仿此推导得函数 f (X)在点 X (k) 沿方向 S 的 方向导数为
?f ( X ( k ) ) ?f ( X ( k ) ) ?f ( X ( k ) ) ?f ( X ( k ) ) ? ? cos ?1 ? ? cos ? 2 ? ? ? ? cos ? n ?S ?x1 ?x2 ?xn ?f ( X ( k ) ) ?? ? cos ? i ?xi i ?1
n

(2-6)

?f ( X ( k ) ) 式中, ?xi

—— 为函数 f (X)对坐标轴 xi 的偏导数;

cos? i ——为 S 方向的方向余弦。

由式(2-5)可知,在同一点(如 X (k) 点),沿不同的方向(α1或α2 不同),函数的方向导数值是不等的,也就是表明函数沿不同的方向 上有不同的变化率。 因此,方向导数是函数在某点沿给定方向的变化率。

2. 函数的梯度
函数在某一确定点沿不同方向的变化率是不同的。为求得函数在 点X (k) 的方向导数为最大的方向,需引入梯度的概念。 将式(2-5)写成矩阵形式,则有
?f ( X ( k ) ) ?f ( X ( k ) ) ?f ( X ( k ) ) ? ? cos ?1 ? ? cos ? 2 ?S ?x1 ?x2 ? ?f ( X ( k ) ) ?? ? ?x1 ?f ( X ( k ) ) ? ?cos ?1 ? ?? ? ?x2 ? ?cos ? 2 ?

若令
? ?f ( X ( k ) ) ? ? ?x ? 1 ?, ?f ( X ( k ) ) ? ? ? ?f ( X ( k ) ) ? ? ? ?x2 ? ? ?cos ?1 ? S?? ? ?cos ? 2 ?

(2-7)

?f ( X ( k ) ) 于是,可将方向导数 表示为 ?S

?f ( X ( k ) ) ? ?f ( X ( k ) )T ? S ? ?f ( X ( k ) ) ? S ? cos ? ?S

(2-8)

式中,?f ( X ( k ) ) 和 S 分别为向量 ?f ( X (k ) ) 和向量 S 的模,其值为
? 2 ? ?f ( X ( k ) ) ? 2 ? ?f ( X ( k ) ) ? ? ? ? ? ? ? i ?1 ? ?xi ? ? ? ?
? 2 2? S ? ? ? ? cos ? i ? ? ? i ?1 ?
1/ 2

1/ 2

(2-9)



?1

(2-10)

式中,θ——为向量和 S 之间的夹角。

由式(2-8)可以看出,由于一1≤cosθ≤1,故当 cosθ=1,即向量
?f ( X
(k )

) 与 S 的方向相同时,方向导数

?f ( X ( k ) ) 最大,其值为 ?f ( X ( k ) ) ?S



这表明向量 ?f ( X (k ) ) 就是点X (k) 处的方向导数最大的方向,即函数变化 率最大的方向,称 ?f ( X (k ) ) 为函数在该点的梯度,记作 grad f ( X ( k ) ) 。

同理,上述梯度的概念可以推广到多元函数中去,对于n元函数 f ( x1 , x2 ,?, xn ) 在某点 X (k) 的梯度及梯度的模可写为
? ?f ( X ( k ) ) ?f ( X ( k ) ) ?f ( X ( k ) ) ? (k ) ?f ( X ) ? ? , ,?, ? ?x1 ?x2 ?xn ? ?
T

(2-11)
1/ 2

2 ?? ?f ( X ( k ) ) ? 2 ? ?f ( X ( k ) ) ? 2 ? ?f ( X ( k ) ) ? ? ?f ( X ( k ) ) ? ? ? ? ? ? ?? ? ??? ? ?? ?x1 ? ? ?x2 ? ? ?xn ? ? ? ?

(2-12)

函数的梯度 ?f (X )在优化设计中有着十分重要的作用。 由于梯度是一个向量,而梯度方向是函数具有最大变化率的方向。 亦即梯度 ?f (X )方向是函数 f (X) 的最速上升方向,而负梯度 ? ?f (X ) 则为函数 f (X) 的最速下降方向。
梯度向量 ?f ( X (k ) )与过点X (k) 的等值线(或等值面)的切线是正交 (垂直)的,如图2-2、图2-3所示。所以,函数 f (X) 在给定点X (k)的梯 度向量是函数等值线或等值面在该点X (k)的法线方向。

图2-2 梯度方向与等值线的关系

图2-3 梯度向量与等值面的关系

2.3 函数的泰勒近似展开式和黑塞矩阵
在最优化方法的讨论中,为研究复杂函数极值问题的方便,常将 目标函数(或约束函数)展成泰勒近似多项式。其中最常用的是泰勒 二次近似式。 设 n 维目标函数 f (X)在X (k)点至少有二阶连续的偏导数,则在这 一点邻近的泰勒二次近似展开式并写成矩阵形式时有
f ( X ) ? f ( X ( k ) ) ? ? ?f ( X ( k ) ) ? ? X ? X ( k ) ? ? ? ? ? T 1 ? ? X ? X (k ) ? ?2 f ( X (k ) ) ? X ? X (k ) ? ? ? ? 2?
T

(2-13)

式(2-13)称为函数 f (X)的泰勒二次近似式。 其中,?f ( X (k ) ) 是函数 f (X)在点X (k)的梯度; ?2 f ( X ( k ) ) 是由函数 f (X)在点X (k) 的所有二阶偏导数组成的矩阵,称 函数 f (X)在点X (k)的二阶导数矩阵或黑塞(Hessian)矩阵,记作H (X (k) )。 该二阶导数矩阵的组成形式如下:

? ?2 f ( X (k ) ) ?2 f ( X (k ) ) ?2 f ( X (k ) ) ? ? ? ?x 2 ?x1?x2 ?x1?xn ? 1 ? ? 2 (k ) 2 (k ) 2 (k ) ? ?? f (X ) ? f (X ) ? f (X ) ? ? ? 2 ? 2 f ( X ( k ) ) ? H ( X ( k ) ) ? ? ?x2?x1 ?x2 ?x2?xn ? ? ? ? ? ? ? ? ? 2 (k ) 2 (k ) 2 (k ) ?? f (X ) ? f (X ) ? f (X )? ? ? ?x ?x ? 2 ?xn ?x2 ?xn n 1 ? ?

(2-14) 黑塞矩阵 H (X (k)) 是由目标函数 f (X) 在点 X (k) 处的二阶偏导数组 成的 n ×n 阶对称矩阵。

2.4 无约束优化问题的极值条件
求解无约束优化问题的实质是求解目标函数 f (X)在 n 维空间 Rn 中的极值,因而有必要讨论无约束优化问题的极值条件。 由高等数学可知,任何一个单值、连续并可微的一元函数 f (X) ,在 给定区间内的一点X (*)有极值,其必要条件为
f ' ( X (*) ) ? 0

(2-15)

仅满足此条件只表明该点是个驻点,尚不能肯定为极值点,即使 是极值点也还不能断定是极小点还是极大点,因此还需用函数在该点 的二阶导数来判断。 驻点为极值点的充分条件为:对应的二阶导数不等于零,且若 f ' ' ( X (*) ) > 0,则点为极小点;若 f ' ' ( X (*) ) < 0,则点为极大点。

(*) 同理,对于二元函数 f (X) = f (x1, x2)来说,在点 X (*) ? x1(*) , x2 取得极值的必要条件是

?

?

T

?f ( X (*) ) ? 0, ?x1

?f ( X (*) ) ?0 ?x2

写成矩阵形式,即
? ?f ( X (*) ) ?f ( X (*) ) ? (*) ?f ( X ) ? ? , ? ?0 ?x2 ? ? ?x1
T

(2-16)

(*) 点 X (*) ? ?x1(*) , x2 ?T 作泰勒二次近似展开,得到二次近似表达式为

为推得二元函数极值存在的充分条件,将二元函数 f (x1, x2)在驻

f ( X ) ? f ( X (*) ) ? ??f ( X (*) ) ? ( X ? X (*) ) ? ? ?

T

T 1 ? X ? X (*) ? H ( X (*) )( X ? X (*) ) ? 2?

因为驻点满足 ?f ( X (*) ) ? 0 的条件,故由上式可得

f ( X ) ? f ( X (*) ) ?

T 1 ? X ? X (*) ? H ( X (*) )( X ? X (*) ) ? 2?
T

(*) 若 f (x1, x2) 在点 X (*) ? ? x1(*) , x2 ? 处取得极小值,则要求在点附 ? ? 近的一切 X 均满足条件

(*) f ( X ) ? f ( X (*) ) ? f ( x1, x2 ) ? f ( x1(*) , x2 ) >0

依据这一条件,应有
T 1 ? X ? X (*) ? H ( X (*) )( X ? X (*) ) ? 0 ? 2?

此时,X(*)为极小点。为使上式成立,根据二次型的理论可知,只要 函数的二阶偏导数矩阵 ?2 f ( X (*) )(即黑塞矩阵H(X(*)))必须是正定 矩阵。

由此可得,二元函数 f (x1,x2) 在点 X(*) 取得极小值的充分条件是: 函数 f (x1,x2) 在点 X(*) 处的二阶导数矩阵(即黑塞矩阵H(X(*)))为 正定。 同理,函数在 X(*) 处取得极大值的充分条件是: 函数 f (x1,x2) 在点 X(*) 处的黑塞矩阵 H(X(*)) 为负定。
(*) (*) 即多元函数 f (x1,x2,…,xn) 在点 X (*) ? ?x1(*) , x 2 ,? , x n ? 取得极 小值的充分必要条件是: T

上述结论可推广至多元函数的极值问题。

函数 f (X) 在该点的梯度为零,二阶偏导数矩阵(即黑塞矩阵 H(X(*)))为正定,即
?f ( X (*) ) ? 0

(2-17) (2-18)

H(X(*))正定

(*) (*) 同理,多元函数 f (x1,x2,…,xn) 在点 X (*) ? ?x1(*) , x 2 , ? , x n ? 取得极大值的充分必要条件是:

T

函数 f (X)在该点的梯度为零,二阶偏导数矩阵为负定。

2.5 凸函数与凸规划
由于一个函数的极小点(局部极值点)并不是唯一的,而优化问题 总是期望能获得函数的全域最小点(全域极值点)。为此,就需知在 什么情况下所获得的极小点就是全域最小点,这就涉及到凸集、凸函 数与凸规划问题。

1. 凸集
设 D 为 n 维欧氏空间Rn中的一个集合。如果在D内任取两点X (1) 和X (2),其连线上的所有点均在D内,则称这种集合D为 n 维欧氏空 间Rn 的一个凸集。 图2-5(a)、(c)是二维空间的一个凸集;图2-5 (b)是非凸集。

图2-5

凸集与非凸集

X (1)、X (2)两点之间的连线,可用数学式表达为

X ? ? X (1) ? (1 ? ? ) X (2) ? D

(2-19)

式中,λ为由0~1(0≤λ≤1)间的任意实数。即对[0,1]上一切λ值得到的点 X 的全体组成X (1)、X (2) 点 的连线。

则凸集的数学定义式为
X (1),X (2) ∈D 且 X =λX (1) + (1一λ) X (2) ∈D,0≤λ≤1

2. 凸函数
凸函数的数学定义如下:

设 f (X)为定义在凸集D上的一个函数,X (1)、X (2) 为D 上的任意 两点,若对于任意实数λ(0≤λ≤1)恒有

f [? X (1) ? (1 ? ? ) X (2) ] ? ? f ( X (1) ) ? (1 ? ? ) f ( X (2) )
则称 f (X)为凸集D上的凸函数。 (2-20)

若式(2-20)中的 “≤” 为 “<”,则称 f (X)为严格凸函数; 若式(2-20)中不等号反向,即 “≤” 为 “≥” ,则称 f (X)为D上的 凹函数。

凸函数的几何意义可用一元函数情形说明,如图2-6所示,若函数 f (X)在区间[a, b]内为凸函数,则函数 f (X)曲线上任意两点所连的直线 不会落在曲线弧线以下。

图2-6

凸函数的几何意义

凸函数具有如下特性: (1)设 f (X)为定义在凸集D上的一个凸函数,则对于任意实数λ( λ >0),则函数λ f (X)在凸集上也是凸函数; (2)设 f1(X)和 f2(X)为定义在凸集D上的两个凸函数,则 f1(X)和 f2(X)的线性组合函数 f(X) = f1(X) + f2(X)在D上也是凸函数;

(3)若 f(X)为定义在凸集D上的函数,且存在连续二阶导数,则 f(X)为D上的凸函数的充要条件是: f (X)的黑塞矩阵H(X)处处是半正 定的。若黑塞矩阵H(X)对一切X∈D都正定,则 f(X)是D上的严格凸函 数。 利用以上性质,就可以判别函数是否具有凸性。
如果 f(X)是凸集D上的凸函数,并且在D内有极小点,则极小 点是唯一的。

3. 凸规划
对于约束优化问题

min f (X) X∈Rn s.t. gu (X) ≤0, u = 1, 2, …, m
如果目标函数 f(X)和所有的不等式约束gu(X)≤0(u =1,2,…, m)均为凸 函数,则称此约束优化问题为凸规划。并需指出的是,如果不等式约 束的形式为gu(X)≥0,则 gu (X)(u =1,2,…, m)应为凹函数。 凸规划的一个重要特性为: 凸规划的任何局部极小解一定是全域最优解。 因此,对于凸规划问题,只要求出一个局部极小解,它就是全域 最优解。 所以,优化理论与方法常限于讨论凸规划问题。

需要指出的是,实际工程优化问题往往不是凸规划问题。

所以,采用常用的优化方法,求得的最优解往往是局部最优解。 而且,对于一个复杂的工程优化问题,往往难以判断其是否为凸规划 问题。
为此,在采用迭代方法求解时,常从多个初始点出发,进行不同 的迭代,以求得多个局部极小点,然后比较这些局部极小点,最后得 到一个近似全域极小点,作为该问题的最优解。

2.6 约束优化问题的极值条件
求解约束优化问题
min f ( X ), X ? Rn (v ? 1, 2, ?, p) s.t. gu ( X ) ? 0 (u ? 1, 2, ?, m) hv ( X ) ? 0

的实质就是在所有的约束条件所形成的可行域内,求得目标函数的 极值点,即约束最优点。 因而约束优化问题比无约束优化问题更为复杂。

约束优化问题的极值点可能出现两种情况: 一种是如图2-7(a)所示,即目标函数的极值点X * 处于可行域 D之 内,故目标函数的极值点X *即为该约束优化问题的极值点; 另一种如图2-7(b)所示,即某约束边界 g i (X) = 0 将目标函数的自 然极值点隔到可行域 D之外,因此这时约束优化问题的极值点不是目 标函数的自然极值点,而是该约束边界g i (X) = 0 与目标函数等值线的 切点X *。

图2-7 约束优化问题极值点
(a)极值点在可行域内 (b)极值点在可行域的边界上

1. 等式约束的极值条件
由高等数学可知,对于等式约束优化问题
min f ( X ) s.t. hv ( X ) ? 0 ? ? (v ? 1, 2,?, p) ?

(2-21)

可建立如下拉格朗日函数
L( X , ? ) ? f ( X ) ? ? ?v hv ( X )
v ?1 p

(2-22)

式中,? ? [?1, ?2 ,?, ?n ]T 为拉格朗日乘子向量。令 ?L( X * , ? ) ? 0,得
?f ( X ) ? ? ?v?hv ( X * ) ? 0 (v ? 1, 2, ?, p, p ? n; ?v不全为零)
* v ?1 p

(2-23)

式(2-23)就是等式约束问 题在点 X * 取得极值的必要条 件。 式(2-23)的几何意义可以 解释为:在等式约束的极值 点上,目标函数的负梯度等 于诸约束函数梯度的线性组 合。 如图2-8所示,在两个等 式约束的交线 E上的点X *, 约束函数的梯度与目标函数 的梯度共面,因此式(2-23)成 立,故X *就是极值点。

图2-8

等式约束问题的极值条件

2. 不等式约束的极值条件
对于不等式约束优化问题
min f ( X ) s.t. gu ( X ) ? 0 ? ? (u ? 1, 2,?, m) ?

(2-24)

引入 m个松弛变量 xn?u ? 0(u ? 1, 2,?, m) ,可将上面的不等式约束 优化问题变成等式约束问题
min f ( X )
2 s.t. gu ( X ) ? xn ?u

? ? ? 0 (u ? 1, 2, ?, m) ?
m

(2-25)

建立这一问题的拉格朗日函数
2 L( X , ? , X ) ? f ( X ) ? ? ?u [ gu ( X ) ? xn ?u ] u ?1

式中,X ? [ xn?1, xn?2 ,?, xn?m ]T 为松弛变量组成的向量。

令该拉格朗日函数的梯度等于零,即使
?L( X , ?, X ) ? 0

则有

m ?L ? ?f ( X ) ? ? ?u ?gu ( X ) ? 0 ?X u ?1 ?L 2 ? gu ( X ) ? xn ?u ? 0 ??u

?L ? 2?u xn ?u ? 0 , ?xn ?u

? ? ? ? ? ? ? (u ? 1, 2, ?, m) ? ?

(2-26)

式中,当 ?u ? 0 时有 xn?u ? 0 和 gu ( X ) ? 0,这说明点 X 在约束边界 上, u ( X ) ? 0 为点 X 的起作用约束。 g 注意到约束条件为 “≤0” 的形式,可知约束函数的梯度方向指
?L 向可行域外,为满足 ?X ?0

, ?u

必须大于零;而当 ? 0 ?u

xn 时,有 ?u ? 0

和 gu ( X ) ? 0 ,这说明点 X 在可行域内。

设 gi ( X ) ? 0(i ? I k ) 为点 X * 的 n 个起作用约束,且 X * 是极值 点,则由式(2-26)及其分析可知,必有
?f ( X * ) ? ? ?i ?gi ( X * ) ? 0 ? ? i?I k ? ? ?i ? 0 (i ? I k ) ?

(2-27)

式(2-27)就是不等式约束优化问题的极值条件,称Kuhn-Tucker 条件,简称 K-T条件。

该条件表明,若设计点 X *是函数 f (X)的极值点,要么 ?f ( X * ) ? 0 ( 如图2-9所示,此时 ?i ? 0 ),要么目标函数的负梯度位于诸起作 用约束梯度所构成的夹角或锥体之内。
也就是说,目标函数的负梯度 ??f ( X * ) 等于诸起作用约束梯 度 ?gi ( X * ) 的 非负线性组合(如图2-10所示,此时 )。 ?i ? 0

图2-9

极值点处目标函数 的梯度为零

图2-10

极值点处目标函数 的梯度不为零

应该指出,K-T 条件是多元函数取得约束极值的必要条件,既可 以用来作为约束极值点的判别条件,又可以用来直接求解比较简单 的约束优化问题。 但 K-T条件不是多元函数取得约束极值的充分条件。只有当目 标函数 f (X)是凸函数,而全部约束函数 gu ( X ) ? 0(u ? 1,2,?, m) 也 是凸函数(或 gu ( X ) ? 0 为凹函数),即为凸规划时,K-T条件才 是极值存在的充分必要条件。 下面通过一个实例来说明 K-T条件的应用。

例2-5 试用 K-T条件判定点X * = [1, 0]T是否为如下优化问题的 极值点。 2 min f ( X ) ? ( x1 ? 2) 2 ? x2 , X ? R 2 s.t. g1 ( X ) ? ? x1 ? 0 g 2 ( X ) ? ? x2 ? 0
g3 ( X ) ? x12 ? x2 ? 1 ? 0

解:(1)画出该优化问题的目标函数等值线和可行域图
根据该优化问题给出的目标函数和约束条件,表示该问题的可 行域 D 和目标函数 f (X)的一些等值线图如图2-11所示。

图2-11

例2-5的极值点判断

(2)找出起作用的约束 由图2-11可见,在点X * = [1,0]T 处起作用的约束有g2(X)和 g3(X)。

(3)求 f (X) 、g2(X) 和 g3(X) 在点X * 处的梯度
? 2( x1 ? 2) ? ? ?2 ? ?f ( X ) ? ? ?? ? ? ? 2 x2 ? X * ?[1,0]T ? 0 ?
*

? 0? ? 0? ?g 2 ( X * ) ? ? ? ?? ? 、 ? ?1? X * ?[1,0]T ? ?1? ?2 x ? ?2? 、 ?g 3 ( X * ) ? ? 1 ? ?? ? ? 1 ? X * ?[1,0]T ?1 ?
* * * (4)将以上 ?f ( X ), ?g 2 ( X ), ?g3 ( X )代入K-T条件式(2-27),即

??f ( X * ) ? ?2?g2 ( X * ) ? ?3?g3 ( X * )



? 2? ? 0? ? 2? ?0? ? ?2 ??1? ? ?3 ?1 ? ? ? ? ? ? ?

当λ2 = 1,λ3 = 1时,上式成立,满足K-T条件,故点X * = [1, 0]T就 是该约束优化问题的极小点,如图2-11所示。 另外,又经检验得知 f (X) 和 gi (X) 均为凸函数,故 f (X)在 gi (X)

≤0 (i = 1, 2, 3)下的极小点X * = [1, 0]T是唯一的。

本章结束
Thank You!


网站首页 | 网站地图 | 学霸百科 | 新词新语
All rights reserved Powered by 大学生考试网 9299.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com