第四章 约束非线性规划

非线性规划非线性规划是一种涉及非线性目标函数和/或非线性约束条件的优化问题。

与线性规划不同，非线性规划可能存在多个局部最优解，而不是全局最优解。

非线性规划在许多领域都有广泛的应用，如经济学、工程学和管理学等。

非线性规划的一般形式可以表示为：最小化或最大化 f(x)，其中 f(x) 是一个非线性函数，x 是决策变量向量。

满足一组约束条件g(x) ≤ 0 和 h(x) = 0，其中 g(x) 和 h(x) 是非线性函数。

为了求解非线性规划问题，可以使用不同的优化算法，如梯度下降法、牛顿法和拟牛顿法等。

这些算法的目标是找到目标函数的最小值或最大值，并满足约束条件。

非线性规划的难点在于寻找全局最优解。

由于非线性函数的复杂性，这些问题通常很难解析地求解。

因此，常常使用迭代算法来逼近最优解。

非线性规划的一个重要应用是在经济学中的生产计划问题。

生产活动通常受到多个因素的限制，如生产能力、原材料和劳动力等。

非线性规划可以帮助确定最佳的生产数量，以最大化利润或最小化成本。

另一个应用是在工程学中的优化设计问题。

例如，优化某个结构的形状、尺寸和材料以满足一组要求。

非线性规划可以帮助找到最佳设计方案，以最大程度地提高性能。

在管理学中，非线性规划可以用于资源分配和风险管理问题。

例如，优化一个公司的广告预算，以最大程度地提高销售额。

非线性规划可以考虑多种因素，如广告投入和市场需求，以找到最佳的广告投放策略。

总之，非线性规划是一种重要的优化方法，用于解决涉及非线性目标函数和约束条件的问题。

它在经济学、工程学和管理学等领域有广泛的应用。

尽管非线性规划的求解难度较大，但通过合适的优化算法，可以找到最佳的解决方案。

求解带约束的非线性规划问题罚函数法求解带约束的非线形规划问题的基本思想是：利用问题的目标函数和约束函数构造出带参数的所谓增广目标函数，把约束非线形规划问题转化为一系列无约束非线形规划问题来求解。

增广目标函数由两个部分构成，一部分是原问题的目标函数，另一部分是由约束函数构造出的“惩罚”项，“惩罚”项的作用是对“违规”的点进行“惩罚”。

罚函数法主要有两种形式。

一种称为外部罚函数法，或称外点法，这种方法的迭代点一般在可行域的外部移动，随着迭代次数的增加，“惩罚”的力度也越来越大，从而迫使迭代点向可行域靠近；另一种成为内部罚函数法，或称内点法，它从满足约束条件的可行域的内点开始迭代，并对企图穿越可行域边界的点予以“惩罚”，当迭代点越接近边界，“惩罚”就越大，从而保证迭代点的可行性。

1. 外部罚函数法(外点法)约束非线形规划问题min f(x),s.t. g(x)>=0,其中g (x) = (g 1(x),…,gm(x)),将带约束的规划问题转化为无约束非线形规划问题来求解的一个直观想法是：设法加大不可行点处对应的目标函数值，使不可行点不能成为相应无约束问题的最优解，于是对于可行域 S= { x | g(x) >= 0} 作一惩罚函数P(x) = 0, x∈S;K, else其中K是预先选定的很大的数。

然后构造一个增广目标函数F (x) = f (x) + P (x) ,显然x∈S时，F（x）与f (x)相等，而x S 时，相应的F值很大。

因此以F(x)为目标函数的无约束问题minF x) = f(x) + P (x) （1）的最优解也是原问题（NP）的最优解。

上述P(x)虽然简单，但因它的不连续性导致无约束问题（1）求解的困难。

为此将P(x)修改为带正参数M（称为罚因子）的函数P(x) =M ∑[min (0,gj(x))]²则min F(x,M) = f(x) + M∑[min (0,gj(x))]²的最优解x(M) 为原问题的最优解或近似最优解。

非线性规划什么是非线性规划？非线性规划（Nonlinear Programming，简称NLP）是一种数学优化方法，用于求解包含非线性约束条件的优化问题。

与线性规划不同，非线性规划中的目标函数和约束条件都可以是非线性的。

非线性规划的数学表达式一般来说，非线性规划可以表示为以下数学模型：minimize f(x)subject to g_i(x) <= 0, i = 1, 2, ..., mh_j(x) = 0, j = 1, 2, ..., px ∈ R^n其中，f(x)是目标函数，g_i(x)和h_j(x)分别是m个不等式约束和p个等式约束，x是优化变量，属于n维实数空间。

非线性规划的解法由于非线性规划问题比线性规划问题更为复杂，因此解决非线性规划问题的方法也更多样。

以下列举了几种常用的非线性规划求解方法：1. 数值方法数值方法是最常用的非线性规划求解方法之一。

它基于迭代的思想，通过不断优化目标函数的近似解来逼近问题的最优解。

常见的数值方法有梯度下降法、牛顿法、拟牛顿法等。

2. 优化软件优化软件是一类针对非线性规划问题开发的专用软件，它集成了各种求解算法和优化工具，可以方便地求解各种类型的非线性规划问题。

常见的优化软件有MATLAB、GAMS、AMPL等。

3. 线性化方法线性化方法是一种将非线性规划问题转化为等价的线性规划问题的求解方法。

它通过线性化目标函数和约束条件，将非线性规划问题转化为线性规划问题，然后利用线性规划的求解方法求解得到最优解。

4. 分类方法分类方法是一种将非线性规划问题分解为若干个子问题求解的方法。

它将原始的非线性规划问题分解为多个子问题，然后将每个子问题分别求解，并逐步逼近原始问题的最优解。

以上仅是非线性规划求解方法的一小部分，实际上还有很多其他的方法和技巧可供选择。

在实际应用中，选择合适的方法和工具是非常重要的。

非线性规划的应用非线性规划在实际生活和工程中有着广泛的应用。

第四章 非线性规划教学重点：凸规划及其性质，无约束最优化问题的最优性条件及最速下降法，约束最优化问题的最优性条件及简约梯度法。

教学难点：约束最优化问题的最优性条件。

教学课时：24学时主要教学环节的组织：在详细讲解各种算法的基础上，结合例题，给学生以具体的认识，再通过大量习题加以巩固，也可以应用软件包解决一些问题。

第一节 基本概念教学重点：非线性规划问题的引入，非线性方法概述。

教学难点：无。

教学课时：2学时主要教学环节的组织：通过具体问题引入非线性规划模型，在具体讲述非线性规划方法的求解难题。

1、非线性规划问题举例例1 曲线最优拟合问题已知某物体的温度ϕ 与时间t 之间有如下形式的经验函数关系：312c t c c t e φ=++ （*）其中1c ，2c ，3c 是待定参数。

现通过测试获得n 组ϕ与t 之间的实验数据),(i i t ϕ，i=1，2，…,n 。

试确定参数1c ，2c ，3c ，使理论曲线(*)尽可能地与n 个测试点),(i i t ϕ拟合。

∑=++-n 1i 221)]([ min 3i t c i i e t c c ϕ例 2 构件容积问题通过分析我们可以得到如下的规划模型：⎪⎪⎩⎪⎪⎨⎧≥≥=++++=0,0 2 ..)3/1( max 212121222211221x x S x x x x a x x t s x x a V ππππ基本概念设n T n R x x x ∈=),...,(1，R R q j x h p i x g x f n j i :,...,1),(;,...,1),();(==,如下的数学模型称为数学规划(Mathematical Programming, MP)：⎪⎩⎪⎨⎧===≤q j x h p i x g t s x f j i ,...,1,0)( ,...,1,0)( ..)( min约束集或可行域X x ∈∀ MP 的可行解或可行点MP 中目标函数和约束函数中至少有一个不是x 的线性函数，称(MP)为非线性规划令 T p x g x g x g ))(),...,(()(1=T p x h x h x h ))(),...,(()(1=，其中，q n p n R R h R R g :,:，那么(MP )可简记为⎪⎩⎪⎨⎧≤≤ 0)( 0 ..)( min x h g(x)t s x f 或者 )(min x f X x ∈ 当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。

第五节 可行方向法（FDM ）可行方向法是用梯度去求解约束非线性最优化问题的一种有代表性的直接探索方法，也是求解大型约束优化设计问题的主要方法之一。

其收敛速度快，效果较好，适用于大中型约束最优化问题，但程序比较复杂。

可行方向法(Feasible Direction Method)是一种直接搜索方法，其搜索方向的获取利用了目标函数和约束函数的梯度信息。

用目标函数的梯度可以得到目标函数值的下降方向，而利用约束函数的梯度则可以得到可行的搜索方向。

因此，可行方向法的搜索方向实质上是既使目标函数值下降，同时又可行的方向，即可行下降方向。

满足这一条件的方法就称为可行方向法。

一、基本原理当求解目标函数的极小值min () ..()0 1,2,3,nu f X X R s t g X u m ⎧∈⎨≤=⎩ 当设计点()k X 处于起作用约束i g 上时，下降可行方向S 必须同时满足条件： ()0T k i S g X ∇≤()0T k S f X ∇<由于于多数非线性规划的最优点都处在可行区的约束边界上或者几个约束边界的交点上，因此最优搜索如能沿着约束边界附近进行，就有可能加速最优化搜索的进程。

按照这一基本思路，在任意选定—初始点后到最后得到最优点必须解决三个问题： 一是如何尽快使最优搜索从初始点到达约束边界二是到达边界后怎样判断所找到的边界点是否是最优点；三是如果边界点经判断不是最优点，那么下一步应如何进行最优搜索。

二、如何从初始点尽快到达边界在任意选定初始点0X 之后，首先判断0X 是否为可行点，若是可行点，则选择目标函数的负梯度方向作为下一步的搜索方向。

若是非可行点，则选择目标函数的梯度方向为搜索方向。

搜索的步长可采用试探的方法逐步缩小，直到最后到达边界。

如图5-13表示了初始点为可行点时的搜索过程。

从初始点0X 出发沿0()f X -∇方向，取步长为t ，进行搜索，得到1X100()X X t f X =-∇若1X 仍在可行区内，则把步长加大一倍继续搜索得到2112()X X t f X =-∇若1X 仍在可行区内，则把步长再加大一倍继续搜索，如此方法得到新点只要仍在可行区内，则加大步长只到得到的点进入非可行区。

第二节 SUMT 方法（罚函数法）一、SUMT 方法的原理SUMT （sequential unconstrained minimization technique ）法，序列无约束极小化方法,亦称为罚函数法。

它是一种不等式约束最优化问题的间接解法 它的基本思想是将原来的目标函数和约束函数按一定的方式构成一个新的函数，在这个新函数中，既包括目标函数，又包括全部约束函数和一个可以变化的乘子。

当这个乘子按一定的方式改变时，就得到一个新函数序列，求每一个新函数的最优解都是一个无约束最优化问题，这样就把一个约束最优化问题转化为一系列无约束最优化问题进行求解。

所得到的最优解序列将逐步逼近原问题的最优解。

引例一：min()f X ax = s.t()0g X b x =-≤ 显然f （X ）的最优点为x*=b ，对应的最小值为f（X*）=ab用SUMT 求解函数的最优解构造函数 11(,)()()k k kX r f X r ax r g X b xΦ=-=-- 0k r >—可变化乘子，它是一个很小的正数。

其最优解为：*()k X r b =+此时对应的(,)k X r Φ的最小值为***1(,)k kX r ax r b x ab Φ=--=+ 最优点*()k X r 和最小值*(,)k X r Φ均是k r 的函数。

当k r 取不同值时，它们有不同的值，而当0k r →时，**()k X r X b →=，*(,)*k X r f X ab Φ→=（），即最后收敛于约束最优点。

0min lim[min (,)]() {|()0}k k i r X r f X R X g X X R→Φ==≤∈ 以上分析从理论上说明了无约束最优化问题min (,)k X r Φ与约束优化问题min () {|()0}i f X R X g X X R=≤∈之间的联系：约束非线性规划问题可以通过构造新目标函数序列，用无约束优化方法求其极小点，并逐次逼近原问题的最优点。

第四章 非线性规划⎧⎪⎧⎨⎨⎪⎩⎩无约束最优化问题线性规划约束最优化问题非线性规划⎧⎨⎩凸规划约束最优化问题非凸规划⎧⎨⎩直接解法约束最优化问题求解方法间接解法间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。

由于这类方法可以选用有效的无约束优化方法，且易于处理同时具有不等式约束和等式约束的问题，因而在工程优化中得到了广泛的应用。

直接解法是在满足不等式约束的可行设汁区域内直接按索问题的约束最优解。

第一节 目标函数的约束极值问题所谓约束优化设计问题的最优性条件．就是指在满足等式和不等式约束条件下，其目标函数值最小的点必须满足的条件，须注意的是，这只是对约束的局部最优解而言。

对于带有约束条件的目标函数，其求最优解的过程可归结为：一、约束与方向的定义 一）起作用约束与松弛约束对于一个不等式约束()0g X ≤来说，如果所讨论的设计点()k X 使该约束()0g X =(或者说()k X当时正处在该约束的边界上)时，则称这个约束是()k X点的一个起作用约束或紧约束，而其他满足()0g X <的约束称为松弛约束。

冗余约束40g ≤当一个设计点同时有几个约束起作用时，即可定义起作用约束集合为{}()()()|()0,1,2,,k k u I X u g X u m ===其意义是对()k X点此时所有起作用约束下标的集合。

二）冗余约束如果一个不等式约束条件的约束面(即()0g X =)对可行域的大小不发生影响，或是约束面不与可行域D 相交，即此约束称为冗余约束。

三）可行方向可行方向：一个设计点()k X 在可行域内，沿某一个方向S 移动，仍可得到一个属于可行域的新点，则称该方向为可行方向。

1）设计点为自由点 设计点()k X 在可行域内是一个自由点，在各个方向上都可以作出移动得到新点仍属于可行域，如图所示。

2）设计点为约束边界点当设计点()k X 处于起作用约束i g 上时，它的移动就会受到可行性的限制。

第二节 SUMT 方法（罚函数法）一、SUMT 方法的原理SUMT （sequential unconstrained minimization technique ）法，序列无约束极小化方法,亦称为罚函数法。

它是一种不等式约束最优化问题的间接解法 它的基本思想是将原来的目标函数和约束函数按一定的方式构成一个新的函数，在这个新函数中，既包括目标函数，又包括全部约束函数和一个可以变化的乘子。

当这个乘子按一定的方式改变时，就得到一个新函数序列，求每一个新函数的最优解都是一个无约束最优化问题，这样就把一个约束最优化问题转化为一系列无约束最优化问题进行求解。

所得到的最优解序列将逐步逼近原问题的最优解。

引例一：min ()f X ax =s.t ()0g X b x =-≤显然f （X ）的最优点为x*=b ，对应的最小值为f （X*）=ab用SUMT 求解函数的最优解 构造函数11(,)()()k k kX r f X r ax r g X b xΦ=-=-- 0k r >—可变化乘子，它是一个很小的正数。

其最优解为：*()k X r b =+ 此时对应的(,)k X r Φ的最小值为***1(,)k kX r ax r b x ab Φ=--=+最优点*()k X r 和最小值*(,)k X r Φ均是k r 的函数。

当k r 取不同值时，它们有不同的值，而当0k r →时，**()k X r X b →=，*(,)*k X r f X ab Φ→=（），即最后收敛于约束最优点。

0min lim[min (,)]() {|()0}k k i r X r f X R X g X X R→Φ==≤∈ 以上分析从理论上说明了无约束最优化问题min (,)k X r Φ与约束优化问题min () {|()0}i f X R X g X X R=≤∈之间的联系：约束非线性规划问题可以通过构造新目标函数序列，用无约束优化方法求其极小点，并逐次逼近原问题的最优点。