16.323讲课2
非线性优化
z约束非线性优化
z拉格朗日乘子
z罚函数/障碍函数也经常用到，但是这里不讨论。
可行域
MIT OCW供图
约束优化
z考虑如下复杂度的问题：有等式约束的最优化
F
y
min()
y
y
受约束于F()=0
n个约束的向量
z为简化表示法，假定p个状态的向量y能分解为m维决策向量u和与决策向量通过约束相关的n维状态向量x。问题因此变为：
x u
min(,)
F
u
f x u
受约束于(,)=0
>，否则问题完全由约束指定（或者超定）。
-假设p n
z一个求解方法是直接带入法，它包括
- 利用f，根据u求解x
- 把表达式带入F，使用无约束最优化求解u
- 如果f是线性的效果最好（假设条件是f和F不都是线性的。）
z 例子：最小化22
12
F x x =+，受约束于1220x x ++= - 明显的，在1
20x x ==时得到无约束最小
- 在这种情况下带入法给出了等价的问题：
2
22222
min (2)x F x x =??+ 或者
1
22111
min (2)x F x x =+?? 这种情况下解2
2(/0)F x ??= 是121x x ==?
图1：有约束时简单函数的最小化
z 小结：带入法适用于线性约束，但是对于较大的系统或者非线性约束较难
推广。
拉格朗日乘子
z 需要更通用的策略 – 使用拉格朗日乘子 z 既然(,)0=f x u ，可以把它和约束
1[]T n λλλ="
联系在一起构成代价函数，约束不改变函数值的情况下，生成拉格朗日函 数
(x,u,)(x,u)f (x,u)T L F λλ=+
z 给定x 和u 的值，满足(,)0=f x u ，考虑x 和u 的微分改变引起的拉格朗
日微分变化：
+L L dL d d ??=
??x u x u
其中1m
L L
L
u u ????????=??
u
"
（行向量） z 既然u 是决策变量，则便于改变λ使得
+0T L F λ???≡???f
x x x
(1) 1
T
F λ??????=???????
f x x (2)
z 下一步，必须确定代价函数的什么变化可能保持需要满足的等价约束。
- x 和u 的变化使得(,)0=f x u ，则
+0d d d ??=≡??f f
f x u x u (3)
1
d d ??????=???????f f
x u x u
(4)
z 则允许的代价变化是：
+F F dF d d ??=
??x u x u
(5) 1+F F d ?????????=??????????????
?f f u x x u u T F d λ????=+??????f u u
u (6)
L
d ?≡?u u
(7) z 保持约束为(,)0=f x u ，关于u 的代价F 的梯度就是
L ??u
该梯度等于零应包含一个驻点，这样dF 对于任意的d u 为零。 z 因而对于F 的驻值的必要条件是
0x
L
?=? (8) 0u
L
?=? (9) f(x,u)0L
λ
?==? (10) 即有2n m +未知量的2n m +个方程。 z 注意式8-10可以简化为
0L
?=?y
(11) 0L
λ
?=? (12)
z 直观的，约束解是常数代价曲线和约束函数相切的点 ?满足约束时没有进一步改善的可能。 z 代价的梯度（垂直于常数代价曲线）/F
??y 必须位于约束梯度f /??y 张
成的空间内，所以不违反约束时代价不会改变。 - 在二维的情况，这对应于/F
??y 与/??f y 共线
图2：等式约束的最小化：函数和代价梯度在最优点附近几乎共线，而且相差不远。
3
2
1,22111()((2)(2)(2)2)0f x x x x x x =????+?+=和1112T
F ??
=????
x x
- 如果不成立，则可能通过在代价梯度和约束梯度正交的部分的反方向选择 d y ，因此减少代价，仍然可以满足约束。
1
X
图3：放大图
z 把这种“共线”的直观结果推广到更大状态维数，就是代价梯度一定位于
约束梯度张成的空间。
- 等价的意思就是说有可能把代价梯度表示为约束梯度的线性组合 - 所以在约束最小点，一定存在常数使得代价梯度满足：
1212n n f f f F
λλλ????=????????y y y y
" (13) T
λ?=??f
y
(14)
或者等价的
0T F λ??+=??f y y
当然，这与式.11是一样的。
有约束的例子
z 最小化22
1212
(,)F x x x x =
+，受约束于1212(,)20f x x x x =++= - 构成拉格朗日算式
22
12121212(,)(,)(2)L F x x f x x x x x x λλ+=++++
- 其中λ是拉格朗日乘子。
z 无约束的求解方法是找到12(,)F x x 的驻点（1
2//0F x F x ??=??=）
- 有约束时，可以找到L 的驻点
12y x x ??=????，0y
L ?=?，0L
λ?=?
此时得到
11
20L
x x λ?=+=? 22
20L
x x λ?=+=?
1220L
x x λ
?=++=? z 这是给出有3个未知量的3个方程，求解得到1
2
1x
x ?
?==?
z 关键在于因为约束，最小化时1x 和2x 的选取不是独立的
- 拉格朗日乘子表示了这种相关性。
z 对于最优点，困难在于求解推导出的方程（可能是非线性方程）
不等式约束
z 现在考虑问题
min ()F y
y (15)
受约束于F()0≤y (16)
- 假定有n 个约束，但是由于不是所有的不等式约束都将限制解的自由度，
所以状态维数为
p 时不需要n 个约束。
z 和前面的图相似，但是现在不是所有的约束都有效
- 因为在优化值[]x
10.60=?处，1210x x +?<，顶部的黑线是无效
的?它没有限制问题中的自由度
- 蓝色的约束是有效的，代价比左边的低，但是
10f >
图4：符号显示0f >的部分
图5：有效和无效约束的其他情况
z 这种情况下直观结果就是在极小点，代价梯度一定位于有效约束张成的空
间内 — 所以展开：
j i i j
i j
f f F
λλ???=?????∑∑x x x (17) 有效的 无效的
- 如果约束无效，则可以令0j λ=
z 对于等式约束，需要代价和函数梯度是共线的，但是它们可以是任意方向。
z 对于不等式约束，需要一个和状态允许变化相关的附加约束。
- 必须限制条件17使得代价梯度点在约束的“允许边”的方向（
0f <）
。 ?没有违反约束时，代价不能减少。 ?代价和函数梯度一定在相反方向。 - 给定17，需要对有效的约束有0i
λ≥
z 总结：有效的约束，0i λ≥，而无效的约束，0j λ=
z 给定这些，我们可以和以前一样定义拉格朗日函数为T L F λ=+f ，而且
最优化的必要条件是：
0L
?=?y
(18) 0 i i
L i λλ?=?? (19) 其中第二个性质适合于所有约束 - 有效的约束有0i λ≥，而且满足0i L
i f λ??== - 无效的约束有0i λ=，而且满足0i L i f λ??=<。
z 等式18和19是非线性规划中Kuhn-Tucker 定理的“本质”— 更多的精确
叙述放在对约束性质的更翔实的说明中。
z 注意在这里有个规则的潜在假设 — 就是有效约束梯度是线性无关的—
λ被良好地定义时。
- 避免冗余
代价灵敏度
z 经常发现问题中的约束有时候可任意选取 – 限制上有弹性
- 需要研究那些约束选择影响求解的程度
z 注意在求解点，
0T L F λ???=?=????f y y y
如果状态由Δy 改变，相应的变化为
代价
F
F ?Δ=Δ?y y
约束
f f ?Δ=
Δ?y y
所以我们有
f
T
T F λλ?Δ=?Δ=?Δ?y f y
T dF d λ?=?f
- 代价对约束函数变化的灵敏度由拉格朗日乘子给定。
z 对于有效的约束0λ≥，期望0dF d ≤f
- 意义在于如果它是有效的，则允许f 增加将使约束边界在减少F 的方向 移动。
- 无效的约束不会有效果。
图6：说明约束的变化影响代价的情况可以用拉格朗日乘子预测
生成图4的代码
常用无约束最优化方法评价准则 方法算法特点适用条件 最速下降法属于间接法之一。方法简便，但要计算一阶偏导 数，可靠性较好，能稳定地使函数下降，但收敛 速度较慢，尤其在极点值附近更为严重 适用于精度要求不高或用于对 复杂函数寻找一个好的初始 点。 Newton法属于间接法之一。需计算一、二阶偏导数和Hesse 矩阵的逆矩阵，准备工作量大，算法复杂，占用 内存量大。此法具有二次收敛性，在一定条件下 其收敛速度快，要求迭代点的Hesse矩阵必须非 奇异且定型（正定或负定）。对初始点要求较高， 可靠性较差。 目标函数存在一阶\二阶偏导 数，且维数不宜太高。 共轭方向法属于间接法之一。具有可靠性好，占用内存少， 收敛速度快的特点。 适用于维数较高的目标函数。 变尺度法属于间接法之一。具有二次收敛性，收敛速度快。 可靠性较好，只需计算一阶偏导数。对初始点要 求不高，优于Newton法。因此，目前认为此法是 最有效的方法之一，但需内存量大。对维数太高 的问题不太适宜。 适用维数较高的目标函数 （n=10～50）且具有一阶偏导 数。 坐标轮换法最简单的直接法之一。只需计算函数值，无需求 导，使用时准备工作量少。占用内存少。但计算 效率低，可靠性差。 用于维数较低（n<5）或目标函 数不易求导的情况。 单纯形法此法简单，直观，属直接法之一。上机计算过程 中占用内存少，规则单纯形法终止条件简单，而 不规则单纯形法终止条件复杂，应注意选择，才 可能保证计算的可靠性。 可用于维数较高的目标函数。
常用约束最优化方法评价标准 方法算法特点适用条件 外点法将约束优化问题转化为一系列无约束优化问题。 初始点可以任选，罚因子应取为单调递增数列。 初始罚因子及递增系数应取适当较大值。 可用于求解含有等式约束或不等 式约束的中等维数的约束最优化 问题。 内点法将约束优化问题转化为一系列无约束优化问题。 初始点应取为严格满足各个不等式约束的内点， 障碍因子应取为单调递减的正数序列。初始障碍 因子选择恰当与否对收敛速度和求解成败有较大 影响。 可用于求解只含有不等式约束的 中等维数约束优化问题。 混合罚函数法将约束优化问题转化为一系列无约束优化问题， 用内点形式的混合罚函数时，初始点及障碍因子 的取法同上；用外点形式的混合罚函数时，初始 点可任选，罚因子取法同外点法相同。 可用于求解既有等式约束又有不 等式约束的中等维数的约束化问 题。 约束坐标轮换法由可行点出发，分别沿各坐标轴方向以加步探索 法进行搜索，使每个搜索点在可行域内，且使目 标函数值下降。 可用于求解只含有不等式约束， 且维数较低（n<5），目标函数的 二次性较强的优化问题。 复合形法在可行域内构造一个具有n个顶点的复合形，然 后对复合形进行映射变化，逐次去掉目标函数值 最大的顶点。 可用于求解含不等式约束和边界 约束的低维优化问题。
线性和非线性最优化理论、方法、软件及应用 最优化在航空航天、生命科学、水利科学、地球科学、工程技术等自然科学领域和经济金融等社会科学领域有着广泛和重要的应用, 它的研究和发展一直得到广泛的关注. 最优化的研究包含理论、方法和应用.最优化理论主要研究问题解的最优性条件、灵敏度分析、解的存在性和一般复杂性等.而最优化方法研究包括构造新算法、证明解的收敛性、算法的比较和复杂性等.最优化的应用研究则包括算法的实现、算法的程序、软件包及商业化、在实际问题的应用. 这里简介一下线性和非线性最优化理论、方法及应用研究的发展状况. 1. 线性最优化 线性最优化, 又称线性规划, 是运筹学中应用最广泛的一个分支.这是因为自然科学和社会科学中许多问题都可以近似地化成线性规划问题. 线性规划理论和算法的研究及发展共经历了三个高潮, 每个高潮都引起了社会的极大关注. 线性规划研究的第一高潮是著名的单纯形法的研究. 这一方法是Dantzig在1947年提出的,它以成熟的算法理论和完善的算法及软件统治线性规划达三十多年. 随着60年代发展起来的计算复杂性理论的研究, 单纯形法在七十年代末受到了挑战. 1979年前苏联数学家Khachiyan提出了第一个理论上优于单纯形法的所谓多项式时间算法--椭球法, 曾成为轰动一时的新闻, 并掀起了研究线性规划的第二个高潮. 但遗憾的是广泛的数值试验表明, 椭球算法的计算比单纯形方法差. 1984年Karmarkar提出了求解线性规划的另一个多项式时间算法. 这个算法从理论和数值上都优于椭球法,因而引起学术界的极大关注, 并由此掀起了研究线性规划的第三个高潮. 从那以后, 许多学者致力于改进和完善这一算法,得到了许多改进算法.这些算法运用不同的思想方法均获得通过可行区域内部的迭代点列,因此统称为解线性规划问题的内点算法. 目前内点算法正以不可抗拒的趋势将超越和替代单纯形法. 线性规划的软件, 特别是由单纯形法所形成的软件比较成熟和完善.这些软件不仅可以解一般线性规划问题, 而且可以解整数线性规划问题、进行灵敏度分析, 同时可以解具有稀疏结构的大规模问题.CPLEX是Bi xby基于单纯形法研制的解线性和整数规划的软件, CPLEX的网址是https://www.doczj.com/doc/5911911828.html,/. 此外,这个软件也可以用来解凸二次规划问题, 且特别适合解大规模问题. PROC LP是SAS软件公司研制的SAS商业软件中OR模块的一个程序. 这个程序是根据两阶段单纯形法研制的,可以用来解线性和整数规划问题并可进行灵敏度分析, 是一个比较完善的程序.用户可以根据需要选择不同的参数来满足不同的要求。关于内点法的软件也在研制之中.BPMP D是Cs.Mzos基于原始对偶内点法研制的解线性和整数规划的软件，其FTP地址是ftp://ftp.sztaki.hu/pub /oplab/SOFTWARE/BPMPD/ ，可以自由下载.此外,在互联网上能访问到的解线性和整数规划问题的软件还有:EQPS（线性，整数和非线性规划）,FMP（线性和混合整数规划），HS/LPLO（线性规划），KORBX（线性规划），LAMPS（线性和整数规划），LPBLP（线性规划），MILP（混合整数规划），MINTO（混合整数规划），MPSIII（线性和混合整数规划），OML（线性和混合整数规划），OSL（线性，二次和混合整数规划），PROCLP（线性和整数规划），WB（线性和混合整数规划），WHIZARD（线性和混合整数规划），XPRESSMP（线性和混合整数规划）等.
习题二包括题目：P36页5（1）（4） 5（4）
习题三 包括题目：P61页1(1)(2); 3; 5; 6; 14；15(1) 1(1)(2)的解如下 3题的解如下
5,6题 14题解如下 14. 设22121212()(6)(233)f x x x x x x x =+++---, 求点在(4,6)T -处的牛顿方向。 解：已知 (1) (4,6)T x =-，由题意得 121212212121212(6)2(233)(3)()2(6)2(233)(3)x x x x x x x f x x x x x x x x +++-----?? ?= ?+++-----?? ∴ (1)1344()56g f x -?? =?= ??? 21212122211212122(3)22(3)(3)2(233)()22(3)(3)2(233)22(3)x x x x x x x f x x x x x x x x +--+--------? ??= ? +--------+--?? ∴ (1)2(1)1656()()564G x f x --?? =?= ?-?? (1)1 1/8007/400()7/4001/200G x --?? = ?--?? ∴ (1)(1)11141/100()574/100d G x g -?? =-= ?-?? 15（1）解如下 15. 用DFP 方法求下列问题的极小点 （1）22 121212min 353x x x x x x ++++ 解：取 (0) (1,1)T x =，0H I =时，DFP 法的第一步与最速下降法相同 2112352()156x x f x x x ++???= ?++??， (0)(1,1)T x =，(0) 10()12f x ???= ??? (1)0.07800.2936x -??= ?-??， (1) 1.3760() 1.1516f x ???= ?-?? 以下作第二次迭代 (1)(0) 1 1.07801.2936x x δ-??=-= ?-??， (1)(0) 18.6240()()13.1516f x f x γ-??=?-?= ?-?? 0110 111011101 T T T T H H H H H γγδδδγγγ=+-
第３３卷第２期 测绘科学 ＶｏＬ３３Ｎｏ．２ ２００８年３月 ＳｃｉｅｎｃｅｏｆＳｕｒｖｅｙｉｎｇａｎｄＭａｐｐｉｎｇ Ｍａｒ． 测量控制网优化设计的可靠性准则法 张正禄①②，邓勇①。罗长林①，杨奇儒③ （①武汉大学测绘科学与技术学院，武汉４３００７９；②武汉大学测绘遥感信息工程国家重点实验室，武汉４３００７９； ③河南平顶山市国土资源局，河南平顶山４６７０００） 【摘要】测量控制网优化设计与网的精度、可靠性、灵敏度以及费用等准则有关，但这些准则之间的关系又十分密切，本文提出了一种基于观测值内部可靠性指标的测量控制网模拟法优化设计新方法，介绍了其原理和特点，并用实例说明了用该方法的计算步骤和优化效益。 【关键词】测量控制网；优化设计；可靠性；多余观测分量【中图分类号】Ｐ２５８；Ｐ２１【文献标识码】Ａ【文章编号】１００９－２３０７（２００８）０２－００２３－０３ ＤｏＩ：１０．３７７１／ｊ．ｉｓｓｎ．１００９－２３０７．２００８．０２．００８ １引言 ２ ｒｉ的计算及性质 测量控制网的优化设计有解析法和模拟法两种，它们都要依赖计算机程序作大量计算。解析法是以最优化理论为基础的严密方法，其数学模型一般表示为 臻离０ ｃ １０， 妒（ｘ）≥ ｝ （）哕（Ｘ）＝ Ｊ 第一式称目标函数，第二、三式称约束条件。目标函数可以是精度、可靠性、灵敏度或费用等指标，约束条件也可以是上述指标。其实质是在给定的约束条件下通过求目标函数的极值求最优解。在实际中要对优化的观测方案进行调整，故解析法的结果不是最优的。研制通用的解析法优化设计软件的难度较大，对解析法的研究很多，但应用很少。 模拟法是一种试算法。一般是根据优化的任务和设计者的经验，制定初始设计方案，用模拟观测值作平差计算分析，通过计算、修改、再计算、再修改，直到满意为止。模拟法的缺点是依赖于设计者的知识和经验，不同人的优本文提出了一种基于观测值内部可靠性指标的测量控制网的模拟优化设计方法。采用该方法，只需一个量化的可靠性指标，优化结果不以人的知识和经验为转移，具有一致性和严密性，在控制网数据处理通用软件包中增加一个优化设计模块即可应用。值得说明的是，本文提出的方法既适合地面边角网，也适合ＧＰＳ网，ＧＰＳ基线向量可看成是投影到与某一参考椭球面相应的高斯平面上的一条边，其长度和方向都可得到，因此，可将ＧＰＳ网看成是观测了边长和方向的平面网。 作者简介：张正禄（１９４４－），男，四川省渠县人，工学博士，武汉大学测绘学院教授，博士生导师，主要从事精密工程测量、变形监测分析与预报、测量数据处理和工程信息系统方面的科研和教学工作。 Ｅ．ｍａｉｌ：ｚｚｌ６２３＠ｗｔｕｓｍ．ｅｄｕ．ｃｎ 收稿日期：２００７－０５．１７ 基金项目：国家重点基础研究发展计划（９７３计划）项目（２００３ＣＢ７１６７０５） 网的可靠性可分网的总体可靠性，观测值的内部可靠 性（也称局部可靠性）和外部可靠性。在此，主要讨论观测值的内部可靠性。 对于一个测量控制网来说，由其间接观测平差模型（ｚ，Ａｘ，口。２ｐ一）可得观测值ｔ的多余观测分量ｒｊ（又称内部可靠性）‘¨： ｒｉ＝（Ｑ。Ｐ）ｄ （２） 且满足 ∑ｒ；＝ｒ＝ｎ—ｔ （３） 式中，Ｑ。为观测值改正数的协因数阵，Ｐ为观测值的 权阵。观测值ｆｆ能被发现的粗差下界值Ｖ。ｆｆ为： ｖ。丘＝业／－－－ （４） √Ｆｉ 其中，‰为非中心参数，其取值与显著水平Ｏｔ和检验功效’，有关，常取２．７９（ａ＝０．０５，＇，＝０．８０）或４．１３（Ｏｔ＝０．００１，ｙ＝０．８０）晗］。叽为观测值ｆｆ中误差，ｒ；又称为观测值屯的多余观测分量，ｒｆ愈大，Ｖ。ｔ愈小，发现观测值中粗差的能力愈强。观测值相互独立（本文只讨论这种情况）时。有 Ｉ＂ｉ：Ｉ一１０＂ｉ （５） 口￡ 上式中Ｚ为ｚ。的平差值的方差。观测值的内部可靠性 Ｌ具有以下性质： Ｉ）０≤ｒｉ≤Ｉ：‘愈小，该观测值在网中的地位愈高，若＾等于零，则该观测值为已知值；愈大，该观测值在网中的地位愈低，若‘等于Ｉ，表示对已知的量进行了观测，须删除。 ２）ｒｆ愈小，该观测值能被发现的粗差下界值Ｖ。ｆｆ愈 大，ｒｆ愈大，观测值能被发现的粗差下界值Ｖ。ｔ愈小；粗差下界值Ｖ。ｆｆ对平差结果的影响随ｒｆ的增大而减小。 ３）对于一个确定的网和设计方案，即在网形、观测值数和精度确定的情况下，观测值的精度愈高，则ｒ｛愈小，观测值的精度愈低，则ｒｆ愈大，即观测值的内部可靠性与观测值的精度成反比。 ４）在确定的观测精度情况下，网的多余观测数愈多，则ｒｆ愈大，建网费用愈高。 ５）对于独立网来说，ｒｉ是与基准的位置无关的不变量。设控制网的网点数为ｍ，已知点数为ｍ。，未知点数为 ｍ。，已知边和已知方位角数分别为屯和＿｜｝。．有方向观测的 万方数据
Advances in Education教育进展, 2019, 9(4), 450-453 Published Online July 2019 in Hans. https://www.doczj.com/doc/5911911828.html,/journal/ae https://https://www.doczj.com/doc/5911911828.html,/10.12677/ae.2019.94076 A Good Textbook for Optimization —Review of Theory and Algorithms on Nonlinear Programming Naiyang Deng School of Science, China Agricultural University, Beijing Received: Jun. 30th, 2019; accepted: Jul. 12th, 2019; published: Jul. 22nd, 2019 Abstract This paper provides a review for the textbook written by Professors Yiju Wang and Naihua Xiu, named Theory and Method of Nonlinear Optimization published by Science Publishing House in 2012 by pointing out some highlights and features of the book, and giving some suggestions for improvement. Keywords Book Review, Highlights and Features, Suggestions 最优化课程的一本好教材 ——《非线性最优化理论与方法》书评 邓乃扬 中国农业大学理学院，北京 收稿日期：2019年6月30日；录用日期：2019年7月12日；发布日期：2019年7月22日 摘要 本文对王宜举教授和修乃华教授2012年在科学出版社出版的《非线性最优化理论与方法》进行了评述，指出了该书的一些亮点和特色，同时也给出了进一步提升的建议。 关键词 书评，亮点与特色，建议
最优化理论 一、最优化理论概述 优化是从处理各种事物的一切可能的方案中，寻求最优的方案。优化的原理与方法，在科学的、工程的和社会的实际问题中的应用，便是优化问题。优化一语来自英文Optimization，其本意是寻优的过程；优化过程：是寻找约束空间下给定函数取极大值（以max表示)或极小(以min表示)的过程。优化方法也称数学规划，是用科学方法和手段进行决策及确定最优解的数学。在生产过程、科学实验以及日常生活中，人们总希望用最少的人力、物力、财力和时间去办更多的事，获得最大的效益，在管理学中被看作是生产者的利润最大化和消费者的效用最大化，如果从数学的角度来看就被看作是“最优化问题”。在最优化的研究生教学中我们所说的最优化问题一般是在某些特定的“约束条件”下寻找某个“目标函数”的最大(或最小)值，其解法称为最优化方法。 最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。 最优化理论与方法作为一个重要的数学分支，它所研究的就是在众多的方案中怎么能找到最优、最好的方案。由于科学技术与生产技术的迅速发展，尤其是计算机应用的不断扩大，使最优化问题的研究不仅成为了一种迫切的需要，而且有了求解的有力工具，因此，发展成了一种新的科学。最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：连续优化：包括线性规划、非线性规划、全局优化、锥优化等；离散优化：网络优化、组合优化等；和近年来发展迅速的智能优化等。 一般而言，最优化问题的求解方法大致可分为4类：1)解析法：对于目标函数及约束条件具有简单而明确的数学表达式的最优化问题，一般都可采用解析法。在解决实际问题时，由于描述实际问题的解析形式的数学表达式很难找到，因此，这种表达式则缺
单纯形法求最优解问题 题目（老师布置的那道作业题）：2153m ax x x f +=，其中 ??? ??? ?=≥=++=+=+5,4,3,2,1,0182312245214 231j x x x x x x x x j ，求2153m ax x x f +=的最大值。 这张表是根据题目画的，Cj （行向量）为5432100053m ax x x x x x f ++++=中各个变量的系数，Ci （列向量）为与X B （列向量）相对应的各项的系数，X B 称为基变量（3列，由题目中的方程个数决定），起初的基变量由构造的变量x3、x4、x5组成，b 为对应三个方程等式右边的常数，z j 为Ci 各列与xj 各列乘积的和，如z1=0*1+0*0+0*3=0。i θ为判别将哪个基变量换出的依据，根据c j -z j 为正，要先将x2换入XB 中，关键是判断x3、x4、x5哪个跟x2换，这就要根据各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，如上表可知x2跟x4换，换完之后注意原来x4所对应的列向量为[0 1 0]T ,故要将x2所对应的列向量变换为为[0 1 0]T ，注意b 也要跟着变化，于是得下表.
由上表知c 1-z 1=3>0，故仍需将x1换入XB 中，用各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，结合i θ可知，x1跟x5换，于是得下表。 由上表可知c j -z j 均非正，故5432100053m ax x x x x x f ++++=取最大值时，????? ?? ?????????=00662x ， 对应的最大值36max =f . 系统工程导论知识点整理： 系统是由相互作用和相互依赖的若干组成部分(要素)结合的具有特定功能的有机整体。 系统的特征：整体性、相关性、目的性、环境适应性。 系统的功能是指系统与外部环境相互作用所反映的能力。 结构是功能的内在根据，功能是结构的外在表现。 系统功能的特性：易变性、相关性。 系统工程就是用科学的方法规划和组织人力、物力、财力，通过最优途径的选择，使人们的工作在一定期限内收到最合理、最经济、最有效的效果。 科学的方法：从整体观念出发，通盘筹划，合理安排整体中的每一个局部，以求得整体的最优规划、最优管理和最优控制，使每个局部都服从一个整体目标，力求避免资源的损失和浪费。
非线性规划的罚函数算法 摘要：最优化理论和方法是一门十分活跃的学科，罚函数法是将约束问题无约束化的一种主要方法。本文简要介绍了最优化问题的优化算法，主要介绍了非线性规划的罚函数算法的基本理论和相应的发展过程。 关键词：最优化理论；非线性规划；惩罚函数法 1 前言 最优化理论和方法的出现可以追溯到十分古老的极值问题，然而，它成为一门独立的学科还是在上世纪40年代末．Dantzing在1947年提出求解一般线性规划问题的单纯形算法之后，随着工业革命、信息革命的不断深化，以及计算机技术的巨大发展，至今短短的几十年，它得到了迅猛的发展．现在，解线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等各种最优化问题的理论研究发展迅速，新方法不断涌现，在经济、军事、科学技术等方面得到了广泛的应用，成为一门十分活跃的学科． 约束非线性规划问题广泛见于工程、国防、经济等许多重要领域．求解约束非线性规划问题的主要方法之一是把它化成无约束非线性规划问题，而罚函数方法和拉格朗日对偶方法是将约束规划问题无约束化的两种主要方法．罚函数方法通过求解一个或多个罚问题来得到约束规划问题的解，如果当罚参数充分大时，求单个罚问题的极小点是原约束规划问题的极小点，则称此罚问题中的罚函数为精确罚函数，否则称为序列罚函数．针对传统罚函数的定义而言，若罚函数是简单的、光滑的，则它一定是不精确的；若罚函数是简单的、精确的，则它一定是不光滑的；若罚函数是精确的、光滑的，则它一定是复杂的．因此我们的工作是对传统罚函数进行了改造，主要是引入了指数型罚函数和对数型罚函数，并在改造后的罚函数中增添了乘子参数，使之成为既是简单的、光滑的，又是精确的结
统计学梯度下降法（SGDs）易于实现，然而它有两个主要的缺陷。第一个缺陷是它需要手动调谐大量的参数，比如学习速率和收敛准则。第二个缺陷是它本质上是序列方法，不利于并行计算或分布式计算。（然而，在计算资源如RAM受限的情况下，序列方法倒是一个不错的选择。） 这里介绍一些非线性优化算法：牛顿算法，伪牛顿算法和共轭梯度法。其中，伪牛顿算法包括DFP、BFGS和L-BFGS算法。 考虑如下的无约束最小化问题： min x f(x)（1） 其中x=(x1,…,x N)T∈?N. 为简便起见，这里假设f是凸函数，且二阶连续可导。记（1）的解为x?. 牛顿算法（Newton‘s Method） 基本思想：在现有的极小点估计值的附近对f(x)做二阶泰勒展开，进而找到下 其中g(k)=?f(x)| x(k)是梯度矩阵，H(k)=?2f(x)| x(k) 是海森矩阵。 牛顿算法是一种具有二次收敛性的算法。对于非二次函数，若函数的二次性态较强，或迭代点已进入极小点的领域，则其收敛速度也是很快的，这是牛顿算法的主要优点。但牛顿算法由于迭代公式中没有步长因子，而是定步长迭代，所以对于非二次函数，有时会出现f(x(k+1))>f(x(k))的情况，这表明牛顿算法不能保证函数值稳定地下降。由此，人们提出了阻尼牛顿算法，在原始牛顿算法的第4步中，采用一维搜索（line search）算法给d(k)加一个步长因子λ(k)，其中： λ(k)=arg minλ∈?f(x(k)+λd(k))（2）一维搜索算法将另作介绍。 拟牛顿算法（Quasi-Newton Methods） 基本思想：不直接计算二阶偏导数，而是构造出近似海森矩阵（或海森矩阵的逆）的正定对称阵，在拟牛顿条件下优化目标函数。 下文中，用B表示对H的近似，用D表示对H?1的近似，并令s(k)=x(k+1)?x(k)，y(k)=g(k+1)?g(k).
分数: ___________任课教师签字：___________ 课程作业 学年学期：2017——2018学年第二学期 课程名称：优化理论 作业名称：作业三 学生姓名： 学号： 提交时间：
一、问题重述 形如的min (x),x R n f ∈问题称为无约束优化问题，常用下降算法来解决这类问题。下降算法的关键在于步长和搜索方向的选取。步长的求取可以借助前面作业中提到的一维搜索等方法求取，而搜索方向算法可以分为两大类，解析法和直接法。 解析法借助了目标函数的导数进行搜索，这类算法搜索速度快、效率高，但是对目标函数的要求更为严格。常用的方法有最速下降法、Newton 法、共轭梯度法、拟Newton 法等。 直接法不使用导数，也不需要得到目标函数的明确解析式，只需要能够得到某些函数上的点即可。因此直接法的适用范围更广，但相应的收敛速度会较慢，计算量也会随着问题维数的增加而迅速增大。常用的方法有单纯形法、Powell 方向加速法以及Powell 改进算法。 本作业以直接法的Powell 法为例，解决具体的无约束优化问题，并对将Powell 方向加速法和Powell 改进算法解决结果进行对比。 二、算法原理 对于n 维正定二次函数(x)0.5T T f x Gx b x c =++，设011,,...(k n)k p p p -<关于G 共轭，0x 与1x 为任意不同点。分别从0x 与1x 出发，依次沿011,,...k p p p -作一维搜索。如果最后找到两个互不相同的极小点x a 与x b ，则x b a x -与011,,...k p p p -关于G 共轭。 Powell 方向加速法正是基于这一原理，每次迭代过程作n+1次一维搜索。第一次沿给定的n 个线性无关的方向011,,...n p p p -依次作一维搜索，之后沿由这一阶段的起点到第n 次搜索所得到的点的方向P 再做一次一维搜索，并把这次所得点作为下一阶段的起点，下一阶段的n 个搜索方向为011,,...,n p p p p -。以此直到找到最优解。 此算法是在迭代中逐次生成共轭方向，而共轭方向又是较好的搜索方向，所以称之为方向加速法。但是，此算法产生的n 个向量可能线性或近似线性相关，这时张不成n 维空间，可能得不到真正的极小点。因此，Powell 原始算法存在一定的缺陷。 Powell 改进算法虽然不再具有二次终止性，但克服了搜索方向的线性相关的不利情形，是解决无约束优化问题较有效的直接法之一。 本次作业一维搜索的过程是利用函数求导，求得最小值。经过试验发现，α是允许为负数的。否则最终寻优得到的极值点与实际结果存在很大的偏差，
非线性约束最优化方法 ——乘子法 1.1 研究背景 最优化理论与方法是一门应用性相当广泛的学科，它的最优性主要表现在讨论决策问题的最佳选择性，讨论计算方法的理论性质，构造寻求最佳解的计算方法，以及实际计算能力。伴随着计算数学理论的发展、优化计算方法的进步以及计算机性能的迅速提高，规模越来越大的优化问题得到解决。因为最优化问题广泛见于经济计划、工程设计、生产管理、交通运输、国防等重要领域，它已受到政府部门、科研机构和产业部门的高度重视。然而，随着人们对模型精度和最优性的要求所得到的优化命题往往具有方程数多、变量维数高、非线性性强等特点，使得相关变量的存储、计算及命题的求解都相当困难，从而导致大规模非线性优化很难实现。因此，寻求高效、可靠的大规模非线性优化算法成为近年来研究的热点。 本文讨论的问题属于非线性约束规划的范畴，讨论了其中的非线性等式约束最优化问题方面的一些问题。 1.2非线性约束规划问题的研究方法 非线性约束规划问题的一般形式为 （NPL ） {}{} m in (),, s.t. ()0,1,2,...,, ()0,1,2,...,n i i f x x R c x i E l c x i I l l l m ∈=∈=≤∈=+++ 其中，(),()i f x c x 是连续可微的. 在求解线性约束优化问题时，可以利用约束问题本身的性质，
但是对于非线性约束规划问题，由于约束的非线性使得求解这类问题比较复杂、困难。因此，我们将约束问题转化为一系列无约束优化问题，通过求解一系列无约束优化问题，来得到约束优化问题的最优解。我们用到的几类主要的方法有:罚函数法、乘子法以及变尺度法。 传统上我们所提出的非线性约束最优化方法一般都遵循下列三个基本思路之一 1 借助反复的线性逼近把线性方法扩展到非线性优化问题中来 2 采用罚函数把约束非线性问题变换到一系列无约束问题 3 采用可变容差法以便同时容纳可行的和不可行的X 矢量 其中源于思路2 的乘子罚函数法具有适合于等式及不等式约束不要求初始点为严格内点，甚至不要求其为可行点对自由度的大小无任何要求等特点。 1.3乘子法 罚函数法的主要缺点在于需要惩罚因子趋于无穷大，才能得到约束问题的极小点，这会使罚函数的Hesse矩阵变得病态，给无约束问题的数值求解带来很大问题，为克服这一缺点，Hestenes和Powell 于1964年各自独立地提出乘子法。所谓乘子法是：由问题的Lagrange 函数出发，考虑它的精确惩罚，从而将约束优化问题化为单个函数的无约束优化问题，它同精确罚函数法一样，具有较好的收敛速度和数值稳定性，且避免了寻求精确罚函数法中关于罚参数阈值的困难，它们一直是求解约束优化问题的主要而有效的算法。 考虑如下非线性等式约束优化问题：
分数: ___________ 任课教师签字：___________ 课程作业 学年学期：2017——2018学年第二学期 课程名称：优化理论 作业名称：作业三 学生姓名： 学号： 提交时间：
一、问题重述 形如的min (x),x R n f ∈问题称为无约束优化问题，常用下降算法来解决这类问题。下降算法的关键在于步长和搜索方向的选取。步长的求取可以借助前面作业中提到的一维搜索等方法求取，而搜索方向算法可以分为两大类，解析法和直接法。 解析法借助了目标函数的导数进行搜索，这类算法搜索速度快、效率高，但是对目标函数的要求更为严格。常用的方法有最速下降法、Newton 法、共轭梯度法、拟Newton 法等。 直接法不使用导数，也不需要得到目标函数的明确解析式，只需要能够得到某些函数上的点即可。因此直接法的适用范围更广，但相应的收敛速度会较慢，计算量也会随着问题维数的增加而迅速增大。常用的方法有单纯形法、Powell 方向加速法以及Powell 改进算法。 本作业以直接法的Powell 法为例，解决具体的无约束优化问题，并对将Powell 方向加速法和Powell 改进算法解决结果进行对比。 二、算法原理 对于n 维正定二次函数(x)0.5T T f x Gx b x c =++，设011,,...(k n)k p p p -<关于G 共轭，0x 与1x 为任意不同点。分别从0x 与1x 出发，依次沿011,,...k p p p -作一维搜索。如果最后找到两个互不相同的极小点x a 与x b ，则x b a x -与011,,...k p p p -关于G 共轭。 Powell 方向加速法正是基于这一原理，每次迭代过程作n+1次一维搜索。第一次沿给定的n 个线性无关的方向011,,...n p p p -依次作一维搜索，之后沿由这一阶段的起点到第n 次搜索所得到的点的方向P 再做一次一维搜索，并把这次所得点作为下一阶段的起点，下一阶段的n 个搜索方向为011,,...,n p p p p -。以此直到找到最优解。 此算法是在迭代中逐次生成共轭方向，而共轭方向又是较好的搜索方向，所以称之为方向加速法。但是，此算法产生的n 个向量可能线性或近似线性相关，这时张不成n 维空间，可能得不到真正的极小点。因此，Powell 原始算法存在一定的缺陷。 Powell 改进算法虽然不再具有二次终止性，但克服了搜索方向的线性相关的不利情形，是解决无约束优化问题较有效的直接法之一。 本次作业一维搜索的过程是利用函数求导，求得最小值。经过试验发现，α是允许为负数的。否则最终寻优得到的极值点与实际结果存在很大的偏差，而且寻优的效率特别低下。
五种最优化方法 1. 最优化方法概述 1.1最优化问题的分类 1）无约束和有约束条件； 2）确定性和随机性最优问题（变量是否确定）； 3）线性优化与非线性优化（目标函数和约束条件是否线性）； 4）静态规划和动态规划（解是否随时间变化）。 1.2最优化问题的一般形式（有约束条件）： 式中f(X)称为目标函数(或求它的极小，或求它的极大)，si(X)称为不等式约束，hj(X)称为等式约束。化过程就是优选X，使目标函数达到最优值。 2.牛顿法 2.1简介 1）解决的是无约束非线性规划问题； 2）是求解函数极值的一种方法； 3）是一种函数逼近法。 2.2 原理和步骤
3. 最速下降法（梯度法） 3.1最速下降法简介 1）解决的是无约束非线性规划问题； 2）是求解函数极值的一种方法； 3）沿函数在该点处目标函数下降最快的方向作为搜索方向； 3.2 最速下降法算法原理和步骤
4. 模式搜索法(步长加速法) 4.1 简介 1）解决的是无约束非线性规划问题； 2）不需要求目标函数的导数，所以在解决不可导的函数或者求导异常麻烦的函数的优化问题时非常有效。 3）模式搜索法每一次迭代都是交替进行轴向移动和模式移动。轴向移动的目的是探测有利的下降方向，而模式移动的目的则是沿着有利方向加速移动。 4.2模式搜索法步骤
5.评价函数法 5.1 简介 评价函数法是求解多目标优化问题中的一种主要方法。在许多实际问题中，衡量一个方案的好坏标准往往不止一个，多目标最优化的数学描述如下：min (f_1(x),f_2(x),...,f_k(x)) s.t. g(x)<=0 传统的多目标优化方法本质是将多目标优化中的各分目标函数，经处理或数学变换，转变成一个单目标函数，然后采用单目标优化技术求解。常用的方法有
毕业论文 题目非线性最优化计算方法与算法学院数学科学学院 专业信息与计算科学 班级计算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
%%%%%%%%%%考虑外部性%%%%%%%%% K=[0.238982596 0.287307802 0.316082138 0.41731 0.44684 0.554375 0.7433476 -0.5]; Ae=[]; be=[]; Au=[-4312.03 -4428.81 -4762.01 -3621 -1742 -1125 -7042 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 16.99234332 15.49032101 16.29521726 0 0 0 0 0 28.69966647 24.77171169 25.46127697 0 0 0 0 0 0.374634341 0.243236446 0.217269563 0 0 0 0 0 3.709548964 3.549331817 3.764874154 0 0 0 0 0 0.519208086 0.439245837 0.453720507 -0.687558374 -0.330772352 -0.213615899 -1.337140588 0 0.800693399 0.626156548 0.637213949 -0.754544082 -0.362998009 -0.234427532 -1.467412158 0 1.389212223 0.956314404 0.910849795 -1.243454189 -0.598204142 -0.386325867 -2.418228224 0 0.02072254 0.007129367 0.003239074 -0.01405806 -0.006763088 -0.004367666 -0.027339646 0 1.481346246 1.260784084 1.304148318 -1.871119181 -0.900162832 -0.581333631 -3.638890162 0 -4070.125117 -4222.427454 -4572.482002 -3578.6343 -1688.3464 -1097.6625 -6592.7204 0 -0.87848773 -0.8804649 -0.87608648 -0.9171424 -0.9362472 -0.95345404 -0.9357319 0]; bu=[0;6.76;2.53;5022.16;300;250;40;36.351;0;0;0;0;0;-59200;-12.3074]; B1=[0;0;0;0;0;0;0;0]; X=linprog(K,Au,bu,Ae,be,B1); X %%%%%%%%%%%%%%%%%%%% %%%%%%不考虑外部性%%%%%%%%%%% K=[0.232622352 0.281860365 0.310653447 0.574625 0.46229 0.56 0.7433476 -0.5]; Ae=[]; be=[]; Au=[-4312.03 -4428.81 -4762.01 -3621 -1742 -1125 -7042 1 0 0 0 1 0 0 0 0