第五章 非线性规划：理论和算法5.5 约束优化我们现在继续讨论更一般的有约束的线性优化问题。
特别的,我们考虑一个具有非线性目标函数和（或者）非线性约束的优化问题。
我们可以将这种问题表示为下面的一般形式：I∈≥∈=i x g i x g x f i i x ,0)(,0)()(min ε (5.10) 在本节的末尾，我们假设f 和i g ，i ε∈⋃I 全部是连续可微的。
拉格朗日函数是研究有约束的优化问题的一个重要工具。
为了定义这个函数，我们结合每个约束的乘子i λ——称作拉格朗日乘子。
对于问题（5.10）拉格朗日函数如下定义：∑I⋃∈-=ελλi iix g x f x L )()(:),( （5.11） 本质上，我们考虑的是目标函数违反了可行约束时的惩罚函数。
选择合适的i λ，最小化无约束函数(),L x λ等价于求解约束问题（5.10）。
这就是我们对拉格朗日函数感兴趣的最根本的原因。
与这个问题相关的最重要问题之一是求解最优问题的充要条件。
总之，这些条件称为最优性条件，也是本节的目的。
在给出问题（5.10）最优性条件之前，我们先讨论一个叫做正则性的条件，由下面的定义给出：定义5.1：设向量x 满足ε∈=i x g i ,0)(和I ∈≥i x g i ,0)(。
设J ⊂I 是使得0)(≥x g i 等号成立的指标集。
x 是问题（5.10）约束条件的正则点，如果梯度向量)(x g i ∇（i J ∈⊂I ）相互线性无关。
在上述定义中与J ε对应的约束，即满足0)(=x g i 的约束称为在x 点处的有效约束。
我们讨论第一章提到的两个优化的概念，局部和全局。
回顾（5.10）的全局最优解向量*x ，它是可行的而且满足)()(*x f x f ≤对于所有的x 都成立。
相比之下，局部最优解*x 是可行的而且满足)()(*x f x f ≤对于{}ε≤-*:x x x （0>ε）成立。
因此局部解一定是它邻域的可行点中最优的。
下面我们考虑的最优性条件仅仅判别局部解，则可能是全局最优解，也可能不是。
幸运的是，这里存在一类局部最优解和全局解一致的问题——凸优化问题。
附录A 中讨论的就是基于凸集的凸优化问题。
定理5.1 （一阶必要条件）设*x 是问题（5.10）的局部最小值，假设*x 是这个问题的约束的正则点。
则存在i λ，I ∈ εi 使得：0)()(**=∇-∇∑I∈ ελi iix g x f （5.12）I ∈≥i i ,0λ（5.13）I ∈=i x g i i ,0)(*λ（5.14）注意，（5.12）左边表达的意思是拉格朗日函数(),L x λ对每个变量x 的梯度。
一阶条件在局部最小值，局部最大值及鞍点处满足。
当目标函数和约束函数是二次连续可微的时候，可以用函数的曲率排除最大值和鞍点。
根据定理5.1，我们考虑拉格朗日函数(),L x λ和这个函数对每个变量x 的海森矩阵，来计算目标函数和约束函数在当前点处的曲率。
定理5.2（二阶必要条件）假设函数f 和i g （i ε∈⋃I ）都是二次连续可微的。
假设*x 是问题（5.10）局部最小值而且是这个问题的约束正则点。
则存在i λ，i ε∈⋃I 满足（5.12）—（5.14）及下面的条件：∑I∈∇-∇ ελi i ix g x f )()(*2*2 （5.15）在*x 处有效约束的切线子空间处是半正定的。
定理后半部分可以改写为含有效约束的雅阁比矩阵的形式。
设)(*x A 表示*x 处有效约束的雅阁比矩阵，设)(*x N 表示基于)(*x A 的零空间。
则定理的最后一个条件等价于下面的条件：)()()()(**2*2*x N x g x f x N i i i T ⎪⎪⎭⎫ ⎝⎛∇-∇∑I ∈ ελ （5.16） 是半正定的。
二阶必要条件并非常常保证给出的解的局部最优性。
局部最优性的充分条件更加严格和复杂，因为要考虑到退化的可能性。
定理5.3（二阶充分条件）假设函数f 和i g ，i ε∈⋃I 都是连续二次可微的。
同时假设*x 是问题（5.10）可行点而且是这个问题的约束正则点。
设)(*x A 表示*x 处有效约束的雅阁比矩阵，设)(*x N 表示基于)(*x A 的零空间。
如果存在i λ，i ε∈⋃I 满足（5.12）—（5.14）及下面的条件：I ∈=i x g i ,0)(*暗示0>i λ （5.17）和)()()()(**2*2*x N x g x f x N i i i T ⎪⎪⎭⎫ ⎝⎛∇-∇∑I ∈ ελ （5.18） 是正定的，则*x 是问题（5.10）的局部最小值。
定理5.1、5.2和5.3中列出的条件称作Karush-Kuhn-Tucker (KKT) 条件，以它们的发明者命名的。
一些求解约束优化问题的方法表达成一系列简单的可以用一般迭代步骤求出解的简单优化问题。
这些“简单”的问题可以是无约束的，此时可以应用我们前面章节介绍的方法求解。
我们在5.5.1中考虑这些策略。
在其他情况下，这些简单的问题是二次规划且可以应用第七章中的方法求解。
这个策略的典型例子是5.5.2中讨论的连续二次规划问题。
5.5.1广义简约梯度法在本节中，我们介绍一种求解有约束的非线性规划的方法。
这种方法建立在前文讨论的无约束优化法之最速下降法的基础上的。
这种方法的思想是利用约束减少变量的个数，然后用最速下降法去求解简化的无约束的问题。
线性等式约束首先我们讨论一个约束是线性方程组的例子。
2212341123421234min ()()4440()2220f x x x x xg x x x x x g x x x x x =+++=+++-==-++-+=在其他变量给定情况下，很容易求解只有两个变量的约束方程。
给定1x ，4x ，令214388x x x =+- 和31433x x x =--+。
把这些变量代入目标函数，然后得到下面简化的形式：()2214114144min (,)38833f x x x x x x x x =++-+-++这个简化形式是无约束的，因此可以利用5.4.1节的最速下降法求解。
例1：用最速下降法求min f(x)=f=(x −2)2+(y −4)2 Matlab 程序：M 文件：function [R,n]=steel(x0,y0,eps)syms x;syms y;f=(x-2)^4+exp(x-2)+(x-2*y)^2;v=[x,y];j=jacobian(f,v);T=[subs(j(1),x,x0),subs(j(2),y,y0)];temp=sqrt((T(1))^2+(T(2))^2);x1=x0;y1=y0;n=0;syms kk;while (temp>eps)d=-T;f1=x1+kk*d(1);f2=y1+kk*d(2);fT=[subs(j(1),x,f1),subs(j(2),y,f2)];fun=sqrt((fT(1))^2+(fT(2))^2);Mini=Gold(fun,0,1,0.00001);x0=x1+Mini*d(1);y0=y1+Mini*d(2);T=[subs(j(1),x,x0),subs(j(2),y,y0)];temp=sqrt((T(1))^2+(T(2))^2);x1=x0;y1=y0;n=n+1;endR=[x0,y0]调用黄金分割法：M文件：function Mini=Gold(f,a0,b0,eps)syms x;format long;syms kk;u=a0+0.382*(b0-a0);v=a0+0.618*(b0-a0);k=0; a=a0;b=b0;array(k+1,1)=a;array(k+1,2)=b; while((b-a)/(b0-a0)>=eps) Fu=subs(f,kk,u); Fv=subs(f,kk,v); if(Fu<=Fv) b=v; v=u;u=a+0.382*(b-a); k=k+1; elseif(Fu>Fv) a=u; u=v;v=a+0.618*(b-a); k=k+1; endarray(k+1,1)=a;array(k+1,2)=b; endMini=(a+b)/2; 输入：[R,n]=steel(0,1,0.0001)R = 1.99999413667642 3.99999120501463 n = 1 非线性等式约束现在考虑用一个线性方程去逼近一个拥有非线性约束问题的可能性，而线性问题就可以像上面的例子那样解决。
要了解如何工作的，考虑下面的例子，它和前面提到的例子类似，但是它的约束是非线性的。
221234211234221234min ()()4440()2220f x x x x xg x x x x x g x x x x x =+++=+++-==-++-+=在当前点x 我们用Taylor 级数逼近约束方程：()()()()Tg x g x g x x x≈+∇-于是：)4(442)4,4,1,2()444()(214321144332211143211=+-+++≈⎪⎪⎪⎪⎪⎭⎫⎝⎛----+-+++≈x x x x x x x x x x x x x x x x x x x x g 和0)2(2)(24443212=++-++-≈x x x x x x x g广义简约梯度法（GRG ）的思想是求解一系列子问题，每个子问题可以利用约束的线性逼近。
在算法的每一步迭代中，利用先前获得的点重新计算线性化约束的点。
一般来说，即使约束是线性逼近的，但每一步迭代获得值也是逐步逼近最优点的。
线性化的一个性质是在最优点，线性化的问题和原问题有相同的解。
使用GRG 的第一步是选择一个初值。
假设我们开始设()00,8,3,0x =，而这个值恰好逼近公式，我们构造的首个逼近问题如下：22123412342123min ()()4440()220f x x x x xg x x x x g x x x x =+++=++-==-+++=程序思路与例1相似，具体参考例1程序。
5.5 约束优化现在我们这个逼近问题的等式约束，用其他变量表示其中的两个变量。
不妨选择2x 和3x ，即得：214248x x x =+-和3141232x x x =--+把这些表达式代入目标函数，获得简化的问题：22141141441min (,)(248)232f x x x x x x x x ⎛⎫=++-+--++ ⎪⎝⎭求解这个无约束的最小化问题，得到140.375,0.96875x x =-=再代入上面表达式，得：234.875, 1.25x x =-=。
因此GRG 方法的第一步迭代产生了一个新点1(0.375, 4.875,1.25,0.96875)X =--继续这个求解过程，在新点上我们重新线性化约束函数，利用获得的线性方程组，把其中两个变量用其他变量表示，然后代入目标函数，就可以得到新的简化问题，求解这个新的简化问题得到新的点2X ，依此类推。