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

重点学习库恩-塔克条件(Kuhn –Tucker, K-T条件)，学会计算库恩-塔克点(K-T点)。其他次要。 第2章 最优化的基础理论和基本方法§2 有约束最优化§2.2 一般约束情况 问题：min f(x), x∈Rn (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 = ? （空集） 考虑问题的局部解。考虑最优性条件。 看两个例子：不等式约束。 例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) ≤0 D: 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。 ?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 满足非负条件 满足松弛互补条件 — 对应不等式约束。 起作用约束和不起作用约束(对不等式约束) 在可行点x处 起作用约束：使得ci (x) = 0, i?I的不等式约束ci(x)。 不起作用约束：使得ci(x) 0, i?I的不等式约束ci(x)。 （这是由局部解的局部性决定的，只考虑x的邻域。） 引入符号I(x)：表示在可行点x处的所有起作用的 不等式约束的下标，即 I(x)={i | i∈I,ci(x)=0}。 综合等式约束、不等式约束情况一般约束优化的局部解的必要条件 库恩-塔克定理 对于一般约束问题(2-1)，设x=x*为问题的局部解。又设f(x)、 ci(x)在x*处有连续偏导数，n维向量组?ci(x*), i?E∪I(x*) 线性无关。则存在常数向量?* =(?1*, ?2*, …, ?l+m*)T，使如下条件成立： 令 说明 上述5式称为库恩-塔克条件(Kuhn-Tucker) ，由二人于1951给出。 其中的第4式称为非负条件，只对不等式约束对应的拉格朗日乘子?成立。 (等式约束对应的?可正可负，正像在前面等式约束的例题中的那样) 。 第5式称为互补松弛条件，针对不等式约束的（实际上对等式约束也成立，但把等式情况包括进来是多余的）。 第1式中的和式对应等式约束和不等式约束两部分. 满足库恩-塔克条件的点x*简称为K-T点。 例 求k-T点(p252) 该点是问题可能的局部解。 该点是问题 的最优解(下页图) (根据其他方法可知) K-T点：（0，-3）T λ=μ=0，矛盾方程。 λ=0，必须μ=-1，不满足非负条件。 λ≠0，μ≠0，由松弛互补条件可解得—见书p253，这时让?2L =0的两个式子相减，可见总是λ0 ，不满足非负条件。 λ≠0，μ=0， 有一个（1+ λ ）x1 = 0，由此只有x1 = 0（否则不满足非负条件）。 可知x2= +3或 -3。前者不满足c2约束。故x2=-3. 所以，x=(0，-3）)T 为该优化问题的 K-T点。 该点是最优解。 f=0 f=-5 对于凸优化问题 定理 如果问题(2-1)为一个凸优化问题（即 可行域D是凸集，目标函数f是D上的凸函数）， 又设目标函数f(x)和约束函数ci(x)都存在一阶 连续偏导数，则问题的K-T点是问题的最优解。 例子：上例。所以，该点是最优解。 最