第2章 最优化的基本理论和基本方法 最优性条件 2.2一般约束优化 库塔定理和库塔条件

1、o 重点重点学习库恩库恩-塔克条件塔克条件(Kuhn Tucker, K-T条件)，学会学会计算库恩库恩-塔克塔克点点(K-T点)。 其他次要。 第2章 最优化的基础理论和基本方法 2 有约束最优化 2.2 一般约束情况一般约束情况 问题：min f(x), xRn (2-1) st ci(x1, x2, ., xn) = 0, i E ci(x1, x2, ., xn) 0, i I 其中E和I分别表示等式和不等式约束的指标集, E= 1, 2, ., l I= l+1, l+2, ., l+m E I = （空集） 考虑问题的局部解。考虑最优性条件考虑问题的局部解。考虑最优性条件。 看两个

2、例子：不等式约束不等式约束。 o 例1 min f(x) = x1 + x2 st c1(x) = x12 + x2 2 - 2 0 f(x*) c1(x*) x* f(x) f(x) = x1 + x2 = -2 c1(x) c1(x) 0D: O 例例1 min f(x) = x1 + x2 st c1(x) = x12 + x2 2 - 2 0 可见满足： 非负条件非负条件 * 0 叫做松弛互补条件松弛互补条件 对应不等式约束。对应不等式约束。 1. 由图解法， x*为最优解， 当然也是局部解。局部解。 2. 局部解局部解x*在在D的边界上， 约束C1起作用起作用: c1(x*) = 0

3、。 f(x*) + * c1(x*) =0 * 0 * c1(x*) = 0 f(x*)=0 f(x) = (x1 -1)2 + x22 c1(x*) D x* O 例例2 min f(x) = (x1 -1)2 + x22 st c1(x) = x12 + x2 2 - 2 0 1. D内的点x* = (1,0)T为最优 解，当然也是局部解。局部解。 2. 约束C1不起作用不起作用: c1(x*)0。 3. x*是无约束问题局部解。 所以：f(x*) =0。 f(x*) + * c1(x*) =0 * = 0 * c1(x*) = 0 满足非负条件非负条件 满足松弛互补条件松弛互补条件 对应

4、不等式约束。对应不等式约束。 起作用约束和不起作用约束(对不等式约束) 在可行点x处 起作用约束起作用约束：使得ci (x) = 0, i I的不等式约束ci(x)。 不起作用约束不起作用约束：使得ci(x) 0, i I的不等式约束ci(x)。 （这是由局部解的局部性决定的，只考虑x的邻域。） 引入符号I(x)：表示在可行点x处的所有起作用的 不等式约束的下标，即 I(x)=i | iI,ci(x)=0。 综合等式约束、不等式约束情况 一般约束优化的局部解的必要条件一般约束优化的局部解的必要条件 库恩库恩-塔克定理塔克定理 对于一般约束问题对于一般约束问题(2-1)，设，设x=x*为问题的局

5、部解。为问题的局部解。 又设又设f(x)、 ci(x)在在x*处有连续偏导数，处有连续偏导数，n维向量维向量组组 ci(x*), i EI(x*) 线性无关。则存在常数向量线性无关。则存在常数向量 * =( 1*, 2*, , l+m*)T，使如下条件成立：，使如下条件成立： 0*)(*)(*)*,( 1 ml i iix xcxfxL ,.,2 , 10*)(lEixci ,.,2, 10*)(mlllIixci Ii i 0* Iixci i 0*)(* 乘数。拉 i ml i ii xcxfxL, )()(),( 1 令令 说明 o 上述5式称为库恩库恩-塔克条件塔克条件(Kuhn-Tu

6、cker) ，由 二人于1951给出。 o 其中的第4式称为非负条件非负条件，只对不等式约束对应只对不等式约束对应 的拉格朗日乘子的拉格朗日乘子 成立成立。 (等式等式约束对应的约束对应的 可正可负可正可负 ，正像在前面等式约束的例题中的那样) 。 o 第5式称为互补松弛条件互补松弛条件，针对不等式约束的（实际 上对等式约束也成立，但把等式情况包括进来是多余的）。 o 第1式中的和式对应等式约束和不等式约束两部分. o 满足库恩-塔克条件的点x*简称为K-T点。点。 例 求k-T点(p252) ),252( 01)( 09)( )(min 212 2 2 2 11 2 2 1 薛毅薛毅点。点。

7、的的 求约束优化问题求约束优化问题 pTK xxxc xxxcst xxxf ) 1( )9( ),( 21 2 2 2 12 2 1 xx xxxx xL 点。唯一的 为该问题 TK )3, 0( T 种情况讨论，分为 是否求解过程可以按 40 , 该点是问题可能的局部解。 该点是问题 的最优解(下页图) (根据其他方法可知) K-T点：（0，-3）T o=0，矛盾方程。，矛盾方程。 o=0，必须，必须=-1，不满足非负条件。，不满足非负条件。 o0，0，由松弛互补条件可解得，由松弛互补条件可解得见书见书p253， 这时让这时让2L =0的两个式子相减，可见总是的两个式子相减，可见总是0 ，

8、不，不 满足非负条件。满足非负条件。 o0，=0， n 有一个（1+ ）x1 = 0，由此只有x1 = 0（否则 不满足非负条件）。 n 可知x2= +3或 -3。前者不满足c2约束。故x2=-3. 所以，x=(0，-3）)T 为该优化问题的 K-T点。 该点是最优解。 f=0 f=-5 对于凸优化问题 o 定理定理 如果问题(2-1)为一个凸优化问题（即 可行域D是凸集，目标函数f是D上的凸函数）， 又设目标函数f(x)和约束函数ci(x)都存在一阶 连续偏导数，则问题的K-T点是问题的最优解。 例子：上例。所以，该点是最优解。 最优化的基本理论和基本方法 o 5个重要定理最优化的基本理论。 n 无约束 3个，有约束 2个。 n 历史上的最优化3个重要成果。 n 凸优化：驻点凸优化：驻点/K-T点是最优解是最优解。 o 是理论指导和基本方法。 n 准确方法，但不够实用，对规模大的或复杂的问题。 （以后将讲实用方法，即优化算法，为近似方法。） n 有时不能确定是否为局部解（充分条件不满足时）。 费马定理费马定理1629 拉格朗日定理拉格朗日定理1788 库恩塔克定理库恩塔克定理1951 大约相隔大约相隔150年。年。 作业 o求