非线性规划理论与算法

《非线性规划理论与算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、非线性规划理论与算法非线性规划及其最优性条件对偶理论外点罚函数法内点罚函数法1非线性规划及其最优性条件约束集或可行域:非线性规划x*是整体(全局)极小点x*是严格整体(全局)极小点x*是局部极小点x*是严格局部极小点非线性规划向量化表示p=q=0即无约束规划3非线性规划的几个概念线性化可行方向:可行方向锥4定义3:积极约束:或起作用约束（紧约束积极约束有效约束）。5证明:定理1:定义4:可行下降方向6定理2:定理3:证略③极值点的必要条件:7严格凸组合严格凸线性组合为凸规划。若f(x)是凸函

2、数，S是凸集，一般要求当i=1,2,…,p时为凸函数，当i=p+1,…,p+q时为线性函数。凸规划的局部解是整体解！89定理：可微函数解的必要条件：x*是局部解,则：最优性条件无约束规划x*是驻点(稳定点)可微凸函数解的充要条件：x*是整体极小解当且仅当10约束规划最优性条件的几何表述梯度共线11共面梯度被线性标示约束规划最优性条件的几何表述12结论：在解处仅等式(紧)约束有效！约束规划最优性条件的几何表述13对约束定义7.有效约束(紧约束、积极约束)——activeconstraint在x

3、*处有则称在x*处ci(x)是紧约束。x*处有效约束指标集梯度的负线性表示!14向量化表示约束规划最优性必要条件Karush-Kuhn-Tucker条件——KKT条件互补松弛条件15Lagrange函数Karush-Kuhn-Tucker条件——KKT条件Lagrange乘子：互补松弛条件：约束规格——约束限制(规范)条件16约束规划最优性充分条件鞍点条件同时的最优解！证明：由的任意性知:且进一步由不等式的后两部分知:17凸规划最优性充要条件Karush-Kuhn-Tucker条件——KKT条件

4、18定理(FritzJohn条件):其他最优性条件19FritzJohn条件与KKT条件的区别:FritzJohn条件可能出现w0=0的情形。这时FritzJohn条件中实际上不包含目标函数的任何数据，只是把起作用约束的梯度组合成零向量。这样的条件，对于问题的解的描述，没有多大价值。我们感兴趣的是w0≠0的情形，所以为了保证w0≠0，还需要对约束施加某种限制。这种限制条件通常称为约束规格。在上一个定理中，如果增加紧约束的梯度线性无关的约束规格，则给出问题的KKT条件。201)所有规划解的最优性必

5、要条件=KKT条件+约束规格2)凸规划解的最优性充分条件=KKT条件最优性条件总结最优性必要条件证明：需要用到凸集分离定理、择一性定理(Farkas引理凸规划最优性充分条件证明较简单，但对非凸规划结果没有实际指导意义，蕴含着对偶原理——Langrange对偶21例:求约束极值问题22232425最优性条件举例线性规划最优性条件是充分的？是必要的？标准形式：练习：推广形式的最优性条件26最优性条件举例二次规划最优性条件什么条件下是充分的？什么条件下是必要的？推广一：推广二：简化：27对偶理论最大最

6、小对偶目标函数:x方的目标是无论y怎样，都应使F越小越好；y方的目标是无论x怎样，都应使F越大越好；立于不败之地的决策方法——保守主义决策相关结论：——一对对偶问题——弱对偶定理——对偶间隙29最大最小对偶举例——博弈30最大最小对偶鞍点条件:对相关结论：——弱对偶定理——对偶间隙若有点则称(x*,y*)满足鞍点条件。——强对偶定理满足鞍点条件。31原规划:Lagrange对偶Lagrange函数Lagrange对偶弱对偶性:——弱对偶定理——对偶间隙原规划凹函数32Lagrange对偶举例33

7、像集343536连续可微凸规划:强对偶定理：连续可微凸规划，满足一约束规格，则Lagrange对偶的强对偶定理f、g可微凸，h线性1)：若原问题有解，则对偶问题也有解；2)：若原问题与对偶问题分别有可行解，则他们是最优解的充分必要条件是他们对应相同的目标值(对偶间隙为0).证1)：即证可微凸规划的最优解与其KKT条件的乘子满足鞍点条件！证2)：利用鞍点条件可得。3)：对偶问题无上界，则原问题不可行；原问题无下界，则对偶问题不可行。37连续可微凸规划:Wolfe对偶：Wolfe对偶f、g可微凸，h

8、线性1)：若原问题有解，则对偶问题也有解；2)：若原问题与对偶问题分别有可行解，则他们是最优解得充分必要条件是他们对应相同的目标值(对偶间隙为0).Lagrange函数Wolfe对偶定理：连续可微凸规划，满足一约束规格，则38凸规划对偶举例(Q正定)二次规划(Q正定)推广一：推广二：Lagrange对偶共轭对偶、广义Lagrange对偶——参阅《非线性规划及其理论》(应玖茜、魏权龄)第6章39罚函数法惩罚函数法将有约束优化问题转化为一系列无约束优化问题进行求解。（SequentialUncons