第四章 非线性规划 山大刁在筠 运筹学讲义

第四章 非线性规划

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

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

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

第一节 基本概念

教学重点：非线性规划问题的引入，非线性方法概述。 教学难点：无。 教学课时：2学时

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

1、非线性规划问题举例 例1 曲线最优拟合问题 已知某物体的温度?

与时间t之间有如下形式的经验函数关系：

3??c1?c2t?ect （*）

c3是待定参数。c2，其中c1，现通过测试获得n组?与t之间的实验数据(ti,?i)，

i=1，2，…,n。试确定参数c1，c2，c3，使理论曲线(*)尽可能地与n个测试点

(ti,?i)拟合。

min ?[?i?(c1?c2ti?ec3ti)]2

i?1n?

t例 2 构件容积问题

设计一个右图所示的由圆锥和圆柱面 围成的构件，要求构件的表面积为S， 圆锥部分的高h和圆柱部分的高x2之 比为a。确定构件尺寸，使其容积最 大。 通过分析我们可以得到如下的规划模型：

?max V?(1?a/3)?x12x2??2222?s.t. ?x1x1?ax2?2?x1x2??x1?S ? x?0,x?012??x3x2x1

基本概念

设x?(x1,...,xn)T?Rn，f(x);gi(x),i?1,...,p;hj(x),j?1,...,q:Rn?R, 如下的数学模型称为数学规划(Mathematical Programming, MP)：

?min f(x)??s.t. gi(x)?0,i?1,...,p ? hj(x)?0,j?1,...,q?约束集或可行域

? x?X MP的可行解或可行点

MP中目标函数和约束函数中至少有一个不是x的线性函数，称(MP)为非线性规划

令 g(x)?(g1(x),...,gp(x))T

h(x)?(h1(x),...,hp(x))T，

其中，g:Rn?Rp,h:Rn?Rq，那么(MP)可简记为

?min f(x)?f(x) ?s.t. g(x)?0 或者 minx?X? h(x)?0 ?当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。

否则，称为约束非线性规划或者约束最优化问题。 定义4.1.1 对于非线性规划(MP)，若x*?X，并且有

f(x*)?f(x), ? x ?X

则称x*是(MP)的整体最优解或整体极小点，称f(x*)是 (MP)的整体最优值或整体极小值。如果有

f(x*)?f(x), ? x ?X, x?x*

则称x*是(MP)的严格整体最优解或严格整体极小点，称

f(x*)是(MP)的严格整体最优值或严格整体极小值。

定义 4.1.2 对于非线性规划(MP)，若x*?X，并且存在x*的一个 领域N?(x*)?x?Rn x?x*??(??0,??R)，使

??f(x*)?f(x), ? x?N?(x*)?X，

则称x*是(MP)的局部最优解或局部极小点，称f(x*)是(MP)的局部 最优值或局部极小点。如果有

f(x*)?f(x), ? x?N?(x*)?X, x?x*，

则称x*是(MP)的严格局部最优解或严格局部极小点，称f(x*)是(MP) 的严格局部最优值或严格局部极小点。

定义 4.1.3 设f:Rn?R,x?Rn,p?Rn,p?0，若存在??0 ，使

f(x?tp)?f(x), ?t?(0,?)

则称向量p是函数f(x)在点x处的下降方向。

定义 4.1.4 设X?Rn,x?X,p?Rn,p?0，若存在t?0，使

x?tp?X

则称向量p是函数f(x)在点x处关于X的可行方向。 一般解非线性规划问题的迭代方法的步骤：

第一步：选取初始点x0,k:?0； 第二步：构造搜索方向pk； 第三步：根据pk，确定步长tk；

第四步：令xk?1?xk?tkpk若xk?1已满足某种终止条件，停止迭代，输出近似最优解xk?1，否则令k:?k?1，转回第二步。

常用规则：

1、相邻两次迭代点的绝对差小于给定误差，即xk?1?xk??； 2、相邻两次迭代点的相对差小于给定误差，即3、?f(xk)??； 4、f(xk?1)?f(xk)??

xk?1?xkxk??；

第二节 凸函数和凸规划

教学重点：凸函数的概念及性质，凸规划的概念、性质及判定。 教学难点：凸规划的概念及性质。 教学课时：4学时

主要教学环节的组织：首先介绍凸函数的定义，然后给出凸函数及凸规划的性质。

凸函数的定义及性质：

定义 4.2.1 设S?Rn是非空凸集，f:S?R，如果对任意的??(0,1)有

f(?x1?(1??)x2)??f(x1)?(1??)f(x2)，?x1,x2?S

则称f是S上的凸函数，或f在S上是凸的。如果对于任意的??(0,1)有

f(?x1?(1??)x2)??f(x1)?(1??)f(x2)，x1?x2

则称f是S上的严格凸函数，或f在S上是严格凸的。

若-f是S上的（严格）凸函数，则称f是S上的（严格）凹函数， 或f在S上是（严格）凹的。

(a) 凸函数 (b)凹函数

凸函数的性质：

定理 4.2.1 设S?Rn是非空凸集。

（1）若f:Rn?R是S上的凸函数，??0，则 ?f是S上的凸函数； （2）若f1,f2:Rn?R都是S上的凸函数，则f1?f2是S上的凸函数。 定理 4.2.2 设S?Rn是非空凸集，f:Rn?R是凸函数，c?R，则集合

HS(f,c)??x?Sf(x)?c?

是凸集。

注：一般来说上述定理的逆是不成立的。

定理 4.2.3 设S?Rn是非空开凸集，f:S?R可微，则 （1） f是S上的凸函数的充要条件是

?f(x1)T(x2?x1)?f(x2)?f(x1)， ? x1,x2?S

?f(x1)?f(x1)T1,....,)其中?f(x)?(是函数f在点处的一阶 x1n?x?x1导数或梯度。

（2） f是S上的严格凸函数的充要条件是

?f(x1)T(x2?x1)?f(x2)?f(x1)， ? x1,x2?S,x1?x2

证明

（1）. 必要性.设f是S上的凸函数，对???(0,1)有：

f(?x2?(1??)x1)??f(x2)?(1??)f(x1),????x1,x2?S

故

f(x1??(x2?x1))?f(x1)??f(x2)?f(x1)

（4.2.3）

由多元函数Taylor展开式可知：

f(x1??(x2?x1))?f(x1)???f(x1)T(x2?x1)??(?(x2?x1))

将其带入（4.2.3）并令????便便可得到

?f(x1)T(x2?x1)?f(x2)?f(x1)

充分性.设

?f(x1)T(x2?x1)?f(x2)?f(x1)????x1,x2?S

对???(0,1),取x??x1?(1??)x2，由S凸知x?S，对x1,x?S和x2,x?S分别有： 和

f(x)??f(x)T(x2?x)?f(x2),?????x2?S f(x)??f(x)T(x1?x)?f(x1),?????x1?S

（4.2.4）

（4.2.5）

将（4.2.4）乘以?，（4.2.5）乘以(1??)，两式相加得到

f(?x1?(1??)x2)?f(x)?f(x)??f(x)T(?x1?(1??)x2?x)??f(x1)?(1??)f(x2),????x1,x2?S

（2）. 证明和（1）类似.

定理 4.2.4 设S?Rn是非空开凸集，f:S?R二阶连续可导，则f是S上的凸函数的充要条件是f的Hesse矩阵?2f(x)在S上是半正定的。

当?2f(x)在S上是正定矩阵时，f是S上的严格凸函数。（注意：该逆命题不成立。）

??2f(x)?2?x1?2??f(x)??x?x2?f(x)??21.??.?2??f(x)???xn?x1凸规划及其性质

?2f(x)?2f(x)?....??x1?x2?x1?xn??2f(x)?2f(x)?...2?x2?x2?xn?? .??.??2f(x)?2f(x)?2??xn?x2?xn??min f(x)??s.t. gi(x)?0,i?1,...,p (MP) ? h(x)?0,j?1,...qj??gi(x)?0,i?1,...,p???nX??x?R? 约束集

h(x)?0,j?1,...,q?j???如果(MP)的约束集X是凸集，目标函数f是X上的凸函数，则(MP)叫做非线性凸规划，或简称为凸规划。 凸规划的性质

定理 4.2.5 对于非线性规划(MP)，若gi(x),i?1,...,p 皆为Rn上的凸函数，hj(x),j?1,...,q皆为线性函数， 并且f是X上的凸函数，则(MP)是凸规划。

定理 4.2.6 凸规划的任一局部最优解都是它的整体最优解。

证明：设x*是凸规划（MP）的一个局部解，存在则x*的临域N?(x*)使得

f(x*)?f(x),?????x?XN?(x*)

若x*不是（MP）的整数最优解，则存在x?X，使

f(x)?f(x*)

又因为f是凸函数，有

f(?x?(1??)x*)??f(x)?(1??)f(x*)??f(x*)?(1??)f(x*)?f(x*)

显然，当?充分小时，有

?x?(1??)x*?X出现矛盾。

例 4.2.3 验证下列（MP）是凸规划 解答：将二次目标函数改写为：

N?(x*)

?4?11??x1??x1?1??????f(x1,x2,x3)?(x1,x2,x3)??120??x2??(1,2,0)?x2?

2?104??x??x????3??3?由例4.2.2知f的 Hesse矩阵为：

?4?11??? ?2f???120?

?104????2f的一、二、三阶顺序主子式分别为：

4?114?14?0,?????7?0,?????120?26

?12104?2f正定，f为凸函数。

?200???而?2g1(x)??020?半正定，g1(x)是凸函数。其他约束条件均为线性。故改

?000???（MP）为凸规划。

第三节 一维搜索

教学重点：0.618法，牛顿法，非精确一维搜索方法。 教学难点：0.618法和牛顿法。 教学课时：4学时

主要教学环节的组织：首先介绍凸函数的定义，然后给出凸函数及凸规划的性质。

目标函数为单变量的非线性规划问题称为一维搜索问题(或线性搜索问题)，其数学模型为

min ?(t) ，

t?0(0?t?tmax)其中t?R。 1、0.618法

函数?(t)称为在[a,b]上是单谷的，如果存在一个t*?[a,b]，使得?(t)在[a,t*]上严格递减，且在[t*,b]上严格递增。区间[a,b]称为?(t)的单谷区间。 第一步： 插入t1,t2使?a,t2??t1,b?等长度，令

w?t2?ab?t1??t1?a?(1?w)(b?a),??t2?a?w(b?a) b?ab?a第二步： 使区间缩小同样的比例w，不妨设新区间为?a,t2? 设插入t1?,t2?，则

2?t2??at2?t1??t1??a?w(b?a)?w(b?a) w????2t2?at2?a??t2??a?w(b?a) 若令t1??t1，则有w?1；若令t2??t1，则有w?0.618 以后类似迭代

算法的具体步骤：

第1步 确定单谷区间[a,b]，给定最后区间精度??0; 第2步 计算最初两个探索点

t1?a?0.382(b?a)?b?0.618(b?a) t2?a?0.618(b?a)

并计算?1??(t1)，?2??(t2)；

第3步 若?1??2，转第4步。否则转第5步；

第4步 若t2?a??，停止迭代，输出t1。否则令b:?t2，

t2:?t1，t1:?b?0.618(b?a)，?2:??1，计算?1??(t1)，转第3步；

第5步 若b?t1??，停止迭代，输出t2。否则令a:?t1，

t1:?t2，t2:?a?0.618(b?a)，?1:??2，计算?2??(t2)，转第3步。

? 例4.3.1 用0.618法求解的单谷区间为[0,3]，

迭代步骤可以由下表给出： 0 1 2 3 4 0 0 0 0.438 0.708 3 1.146 1.854 0.708 1.146 0.438 1.146 0.708 1.146 1.854 1.146 0.708 0.876 0.2131 -0.0611 0.2082 -0.0611 ∧ ∧ ∨ ∨ 3.6648 0.2131 -0.0611 -0.0798 换 ? ? 换 ? ? 在0.618法中每次迭代搜索区间按常比例缩小，所以要使给定的单谷区间减少到所要求的区间精度，需要的迭代次数是可以预估的。另外若每次每次迭代按不同比例缩小搜索区间，但仍要求每次迭代只计算一个函数值，且希望在搜索点个数相同的情况下使最终的搜索区间的长度最小，按此要求设计的方法是Fibonacci法

2、牛顿法

考虑一维搜索问题min ?(t)，其中?(t)是二次可微的，且???(t)?0。 Newton法的基本思想是：用?(t)在探索点tk处的二阶泰勒展开式g(t)来替代

?(t)，然后用g(t)的最小点作为新的探索点tk?1.据此，可得：

tk?1?tk???(tk)

???(tk?1)开始时给定一个初始点t1，然后按照上式进行迭代计算，当??(tk)??时，终止迭代，tk为?(t)的最小点的近似。 Newton法步骤

第1步 给定初始点t1，??0,k:?1；

第2步 如果??(tk)??，停止迭代，输出tk.否则，当???(tk)?0时，停止，

解题失败；当???(tk)?0时，转下一步；

??(tk)第3步 计算tk?1?tk?，如果tk?1?tk??，停止迭代，输出tk?1，

???(tk)否则k??k?1，转至第2步；

例 用牛顿法求下题。

解：首先求出

??(t)?arctant???????????(t)?取t1?1，计算结果列于下表

1， 21?tk 1 2 3 4 tk ??(tk) 0.7854 -0.5178 0.1163 1???(tk) 1 -0.5708 0.1169 -0.001061 2 1.3258 1.0137 用数学分析方法知，?(t)的精确最优解是t*?0，用Newton法迭代三此后就已经十分接近该最优解。 但是取t1?2，则有：

k 1 2 3 点列?tk?不收敛于t*?0

tk ??(tk) 1.1071 -1.2952 1???(tk) 2 -3.5357 13.95 5 13.50 从任意初始点开始的Newton法产生的点列，一般来说不一定收敛，即使收敛，其极限点也不一定是 的极小点，只能保证它是

的驻点。但当初始点充分接近 时，可以证明Newton法是收敛的。 非精确一维搜索： 3、Goldstein法思想

预先指定两个数m1,m2满足0?m1?m2?1，用一下两个式子限定tk

?(tk)??(0)?m1tk??(0) （4.3.10）

?(tk)??(0)?m2tk??(0) （4.3.11）

（4.3.10）式所限定的tk是使?(tk)位于直线y??(0)?m1??(0)t之下的点，

用以控制tk不太大；（4.3.11）用于限定tk使?(tk)位于直线y??(0)?m2??(0)t 之上的点，用以控制tk不太小.

第1步 给定满足0?m1?m2?1的正数m1,m2，增大探索点系数??1； 初始探索点t0?(0,??)（或(0,tmax]）。令a0:?0,b0:???（或tmax），k:?0 第2步 计算?(tk)

若?(tk)??(0)?m1tk??(0)，进行第3步；否则，令ak?1:?ak,bk?1:?tk 转第4步；

第3步 若?(tk)??(0)?m2tk??(0)，停止迭代，输出tk。否则，令

ak?1:?tk,bk?1:?bk

若bk?1???，进行第4步；否则，令tk?1:??tk,k:?k?1，转第2步； 第4步 取tk?1:?

例 用 法 求解下题

解答：取a0:?0,b0:???,并且?(0)?1,??(0)??2,因为?(t0)?5，

ak?1?bk?1，令k:?k?1，转第2步。 2?(t0)?5??(0)?m1t0??(0)?0.2

令

a1:?a0?0????b1:?t0?2

由于b1?2???，选取新探索点

t1?a1?B1?1 2并计算?(t1)?0，因为有

?(t1)?0??(0)?m1t1??(0)?0.6

和

?(t1)?0??(0)?m2t1??(0)??0.4

停止迭代，得到非精确解t1?1

4.Armijo法

取定0?m?1?M，用以下两个式子限定tk不太大也不太小：

?(tk)??(0)?mtk??(0)

?(Mtk)??(0)?mMtk??(0)

(0.0.1) (0.0.2)

第四节 无约束最优化问题

教学重点：无约束最优化问题的最优性条件，最速下降法。 教学难点：最速下降法。 教学课时：6学时

主要教学环节的组织：首先给出无约束最优化条件，然后介绍无约束最优化问题的两种算法，最速下降法、共轭方向法。 1 无约束问题的最优性条件

定理4.4.1 设f:Rn?R在点x?Rn处可微。若存在p?Rn，使

?f(x)Tp?0

则向量p是f在点x处的下降方向。 证：因为f在点x处可微，有泰勒展开，

f(x?tp)?f(x)?t?f(x)Tp??(tp) （4.4.1） 由于?f(x)Tp?0,t?0，因而t?f(x)Tp?0，则存在??0，对

?t?(0,?)有

t?f(x)Tp??(tp)?0

由（4.4.1）

f(x?tp)?f(x),?????t?(0,?)

由定义知p是f在点x的处下降方向

定理 4.4.2 设f:Rn?R在点x?Rn处可微。若x*是(UMP)的局部最优解，则

?f(x*)?0

定理4.4.3 设f:Rn?R在点x?Rn处的Hesse矩阵?2f(x*)存在。若

?f(x*)?0，并且?2f(x*)正定

则x*是(UMP)的局部最优解。

定理4.4.4 设f:Rn?R，x*?Rn，f是Rn上得可微 凸函数。若有?f(x*)?0 则x*是(UMP)的整体最优解。

证：因为f是Rn上的可微凸函数，由定理4.2.3知

?f(x*)T(x?x*)?f(x)?f(x*),?????x?Rn

由于?f(x*)?0，因而推知

f(x*)?f(x,)?????x?Rn

由此x*是（UMP）问题的整数最优解 2 最速下降法

设（NMP）问题中的目标函数f:Rn?R一阶连续可微

最速下降法基本思想：从当前点xk出发，取函数f(x)在点xk处下降最快的方向作为我们的搜索方向pk，由f(x)的Taylor展开式知

f(xk)?f(xk?tpk)??t?f(xk)Tpk??(tpk)

忽略t的高阶无穷小项，可见取pk???f(xk)时，函数值下降的最多。 最速下降法的计算步骤：

第1步 选取初始点x0，给定终止误差??0，令k:?0；

第2步 计算?f(xk)，若?f(xk)??，停止迭代，输出xk。否则进行第3步； 第3步 取pk???f(xk)

第4步 进行一维搜索，求tk，使得f(xk?tkpk)?minf(xk?tpk)

t?0令xk?1?xk?tkpk，k:?k?1，转第2步。 例4.4.2 用最速下降法求解如下（UMP）问题

2minf(x1,x2)?x12?25x2

取初始点x0?(2,2)T,终止误差??10?6 显然，该问题的整体最优解为x*?(0,0)T 下面用最速下降法求解. 由?f(x)?(?f?fT,)?(2x1,50x2)T ?x1?x2构造负梯度方向

p0???f(x0)??(4,100)T

则f(x0?tp0)?(2?4t)2?25(2?100t)2

df(x0?tp0)?0，解得：t0?0.020037， 令

dt?2???4??1.919878?所以x1?x0?t0p0????0.020037?????

?2???100???0.003070?重复上述过程，经十轮迭代可得满足误差??10?6要求的解。

最速下降法算法分析：

1）随着迭代次数的增加，收敛速度越来越慢； 2）最速下降法的相邻两个搜索方向是彼此正交的； 3）具有全局收敛性。 3 共轭方向法

定义 4.4.1 设A为n阶实对称，对于非零向量p,q?Rn，若有

pTAq?0

则称p和q是相互A共轭的。对于非零向量组pi?Rn,i?0,1,...,n?1，若有

(pi)TApj?0, i,j?0,1,...,n?1 i?j

则称p0,p1,...,pn是A共轭方向组，也称它们为一组A共轭方向。

定理4.4.5 设A是n阶实对称正定矩阵，pi?Rn(i?0,1,...,n?1)是非零向量。若p0,p1,...,pn?1是一组A共轭方向，则它们一定是线性无关的。 考虑二次严格凸函数的无约束最优化问题：

min f(x)?1TxAx?bTx?c （AP） 2其中A是n阶实对称正定矩阵，b?Rn，c?R

.定理 4.4.6 对于问题(AP)，若p0,p1,pn?1为任意一组A共轭方向，则由任意

初始点x0?Rn出发，依次沿p0,p1,...,pn?1进行精确一维搜索，则最多经n次迭代可达(AP)的整体最优解。

共轭方向法-步骤

第1步 选取初始点x0，给定终止误差??0；

第2步 计算?f(x0)，若?f(x0)??，停止迭代，输出x0；否则，进行第3

步；

第3步 取p0???f(x0)，令k:?0；

第4步 进行一维搜索求tk使得f(xk?tkpk)?minf(xk?tpk)，令

t?0xk?1?xk?tkpk；

第5步 计算?f(xk?1)，若?f(xk?1)??，停止迭代，输出xk?1；否则，进行第6步；

第6步 若k+1=n，令x0:?xn，转第3步；否则进行第7步；

?f(xk?1k第7步 用F-R公式取pk?1???f(xk?1)??kpk，其中?k?k:=k+1，转第4步。

例 用F-R法求解如下（UMP）问题

2minf(x1,x2)?x12?25x2

)22?f(x)。令

取初始点x0?(2,2)T,终止误差??10?6

解： F-R方法的第一轮迭代与最速下降法相同，由例4.4.2知

p0???f(x0)??(4,100)T

?2???4??1.919878?x?x?t0p????0.020037?????

2?100?0.003070??????100?f(x1)?(3.83975,?0.15359)

下面利用F-R公式（4.4.9）构造新的共轭方向，其中：?0??f(x1)?f(x)022?0.001472

??3.84565?所以p1???f(x1)??0p0???

?0.00615??0?df(x1?tp1)211?0，有t1?0.49923，因而得到下一个迭代点x?x?t1p???, 令

dt?0?由于?f(x2)?0??，停止迭代，输出整体最优解x2?(0,0)T 共轭方向法-算法分析：

1）F-R法具有二次终止性。对一般可微函数的无约束优化问题，当函数满足一定的条件时，可以证明F-R方法具有全局收敛性其收敛速度比最速下降法快； 2）F-R法强烈依赖于一位搜索的精确性。

第五节 约束最优化方法

教学重点：约束最优化问题的最优性条件，简约梯度法和惩罚函数法。 教学难点：约束最优化问题的最优性条件。 教学课时：8学时

主要教学环节的组织：首先给出约束最优化问题的最优性条件即K_T条件，然后介绍两种约束最优化方法：简约梯度法和惩罚函数法。 1、约束最优化问题的最优性条件

给定约束最优化问题：

x?Rn, f:Rn?R ?min f(x)?n?s.t. gi(x)?0 i?1,...,p 其中 gi:R?R, i?1,...,p ? h(x)?0 j?1,...,q hj:Rn?R j?1,..q.,j?设(MP)问题的可行区域为X?x?Rgi(x)?0,i?1,...,p,hj(x)?0,j?1,...,q对? x*?X,令J?{1,2,?,q}，即满足hj(x)?0, j?J*?n?

积极约束：称使gi(x*)?0的约束gi(x)?0为点x*的一个积极约束。 我们记积极约束的下标集为：I(x*)?{igi(x*)?0,i?I} K-T条件：

定理 4.5.1 设f:Rn?R和gi:Rn?R,i?I(x*)在点x*处可微，

gi,i?I\\I(x*)在点x*处连续，hj:Rn?R,j?J在点x*处连续可微，并且各

?gi(x*), i?I(x*), ?hj(x*), j?J线性无关。若x*是(MP)的局部最优解，则存

**在两组实数?*i,i?I(x)和?j,j?J，使得：

***??f(x*)???*i?gi(x)???j?hj(x)?0?j?Ji?I(x*) ?*?i?I(x*)??i?0, “向量组?gi(x*), i?I(x*), ?hj(x*), j?J线性无关”—这个条件称为约束规范条件

其几何意义可以用下图来说明。

图4.5.1

若定理4.5.1中进一步要求gi(x),??i?I在点x*处均可微，则K-T条件可简便写为

*?f(x)????gi(x)???*j?hj(x)?0**i*i?1j?1pq?i*?gi(x*)?0,????i?1,?i*?0,????i?1,,p,p （4.5.8）

其中?i*?gi(x*)?0,????i?I为互补松紧条件 例4.5.1用K-T条件求解下列问题

解：问题（4.5.1）的Lagrange函数为：

L(x,?,?)?(x1?1)2?(x2?2)2??1(x1?x2?2)??2(?x1)??????????????????????3(?x2)??(?x1?x2?1)得到K-T条件如下

?2(x1?1)??1??2???0?2(x?2)???????013?2???1(x1?x2?2)?0 ??x?0?21??3x2?0????1,?2,?3?0作为K-T点，还应满足可行性条件：

?x1?x2?2?0???x1?x2?1?0 ?x?0,????x?02?1从互补松紧条件入手进行讨论 （1） 设x1?0,x2?0,?1?0

此时可求解出x1?1,x2?2,??0，不满足可行性条件中的不等式约束。舍弃。 （2） 设?1?0

13解出x*?(,)T为K-T点

2213由定理4.5.2知x*?(,)T为整体最优解

22定理 4.5.2 对于(MP)问题，若f,gi,i?I，hj,j?J在点x*处连续可微，可行点x*满足(MP)的K-T条件，且f, gi,i?I(x*)是凸函数， hj,j?J是线性函数，则x*是(MP)的整体最优解。 2. 简约梯度法

?min f(x)??s.t. Ax?b ? x?0?其中，x?Rn, f:Rn?R，r(Am?n)?m，b?Rm

Xl?{x?Rn| Ax?b, x?0}

简约梯度法-基本思想

首先，分析等式约束Ax?b得xB?B?1b?B?1NxN，带入目标函数

f(x)?f(xB,xN)?F(xN);

令rN??F(xN)，即为f在x处对应B的简约梯度. 其次，再由rNk构造pk

定理 4.5.3 对于非线性规划问题(4.5.12)，设f是可微函数，xk?Xl，并且有分解

k?xBxk??k?x?Nk???pBk?，xB?0。若pk?????pk?由下式确定， ??N?k?k?rik?0??ri, kk i?I?pN:pi??Bkk (*) ?rik?0???xiri ?k?1k?pB??BkNkpN则：

（1） 当pk?0时，pk是f在点xk处关于Xl的可行下降方向； （2） pk?0的充要条件是xk是问题(4.5.12)的K-T点。 简约梯度法-Wolfe法步骤

第1步 选取初始可行点x0?Xl，给定终止误差??0，令k:=0;

k第2步 设IB是xk的m个最大分量的下标集，对矩阵A进行相应分解

A?(Bk,Nk)

k??f(x)?Bk??，然后，计算简约梯度 第3步 计算?f(x)??k???Nf(x)?k?1rN??(BkNk)T?fB(xk)??fN(xk)

kk)个分量为rik； 记rN的第i(i?IB第4步 按(*)式构造可行下降方向pk。若pk??，停止迭代，输出xk；

否则进行第5步；

kkkf(x?tp)t第5步 进行有效一维搜索，求解min，得到最优解，其中 k0?t?tmaxktmax??? pk?0?k???， ??xikkkmin?p?0 p?0或者p?0??1?i?n?pki?i???令xk?1?xk?tkpk，k:=k+1，转第2步

例 用Wolfe法求解约束极小化问题 解：首先将问题化为：

2?min????x12?x2?2x1x2?2x1?6x2?t??????x1?x2?x3?4?s..?????????????x1?x2?x4?2???????????xj?0,j?1,2,3,4?

取x0?(1,1,2,2)T,??10?6?1110?0第一轮迭代： IB??????3,4?，A???，相应分解为

?1101???10??11?B0???,N0???

?01???11??6?0?1rN??(B0N0)T?Bf(x0)??Nf(x0)???

?10?由公式（4.5.20）有

??6?0?16?0?10pN??,??p??BNp?00N?B??，由此可得可行下降方向为

??10??4?p0?(?6,?10,16,4)

?11?10?min?,??， 根据（4.5.23）式有tmax?610?10求解minf(x0?tp0)可得最优解t0?10?t?101，于是得到下一个迭代点 1021812x1?x0?t0p0?(,0,,)T。

555然后依次进行第二轮第三轮迭代，最后得到整体最优解x*?(0,0)T

3. 惩罚函数法

思想：利用问题中的约束函数做出适当的带有参数的惩罚函数，然后在原来的目标函数上加上惩罚函数构造出带参数的增广目标函数，把(MP)问题的求解转换为求解一系列无约束非线性规划问题。

?min f(x)??s.t. gi(x)?0,i?1,...,p? hj(x)?0,j?1,...,q?

?gi(x)?0,i?1,...,p???X??x?Rn?

h(x)?0,j?1,...,qj????设法适当地加大不可行点处对应的目标函数值，使不可行点不能成为相应无约束极小化问题的最优解。

cq可取罚函数：pc(x)?c?[max(gi(x),0)]??[hj(x)]2

2j?1i?12p相应的构造增广目标函数：Fc(x)?f(x)?pc(x)

当c充分大时，总可使（MP）问题转换为无约束的极小化问题

min Fc(x)

实际应用中，选取一个递增且趋于无穷的正罚函数参数列：

min Fck(x)?f(x)?pck(x)

ck2其中， pck(x)?ck?[max(gi(x),0)]?2i?1罚函数法计算步骤

第1步 选取初始点x0，罚参数列{ck}(k?1,2,...)， 给出检验终止条件的误差??0，令k:=1；

第2步 按(***)构造函数pck(x)，再按(**)构造(MP) 的增广目标函数，即Fck(x)?f(x)?pck(x)

第3步 选用某种无约束最优化方法，以xk?1为初始点， 求解min Fck(x)，设得到最优解xk。若xk已满足某种 终止条件，停止迭代，输出xk。否则令k:=k+1，转第2步； 例4.5.3 用罚函数法求解 解：罚函数为

p?[h(x)]jj?1q2

pck(x)?ck?max(1?x,0)??k?max(1?x,0)?

相应的增广目标函数为：

22??x?k(1?x),????x?1Fck(x)?x?k?max(1?x,0)???2

??x,?????????????????????x?12222原问题转换为求解一系列无约束最优化问题

minFck(x),????k?1,2,

用解析方法求解： 令

dFck(x)dx?0，求得

xk?k,????k?1,2,1?k

可以看到，当k无限增大时xk是从问题（4.5.31）可行域外部趋于它的最优解

x*?1的。图见

障碍函数法

在可行区域的边界上筑起一道“墙”，当迭代点靠近边界时，所构造的增广目标函数值陡然增大，于是最优点就被“挡”在可行区域内部了。

?min f(x) ?s.. tg(x)?0,i?1,...,pi?令g(x)?(g1(x),g2(x),...,gp(x))T， 可行域X的内部记为

Xo?{x?Rn| g(x)?0}

构造障碍函数 当x?Xo时，

p1或Bdk(x)??dk?ln[?gi(x)] Bdk(x)??dk?i?1i?1gi(x)p其中，dk为罚参数或罚因子

Fdk(x)?f(x)?Bdk(x) min Fdk(x), k?1,2,...

障碍函数法步骤

第1步 选取初始点x0?Xo，罚参数列{dk}(k?1,2,...)，给出检验终止条件

??0，令k:=1；

第2步 做障碍函数Bdk(x)，构造增广目标函数Fdk(x)?f(x)?Bdk(x) 第3步 选用某种无约束最优化方法，以xk?1为初始点求解

min Fdk(x), x?Xo

得到最优解xk。若xk已满足某种终止条件，停止迭代，输出xk。否则，令k:=k+1，转第2步。

例4.5.4 用障碍函数法求解例4.5.3取 采用对数形式的障碍函数 解: 取

1Bdk??dkln(x?1)??ln(x?1),????x??

k相应的增广目标函数为：

1Fdk(x)?x2?ln(x?1),????x??

k用解析方法求得minFdk(x)的最优解为

k?k2?2kx?,??????k?1,2,2kk

由上式可见，当k无限增大，即dk无限减小时，xk从问题（4.5.31）的可行域内部趋于最优解x*?1

两类方法的优缺点比较： 优点：

罚函数法：结构简单初始点选取比较自由

障碍函数法：结构简单但初始点必须是可行内点，由此产生的迭代点均为可行内点 缺点：

1、收敛速度慢

2、工作量大，每次迭代都要求解一个无约束优化问题 3、方法本身造成数值困难性

本文来源：https://www.bwwdw.com/article/acbp.html