北航最优化方法作业答案uco_trustregion

格式：pdf
大小：672.86 KB
文档页数：23

下载文档原格式

/ 23

北航最优化方法大作业参考

1 流量工程问题1.1 问题重述定义一个有向网络G=(N,E)，其中N是节点集，E是弧集。

令A是网络G的点弧关联矩阵，即N×E阶矩阵，且第l列与弧里(I,j)对应，仅第i行元素为1，第j行元素为-1，其余元素为0。

再令b m=(b m1,…,b mN)T，f m=(f m1,…,f mE)T，则可将等式约束表示成：Af m=b m本算例为一经典TE算例。

算例网络有7个节点和13条弧，每条弧的容量是5个单位。

此外有四个需求量均为4个单位的源一目的对，具体的源节点、目的节点信息如图所示。

这里为了简单，省区了未用到的弧。

此外，弧上的数字表示弧的编号。

此时，c=((5,5…,5)1 )T，×13)。

根据上述四个约束条件，分别求得四个情况下的最优决策变量x=((x12,x13,…,x75)1×13图 1 网络拓扑和流量需求1.2 7节点算例求解1.2.1 算例1（b1=[4;-4;0;0;0;0;0]T）转化为线性规划问题：Minimize c T x1Subject to Ax1=b1x1>=0利用Matlab编写对偶单纯形法程序，可求得:最优解为x1*=[4 0 0 0 0 0 0 0 0 0 0 0 0]T对应的最优值c T x1=201.2.2 算例2（b2=[4;0;-4;0;0;0;0]T）Minimize c T x2Subject to Ax2=b2X2>=0利用Matlab编写对偶单纯形法程序，可求得:最优解为x2*=[0 4 0 0 0 0 0 0 0 0 0 0 0]T对应的最优值c T x2=201.2.3 算例3（b3=[0;-4;4;0;0;0;0]T）Minimize c T x3Subject to Ax3=b3X3>=0利用Matlab编写对偶单纯形法程序，可求得:最优解为x3*=[4 0 0 0 4 0 0 0 0 0 0 0 0]T对应的最优值c T x3=401.2.4 算例4（b4=[4;0;0;0;0;0;-4]T）Minimize c T x4Subject to Ax4=b4X4>=0利用Matlab编写对偶单纯形法程序，可求得:最优解为x4*=[4 0 0 4 0 0 0 0 0 4 0 0 0]T对应的最优值c T x4=601.3 计算结果及结果说明1.3.1 算例1（b1=[4;-4;0;0;0;0;0]T）算例1中，由b1可知，节点2为需求节点，节点1为供给节点，由节点1将信息传输至节点2的最短路径为弧1。

北航最优化大作业

北航最优化大作业1.引言旅行商问题（Traveling Salesman Problem，TSP）是一种经典的组合优化问题，目标是找到一条路径，使得旅行商从起点出发，途经所有城市一次后返回起点，并且总路径长度最短。

TSP问题具有NP-hard的特性，寻找最优解是一个非常具有挑战性的任务。

本文将基于禁忌算法，探讨TSP问题的求解方法。

2.禁忌算法简介禁忌算法是一种基于局部的元启发式算法，通过在过程中禁止一定的动作来跳出局部最优解，以期望获得更好的全局最优解。

算法通过引入禁忌表和禁忌长度等机制，避免过程中陷入局部最优解。

3.TSP问题的数学建模假设有n个城市，城市之间的距离可以表示为一个n×n的距离矩阵D。

TSP问题的目标可以定义为：min ∑_(i=1)^n ∑_(j=1)^(n) D_ij*x_ijs.t. ∑_(i=1)^n x_ij=1,∑_(j=1)^n x_ij=1,∀i ≠ jx_ij∈{0,1}, 1≤i,j≤n其中x_ij表示城市i与城市j之间的路径是否存在，1表示存在，0表示不存在。

4.禁忌算法在TSP问题中的应用（1）初始化选取一个起始解x，计算其路径长度f(x)。

将x设为当前解x_best，将f(x)设为当前解的最优值f_best。

（2）选择邻域解选择当前解的一个邻域解x'，使得x'与x只有一个位置上的交换。

通过随机选择两个位置，进行交换操作。

（3）禁忌判断如果邻域解x'的路径长度f(x')小于当前解的最优值f_best，则更新f_best为f(x')，并将x'设为新的当前解。

否则，比较x'与当前解的禁忌情况。

（4）禁忌更新如果x'未在禁忌表中，或者禁忌表中对应的禁忌周期已过，则将x'设为新的当前解。

否则，选择一个路径长度较短的邻域解x''，即使其路径长度f(x'')大于f_best。

北航最优化方法最新最全答案2015版

将此问题化成线性规划.
minimize f (x)
x∈Rn
subject to Ax = b
x ≥ 0.
5
解: 引入变量 t ，所给问题等价于
minimize t subject to f (x) = t,
Ax = b, x ≥ 0.
考虑问题
minimize t
subject to f (x) ≤ t, Ax = b,
4. 单纯形法的练习：习题2.10，习题2.11，习题2.12，习题2.13，习题2.20(说明单纯形法的效率的一般性例子中，自变量为三个时所得问题)，习题2.21(说明单纯形法采用最小相对费用系数进基原则确定进基变量时，如果所求解问题是退化的，则单纯形法会出现循环！)，习题2.31.
5. 两阶段法的练习：习题2.14-习题2.16；大 M 法的练习：习题2.18.
2u1 − 2v1 + u3 − v3 = 3, ui, vi, s ≥ 0, i = 1, 2, 3.
方法2: 引入非负变量 t1, t2, t3 ，将原问题转化成等价问题
minimize t1 + t2 + t3 subject to x + y ≤ 1,
2x + z = 3, |x| = t1, |y| = t2, |z| = t3.
(c)
minimize subject to
x1 + 4x2 + x3 x1 − 2x2 + x3 = 4 x1 − x3 = 1
x2 ≥ 0, x3 ≥ 0.
解:
(c) 由于变量 x1 无限制，可利用约束 x1 = x3 + 1 对其消去. 因此，得其标准形

北航最优化大作业

图 18: 前两行为迭代点 xk, 后面一行为梯度的 2 范数，显然，前两行行都趋于无穷大，发散，梯度的 2 范数趋于 13.4536（从 matlab 变量表格中得到）。 4: 初始点 x(0) = (10, 20)T 前两行为迭代点 xk, 后面一行为梯度的 2 范数，显然，前两行行都趋于无穷大，发散，梯度的 2 范数趋于 13.4536（从 matlab 变量表格中得到）。
33
图 57: 7、9、11、13 迭代停止测试。
当 n=50 时，解 x*=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1] 判断矩阵：
图 58: 可以发现，没有发现负曲率的情况，第 1 和第 2 次的迭代到了边界，第 4、6、8、10、12、14、16 次迭代到了边界。
▽f (x) = g = −400x1(x2 − x21) + 2x1 − 2
200(x2 − x21)
[
]
▽2f (x) = G = 1200x21 − 400x2 + 2 −400x1
−400x1
200
14
4.1 最速下降法
代码和流程图：
图 33:
图 34: 15
4.1.1 初始点为 (1.2,1.2)
++
)
x1 + x12 − 100
x11
x1
−
50 1
−
x2

−10 − µ(
++
)
x1 + x2 − 100 x2 −x1 + 50 + x2

北航最优化方法最新最全答案2015版详解

数学规划基础
部分习题参考解答
刘红英编
北京航空航天大学数学与系统科学学院 2015 年 5 月
内容简介
本书是《数学规划基础》(刘红英，夏勇，周水生，北京航空航天大学出版社，2012.10)的配套教学辅导材料，较详细地给出了该教材各章后部分习题的参考解答.
前言
本习题解答自 2008 年春季开始编写，当时由硕士研究生阎凤玉提供部分习题解答，经讨论和确认后，由作者首次录入排版. 后来陆续参加习题解答修订的硕士研究生包括王浩、欧林鑫、朱丽媛、易彩霞和杨茜，其中的数值结果由欧林鑫提供. 作者在此向他们的辛勤劳动表示衷心的感谢.
本解答得到了？项目的资助，在此表示感谢. 由于这些参考解答尚未经过特别严格的校对，仅供参考. 任何意见、建议或其它反馈都可以发送至liuhongying@，在此深表感谢.
刘红英 2015.5 于北京
目录
第一章引言
1
第二章线性规划: 基本理论与方法
3
第三章线性规划：应用及扩展
maximize 200x + 60y + 206z
subject to 3x + y + 5z ≤ 8000000
5x + y + 3z ≤ 5000000
x, y, z ≥ 0, 且 x, y, z 是整数.
忽略掉整性要求后，调用 Matlab 中的 linprog.m 函数求解，得最优解 x = 0, y = 500000, z = 1500000，自动满足整性要求.
(x)(∇ri
(x))T
2A(x)T A(x).
1.6 考虑向量值函数 f (x) : Rn → Rm ，设 f 的每个分量函数 fi(x) 在 x′ 都可微. 写出 f 在 x′ 的Taylor展式，请用 A(x)T 表示 ∇f (x)T (= [∇f1(x), · · · , ∇fm(x)]).

最优化方法信赖域方法

最优化方法信赖域方法Trusted Domain Method of Optimization Methods一、概述信赖域（Trusted Domain）法是一种针对多目标最优化问题的优化方法，属于启发式优化技术，又被称为受信域法（Credible Domain）法或者受信域增强法（Credible Domain Enhancement）。

它由A.K.Chentsov在1980年提出，目前已经在工业优化、控制优化、混合模糊优化等领域有广泛的应用。

信赖域法使多目标最优化问题中的搜索变得更加有效和快捷，可以很好地处理多目标最优化问题中的非凸性和高维问题，使最优解更容易被获取。

二、原理信赖域方法优化的原理是：在解空间中划分子空间，在每个子空间中进行最优优化，同时进行领域大小的优化，以找到最优解。

（1）划分的子空间划分的子空间由一组不可分割的解空间，即称为“信赖域（Trusted Domain）”确定，有一种收敛性的在同一信赖域上的解空间集合，该信赖域中必须包含一个或多个最优解点。

（2）之分的子空间有效性在信赖域中，有一种收敛性的解空间，该解空间必须包含一个或多个最优解点，且此处解的收敛性可以满足要求。

由此可以看出，划分的子空间有效的充分利用解空间，能够使对最优解的搜索效率更高，更快地找到最优解。

（3）领域大小的优化在划分解空间时，信赖域方法重点考虑领域大小的优化，以缩小搜索空间大小，并引导搜索过程朝最优解的方向发展。

三、应用1.工业优化信赖域方法已经在工业优化领域得到应用，使多目标工业优化问题中的搜索更加有效和快捷，可以很好地处理多目标最优化问题中的非凸性和高维问题，使最优解更容易被获取。

2.控制优化由于信赖域方法能够有效地处理多目标非凸性和高维问题，因此已经在控制优化中得到应用，用于设计准确性好的控制系统。

3.混合模糊优化信赖域方法在混合模糊优化领域也有应用，可以用来解决特殊类型的模糊控制优化问题，来有效地提高优化中的效率和准确性。

最优化方法练习题答案

练习题一1、建立优化模型应考虑哪些要素? 答：决策变量、目标函数和约束条件。

2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。

答：针对一般优化模型()()min ()..0,1,2, 0,1,,i j f x s t g x i m h x j p≥===，讨论解的可行域D ，若存在一点*X D ∈，对于X D ∀∈ 均有*()()f X f X ≤则称*X 为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代所得到的序列(1)(2)(),,,K X X X ，满足(1)()()()K K f X f X +≤，则迭代法收敛；收敛的停止准则有(1)()k k x x ε+-<，(1)()()k k k x x x ε+-<，()()(1)()k k f x f x ε+-<，()()()(1)()()k k k f x f x f x ε+-<，()()k f x ε∇<等等。

练习题二1、某公司看中了例2.1中厂家所拥有的3种资源R 1、R2、和R 3，欲出价收购（可能用于生产附加值更高的产品）。

如果你是该公司的决策者，对这3种资源的收购报价是多少？（该问题称为例2.1的对偶问题）。

解：确定决策变量对3种资源报价123,,y y y 作为本问题的决策变量。

确定目标函数问题的目标很清楚——“收购价最小”。

确定约束条件资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。

因此有如下线性规划问题：123min 170100150w y y y =++1231231235210..23518,,0y y y s t y y y y y y ++≥⎧⎪++≥⎨⎪≥⎩ *2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。

答：略。

3、用单纯形法求解下列线性规划问题：（1）⎪⎪⎩⎪⎪⎨⎧≥≤+-≤++≤-++-=0,,43222..min32131321321321x x x x x x x x x x x t s x x x z ；（2）⎪⎪⎩⎪⎪⎨⎧=≥=++=+-=+-+-=)5,,2,1(052222..4min 53243232132 i x x x x x x x x x x t s x x z i解：（1）引入松弛变量x 4，x 5，x 6123456min 0*0*0*z x x x x x x =-++++12341232 =22 5 =3..13 6=41,2,3,4,5,60x x x x x x x x s t x x x x x x x x x +-+⎧⎪+++⎪⎨-++⎪⎪≥⎩因检验数σ2<0，故确定x 2为换入非基变量，以x 2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x 4作为换出的基变量。

最优化计算方法课后习题答案----高等教育出社。施光燕

习题二包括题目： 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)11/8007/400()7/4001/200G x --⎛⎫= ⎪--⎝⎭∴ (1)(1)11141/100()574/100d G x g -⎛⎫=-=⎪-⎝⎭15（1）解如下15. 用DFP 方法求下列问题的极小点（1）22121212min 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 γ-⎛⎫=∇-∇= ⎪-⎝⎭0110111011101T T T TH H H H H γγδδδγγγ=+- 其中，111011126.3096,247.3380T T TH δγγγγγ===111.1621 1.39451.3945 1.6734Tδδ⎛⎫= ⎪⎝⎭ ， 01101174.3734113.4194113.4194172.9646T TH H γγγγ⎛⎫== ⎪⎝⎭所以10.74350.40560.40560.3643H -⎛⎫= ⎪-⎝⎭(1)(1)1 1.4901()0.9776dH f x -⎛⎫=-∇= ⎪⎝⎭令 (2)(1)(1)1xx d α=+ ，利用 (1)(1)()0df x d d αα+=，求得 10.5727α=-所以 (2)(1)(1)0.77540.57270.8535xx d⎛⎫=-= ⎪-⎝⎭ ， (2)0.2833()0.244f x ⎛⎫∇= ⎪-⎝⎭以下作第三次迭代(2)(1)20.85340.5599x x δ⎛⎫=-= ⎪-⎝⎭ ， (2)(1)2 1.0927()()0.9076f x f x γ-⎛⎫=∇-∇= ⎪⎝⎭22 1.4407T δγ=- ， 212 1.9922T H γγ=220.72830.47780.47780.3135T δδ-⎛⎫=⎪-⎝⎭1221 1.39360.91350.91350.5988T H H γγ-⎛⎫= ⎪-⎝⎭所以22122121222120.46150.38460.38460.1539T T T TH H H H H δδγγδγγγ-⎛⎫=+-= ⎪-⎝⎭(2)(2)20.2246()0.1465d H f x ⎛⎫=-∇= ⎪-⎝⎭令 (3)(2)(2)2xxdα=+ ，利用(2)(2)()0df x d d αα+=，求得 21α=所以 (3)(2)(2)11x x d ⎛⎫=+=⎪-⎝⎭，因为 (3)()0f x ∇=，于是停止 (3)(1,1)T x =-即为最优解。

北航最优化方法作业答案co_lcp

第 8 章约束优化：线性约束规划
数学规划基础
LHY-SMSS-BUAA
线性等式约束规划
f (x) 是 n 元函数；ai 是 n 维常向量； bi 是常数有解时凸规划 ⊙ f(x) 是凸函数 KKT点即为全局极小点 f(x) 严格凸：有唯一的极小点 ⊙ f(x) 是非凸函数可能存在不是全局解的局部解找全局解是NP-难问题引入矩阵，使得且非奇异解的情况：无可行解、无界、有解
约束优化：线性约束规划
Constrained Optimization: Linearly Constrained Programming
第 8 章约束优化：线性约束规划
数学规划基础
LHY-SMSS-BUAA
二次规划(quadratic programming)
G 是 n 阶对称方阵 d，ai 是 n 维常向量解的情况：无可行解、无界、有解有解时： ⊙ G半正定 KKT点即为全局极小点凸规划 G 正定：有唯一的极小点 ⊙ G不定可能存在不是全局解的局部解找全局解是NP-难问题
第 8 章约束优化：线性约束规划
数学规划基础
LHY-SMSS-BUAA
等式约束二次规划－广义消元法(续)
第 8 章约束优化：线性约束规划
数学规划基础
LHY-SMSS-BUAA
第 8 章约束优化：线性约束规划
数学规划基础
LHY-SMSS-BUAA
实用二次规划算法概述
⊙ 经典的积极集法(active-set methods)
有价证券的组合优化(续)
Markowitz引入风险容许参数(risk tolerance parameter)
找出“最优的”证券投资组合！ ⊙ 参数，设定值依赖于投资者的个人偏好

最优化方法试卷及答案5套.docx

《最优化方法》1一、填空题:1. _______________________________________________________ 最优化问题的数学模型一般为：_____________________________________________ ,其中___________ 称为目标函数，___________ 称为约束函数，可行域D可以表示为_______________________________ ，若 ________________________________ ，称/为问题的局部最优解，若为问题的全局最优解。

2.设f(x)= 2斤+2“2-兀|+5花，则其梯度为__________ ^x = (l,2)r?6/ = (l,0)r,则f(x)在壬处沿方向d的一阶方向导数为___________ ，几何意义为_____________________________________ ，二阶方向导数为____________________ ,几何意义为_____________________________3.设严格凸二次规划形式为：min /(%) = 2兀］2 + 2x； - 2兀］-x2s.t. 2%! 4- x2 < 1> 0x2 > 0则其对偶规划为_______________________________________________min%（d ） = f （x k +ad k ）的最优步长为务=—叫）F.d kT Gd k2. （10分）证明凸规划min/（x ）,x G D （其中子（兀）为严格凸函数，D 是凸集）的最优解是唯一的3. （13分）考虑不等式约束问题min /（x ）s.t. c i （x ） < 0, Z G / = {1,2,…，加}其中/（x ）,6 （兀）a e /）具有连续的偏导数，设X 是约束问题的可行点，若在元处 d 满足巧（计<0,VC,（元）（可则d 是元处的可行下降方向。

最优化方法习题答案

习题一1.1利用图解法求下列线性规划问题：（1）21x x z max +=⎪⎪⎩⎪⎪⎨⎧≥≤+≥+0x ,x 5x 2x 2x x 3.t .s 212121 解：根据条件，可行域为下面图形中的阴影部分，，有图形可知，原问题在A 点取得最优值，最优值z=5（2）21x 6x z min -=⎪⎪⎩⎪⎪⎨⎧≥≤+-≤+0x ,x 7x x 1x x 2.t .s 212121 解：图中阴影部分表示可行域，由图可知原问题在点A 处取得最优值，最优值z=-6.（3）21x 2x 3z max +=⎪⎪⎩⎪⎪⎨⎧≥-≥-≤+-0x ,x 4x 2x 1x x .t .s 212121 解：如图所示，可行域为图中阴影部分，易得原线性规划问题为无界解。

（4）21x 5x 2z min -=⎪⎪⎩⎪⎪⎨⎧≥≤+≥+0x ,x 2x x 6x 2x .t .s 212121 解：由图可知该线性规划可行域为空，则原问题无可行解。

1.2 对下列线性规划问题，找出所有的基解，基可行解，并求出最优解和最优值。

（1）4321x 6x 3x 2x 5z min -+-=⎪⎪⎩⎪⎪⎨⎧≥=+++=+++0x ,x ,x ,x 3x 2x x x 27x 4x 3x 2x .t .s 432143214321 解：易知1x 的系数列向量⎪⎪⎭⎫ ⎝⎛=21p 1，2x 的系数列向量⎪⎪⎭⎫ ⎝⎛=12p 2，3x 的系数列向量⎪⎪⎭⎫⎝⎛=13p 3，4x 的系数列向量⎪⎪⎭⎫⎝⎛=24p 4。

①因为21p ,p 线性无关，故有⎪⎩⎪⎨⎧--=+--=+43214321x 2x 3x x 2x 4x 37x 2x ，令非基变量为0x x 43==，得⎪⎪⎩⎪⎪⎨⎧=-=311x 31x 21，所以得到一个基解)0,0,311,31(x )1(-=是非基可行解； ②因为31p ,p 线性无关，可得基解)0,511,0,52(x)2(=，543z 2=；③因为41p ,p 线性无关，可得基解611,0,0,31(x )3(-=，是非基可行解；④因为32p ,p 线性无关，可得基解)0,1,2,0(x )4(=，1z 4-=；⑤因为42p ,p 线性相关，42x ,x 不能构成基变量； ⑥因为43p ,p 线性无关，可得基解)1,1,0,0(x )6(=，3z 6-=；所以)6()4()2(x ,x ,x是原问题的基可行解，)6(x 是最优解，最优值是3z -=。

最优化方法练习题答案

基
b
x1
x2
x3
x4
x5
x6
0
x4
2
1
[1]
-2
1
0
0
0
x5
3
2
1
1
0
1
0
0
x6
4
-1
0
1
0
0
1
cj-zj
1
-1
1
0
0
0
因检验数σ2<0，故确定x2为换入非基变量，以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x4作为换出的基变量。
cj→
1
-1
1
0
0
0
CB
基
b
x1
x4
x3
x4
x5
x6
输出结果：
原题无可行解。
5、用内点法和Matlab软件求解下列线性规划问题：
解：用内点法的过程自己书写，参考答案：最优解；最优值5
Matlab调用代码：
f=[2;1;1];
Aeq=[1,2,2;2,1,0];
beq=[6;5];
lb=[0;0;0];
[x,fval]= linprog(f,[],[],Aeq,beq,lb)
确定约束条件资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。
因此有如下线性规划问题：
*2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。
答：略。
3、用单纯形法求解下列线性规划问题：
（1）；（2）
解：（1）引入松弛变量x4，x5，x6
cj→
1
-1
1
0

最优化方法练习题答案修改建议版本--删减版

练习题一1、建立优化模型应考虑哪些要素? 答：决策变量、目标函数和约束条件。

2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。

答：针对一般优化模型()()min ()..0,1,2, 0,1,,i j f x s t g x i m h x j p≥===L L ，讨论解的可行域D ，若存在一点*X D ∈，对于X D ∀∈ 均有*()()f X f X ≤则称*X 为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代所得到的序列(1)(2)(),,,K X X X L L ，满足(1)()()()K K f X f X +≤，则迭代法收敛；收敛的停止准则有(1)()k k x x ε+-<，(1)()()k k k x x x ε+-<，()()(1)()k k f x f x ε+-<，()()()(1)()()k k k f x f x f x ε+-<，()()k f x ε∇<等等。

练习题二1、某公司看中了例2.1中厂家所拥有的3种资源R 1、R2、和R 3，欲出价收购（可能用于生产附加值更高的产品）。

如果你是该公司的决策者，对这3种资源的收购报价是多少？（该问题称为例2.1的对偶问题）。

解：确定决策变量对3种资源报价123,,y y y 作为本问题的决策变量。

确定目标函数问题的目标很清楚——“收购价最小”。

确定约束条件资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。

答：略。

3、用单纯形法求解下列线性规划问题：（1）⎪⎪⎩⎪⎪⎨⎧≥≤+-≤++≤-++-=0,,43222..min32131321321321x x x x x x x x x x x t s x x x z ；（2）⎪⎪⎩⎪⎪⎨⎧=≥=++=+-=+-+-=)5,,2,1(052222..4min53243232132Λi x x x x x x x x x x t s x x z i解：（1）引入松弛变量x 4，x 5，x 6123456min 0*0*0*z x x x x x x =-++++12341232 =22 5 =3..13 6=41,2,3,4,5,60x x x x x x x x s t x x x x x x x x x +-+⎧⎪+++⎪⎨-++⎪⎪≥⎩因检验数σ2<0，故确定x 2为换入非基变量，以x 2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x 4作为换出的基变量。

最优化计算方法课后习题答案解析

习题二包括题目： 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=-，由题意得∴(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)11141/100()574/100d G x g -⎛⎫=-=⎪-⎝⎭15〔1〕解如下15. 用DFP 方法求以下问题的极小点〔1〕22121212min 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 γ-⎛⎫=∇-∇= ⎪-⎝⎭其中，111011126.3096,247.3380T T TH δγγγγγ===11 1.1621 1.39451.3945 1.6734T δδ⎛⎫= ⎪⎝⎭ ， 01101174.3734113.4194113.4194172.9646T TH H γγγγ⎛⎫== ⎪⎝⎭所以令 (2)(1)(1)1xx d α=+ ，利用 (1)(1)()0df x d d αα+=，求得 10.5727α=-所以 (2)(1)(1)0.77540.57270.8535x x d ⎛⎫=-= ⎪-⎝⎭ ， (2)0.2833()0.244f x ⎛⎫∇= ⎪-⎝⎭以下作第三次迭代(2)(1)20.85340.5599x x δ⎛⎫=-= ⎪-⎝⎭ ， (2)(1)2 1.0927()()0.9076f x f x γ-⎛⎫=∇-∇= ⎪⎝⎭22 1.4407T δγ=- ， 212 1.9922T H γγ=所以令 (3)(2)(2)2xxdα=+ ，利用(2)(2)()0df x d d αα+=，求得 21α= 所以 (3)(2)(2)11x x d ⎛⎫=+=⎪-⎝⎭，因为 (3)()0f x ∇=，于是停顿 (3)(1,1)T x =-即为最优解。

北航最优化方法作业答案co_theory

原始问题
min-max问题是研究对偶问题的基础！各种对偶的区别：的定义方式不同！原始问题(primal problem)
◎ 前提: 两人采取理性行为不管对方采取何种策略，该行为都能保证自己的最大获益该行为都能保证自己的最大获益－不管对方采取何种策略 Peter: 选最多要支付 Harriet：选最少收到需要解决的问题： max-min问题←→对偶问题
第 7 章约束优化：理论数学规划基础 LHY‐SMSS‐BUAA 第 7 章约束优化：理论数学规划基础 LHY‐SMSS‐BUAA
4
线性规划的对偶理论
线性规划的对偶理论：原始问题←→对偶问题 • 原始问题－minimize，对偶问题－maximize • 原始问题最优解所对应的单纯形乘子是对偶问题的解 • 弱对偶性 • 强对偶性(之一有解，则另一个必有解，且最优值相等)
其中是凸函数. 定理. 凸规划的任一KKT点是全局极小点. 注1. 凸规划的所有局部解也是全局解. 注2. 线性规划是凸规划；二次规划中目标函数的Hessian阵半正定时，也是凸规划.
第 7 章约束优化：理论数学规划基础 LHY‐SMSS‐BUAA
则 . 从而 Lagrange乘子的解释：最优值关于约束的灵敏度，即约束函数变化时，对应的最优值的变化率！
原始问题(primal problem) 例1.
Lagrange对偶－例
其中的其它约束. 对任意的
, 是凸函数，X是凸集，是希望分别处理，定义对偶函数定义对偶函数(dual (d l function) f ti )
对偶函数
对偶问题：对偶问题(dual problem)：
注：如果要求 ci(x) = 0，则对偶问题中与之对应的变量没有符号限制.

最优化计算方法课后习题集答案解析

（1）
解：取，时，DFP法的第一步与最速下降法相同
，，
，
以下作第二次迭代
，
其中，
，
所以
令，利用，求得
所以，
以下作第三次迭代
，
，
所以
令，利用，求得
所以，因为，于是停止
即为最优解。
习题四
包括题目： P95页 3；4；8；9(1)；12选做；13选做
3题解如下
3.考虑问题，其中
X1,x2,x3≥0 （3）
求出点（1,1,0）处的一个下降可行方向.
解：首先检查在点（1,1,0）处哪些约束为有效约束。检查易知（1），X3≥0为有效约束。设所求可行方向d=(d1,d2,d3)T。根据可行方向d的定义，应存在a>0，使对∀t∈（0，a）能有
X+td=(1+td1,1+td2,0+td3)T
（1）
s.t.
（2）
s.t.
（1）解：非线性规划的K-T条件如下：
（1）
（2）
（3）
再加上约束条件（4）
为求出满足（1）~（4）式的解，分情况考虑：
①若（4）式等号不成立，即，那么由（2）式得，将代入（1）式解得，，所得值不满足的条件，故舍去。
②若（4）式等号成立，由（1）式可以解得，，代入（4）式有：
JBi
1
2
3
4
5
6
7
8
9
di0
1
1
0
-5/6
-1/6
1
10/6
4
0
0
38/6
2
0
1
-9/6

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

－保证方法具有大范围收敛性
理想特性: 在 x(k) 靠近局部解之前线搜索法用步长来限制探搜索方向 p(k) 使 f(x) 获取充分下降; 而在 x(k)接近局部解时, 该限制无效, 即步长为 1，迭代恢复为快速收敛的基本牛顿法. 理想特性: 在 x(k) 靠近局部解之前信赖域法用信赖域约束来限制探测步 s(k) 使 f(x) 获取充分下降; 而在 x(k)接近局部解时, 该限制无效, 从而迭代恢复为快速收敛的基本(即步长为 1)牛顿法.
基本信赖域法的收敛性
第 6 章无约束优化：信赖域法数学规划基础 LHY-SMSS-BUAA
Steihaug-Conjugate Gradient Method
min = q (s) :
s ≤∆ 1 2
s Bs + g s
T T
q(s)
第 6 章无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
第 6 章无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
近似求解信赖域子问题：dog-leg法
min q ( k ) ( s ) = :
s ≤∆ k 1 2
s T G ( k ) s + g ( k )T s + f ( k )
⊙ 近似方法：找 s(k) 使得 q(k) q(k) ⊙ dog-leg法(折线法)，适合 G(k) 正定的问题当 ∆ k 较小时, 柯西点较恰当 − g ( k ) 当 ∆ k 较大时, 牛顿步较恰当
第 6 章无约束优化：信赖域法数学规划基础 LHY-SMSS-BUAA
原型算法的收敛性
信赖域型牛顿法！定理6.1.1 若算法6.1.1产生的序列 {x(k)}有界，且 f(x) 二次连续可微. 则序列 {x(k)} 必有聚点 x*满足一阶和二阶最优性条件，即 g*= 0 且 G* 半正定. 定理6.1.2 若定理6.1.1中的聚点 x*还满足二阶充分条件，即 g*= 0 且G*正定，则 (b) 对充分大的k，信赖域约束收敛速度是二次的.
无约束优化：信赖域法
Trust Region Methods for Unconstrained Optimization
第 6 章无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
信赖域法的动机
Taylor展式：信赖域(trust region)：使得Taylor展式(模型)有效的区域其中是信赖域半径. 信赖域子问题：设信赖域子问题的解为 s(k)，根据 f(k)- f (x(k) + s(k)) 和的吻合程度调整半径真实下降量：预计下降量：定义
使得
正定，则
注2：当 B(k) = G(k)时，可以将牛顿型信赖域法理解成一种特殊的修正牛顿法！
第 6 章无约束优化：信赖域法数学规划基础 LHY-SMSS-BUAA
精确求解信赖域子问题
2 范数信赖域子问题
除G(k)正定且牛顿步满足信赖域约束条件(此时牛顿步为解)外，解均在信赖域边界取得，此种情况需要利用牛顿法解关于标量的方程，从而一次迭代需要做3-4个 Cholysky分解. －－6.2.2小节－－算法6.2.1
x ( k ) + sΝ
LM trajectory
s N = −(G ( k ) ) −1 g ( k )
ˆC x (k ) + s
x ( k ) ( s = 0)
第 6 章无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
近似求解信赖域子问题: 共轭梯度法
= min q (s) :
s ≤∆ 1 2
第 6 章无约束优化：信赖域法数学规划基础
是非积极的，且
LHY-SMSS-BUAA
2范数信赖域子问题解的刻画
考虑其中
注1：这里为了表述简洁和具有一般性，将二阶Taylor展式中的 Hessian阵替换成了B(k)，并去掉了子问题中的迭代指标.
(1)
定理6.2.1 s*是问题(1)的全局解当且仅当存在和成立，且半正定；另外，如果 s*是问题(1)的唯一解.
第 6 章无约束优化：信赖域法
来度量
逼近
数学规划基础
的程度
LHY-SMSS-BUAA
一个原型算法
解的刻画/精确算法 Cauchy点/近似算法收敛性(了解即可)
第 6 章无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
一个信赖域原型算法
模型函数是二阶Taylor展式精确求解子问题特定的信赖域半径更新方式
(a) p ( i )T Bp ( i ) ≤ 0
其中 τ 是二次方程
(b)
x ( i ) + α i p( i )
(i ) 2 2
s' 终止算法，返回信赖域边界上的点=
x
(i )
x ( i ) + τ p( i )
= ∆ 2 的某个根
2
≥∆
+α p
(k ) (k ) (k ) q ( s ) ≤ q ( s s' ≤ ∆ k ' 重要事实： C ), T (k ) ( k )T (k ) q ( k ) ( s) = : 1 s G s + g s + f 2
s ≤∆ k
1 2
s T B ( k ) s + g ( k )T s + f ( k )
第 6 章无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
实用信赖域法－细节
参数的典型值
实用算法的参数选取更精细：如给信赖域的半径设定上界！
定理 (基本信赖域法的收敛性)
第 6 章无约束优化：信赖域法
s ≤∆ 1 2
s B s+ g s
定理假设应用初始点 x(0) = 0 的共轭梯度法来极小化二次函数 q(s)，且对所有0 ≤ i ≤ k, 有 p(i)TB p(i) > 0，则下列不等式成立 x ( j ) < x ( j +1) , j =0, 1, , k − 1
2 2
引入两种新的终止情况：
⊙ 实践中，我们希望(并且能够)比这做得更好
第 6 章无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
近似标准－Cauchy点的图示
⊙ Cauchy点：柯西点! q(k)(
trust region contours of q ( k )
(k ) sC
- g (k )
第 6 章无约束优化：信赖域法数学规划基础 LHY-SMSS-BUAA
第 6 章无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
Cauchy点与近似方法
第 6 章无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
近似标准－Cauchy点
要求近似解满足：模型在近似解处所获取的预测减少量不比按最速下降迭代所获取的少！ ⊙ Cauchy点：在线段上极小化二次函数－－非常容易！柯西点! q(k)( ⊙ 要求所选的步s(k)满足 q(k)( q(k)( 算法即是全局收敛的！
sT Bs + gT s
问题： (i) B 不定时，可能有
( i )T (i )
p Bp = 0 p ( i )T Bp ( i ) < 0
(ii) 违反信赖域约束
第 6 章无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
近似求解信赖域子问题:共轭梯度法 ( 续 ) T T
min = q( s) :
第 6 章无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
例
选取
子
，则
信赖域子问题为求得牛顿步有
第 6 章无约束优化：信赖域法
所以解必在边界上!
数学规划基础 LHY-SMSS-BUAA
例
子(续)
Lagrange乘子法：
因为因为
，所以且所以
第 6 章无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
线搜索法与信赖域法
trust region
line search directiቤተ መጻሕፍቲ ባይዱn
contours of q ( k )
trust region step
contours of f
第 6 章无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
线搜索法与信赖域法的作用
模型预测减少量的下界及全局收敛性
定理 (模型在柯西点处所获取的减少量). q(k)(s) q(k) 推论 q(k)(s) q(k)
第 6 章无约束优化：信赖域法数学规划基础 LHY-SMSS-BUAA
近似求解信赖域子问题
⊙ 近似方法：找 s(k) 使得 q(k) q(k)
◇ dog-leg法(折线法)－解方程 ◇ 二维子空间极小化法估计最小特征值＋求解三次代数方程 ◇ Steihaug-共轭梯度法
数学规划基础
LHY-SMSS-BUAA
实用信赖域法
需要解决的问题一般性的参数设置需要构造模型函数(二阶泰勒展式、一般的二次函数等、插值法) 子问题：近似算法可由各种拟牛顿更新公式构造！近似标准是什么？－Cauchy 点
第 6 章无约束优化：信赖域法
数学规划基础
LHY-SMSS-BUAA
实用信赖域法－描述
min q ( k ) ( s ) = :

北航最优化方法作业答案uco_trustregion

合集下载

北航最优化方法大作业参考

北航最优化大作业

北航最优化方法最新最全答案2015版

北航最优化大作业

北航最优化方法最新最全答案2015版详解

最优化方法信赖域方法

最优化方法练习题答案

最优化计算方法课后习题答案----高等教育出社。施光燕

北航最优化方法作业答案co_lcp

最优化方法试卷及答案5套.docx

最优化方法习题答案

最优化方法练习题答案

最优化方法练习题答案修改建议版本--删减版

最优化计算方法课后习题答案解析

北航最优化方法作业答案co_theory

最优化计算方法课后习题集答案解析

文档推荐

最新文档