非线性规划约束规范 作业

《非线性规划约束规范 作业》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学作业纪旭2012201742在KKT条件下，讨论非线性规划的约束规范文章目录：一、引理论述二、KKT条件三、约束规范及其相互关系3运筹学作业纪旭2012201742一、引理论述本文主要考虑如下形式的约束优化问题：minf(x)s.t.gix≤0,i=1，2，…，m其中，gi表示可行域S.S=x∈Rngix≤0,i=1，2，…，m在可行解x处满足gix=0的约束条件称为x处的有效约束（activeconstraint）。S在x处的切锥可以表示为TSx=y∃tk→0，∃yk→y满足x+tkyk∈S，∀k。S在x处的线性化锥可以表示为CSx=y∈R

2、n∇gix，y≤0，gix是有效约束用图表示如下：切锥TSx由S直接定义，而线性规划锥CSx则依赖于描述集合S的函数gi。因此，两者并未完全一致。虽然TSx=CSx不一定成立，但是TSx∈CSx总是成立的。对于原问题，引入Lagrange乘子λ，得到L0x，λ=fx+i=1mλigix，λ≥0.L0称为Lagrange函数。二、Karush-Kuhn-Tucker条件由以上引理，可以得到描述原问题的最优性必要条件的定理：设x为原问题的局部最优解，并且目标函数f：Rn→Ri=1，2，…，m均在x处可微。若CSx⊆coTSx，则存在Lagrange乘子

3、λ∈Rm，满足∇xL0x,λ=∇fx+i=1mλi∇gix=0λi≥0，gix≤0，λigix=0，i=1，2，…，m上式一般称为Karush-Kuhn-Tucker条件或者KKT条件。该条件是x为原问题的局部最优解的必要条件，但不是充分条件。举反例加以说明：考虑问题3运筹学作业纪旭2012201742minfx=-x2s.t.g1x=-x12+x2≤0g2x=x12+x22-1≤0由于∇fx=0,-1T，∇g1x=0,1T，取λ=1,0T，则KKT条件成立，但是x不是该问题的局部最优解。KKT条件说明，在局部最优解x处目标函数的梯度∇fx乘以-1

4、后得到的向量包含在由有效约束函数的梯度∇gix所张成的凸多面锥中，如下图所示：从KKT表达式我们看出，在假设条件TSx∈coCSx下，KKT条件是原问题最优性条件。一般称这样的假设条件为约束规范（constraintqualification），它是KKT条件成为最优性必要条件不可或缺的条件。但同时有特殊情况，当原问题为凸规划时，在约束规范下，KKT条件也是全局最优性的充分条件。三、约束规范及相互关系接下来来讨论保证KKT条件最优性必要条件的其他约束规范，然后讨论它们之间的关系。首先给出没有约束规范情况下的最优性必要条件——FritzJohn条件：

5、设点x为原问题的局部最优解，目标函数f：Rn→R与约束函数gi：Rn→Ri=1，2，…，m均在x处可微，则存在λ1，λ2，…，λm满足λ0T∇fx+i=1m∇gix=0gix≤0，λigix=0，i=1，2，…，mλi≥0，i=1，2，…，mλ1，λ2，…，λmT≠0,0,…,0T3运筹学作业纪旭2012201742以上式子称为FritzJohn条件，KKT条件可以看做它的特殊情形（即λ0>0的情形）。原问题只包含不等式约束，对于这个问题，具有代表性的约束规范有：（1）线性独立约束规范（linearindependenceconstraintqua

6、lification）：向量组∇gix（有效约束）线性无关；（2）Slater约束规范（Slater’sconstraintqualification）:gi（有效约束）均为凸函数，并且存在x0满足gix0<0（i=1，2，…，m）；（3）Cottle约束规范（Cottle’sconstraintqualification）:存在向量yϵRn满足∇gix，y<0（gi为有效约束）；（4）Abadie约束规范（Abadie’sconstraintqualification）：CSx⊆TSx；（5）Guignard约束规范（Guignard’scons

7、traintqualification）：CSx⊆coTSx。其中Guignard约束规范正是上文KKT条件叙述中所假定的约束规范。通过阅读相关文献，得到它们之间的关系如下的关系：（1）若线性独立约束规范或Slater约束规范成立，则Cottle约束规范也成立；（2）若Cottle约束规范成立，则Abadie约束规范也成立。若Abadie约束规范成立，则Guignard约束规范也成立。证明不加以赘述。综合上两条结论，画出关系图：在这些约束规范中，Guignard约束规范是最弱的条件。因此从理论上来讲，Guignard约束规范是最好的。但是该约束规范

8、不太实用，因为对于实际问题不太容易验证。所以在实际问题中，线性独立约束规范、Slater约束规范、Cottle约束规范使用