下载文档原格式
第六章 非线性规划由前几章知道，线性规划的目标函数和约束条件都是其自变量的线性函数，如果目标函数或约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。
第一节 基本概念一、 非线性规划的数学模型非线性规划数学模型的一般形式是⎪⎩⎪⎨⎧=≥==),,2,1(0)(),,2,1(0)()(min l j x g m i x h x f ji （6.1）其中，X=（n χχχ,,,21 ）T 是n 维欧氏空间E n 中的点（向量），目标函数)(X f 和约束函数)()(X j X i g h 、为X 的实函数。
有时，也将非线性规划的数学模型写成 ⎩⎨⎧=≥),,2,1(0)()(min l j X g X f j (6.2)即约束条件中不出现等式，如果有某一约束条件为等式0)(=X g j ，则可用如下两个不等式约束替代它： ⎩⎨⎧≥-≥0)(0)(X g X g jj模型（6.2）也常表示成另一种形式：{}⎩⎨⎧=≥=⊂∈),,2,1(,0)(|),(min l j X g X R E R X X f j n (6.3)上式中R 为问题的可行域。
若某个约束条件氏“≤”不等式的形式，只需用“-1”乘这个约束的两端，即可将其变成“≥”的形式。
此外，由于[])(m in )(m ax x f X f --=，且这两种情况下求出的最优解相同（如有最优解存在），故当需使目标函数极大化时，只需求其负函数极小化即可。
二、二维问题的图解当只有两个自变量时，求解非线性规划也可像对线性规划那样借助于图解法。
考虑非线性规划问题⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥≥-+=-+-+-=000505)1()2()(min 212122212221x x x x x x x x x X f (6.4)如对线性规划所作的那样，在21Ox x 坐标平面画出目标函数的等值线，它是以点（2.1）为圆心的同心圆，再根据约束条件画出可行域，它是抛物线段ABCD （图6-1）。
九. 非线性规划(Nonlinear Programming)非线性规划是研究目标函数和约束条件中至少包含一个非线性函数的约束极值最优化问题。
由于非线性问题的复杂性，非线性规划与线性规划相比在理论和算法上呈现出明显的多样性，成果非常丰富。
非线性规划的理论成果包括约束极值问题到达极值解的充分和必要条件（即最优性条件）、非线性规划的对偶理论等。
非线性规划的算法种类繁多，但本质上都是采用数值计算迭代方法求解非线性方程组。
解非线性规划问题时所用的计算方法最常见的是迭代下降算法，即算法同时具有迭代和下降两种特征:迭代：从一点x(k)出发，按某种规则算出后继点x(k+1)；用x(k)代替x(k+1)，重复上述过程，产生点列{x(k)}；下降：对某个函数，每次迭代后，后继点的函数值要有所减少。
评价算法的几个要素通用性与可靠性对参数与数据的敏感性准备与计算的工作量收敛性一维搜索算法可以归纳为两大类：试探法和函数逼近法。
试探法：黄金分割法（0.618法）；Fibonacci法（斐波那契法）函数逼近法：牛顿法；割线法；抛物线法；插值法多维搜索中使用导数的最优化算法（无约束问题）最速下降法（梯度法）；牛顿法（二阶梯度法）；共轭梯度法；拟牛顿法；……多维搜索无约束最优化的直接方法（不用导数）模式搜索法；Rosenbrock算法；单纯形法；……有约束最优化方法可行方向法；惩罚函数法；线性逼近法及二次规划；SQP(序贯二次规划)法；……十.多目标数学规划(Multiobjective Programming)多目标规划标准形式：(VP)实际问题往往难以用一个指标来衡量，需要用一个以上相互间不很协调（甚至相互冲突）的衡量指标，形成多目标规划问题。
x f x f V T p )](,),(min[1符号V －min 表示区别于单目标求最小，指对向量形式的p 个目标求最小。
由于实际问题中p 个目标量纲不同，有必要对每个目标事先规范化。
非线性规划的解法非线性规划是一类重要的数学规划问题，它包含了很多实际应用场景，如金融市场中的资产配置问题，工程界中的最优设计问题等等。
由于非线性目标函数及约束条件的存在，非线性规划问题难以找到全局最优解，面对这样的问题，研究人员提出了众多的解法。
本文将从梯度法、牛顿法、共轭梯度法、拟牛顿法等方法进行介绍，着重讨论它们的优劣性和适用范围。
一、梯度法首先介绍的是梯度法，在非线性规划中，它是最简单的方法之一。
梯度法的核心思想是通过寻找函数的下降方向来不断地优化目标函数。
特别是在解决单峰函数或弱凸函数方面优势明显。
然而，梯度算法也存在一些不足之处，例如：当函数的梯度下降速度过慢时，算法可能会陷入局部最小值中无法跳出，还需要关注梯度方向更新的频率。
当目标函数的梯度非常大，梯度法在求解时可能会遇到局部性和发散性问题。
因此，它并不适合解决多峰、强凸函数。
二、牛顿法在牛顿法中，通过多项式函数的二阶导数信息对目标函数进行近似，寻找下降方向，以求取第一个局部极小值，有时还可以找到全局最小值。
牛顿法在计算方向时充分利用二阶导数的信息，使梯度下降速度更快，收敛更快。
因此，牛顿法适用于单峰性函数问题，同时由于牛顿法已经充分利用二阶信息，因此在解决问题时更加精确，准确性更高。
但牛顿法的计算量比梯度法大，所以不适合大规模的非线性规划问题。
此外，当一些细节信息不准确时，牛顿法可能会导致计算数值不稳定和影响收敛性。
三、共轭梯度法共轭梯度法是非线性规划的另一种解法方法。
共轭梯度法沿预定义的方向向梯度下降，使梯度下降的方向具有共轭性，从而避免了梯度下降法中的副作用。
基于共轭梯度的方法需要存储早期的梯度，随着迭代的进行，每个轴线性搜索方向的计算都会存储预定的轴单位向量。
共轭梯度方法的收敛速度比梯度方法快，是求解非线性规划的有效方法。
四、拟牛顿法拟牛顿法与牛顿法的思路不同，它在目标函数中利用Broyden、Fletcher、Goldfarb、Shanno（BFGS）算法或拟牛顿法更新的方法来寻找下降方向。
非线性规划如果目标函数或约束条件中含有一个或多个是变量的非线性函数，我们称这类规划问题为非线性规划（nonlinear programming ，可简记为NP ）。
一般地，解非线性规划问题要比解线性规划问题困难的多，因为它不像解线性规划问题有单纯形法这一通用的方法，非线性规划目前还没有适合于各种问题的一般算法，各个方法都有自己特定的应用范围。
非线性规划的基本概念和基本原理第一节 非线性规划的数学模型例：某金属制品厂要加工一批容积为1米3的长方形容器，按规格要求，上下底的材料为25元/m2，侧面的材料为40元/m2，试确定长、宽、高的尺寸，使这个容器的成本最低。
设容器的长为1x ，宽为2x ，则高为211x x 。
根据题意得：⎪⎩⎪⎨⎧≥++=0,)](1[8050),(min 2121212121x x x x x x x x x x f 例：某公司经营两种设备，第一种设备每件售价30元，第二种设备每件售价为450元，根据统计，售出一件第一种设备所需营业时间平均为0.5小时，第二种设备为()225.02x +时，其中2x 是第二种设备的售出数量，已知该公司在这段时间内的总营业时间为800小时，试决定使其营业额最大的营业计划。
解：设该公司计划经营第一种设备为错误！未找到引用源。
件，第二种设备为错误！未找到引用源。
件，根据题意得：⎪⎩⎪⎨⎧≥≤+++=0,800)25.02(5.045030),(max 212212121x x x x x x x x x f 由这两个例子可以看出，这两个例子在高等数学中代表了两类不同类型的极值问题。
例1是无条件极值；例2是有条件极值。
如果令),,,(21n x x x X =是n 维空间)(n E上的点，则一般非线性的数学模型为：⎪⎩⎪⎨⎧=≥==l j X g m i X h X f ji ,,2,1 ,0)(,,2,1 ,0)()(min)(X f 为目标函数，)()(X g X h j i ，为约束条件，X 为自变量。
非线性规划的算法研究非线性规划是指目标函数或约束条件中至少包含一个非线性项的数学优化问题。
由于非线性项的存在，非线性规划问题的求解相对较为复杂。
为了解决这类问题，研究者们提出了许多非线性规划的算法，下面将介绍其中几种典型的算法。
一、基本方法：基本方法是一类旨在找到局部最优解的算法。
其中最简单的方法是暴力，即将问题的所有可能解进行穷举，并计算它们对应的目标函数值，从中选择最优解。
虽然暴力方法可以找到全局最优解，但是由于计算量大，适用于问题规模较小的情况。
二、梯度方法：梯度方法是一类基于目标函数的梯度信息进行的方法。
最常用的是梯度下降法，它通过迭代的方式，沿着目标函数的负梯度方向逐步逼近最优解。
梯度方法有很好的收敛性质，但是可能会陷入局部最优解。
三、牛顿法和拟牛顿法：牛顿法是通过对目标函数进行泰勒展开，利用二阶导数矩阵（Hessian矩阵）信息进行的方法。
牛顿法具有快速收敛的特点，但是计算Hessian矩阵比较困难，尤其在高维问题上。
为了克服这一问题，人们提出了拟牛顿法，通过动态更新具有类似于Hessian矩阵的矩阵来近似二阶导数信息。
四、分解策略：分解策略是一种将大规模非线性规划问题分解为多个子问题进行求解的方法。
常见的分解策略包括拉格朗日乘子法、逐步规划法等。
分解策略将原问题分解为小规模子问题，降低了问题的复杂性，但是可能会降低求解的精度。
五、进化算法：进化算法是另一类常用于求解非线性规划问题的算法。
典型的进化算法包括遗传算法、粒子群优化算法等。
进化算法通过模拟自然进化过程，通过交叉、变异等操作不断解空间中的潜在解，并通过适应度函数的评估来更新解的位置。
进化算法适用于复杂的非线性规划问题，但是求解效率相对较低。
综上所述，非线性规划的算法研究涵盖了基本方法、梯度方法、牛顿法和拟牛顿法、分解策略以及进化算法等多个方向。
针对具体问题选择合适的算法可以提高非线性规划问题求解的效率和精度。
但是需要注意的是，不同算法的适用性和性能与问题的特性有关，研究者们需要结合具体问题进行算法选择和优化。
非线性规划的理论与算法非线性规划（Nonlinear Programming, NLP）是数学规划的一个重要分支，其研究对象是带有非线性约束条件的最优化问题。
非线性规划模型常见于各类工程技术问题的优化，如工业系统优化、经济系统优化、交通运输系统优化等。
本文将介绍非线性规划的基本理论和常用的求解算法。
一、非线性规划模型min f(x)s.t.g(x)≤0,h(x)=0其中，f(x)为目标函数；g(x)≤0与h(x)=0为约束条件；x为决策变量，其取值范围由约束条件决定。
非线性规划模型常见的类型包括无约束问题、等式约束问题和不等式约束问题等。
二、非线性规划的求解算法1. 顺序二次规划算法（Sequential Quadratic Programming, SQP）顺序二次规划算法是一种常用的非线性规划求解算法。
该算法通过构造拉格朗日函数来将非线性规划问题转化为一系列二次规划子问题。
通过迭代求解这些二次规划子问题，最终得到原始非线性规划问题的最优解。
SQP算法具有高效、稳定性强等优点，已广泛应用于实际问题中。
2. 内点法（Interior Point Methods）内点法是一种常用的非线性规划求解算法，可以有效处理约束条件较多的非线性规划问题。
该算法通过构造适当的增广 Lagrange 函数，将非线性规划问题转化为一系列无约束优化问题。
通过迭代求解这些无约束优化问题，最终找到原始非线性规划问题的解。
内点法具有收敛速度快、计算精度高等优点。
3. 遗传算法（Genetic Algorithm, GA）遗传算法是一种模拟生物进化过程的启发式优化算法，常用于求解非线性规划问题。
该算法通过借鉴自然选择、交叉和突变等遗传操作，逐步演化出一组较好的解，寻找最优解。
遗传算法不需要假设目标函数和约束条件的具体形式，因此适用于复杂的非线性规划问题。
4. 粒子群优化算法（Particle Swarm Optimization, PSO）粒子群优化算法是一种模拟鸟群觅食行为的优化算法，也常用于求解非线性规划问题。
第五章 非线性规划：理论和算法约束优化我们现在继续讨论更一般的有约束的线性优化问题。
特别的,我们考虑一个具有非线性目标函数和（或者）非线性约束的优化问题。
我们可以将这种问题表示为下面的一般形式：I∈≥∈=i x g i x g x f i i x ,0)(,0)()(min ε在本节的末尾，我们假设f 和i g ，i ε∈⋃I 全部是连续可微的。
拉格朗日函数是研究有约束的优化问题的一个重要工具。
为了定义这个函数，我们结合每个约束的乘子i λ——称作拉格朗日乘子。
对于问题（）拉格朗日函数如下定义：∑I⋃∈-=ελλi iix g x f x L )()(:),( （） 本质上，我们考虑的是目标函数违反了可行约束时的惩罚函数。
选择合适的i λ，最小化无约束函数(),L x λ等价于求解约束问题（）。
这就是我们对拉格朗日函数感兴趣的最根本的原因。
与这个问题相关的最重要问题之一是求解最优问题的充要条件。
总之，这些条件称为最优性条件，也是本节的目的。
在给出问题（）最优性条件之前，我们先讨论一个叫做正则性的条件，由下面的定义给出：定义：设向量x 满足ε∈=i x g i ,0)(和I ∈≥i x g i ,0)(。
设J ⊂I 是使得0)(≥x g i 等号成立的指标集。
x 是问题（）约束条件的正则点，如果梯度向量)(x g i ∇（i J ∈⊂I ）相互线性无关。
在上述定义中与J Y ε对应的约束，即满足0)(=x g i 的约束称为在x 点处的有效约束。
我们讨论第一章提到的两个优化的概念，局部和全局。
回顾（）的全局最优解向量*x ，它是可行的而且满足)()(*x f x f ≤对于所有的x 都成立。
相比之下，局部最优解*x 是可行的而且满足)()(*x f x f ≤对于{}ε≤-*:xx x （0>ε）成立。
因此局部解一定是它邻域的可行点中最优的。
下面我们考虑的最优性条件仅仅判别局部解，则可能是全局最优解，也可能不是。
幸运的是，这里存在一类局部最优解和全局解一致的问题——凸优化问题。
附录A 中讨论的就是基于凸集的凸优化问题。
定理 （一阶必要条件）设*x 是问题（）的局部最小值，假设*x 是这个问题的约束的正则点。
则存在i λ，I ∈Y εi 使得：0)()(**=∇-∇∑I∈Y ελi iix g x f （） I ∈≥i i ,0λ （）I ∈=i x g i i ,0)(*λ （）注意，（）左边表达的意思是拉格朗日函数(),L x λ对每个变量x 的梯度。
一阶条件在局部最小值，局部最大值及鞍点处满足。
当目标函数和约束函数是二次连续可微的时候，可以用函数的曲率排除最大值和鞍点。
根据定理，我们考虑拉格朗日函数(),L x λ和这个函数对每个变量x 的海森矩阵，来计算目标函数和约束函数在当前点处的曲率。
定理（二阶必要条件）假设函数f 和i g （i ε∈⋃I ）都是二次连续可微的。
假设*x 是问题（）局部最小值而且是这个问题的约束正则点。
则存在i λ，i ε∈⋃I 满足（）—（）及下面的条件：∑I∈∇-∇Y ελi i ix g x f )()(*2*2 （）在*x 处有效约束的切线子空间处是半正定的。
定理后半部分可以改写为含有效约束的雅阁比矩阵的形式。
设)(*x A 表示*x 处有效约束的雅阁比矩阵，设)(*x N 表示基于)(*x A 的零空间。
则定理的最后一个条件等价于下面的条件：)()()()(**2*2*x N x g x f x N i i i T ⎪⎪⎭⎫ ⎝⎛∇-∇∑I ∈Y ελ （）是半正定的。
二阶必要条件并非常常保证给出的解的局部最优性。
局部最优性的充分条件更加严格和复杂，因为要考虑到退化的可能性。
定理（二阶充分条件）假设函数f 和i g ，i ε∈⋃I 都是连续二次可微的。
同时假设*x是问题（）可行点而且是这个问题的约束正则点。
设)(*x A 表示*x 处有效约束的雅阁比矩阵，设)(*x N 表示基于)(*x A 的零空间。
如果存在i λ，i ε∈⋃I 满足（）—（）及下面的条件：I ∈=i x g i ,0)(*暗示0>i λ （）和)()()()(**2*2*x N x g x f x N i i i T⎪⎪⎭⎫ ⎝⎛∇-∇∑I ∈Y ελ （）是正定的，则*x 是问题（）的局部最小值。
定理、和中列出的条件称作Karush-Kuhn-Tucker (KKT) 条件，以它们的发明者命名的。
一些求解约束优化问题的方法表达成一系列简单的可以用一般迭代步骤求出解的简单优化问题。
这些“简单”的问题可以是无约束的，此时可以应用我们前面章节介绍的方法求解。
我们在中考虑这些策略。
在其他情况下，这些简单的问题是二次规划且可以应用第七章中的方法求解。
这个策略的典型例子是中讨论的连续二次规划问题。
广义简约梯度法在本节中，我们介绍一种求解有约束的非线性规划的方法。
这种方法建立在前文讨论的无约束优化法之最速下降法的基础上的。
这种方法的思想是利用约束减少变量的个数，然后用最速下降法去求解简化的无约束的问题。
线性等式约束首先我们讨论一个约束是线性方程组的例子。
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 =++-+-++这个简化形式是无约束的，因此可以利用节的最速下降法求解。
例1：用最速下降法求min f(x)=f=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,;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+*(b0-a0);v=a0+*(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+*(b-a); k=k+1; elseif(Fu>Fv) a=u; u=v; v=a+*(b-a); k=k+1; endarray(k+1,1)=a;array(k+1,2)=b; endMini=(a+b)/2; 输入：[R,n]=steel(0,1, R = 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程序。
约束优化现在我们这个逼近问题的等式约束，用其他变量表示其中的两个变量。
不妨选择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 ，依此类推。
利用停止准则1k k XX T +-≤其中= 0.0025T 。
我们得到结果如下表.把这个结果同最优解*(0.500, 4.825,1.534,0.610)x=--比较，其目标值是 1.612-。
