非线性规划-KT条件

淮北师范大学2011届学士学位论文数学规划的KT条件学院、专业数学科学学院数学与应用数学研究方向运筹学学生姓名杨传东学号20071101187指导教师姓名张发明指导教师职称副教授2011年4月10日数学规划的KT条件杨传东(淮北师范大学数学科学学院，淮北，235000)摘要数学规划理论包括线性规划理论和非线性规划理论两个主要分支，非线性规划问题的Kuhn-Tucker条件是数学规划论的一个重要结论，1951年P.Kuhn和A.W.Tucker提出了一般非线性规划问题的一阶必要条件，即Kuhn-Tucker条件，标志着非线性规划理论作为一个独立的数学分支被正式确立。

Kuhn-Tucker最优性条件是一个非线性规划问题能有最优化解法的一个必要和充分条件,同时也是解决存在不等式约束，尤其是非负约束条件下最优化的重要工具，因此对非线性规划中对Kuhn-Tucker最优化条件的深入研究，并研究其应用显得尤为必要。

其在数学和经济学中有着广泛的应用，本文首先分析了非线性规划问题的Kuhn-Tucker条件的数学基础，指出将数学结论直接引入经济学的不足．然后根据经济理论和数学模型的方法建立了一个新的非线性规划问题，并用数学分析和线性代数的有关理论证明了新问题的Kuhn-Tucker条件．同时还分别用Farkas 引理和非线性规划问题的Kuhn-Tucker定理证明了这个结果，并对这些证明做了比较分析．最终使得数学与经济学完美结合．关键词非线性规划，Kuhn-Tucker条件，最优性，经济学The KT Condition of the Mathematical ProgrammingYang Chuandong(School of Mathematical Science, Huaibei Normal University, Huaibei, 235000)AbstractKT optimality condition is well-known in nonlinear programming to gain the optimal solution. It is widely used in Mathematics and Economics. Firstly, this paper analyses the mathematical foundations of the Kuhn-Tucker condition of the nonlinear programming problems and points out the disadvantages of taking mathematic conclusions into Economics directly. Then according to economic theory and the method of the mathematical model, it establishes a new nonlinear programming problem and uses the knowledge of mathematical analysis and linear algebra to prove the Kuhn-Tucker condition of the new problem. At the same time, it uses the Farkas lemma and the Kuhn-Tucker theorem of the nonlinear programming problems to prove this conclusion and makes a comparing analysis with these proofs. At last, this paper gives an application of the new conclusion in nonlinear programming theory.Keywords nonlinear programming, Kuhn-Tucker condition，optimization, Economics目录引言 (1)一、预备知识 (1)1 一般的非线性规划问题 (1)2 凸集.凸函数与凸规划 (2)3 P的Kuhn-Tucker条件1 一般的非线性规划问题 (3)二、K UHN-T UCKER条件在经济学中的应用 (3)三、经济理论中的非线性规划问题 (4)四、E-P的K UHN-T UCKER条件 (6)1 术语与约定 (6)2 约束极值问题的Lagrange定理 (6)3 引理 (6)4 E-P的Kuhn-Tucker条件 (8)五、由F ARKAS引理证明E-P的K UHN-T UCKER条件 (9)1 Farkas引理 (9)2 引理 (10)六、E-P的K UHN-T UCKER条件的应用举例 (10)1，一般的线性规划问题及其Kuhn-Tucker条件 (10)2 LP的约束规范条件 (12)结束语 (14)参考文献 (15)致谢 (16)引言数学规划包括线性规划,非线性规划,二次规划，多目标规划等等。

第三讲非线性规划§4约束极值问题(1)问题min(),{|()0,1,}jf XR X g X j l⎧⎨=≥=⎩<1>思路:有约束→无约束; 非线性→线性; 复杂→简;一、最优性条件1. 可行下降方向(有用约束,可行方向,下降方向) (1) 有用(效)约束设<1>式的(),()jf Xg X有一阶连续偏导设(0)X是一个可行解, 下一步考察时，要讨论约束.分析: 应有(0)(0)(0)()0()0()0j j j g X g X g X ⎧>⎪≥→⎨=⎪⎩ 若(0)()0j g X>,则在(0)()U X内,有()0j g X >, 此时各个方向均可选. 若(0)()0j g X =,则(0)X∈()0j g X =形成的边界, 影响下一步选向.1x 2x {()0}R X g X =≥()f X ()0j g X =(0)X故称()0j g X =是(0)X 点的有效约束. (2) 可行方向(对可行域来说) 设(0)X 为可行点, P 为某方向, 若存在00λ>, 使得(0)0,[0,]XP R λλλ+∈∈则称P 是(0)X 点的一个可行方向. (a) 可行方向P 与有效约束(0)()0j g X=的梯度(0)()j g X ∇关系是:(0)()0T j g X P ∇≥.记有效约束下标集(0){|()0,1}j J j g X j l ==≤≤ 若P 为(0)X 的可行方向, 则 存在00λ>, 使得当0[0,]λλ∈,有(0)(0)()()0,j j g X P g X j J λ+≥=∈从而(0)(0)0d ()()0,d j T j g X P g X P j J λλλ=+=∇≥∈见下图.(b)反之, 若(0)()0Tj g XP ∇>, 则P 必为可行方向.(0)(0)(0)()()()()T j j j g X P g X g X P o λλλ+=+∇+Q (0)1()0g X=(0)2()0g X =(0)2()g X∇(0)1()g X ∇P(0)X •<1>对有效约束(0)()0j g X =,只要λ充分小,得(0)()0j g X P λ+≥, 所以P 是可行方向;<2>对无效约束(0)()0j g X >,同样只要λ充分小, 就有(0)()0j g XP λ+≥,故P 也是可行方向;事实上, 对无效(0)()0j g X>,P ∀都是可行方向.(3) 下降方向(对目标函数来说) 设(0)XR ∈, 对某P 方向, 若在00[0,],0λλλ''∈>内, 有(0)(0)()()f X P f X λ+<则称P 是一个下降方向. 下降方向判定: 若(0)()0Tf XP ∇<,则P 是(0)X 的一个下降方向.因为(0)()()f X f X P λ=+(0)(0)()()()T f X f X P o λλ=+∇+,只要λ充分小, 都有(0)()()f X f X <.(4) 可行下降方向若(0)X R ∈的某方向P 是 可行方向+下降方向, 则称P 是(0)X 的可行下降方向. 即 存在00λ>,当0[0,]λλ∈时,有(0)()0j g X P λ+≥且(0)(0)()()f X P f X λ+<,是继续寻优方向. 讨论: (0)X非极小值点⇔存在可行下降方向P ; (0)X极小值点 ⇔ 无可行下降方向P ;(可行但不下降,或下降不可行)定理(局部极(最)小必要条件)设X *是min (),{()0}i f X X g X ∈≥局部极小点,(),(),j f X g X j J ∈(有效约束下标集)在X *处可微, (),j g X j J ∉在X *处连续,则在X *处无可行下降方向P ,即不存在P , 使**()0,,()0,T j Tg X P j J f X P ⎧∇>∈⎨∇<⎩(**) 证 否则由(**)及前面的分析, 可找出可行下降点 →X *非局部极小值点→矛盾. 如图 所示1x 2x ()f X *∇()f X 1()g X *∇*问题:min (),{|()0,1,}j f X R X g X j l ⎧⎨=≥=⎩<1>2. 库恩—塔克条件(局部最小的必要条件) 是非线性规划中最重要成果之一 (1) Gordan 引理(不加证明) 设12,,...,l A A A 是l 个n 维向量, 则P ∃/,使0,1,2,...,T j A P j l <=⇔ 0j μ∃≥,不全为零, 使10lj j j A μ==∑.(不指向同侧的向量, 正组合为零)(如l =3,n =2)若同侧, 则有P (图a), 否则无P (图b),但可正组为0.(2) Fritz John 定理设X *是<1>极小值点, ()f X 和()j g X 有一阶连续偏导数, 则存在不全为零的01,,...,l μμμ, 使3A 1A 2A PH ()a 3A 1A 2A P H()b⎧⎪⎨⎪⎩01()()0()0,1,2,...,0,1,2,...,lj j j j j j f X g X g X j l j lμμμμ**=*∇-∇===≥=∑证明 因X *是问题<1>的解, 故由定理4, 不存在可行下降方向P, 使()0()0,TTj f X P g X P j J**⎧∇<⎪⎨-∇<∈⎪⎩ 由Gordan 引理,存在不全为零非负数0,,j j Jμμ∈使0()()0j j j Jf Xg X μμ**∈∇-∇=∑对无效约束j J ∉, 令0j μ=, 则()0j j g X μ*∇=从而有(对所有l )01()()0lj j j f X g X μμ**=∇-∇=∑且有()0,0,1,2,...,j j j g X j l μμ*=≥=, 证毕.注1: 类似于条件极值的必要条件.注2 若00μ=,则有效约束的()j g X *∇正线性相关→同侧→有可行下降方向→X *非极值点. 故一般设()j g X *∇线性无关→00μ>. 以上条件称为 Fritz John 条件, *X 称为Fritz John 点.(3) 必要条件 (库恩-塔克条件)设X *是<1>极小值点, ()f X 和()j g X 有一阶连续偏导,且有效约束梯度线性无关,则1,...,l μμ**∃, 使⎧⎪⎨⎪⎩1()()0()0,1,2,...,0,1,2,...,lj j j j j j f X g X g X j l j lμμμ***=***∇-∇===≥=∑<2>证明 由Fritz John 引理, ()j g X *∇j J ∈线性无关得00μ>, 作00/0j μμμ*=>, 即得<2>.式<2>=库恩-塔克条件. 相应点=库恩-塔克点. 简称K-T 条件, K-T 点. 对一般非线性规划min (),()0,1,()0,1,i j f X h X i m g X j l⎧⎪==⇒⎨⎪≥=⎩ min (),()0,()0,1,()0,1,i ij f X h X h X i m g X j l⎧≥⎪⎨-≥=⎪≥=⎩<3> 它的K-T 条件如下设X *是<3>极小值点, 相应函数有一阶连续偏导,且有效约束的()i h X *∇和(),j g X j J *∇∈线性无关,则12(,,...,)T m Γγγγ****∃=和1(,...,)Tl M μμ***=,使11()()()0()0,1,2,...,0,1,2,...,m lii j j i j j j j f X h X g X g X j lj lγμμμ*****==***∇-∇-∇===≥=∑∑<4>其中12,,...,m γγγ***,1,...,l μμ**称为广义Lagrange 乘子. 注1 对凸规划, K-T 条件也是充分的. 设k X 为某可行解, 若kX 是极小点,且1()0kg X =,2x ()f X 1()0k g X =和2()0kg X =,则()()k f X∇必与,1()k g X ∇和2()k g X ∇同侧, 否则有可行下降方向.由1()k g X ∇和2()kg X ∇线性无关1122()()()k k f X g X g X μμ*∇=∇+∇即1122()()()0k k f X g X g X μμ*∇-∇-∇=()()k f X -∇()1()0k g X =例10 用库恩-塔克条件解非线性规划2max ()(4)16f x x x ⎧=-⎨≤≤⎩. 解 变为 212min ()(4)()10()60f x x g x x g x x ⎧=--⎪=-≥⎨⎪=-≥⎩, 16412()2(4),()1,()1f x x g x g x ∇=--∇=∇=-, 引入广义拉格朗日乘子12,μμ**, 则有所以1212122(4)0(1)0(6)0,0x x x μμμμμμ*********⎧---+=⎪-=⎪⎨-=⎪⎪≥⎩, 具体分析如下. 若120,0,μμ**>>引出矛盾, 无解;若120,0μμ**>=:1x *=,点; ()9f x *=(1μ*=6)若120,0μμ**==:4x *=,()0f x *=;若120,0μμ**=>:6x *=,()4f x *=(2μ*=4)所以最大值点1x *=, 最大值()9f x *=. 注: 2()(4)f x x =--非凸函数, 在[1,6]上有两个局部最小值点. 还有一个”驻点”附加例题(略)用K-T 条件解非线性规划1642min ()(3)05f x x x ⎧=-⎨≤≤⎩. 解 212min ()(3),()0,()50f x x g x x g x x ⎧=-⎪=≥⎨⎪=-≥⎩,(是凸规划) 12()2(3),()1,()1f x x g x g x ∇=-∇=∇=-,所以1212122(3)00(5)0,0x x x μμμμμμ*********⎧--+=⎪=⎪⎨-=⎪⎪≥⎩, 具体分析如下. 若120,0,μμ**≠≠引出矛盾, 无解;若120,0,μμ**≠=解得10,6x μ**==-,非K-T 点; 若120,0,μμ**=≠解得15,4x μ**==-,非K-T 点; 若120,0,μμ**==解得3x *=,()0f x *=全局最小.习题4.1 已知非线性规划131212max ()(1)0,0f X x x x x x =⎧⎪--≥⎨⎪≥⎩的极大点为(1,0), 试(1) 转化目标函数后, 写出其K-T 条件;(2) 求出K-T 点..4.2 试用K-T 条件求解问题2min ()(4)16f X x x =-≤≤.。

kkt条件中正则条件
在非线性规划问题中，KKT（Karush-Kuhn-Tucker）条件是取得最优解的一阶必要条件。

其中，正则条件是一个重要的前提，它要求目标函数和约束函数都是凸函数，且约束集是有界的。

正则条件可以确保存在一个局部最优解，并且在该点上，所有与约束集对应的线性子空间都满足某种正则性质。

这使得KKT条件可以应用，并确保找到的解是全局最优解。

如果目标函数和约束函数不是凸函数，或者约束集无界，那么正则条件不成立，这时可能需要使用其他方法来求解非线性规划问题。

以上信息仅供参考，建议咨询数学领域专业人士或查阅数学领域书籍获取更多信息。