第五章 非线性规划：理论和算法
约束优化
我们现在继续讨论更一般的有约束的线性优化问题。特别的,我们考虑一个具有非线性目标函数和（或者）非线性约束的优化问题。我们可以将这种问题表示为下面的一般形式：
I
∈≥∈=i x g i x g x f i i x ,0)(,0)()
(min ε
在本节的末尾，我们假设f 和i g ，i ε∈?I 全部是连续可微的。
拉格朗日函数是研究有约束的优化问题的一个重要工具。为了定义这个函数，我们结合每个约束的乘子i λ——称作拉格朗日乘子。对于问题（）拉格朗日函数如下定义：
∑I
?∈-
=ε
λλi i
i
x 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 ≤对于{
}
ε≤-*
:x
x x （0>ε）成立。因此局部解一定是它邻域
的可行点中最优的。下面我们考虑的最优性条件仅仅判别局部解，则可能是全局最优解，也可能不是。幸运的是，这里存在一类局部最优解和全局解一致的问题——凸优化问题。附录A 中讨论的就是基于凸集的凸优化问题。
定理 （一阶必要条件）设*x 是问题（）的局部最小值，假设*
x 是这个问题的约束的
正则点。则存在i λ，I ∈Y εi 使得：
0)()(*
*=?-
?∑I
∈Y ε
λi i
i
x 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 i
x 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) 条件，以它们的发明者命名的。 一些求解约束优化问题的方法表达成一系列简单的可以用一般迭代步骤求出解的简单优化问题。这些“简单”的问题可以是无约束的，此时可以应用我们前面章节介绍的方法求解。我们在中考虑这些策略。在其他情况下，这些简单的问题是二次规划且可以应用第七章中的方法求解。这个策略的典型例子是中讨论的连续二次规划问题。
广义简约梯度法
在本节中，我们介绍一种求解有约束的非线性规划的方法。这种方法建立在前文讨论的无约束优化法之最速下降法的基础上的。这种方法的思想是利用约束减少变量的个数，然后用最速下降法去求解简化的无约束的问题。 线性等式约束
首先我们讨论一个约束是线性方程组的例子。
22
1234
1123421234min ()()4440()2220
f x x x x x
g x x x x x g x x x x x =+++=+++-==-++-+=
在其他变量给定情况下，很容易求解只有两个变量的约束方程。给定1x ，4x ，令
214388x x x =+- 和31433x x x =--+。
把这些变量代入目标函数，然后得到下面简化的形式：
()2
214114144
min (,)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;
end
R=[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; end
array(k+1,1)=a;array(k+1,2)=b; end
Mini=(a+b)/2; 输入：
[R,n]=steel(0,1, R = n = 1 非线性等式约束
现在考虑用一个线性方程去逼近一个拥有非线性约束问题的可能性，而线性问题就可以像上面的例子那样解决。要了解如何工作的，考虑下面的例子，它和前面提到的例子类似，但是它的约束是非线性的。
22
1234
2112342
21234min ()()4440
()2220
f x x x x x
g x x x x x g x x x x x =+++=+++-==-++-+=
在当前点x 我们用Taylor 级数逼近约束方程：
()
()()()T
g x g x g x x x
≈+?-
于是：
)4(442)4,4,1,2()444()(214321144
332211143211=+-+++≈?
???
???
??----+-+++≈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 的第一步是选择一个初值。假设我们开始设()0
0,8,3,0x =，而这个值恰好
逼近公式，我们构造的首个逼近问题如下：
22
1234
12342123min ()()4440()220
f x x x x x
g x x x x g x x x x =+++=++-==-+++=
程序思路与例1相似，具体参考例1程序。
约束优化
现在我们这个逼近问题的等式约束，用其他变量表示其中的两个变量。不妨选择2x 和
3x ，即得：
214248x x x =+-和3141
232
x x x =--+
把这些表达式代入目标函数，获得简化的问题：
2
214114144
1min (,)(248)232f x x x x x x x x ??
=++-+--++ ???
求解这个无约束的最小化问题，得到1
40.375,0.96875x x =-=再代入上面表达式，得：
234.875, 1.25x x =-=。因此GRG 方法的第一步迭代产生了一个新点
1(0.375, 4.875,1.25,0.96875)X =--
继续这个求解过程，在新点上我们重新线性化约束函数，利用获得的线性方程组，把其中两个变量用其他变量表示，然后代入目标函数，就可以得到新的简化问题，求解这个新的
简化问题得到新的点2
X ，依此类推。利用停止准则1
k k X
X T +-≤其中= 0.0025T 。
我们得到结果如下表.
把这个结果同最优解*
(0.500, 4.825,1.534,0.610)x
=--比较，其目标值是 1.612-。
观察表，注意到当1k =或2k =时，函数
()k f x 的值有时比最小值小，这是怎么回事呢原
因是通过GRG 方法计算获得的点k x 通常不满足约束条件。它们只对这些约束条件的线性逼近可行。
现在我们讨论如何在一个不可行的点使用GRG 方法：第一阶段问题是构建一个满足约束条件的点。第一阶段的目标函数是违反约束的绝对值总和。而第一阶段问题的约束都是不违反约束的。假设我们在点()0
1,1,0,1x =开始计算，这个点不满足第一个约束，但满足第二
个约束，所以第一阶段问题是：
212342
1234
min 444
2220
x x x x x x x x +++--++-+=
一旦通过解决第一阶段问题获得一个适宜的解，那么上面阐述的方法就可以用来求最优解。
线性不等式约束
最后，我们讨论GRG 是怎样像解决等式问题那样解决有不等式约束的问题。在每次迭代中，只有严格满足不等式约束的量才能进入线性方程组，以消除变量（这些不等式约束通常被认为是有效的）。这个过程是复杂的，由于为了得到好的结果，在当前点的每一个不等式约束都有被舍弃的可能。我们在下面的例子中说明了这一点。
2212121212215
min (,)()()220
002
f x x x x x x x x x =-+--≥≥≥≤
图广义简约梯度算法的过程
这个问题的可行集合显示在图中。图中的可行箭头表示由每个约束指向的可行的超平面。假设我们从)0,1(0
=x 开始。这一点满足所有约束条件。从图可以看出：
120x x -≥,10x ≥,22x ≤三个约束条件是无效的，而约束20x ≥是有效的。我们必须决
定2x 是否应该留在它的下界还是允许它离开边界。
()()000
12()21,251,5f x x x ?=--=-。
这表明如果我们沿方向()0
()1,5d f x =-?=- 移动，f 减少的最多，即减少1x 增大
2x 。
因为这个方向朝向可行区域内部，我们决定从边界释放2x 。新的点变成1000x x d α=+
其中00α≥。这个约束引入了0α的一个上限，也就是00.8333α≤。接下来我们通过线性搜索来确定0α在这个范围之内的最优值。结果是00.8333α=，从而
()10.8333,0.8333x =；参见图 。
现在，我们重复这个过程：约束
120x x -≥开始起作用，其他约束失效。因为活动约
束不是一个简单的上下限约束，我们引入一个剩余变量 3x ，然后将其中之一用其余变量表示。代入1
23x x x =+，我们得到如下化简的优化问题
()22
232322315min ,2202
f x x x x x x x ?
???=+-+- ? ?
?
???≤≤≥ 在()1
23(,)0.8333,0x x =简约梯度为
()
()
2323223(,)22125,2212.667,0.667f x x x x x x x ?=+-+-+-=-
因此f 在()2.667,0.667-方向降幅最大，也就是要增大 2x 并减小3x 。但是 3x 已经到达其下界，我们无法再减小它。因此我们保持 3x 在它的下界处，即我们沿方向
()1 2.667,0d =到达新的点21112323(,)(,)x x x x d α=+。沿这个方向的线性搜索给出
10.25α=，()223(,) 1.5,0x x =。接下来仍然是该约束有效，所以我们仍然在2x 和3x 的空
间中。在()2
23(,) 1.5,0x x =处的梯度()23(,)0,2f x x ?=与当前解2X 的边界线垂直，且指
向可行区域的外部，因而f 不可能进一步减小。于是我们找到了最优解。对应于最初的变量空间，这个最优解就是1
1.5x =和2 1.5x =。
这就是一些广泛使用的非线性规划求解方法，例如 Excel 的 SOLVER, GINO, CONOPT,GRG2以及一些其他的方法用来求解非线性规划问题的方法。具体求解时只需附加一些额外细节，例如线性搜索时的 Newton-Raphson 方向等。同线性规划相比，能够在一个合理的计算时间内解决的问题通常规模比较小，并且求得的结果也可能不是特别精确。另外，可行集合或目标函数潜在的非凸性会导致求解结果是局部最优的而远非全局解。因此在解释非线性规划的结果时需要更加小心。
序列二次规划
考虑一般的非线性最优化问题
I
∈≥∈=i x g i x g x f i i x ,0)(,0)()
(min ε （） 为了解决这个问题，有人试图利用可得到的较好的算法解决更有条理、更简单的二次规划（参见第七章）。这是连续二次方程背后的思想。在当前可行点k x ，问题（）是由一个二次规划来近似的：拉格朗日函数的近似二次方程可以像近似的线性约束一样计算。可以得到如下的二次方程规划问题：
()()()()()1min ()2
()()0,(5.21)
()()0,T
k T k k k k k T k k i i k T k k i i f x x x x x B x x g x x x g x i g x x x g x i ?-+
--?-+=?∈E ?-+≥?∈I
其中2(,)k k k
xx B L x λ=?，是拉格朗日函数（）的海森矩阵，k
λ为当前估计的拉格朗日
乘数。
这个问题可以用解决二次方程规划问题的一种特殊算法来解，例如我们在第七章讨论的
内点方法。二次规划的最优解是用来确定搜索方向。那么线性搜索或信赖域程序是为了确定下一个迭代。
也许思考序列二次规划的最好方式是将其作为求解有约束条件问题的牛顿法的优化版的扩展。回想一下，牛顿方法的优化版使用目标函数的二次逼近，定义这个逼近的最小值作为下一次迭代值，这很像我们描述的SQP 方法。的确，对于一个无约束问题，二次规划与牛顿法是相同的。对于约束问题，在解决SQP 时的二次规划问题的最优性条件相当于在当前迭代下牛顿法直接指向的原来问题的最优化条件。
序列二次规划迭代直到该问题收敛。就像牛顿法一样，二次规划方法是非常强大，尤其是当运用线性搜索或信赖域方法来处理非线性和非凸性。我们推荐读者翻阅Boggs and Tolle [14]和Nocedal and Wright [55]来进一步了解二次规划方法。
非光滑优化：次梯度方法
在这一部分，我们考虑无约束非线性规划的形式()min f x 当()12,,,n x x x x =???并且
f 是一个不可微的凸函数。由于在此情况下没有定义梯度，所以无法获得基于梯度的最优
条件。然而，梯度的概念可被推广如下。f 在*x 点的次梯度是向量(
)
*
***
12,,,n s s s s =???使
***(x )()()s x f x f x -≤-对任意x 都成立。
当函数f 是可微的，次梯度和梯度是相同的；当函数f 在x 点处不可微，通常在x 处有许多次梯度。例如，考虑含有一个变量的凸函数
{}()max 1,11
f x x x x =--=-
从图可明显看出这个函数在1x =处是不可微的，并且很容易验证任意使得11≤≤-s 的向量是f 在点1x =处的次梯度。其中的一些次梯度以及它们所定义的线性逼近可由图5-6所示。请注意每个函数的次梯度在一点处定义了一个函数的切线，而这些切线永远待在函数图像的下边——这是次梯度定义的属性。
考虑一个不可微的凸函数f 。在点*
x 处取得最小值当且仅当f 在*
x 点有一个为零的次梯度。在上述例子中，0是f 在点1*=x 处的一个次梯度，因此我们得到f 的最小值点。
图
最速下降法可以通过计算任何次梯度方向且使用相反的方向扩展到不可微的凸函数来进行下一步。尽管次梯度方向不总是上升的方向，不过可以选择适当的步长保证收敛到最佳点。一般的次梯度方法可以表述为如下：
1.初始化：从任一点0x 开始，设1i =；
2.迭代 i ：计算函数f 在点x 处的一个次梯度i s 。如果0i s =或趋近于0，停止。否则，让i i i i s x x
α-=+1
（)0>i α表示一个步长，并进行下一次迭代。
几种选取步长i α的方法已在文献中讲过。为了保证收敛到最优点，步长i α需要非常缓慢的递减（例如0→i α使得
∑+∞=i
i
α
成立）
。但是i α缓慢的减少导致i x 缓慢的收敛到最优点。在实际中，为了提高收敛速度，常用到下面的方法:从20=α开始，如果连续的k （k 通常用7或8）次迭代后观察的目标值
()i f x 没有改进，则将步长减半。当人们想快速
的得到最优解时，或者发现精确地最优解不是那么重要（这是在整数规划中的应用，用次梯度最优化方法来快速获得分枝定界算法中的界限）时，这种方法很合适。有了这种思想，在实际中经常用的一个终止准则是一个最大的迭代次数（例如200）而不是i s 为0或趋近于0。
我们将在第12章看到次梯度最优化方法是怎样应用在一个构建基金指数的模型中的。
XX大学 智能优化算法课内实验报告书 院系名称： 学生姓名： 专业名称： 班级： 学号： 时间：
非线性规划问题的粒子群算法 1.1背景介绍 1.1.1 非线性规划简介 具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要的分支，非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的机制问题且目标函数和约束条件至少有一个是未知量的非线性函数，目标函数和约束条件都是线性函数的情形则属于线性规划。 非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年H.W库恩和A.W塔克发表的关于最优性条件的论文是非线性规划正式诞生的一个重要标志。在50年代可得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。 非线性规划问题广发存在于科学与工程领域，是一类比较难以解决的优化问题，没有普遍使用的解法。传统的求解该问题的方法（如罚函数，可行方向法，以及变尺度法等）是基于梯度的方法所以目标函数与约束式必须是可微的，并且这些方法只能保证求的局部最优解。 1.1.2 粒子群算法简介 粒子群算法（Particle Swarm optimization，PSO）的基本概念源于对于鸟群捕食行为的简化社会模型的模拟，1995年由Kenndy和Eberhart等人提出，它同遗传算法类似，通过个体间的协作和竞争实现全局搜索系统初始化为一组随机解，称之为粒子。通过粒子在搜索空间的飞行完成寻优，在数学公式中即为迭代，它没有遗传算法的交叉及变异算子，而是粒子在解空间追随最优的粒子进行搜索。 PSO算法的改进主要在参数选择、拓扑结构以及与其他优化算法相融合方面。据此当前典型的改进算法有：自适应PSO算法、模糊PSO算法、杂交PSO 算法、混合粒子算法（HPSO）和离散PSO算法等等。其中自适应和模糊PSO 算法是EberhartShi研究了惯性因子ω对优化性能的影响，发现较大的ω值有利于跳出局部极小点，较小的ω值有利于算法的收敛。自适应PSO算法通过线性地减少ω值动态的调整参数ω，而模糊PSO算法则在此基础上利用模糊规则动态调
非线性最优化理论与算法 第一章引论 本章首先给出了一些常见的最优化问题和非线性最优化问题解的定义，并且根据不同的条件对其进行了划分。接着给出了求解非线性优化问题的方法，如图解法等，同时又指出一个好的数值方法应对一些指标有好的特性，如收敛速度与二次终止性、稳定性等。随后给出了在非线性最优化问题的理论分析中常用到的凸集和凸函数的定义和有关性质。最后给出了无约束优化最优性条件。 第二章线搜索方法与信赖域方法 无约束优化的算法有两类，分别是线搜索方法和信赖域方法。本章首先给出了两种线搜索方法即精确线搜索方法和非精确线搜索方法。线搜索方法最重要的两个要素是确定搜索方向和计算搜索步长，搜索步长可确保下降方法的收敛性，而搜索方向决定方法的收敛速度。 精确线搜索方法和非精确线搜索方法 对于精确线搜索方法，步长ακ满足 αk=arg min ?x k+αd k α≥0 这一线搜索可以理解为αk是f(x k+αd k)在正整数局部极小点，则不论怎样理解精确线搜索，它都满足正交性条件： d k T??(x k+αk d k)=0 但是精确搜索方法一般需要花费很大的工作量，特别是当迭代点远离问题的解时，精确的求解问题通常不是有效的。而且有些最优化方法，其收敛速度并不依赖于精确搜索过程。对于非精确搜索方法，它总体希望收敛快，每一步不要求达到精确最小，速度快，虽然步数增加，则整个收敛达到快速。书中给出了三种常用的非精确线搜索步长规则，分别是Armijo步长规则、Goldstein步长规则、Wolfe步长规则。第一个步长规则的不等式要求目标函数有一个满意的下降量，第二个不等式控制步长不能太小，这一步长规则的第二式可能会将最优步长排除在步长的候选范围之外，也就是步长因子的极小值可能被排除在可接受域之外。但Wolfe步长规则在可接受的步长范围内包含了最优步长。在实际计算时，前两种步长规则可以用进退试探法求得，而最后一种步长规则需要借助多项式插值等方法求得。紧接着，又介绍了Armijo和Wolfe步长规则下的下降算法的收敛性。 信赖域方法 线性搜索方法都是先方向再步长，即先确定一个搜索方向d k，然后再沿着这个搜索方向d k选择适当的步长因子αk，新的迭代点定义为x k+1=x k+αk d k。与线搜索方法不同，信赖域方法是先步长再方向,此方法首先在当前点附近定义目标函数的一个近似二次模型，然后利用目标函数在当前点的某邻域内与该二次模型的充分近似，取二次模型在该邻域内的最优值点来产生下一迭代点。它把最优化
通常，非线性整数规划是一个具有指数复杂度的NP问题，如果约束较为复杂，Matlab优 化工具箱和一些优化软件比如lingo等，常常无法应用，即使能应用也不能给出一个较为令 人满意的解。这时就需要针对问题设计专门的优化算法。下面举一个遗传算法应用于非线性整数规划的编程实例，供大家参考! 模型的形式和适应度函数定义如下: nun ￡ =迟叼匸［（1_冏）督 i-1 /-I J=K乙员-??严丿=12 M…严 ▼ 0 或1* 适应度函数为3 Fi tn叱O）=》〔?巾1口｛＞?（卡（￡）一/；0?门））转幷亠 Z j'-i 50 4 S0 其中比=2、即士￡ = ￡ =瓦％■，口（1-务），马；j^ = s = ■ x v' y- to.8,02）., /-I i-L i-1 E 这是一个具有200个01决策变量的多目标非线性整数规划，编写优化的目标函数如下，其 中将多目标转化为单目标采用简单的加权处理。 fun ctio n Fit ness=FITNESS(x,FARM,e,q,w) %%适应度函数 %输入参数列表 % x 决策变量构成的 4X50的0-1矩阵 % FARM 细胞结构存储的当前种群，它包含了个体x
% e 4 X50的系数矩阵 % q 4 X50的系数矩阵 % w 1 X50的系数矩阵 %% gamma=0.98; N=length(FARM);% 种群规模 F1=zeros(1,N); F2=zeros(1,N); for i=1:N xx=FARM{i}; ppp=(1-xx)+(1-q).*xx; F1(i)=sum(w.*prod(ppp)); F2(i)=sum(sum(e.*xx)); end ppp=(1-x)+(1-q).*x; f1=sum(w.*prod(ppp)); f2=sum(sum(e.*x)); Fitness=gamma*sum(min([sign(f1-F1);zeros(1,N)]))+(1-gamma)*sum(min([sign(f2- F2);zeros(1,N)])); 针对问题设计的遗传算法如下，其中对模型约束的处理是重点考虑的地方 function [Xp,LC1,LC2,LC3,LC4]=MYGA(M,N,Pm) %% 求解 01 整数规划的遗传算法 %% 输入参数列表
非线性规划模型 在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法。对于线性规划来说，其可行域一般是一个凸集，只要存在最优解，则其最优解一定在可行域的边界上达到；对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到，因此，对于非线性规划模型，迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍了几个比较常用的几个求解方法。 一、非线性规划的分类 1无约束的非线性规划 当问题没有约束条件时，即求多元函数的极值问题，一般模型为 ()min 0 x R f X X ∈??? ≥?? 此类问题即为无约束的非线性规划问题 1.1无约束非线性规划的解法 1.1.1一般迭代法 即为可行方向法。对于问题()min 0x R f X X ∈??? ≥?? 给出)(x f 的极小点的初始值)0(X ，按某种规律计算出一系列的 ),2,1()( =k X k ，希望点阵}{)(k X 的极限*X 就是)(x f 的一个极小点。 由一个解向量) (k X 求出另一个新的解向量)1(+k X 向量是由方向和长度确定的，所以),2,1()1( =+=+k P X X k k k k λ 即求解k λ和k P ，选择k λ和k P 的原则是使目标函数在点阵上的值逐步减小，即 .)()()(10 ≥≥≥≥k X f X f X f 检验}{)(k X 是否收敛与最优解，及对于给定的精度0>ε，是否 ε≤?+||)(||1k X f 。 1.1.2一维搜索法 当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有： （1）试探法（“成功—失败”，斐波那契法，0.618法等）； （2）插值法（抛物线插值法，三次插值法等）；
第一章非线性规划理论（1） 第一节非线性优化规划模型及其解的概念, 第二节凸函数与凸规划, 第三节下降迭代算法 第四节一维搜索方法 第一节非线性优化规划模型及其解的概念 线性规划的目标函数和约束条件都是其自变量的线性函数，如果目标函数或约束条件中含有自变量的非线性函数，则这样的规划问题就是非线性规划。有些实际问题可以表示成线性规划，但有些实际问题则需要用非线性规划模型来表达。 例1 求，使得 （1） 该数学模型中目标函数是一个二次函数，因此它是一个非线性规划。 又如：求，使得 （2） 是一个非线性规划。 1.1 非线性规划问题的数学模型 非线性规划数学模型的一般形式为 （3） 其中是维欧氏空间中的向量（点），是目标函数，为约束条件，、都是元实函数。 说明： （1）由于我们有，当需使目标函数极大化时，只需使其负值极小化即可，因而仅考虑极小化的情况不失一般性。 （2）若某约束条件是“”不等式，仅需要在约束两端乘以“－1”，即可将这个约束变为“”。又由于约束等价于 因而我们可以将非线性规划模型写成下面的形式： （4） 或 （5） 模型中的称为非线性规划的可行域，而中的元素称为可行解。 1.2 二维问题的图解法 当只有两个决策变量时，求解非线性规划也可以像线性规划那样用图解法。 例2
解：先画出可行域 X2 A B C D O x1 可行域 等值线 最优解 画出抛物线 ， 即图中的曲线，再画出 直线，即图中的 直线，得可行域。 画出等值线 ，图中有一条等值线与抛物线 交于B点，当动点从A点出发延 抛物线移动时，动点从A移向B时，目标函数值下降，动点从B移向C 时，目标函数值上升，所以在可行域范围内B点的函数值最小，所以B 点是一个极小点。当动点由C点向D点移动时，目标函数再次下降，在D（4，1）点目标函数值最小，所以D点是最优解。 本例中，B点称为局部极小点，而D点称为全局极小点，即最小点。 1.3 非线性规划的基本概念 1.3.1关局部极小和全局极小的定义 设为定义在维欧氏空间的某一个区域上的元实函数，对于，如果存在某一个使得所有与距离小于的都有，则称为在上的局部极小点，而为局部极小值。如果当时，有，则称为在上的严格局部极小点，而为严格局部极小值。 设为定义在维欧氏空间的某一个区域上的元实函数，如果存在，对于所有，都有，则称为在上的全局极小点，而为全局极小值。如果当时，有，则称为在上的严格全局极小点，而为严格全局极小值。
非线性规划（nonlinear programming） 1.非线性规划概念 非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。 2.非线性规划发展史 公元前500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为0.618,称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。例如阿基米德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。但是最优化方法真正形成为科学方法则在17世纪以后。17世纪，I.牛顿和G.W.莱布尼茨在他们所创建的微积分中，提出求解具有多个自变量的实值函数的最大值和最小值的方法。以后又进一步讨论具有未知函数的函数极值，从而形成变分法。这一时期的最优化方法可以称为古典最优化方法。 最优化方法不同类型的最优化问题可以有不同的最优化方法，即使同一类型的问题也可有多种最优化方法。反之,某些最优化方法可适用于不同类型的模型。最优化问题的求解方法一般可以分成解析法、直接法、数值计算法和其他方法。 (1)解析法：这种方法只适用于目标函数和约束条件有明显的解析表达式的情况。求解方法是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用求导数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。 (2)直接法：当目标函数较为复杂或者不能用变量显函数描述时，无法用解析法求必要条件。此时可采用直接搜索的方法经过若干次迭代搜索到最优点。这种方法常常根据经验或通过试验得到所需结果。对于一维搜索(单变量极值问题)，主要用消去法或多项式插值法；对于多维搜索问题(多变量极值问题)主要应用爬山法。 (3)数值计算法：这种方法也是一种直接法。它以梯度法为基础，所以是一种解析与数值计算相结合的方法。 (4)其他方法：如网络最优化方法等。
第三章 非线性规划 §1 非线性规划 1.1 非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。 下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本概念。 例 1 （投资决策问题）某企业有n 个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金A 元，投资于第),,1(n i i 个项目需花资金i a 元，并预计可收益i b 元。试选择最佳投资方案。 解 设投资决策变量为 个项目 决定不投资第，个项目决定投资第i i x i 0,1，n i ,,1 ， 则投资总额为 n i i i x a 1 ，投资总收益为 n i i i x b 1。因为该公司至少要对一个项目投资，并且总的投资金额不能超过总资金A ，故有限制条件 n i i i A x a 10 另外，由于),,1(n i x i 只取值0或1，所以还有 .,,1,0)1(n i x x i i 最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为： n i i i n i i i x a x b Q 11 max s.t. n i i i A x a 10 .,,1,0)1(n i x x i i 上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中至少有一个非线性函数，这类问题称之为非线性规划问题。可概括为一般形式 )(min x f q j x h j ,,1,0)(s.t. (NP) p i x g i ,,1,0)(
非线性规划模型 在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在 实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都 可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法。对于线性规划来说，其可行域一般是一个凸集，只要存在最优解，则其最优解一定在可行域的边界上达到；对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到，因此，对于非线性规划模型，迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍了几个比较常用的几个求解方法。 一、非线性规划的分类1无约束的非线性规划当问题没有约束条件时，即求多元函数 的极值问题，一般模型为 I r m i n f(X) X 一0 此类问题即为无约束的非线性规划问题 1.1无约束非线性规划的解法 1.1.1 一般迭代法 即为可行方向法。对于问题J mnf(X) [X X O 给出f (X)的极小点的初始值X(O),按某种规律计算出一系列的X(k)(k =1,2,…)， 希望点阵｛X (k)｝的极限X "就是f (X)的一个极小点。 由一个解向量X(k)求出另一个新的解向量X(kI) 向量是由方向和长度确定的，所以XZ I)=X k「k P k(k =12…) 即求解A和P k,选择'k和P k的原则是使目标函数在点阵上的值逐步减小，即 f (X0) 一f (X1) 一- f (X k) 一. 检验｛X(k)｝是否收敛与最优解，及对于给定的精度；7,是否IIlf(X k JlF ； 1.1.2 一维搜索法 当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有： (1)试探法(“成功一失败”，斐波那契法，0.618法等)； (2)插值法(抛物线插值法，三次插值法等)； (3)微积分中的求根法(切线法，二分法等)。考虑一维极小化问题 a?f(t) 若f (t)是[a,b]区间上的下单峰函数，我们介绍通过不断地缩短[a,b]的长度，来
题 目 非线性规划的MATLAB 解法及其应用 （一） 问题描述 非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划是20世纪50年代才开始形成的一门新兴学科。70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。在经营管理、工程设计、科学研究、军事指挥等方面普遍地存在着最优化问题。例如：如何在现有人力、物力、财力条件下合理安排产品生产，以取得最高的利润；如何设计某种产品，在满足规格、性能要求的前提下，达到最低的成本；如何确定一个自动控制的某些参数，使系统的工作状态最佳；如何分配一个动力系统中各电站的负荷，在保证一定指标要求的前提下，使总耗费最小；如何安排库存储量，既能保证供应，又使储存 费用最低；如何组织货源，既能满足顾客需要，又使资金周转最快等。对于静态的最优化 问题，当目标函数或约束条件出现未知量的非线性函数，且不便于线性化，或勉强线性化后会招致较大误差时，就可应用非线性规划的方法去处理。具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划研究一个n 元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。本实验就是用matlab 软件来解决非线性规划问题。 （二） 基本要求 掌握非线性规划的MATLAB 解法,并且解决相关的实际问题。 题一 ：对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？ 题二： 某厂生产一种产品有甲、乙两个牌号，讨论在产销平衡的情况下如何确定各自的产量，使总利润最大. 所谓产销平衡指工厂的产量等于市场上的销量.符号说明：z(x 1,x 2)表示总利润；p 1，q 1，x 1分别表示甲的价格、成本、销量； p 2，q 2，x 2分别表示乙的价格、成本、销量； a ij ，b i ，λi ,c i （i ，j =1，2）是待定 系数. 题三：设有400万元资金, 要求4年内使用完, 若在一年内使用资金x 万元, 则可得效益x 万元(效益不能再使用),当年不用的资金可存入银行, 年利率为10%. 试制定出资金的使用计划, 以使4年效益之和为最大. （三） 数据结构 题一:设剪去的正方形的边长为x ，则水槽的容积为：x x )23(2-;建立无约束优化模型为：min y=-x x )23(2-， 0 第五章 非线性规划的概念和原理 非线性规划的理论是在线性规划的基础上发展起来的。1951年，库恩（H.W.Kuhn ）和塔克（A.W.Tucker ）等人提出了非线性规划的最优性条件，为它的发展奠定了基础。以后随着电子计算机的普遍使用，非线性规划的理论和方法有了很大的发展，其应用的领域也越来越广泛，特别是在军事，经济，管理，生产过程自动化，工程设计和产品优化设计等方面都有着重要的应用。 一般来说，解非线性规划问题要比求解线性规划问题困难得多，而且也不像线性规划那样有统一的数学模型及如单纯形法这一通用解法。非线性规划的各种算法大都有自己特定的适用范围。都有一定的局限性，到目前为止还没有适合于各种非线性规划问题的一般算法。这正是需要人们进一步研究的课题。 5.1 非线性规划的实例及数学模型 [例题6.1] 投资问题： 假定国家的下一个五年计划内用于发展某种工业的总投资为b 亿元，可供选择兴建的项目共有几个。已知第j 个项目的投资为j a 亿元，可得收益为j c 亿元，问应如何进行投资，才能使盈利率（即单位投资可得到的收益）为最高？ 解：令决策变量为j x ，则j x 应满足条件() 10j j x x -= 同时j x 应满足约束条件 1 n j j j a x b =≤∑ 目标函数是要求盈利率()1121 ,,,n j j j n n j j j c x f x x x a x === ∑∑L 最大。 [例题6.2] 厂址选择问题： 设有n 个市场，第j 个市场位置为() ,j j p q ，它对某种货物的需要量为j b ()1,2,,j n =L 。 现计划建立m 个仓库，第i 个仓库的存储容量为i a ()1,2,,i m =L 。试确定仓库的位置，使各仓库对各市场的运输量与路程乘积之和为最小。 解：设第i 个仓库的位置为(),i i x y ()1,2,,i m =L ，第i 个仓库到第j 个市场的货物供应量为i j z ()1,2,,,1,2,,i m j n ==L L ，则第i 个仓库到第j 个市场的距离为 求解非线性规划 ————————————————————————————————作者：————————————————————————————————日期： 非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。 1.2 线性规划与非线性规划的区别 如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。 1.3 非线性规划的Matlab 解法 Matlab 中非线性规划的数学模型写成以下形式 )(min x f ???????=≤=?≤0 )(0)(x Ceq x C Beq x Aeq B Ax , 其中)(x f 是标量函数，Beq Aeq B A ,,,是相应维数的矩阵和向量，)(),(x Ceq x C 是非线性向量函数。 Matlab 中的命令是 X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS) 它的返回值是向量x ，其中FUN 是用M 文件定义的函数)(x f ；X0是x 的初始值；A,B,Aeq,Beq 定义了线性约束Beq X Aeq B X A =≤*,*，如果没有等式约束，则A=[],B=[],Aeq=[],Beq=[]；LB 和UB 是变量x 的下界和上界，如果上界和下界没有约束，则LB=[]，UB=[]，如果x 无下界，则LB=-inf ，如果x 无上界，则UB=inf ；NONLCON 是用M 文件定义的非线性向量函数)(),(x Ceq x C ；OPTIONS 定义了优化参数，可以使用Matlab 缺省的参数设置。 例2 求下列非线性规划问题 非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。 1.2 线性规划与非线性规划的区别 如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。 1.3 非线性规划的Matlab 解法 Matlab 中非线性规划的数学模型写成以下形式 )(min x f ???????=≤=?≤0 )(0)(x Ceq x C Beq x Aeq B Ax , 其中)(x f 是标量函数， Beq Aeq B A ,,,是相应维数的矩阵和向量，)(),(x Ceq x C 是非线性向量函数。 Matlab 中的命令是 X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS) 它的返回值是向量x ，其中FUN 是用M 文件定义的函数)(x f ；X0是x 的初始值；A,B,Aeq,Beq 定义了线性约束Beq X Aeq B X A =≤*,*，如果没有等式约束，则A=[],B=[],Aeq=[],Beq=[]；LB 和UB 是变量x 的下界和上界，如果上界和下界没有约束，则LB=[]，UB=[]，如果x 无下界，则LB=-inf ，如果x 无上界，则UB=inf ；NONLCON 是用M 文件定义的非线性向量函数)(),(x Ceq x C ；OPTIONS 定义了优化参数，可以使用Matlab 缺省的参数设置。 例2 求下列非线性规划问题 非线性整数规划的遗传算法Matlab程序（附图） 通常，非线性整数规划是一个具有指数复杂度的NP问题，如果约束较为复杂，Matlab优化工具箱和一些优化软件比如lingo等，常常无法应用，即使能应用也不能给出一个较为令人满意的解。这时就需要针对问题设计专门的优化算法。下面举一个遗传算法应用于非线性整数规划的编程实例，供大家参考！ 模型的形式和适应度函数定义如下： 这是一个具有200个01决策变量的多目标非线性整数规划，编写优化的目标函数如下，其中将多目标转化为单目标采用简单的加权处理。 function Fitness=FITNESS(x,FARM,e,q,w) %% 适应度函数 % 输入参数列表 % x 决策变量构成的4×50的0-1矩阵 % FARM 细胞结构存储的当前种群，它包含了个体x % e 4×50的系数矩阵 % q 4×50的系数矩阵 % w 1×50的系数矩阵 %% gamma=0.98; N=length(FARM);%种群规模 F1=zeros(1,N); F2=zeros(1,N); for i=1:N xx=FARM{i}; ppp=(1-xx)+(1-q).*xx; F1(i)=sum(w.*prod(ppp)); F2(i)=sum(sum(e.*xx)); end ppp=(1-x)+(1-q).*x; f1=sum(w.*prod(ppp)); f2=sum(sum(e.*x)); Fitness=gamma*sum(min([sign(f1-F1);zeros(1,N)]))+(1-gamma )*sum(min([sign(f2-F2);zeros(1,N)])); 针对问题设计的遗传算法如下，其中对模型约束的处理是重点考虑的地方function [Xp,LC1,LC2,LC3,LC4]=MYGA(M,N,Pm) %% 求解01整数规划的遗传算法 %% 输入参数列表 % M 遗传进化迭代次数 % N 种群规模 % Pm 变异概率 %% 输出参数列表 % Xp 最优个体 % LC1 子目标1的收敛曲线 % LC2 子目标2的收敛曲线 % LC3 平均适应度函数的收敛曲线 % LC4 最优适应度函数的收敛曲线 %% 参考调用格式[Xp,LC1,LC2,LC3,LC4]=MYGA(50,40,0.3) 毕业论文 题目非线性最优化计算方法与算法学院数学科学学院 专业信息与计算科学 班级计算1201 学生陶红 学号20120921104 指导教师邢顺来 二〇一六年五月二十五日 摘要 非线性规划问题是一般形式的非线性最优化问题。本文针对非线性规划的最优化问题进行方法和算法分析。传统的求解非线性规划的方法有最速下降法、牛顿法、可行方向法、函数逼近法、信赖域法，近来研究发现了更多的求解非线性规划问题的方法如遗传算法、粒子群算法。本文对非线性规划分别从约束规划和无约束规划两个方面进行理论分析。 利用最速下降法和牛顿法两种典型算法求解无约束条件非线性规划问题，通过MATLAB程序求解最优值，探讨其收敛性和稳定性。另外给出了阻尼牛顿法，探讨其算法的收敛性和稳定性，求解无约束非线性规划比牛顿法的精确度更高，收敛速度更快。惩罚函数是经典的求解约束非线性的方法，本文采用以惩罚函数法为核心的遗传算法求解有约束条件非线性规划问题，通过MATLAB程序求解最优值，探讨其收敛性和稳定性。并改进遗传算法，给出适应度函数，通过变换适应度函数，提高算法的收敛性和稳定性。 关键词：非线性规划；最速下降法；牛顿法；遗传算法 ABSTRACT Nonlinear programming problem is the general form of the nonlinear optimization problem. In this paper, we carry on the analysis of the method and algorithm aiming at the optimization problem of nonlinear programming. The traditional methods of solving nonlinear programming problems include steepest descent method, Newton method, the feasible direction method, function approximation method and trust region method. Recent studies found more method of solving nonlinear programming problems, such as genetic algorithm, particle swarm optimization (pso) algorithm. In this paper, the nonlinear programming is analyzed from two aspects: the constraint programming and the unconstrained programming. We solve unconstrained condition nonlinear programming problem by steepest descent method and Newton's method, and get the optimal value through MATLAB. Then the convergence and stability are discussed. Besides, the damped Newton method is furnished. By discussing the convergence and stability of the algorithm, the damped Newton method has higher accuracy and faster convergent speed than Newton's method in solving unconstrained nonlinear programming problems.Punishment function is a classical method for solving constrained nonlinear. This paper solves nonlinear programming problem with constraints by using genetic algorithm method, the core of which is SUMT. Get the optimal value through MATLAB, then the convergence and stability are discussed. Improve genetic algorithm, give the fitness function, and improve the convergence and stability of the algorithm through transforming the fitness function. Key words：Nonlinear Programming; Pteepest Descent Method; Newton Method; GeneticAlgorithm 1. 非线性规划 我们讨论过线性规划,其目标函数和约束条件都是自变量的线性函数。如果目标函数是非线性函数或至少有一个约束条件是非线性等式(不等式),则这一类数学规划就称为非线性规划。在科学管理和其他领域中，很多实际问题可以归结为线性规划，但还有另一些问题属于非线性规划。由于非线性规划含有深刻的背景和丰富的内容，已发展为运筹学的重要分支，并且在最优设计,管理科学,风险管理,系统控制,求解均衡模型,以及数据拟合等领域得到越来越广泛的应用。 非线性规划的研究始于三十年代末,是由W.卡鲁什首次进行的，40年代后期进入系统研究，1951年H.W.库恩和A.W.塔克提出带约束条件非线性规划最优化的判别条件,从而奠定了非线性规划的理论基础,后来在理论研究和实用算法方面都有很大的发展。 非线性规划求解方法可分为无约束问题和带约束问题来讨论，前者实际上就是多元函数的极值问题，是后一问题的基础。无约束问题的求解方法有最陡下降法、共轭梯度法、变尺度法和鲍威尔直接法等。关于带约束非线性规划的情况比较复杂，因为在迭代过程中除了要使目标函数下降外，还要考虑近似解的可行性。总的原则是设法将约束问题化为无约束问题；把非线性问题化为线性问题从而使复杂问题简单化。求解方法有可行方向法、约束集法、制约函数法、简约梯度法、约束变尺度法、二次规划法等。虽然这些方法都有较好的效果，但是尚未找到可以用于解决所有非线性规划的统一算法。 1.1 非线性规划举例 [库存管理问题] 考虑首都名酒专卖商店关于啤酒库存的年管理策略。假设该商店啤酒的年销售量为A 箱,每箱啤酒的平均库存成本为H 元,每次订货成本都为F 元。如果补货方式是可以在瞬间完成的,那么为了降低年库存管理费用,商店必须决定每年需要定多少次货,以及每次订货量。 我们以Q 表示每次定货数量,那么年定货次数可以为 Q A ,年订货成本为Q A F ?。由于平均库存量为 2Q ,所以,年持有成本为2 Q H ?,年库存成本可以表示为: Q H Q A F Q C ?+? =2 )( 将它表示为数学规划问题: min Q H Q A F Q C ?+? =2 )( ..t s 0≥Q 其中Q 为决策变量,因为目标函数是非线性的,约束条件是非负约束,所以这是带约束条件的非线性规划问题。 [数据拟合问题] 假设一年期国债利率在市场中的波动符合下述模型 第五章 非线性规划：理论和算法 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 i i x 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 是这个问题的 无约束非线性规划求解方法及其实现 作者：杨玲指导老师：陈素根 摘要: 非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划属于最优化方法的一种，是线性规划的延伸。非线性规划研究一个n元实函数在一组灯饰或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。非线性规划是20世纪50年代才形成的一门新兴学科。1951年H.W库恩和A.W塔克发表的关于最优性条件的论文是非线性规划正是诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程，管理，经济，科研，军事等发面都有广泛的应用，为最优设计提供了有力的工具。20世纪80年代以来，随着计算机技术的快速发展，非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果，无约束非线性规划问题是非线性规划的一个重要内容，很多学者对非线性规划问题进行了深入且系统的研究，研究成果丰硕。 关键词最优化共轭梯度法非线性无约束 1 引言 1.1 无约束非线性规划问题是最基本的非线性规划问题，在1959~1963年幼三位数学家共同研究成功求解无约束问题的DFP变尺度法，该算法的研究成功是无约束优化算法的一个大飞跃，引起了一系列的理论工作，并陆续出现了许多新的算法。20世纪80年代以来，随着计算机技术的快速发展，非线性规划在信赖域法、稀疏牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果。无约束非线性规划问题是非线性规划的一个重要内容，很多学者对非线性规划问题进行了深入且系统的研究，研究成果丰硕。 1.2 本文主要研究无约束非线性规划问题，将文章分成四个部分，首先会具体介绍无约束非线性规划的相关概念，并在此基础上研究非线性规划的相关理论与基本算法问题，接着详细介绍无约束非线性规划的几种主要的求解方法，最后举例说明他在实际生活中的应用，并编程实现它。 2 正文 2.1主要介绍无约束非线性规划的相关概念 一个非线性规划问题的自变量x没有任何约束，或说可行域即是整个n维向量空间：n 错误！未找到引用源。,则称 x R 基于M A T L A B的非线性 规划的求解 The Standardization Office was revised on the afternoon of December 13, 2020 基于MATLAB 的非线性0-1规划的求解 学 生：易棉生 指导教师：宋来忠 三峡大学理学院 摘要：本文主要研究非线性0-1整数规划的解法。首先，通过对传统求解方法的研究，提出从0-1整数规划的变量只取值0和1这个特点来求解，为利用好这个特点，构造了一种数据结构——组合树，还根据目标函数和约束条件所含的变量是否被包含在解中取值为1的变量集中，将0-1整数规划的解细分为目标特殊解和约束特殊解。然后，把这个特点具体化为4条性质。根据这些性质，设计出合理的算法，并用MATLAB 实现该算法。实验表明，该算法是有效的。 Abstract: In this paper, the problem about solving nonlinear 0-1 integer programming is studied. Firstly the view that we can use the feature that the variables of 0-1 integer programming only have two values 0 and 1 is raised after discussing some traditional algorithms. To express the feature, a new tree structure, called combination tree in the paper is given and also object-satisfied solution and constrain-satisfied solution is defined, based on whether the variables with the value 1 in objective function and constrained condition belong to the variables with the value 1 in solution. Then it can be specified by 4 properties. According to these properties, a new algorithm is designed and implemented with MATLAB language. From the experiment, it is proved that the algorithm is effective. 关键词：0-1规划 非线性 组合树 解的标记 MATLAB key words: 0-1 integer programming; nonlinear; combination tree; the mark of solution; MATLAB 前言 本文研究的模型可是： 111min () ..()0()0{0,1}f x Ax b A x b s t C x C x x ≤=??≤=??∈? ，，，， (1) 其中，()f x 都是非线性函数，A 、b 、1A 、1b 是矩阵，1()()C x C x 、非线性矩阵函数。可以看到，本模型实际上代表了一般的0-1整数规划问题。显然，如果一个算法能求解非线性0-1整数规划，也必然能求解一般的0-1整数规划。要完满地解决这个问题，一个算法应具备两个基本条件：1.求解速度较快，即能在较短的时间内计算出非线性规划的概念和原理
求解非线性规划
求解非线性规划
非线性整数规划的遗传算法Matlab程序
非线性最优化计算方法与算法
第九章非线性规划
非线性规划的理论与算法
无约束非线性规划求解方法及其实现
基于MATLAB的非线性规划的求解
相关主题
文本预览