13-14(1)最优化方法期末试卷

作用：①仿真的过程也是实验的过程，而且还是系统地收集和积累信息的过程。

尤其是对一些复杂的随机问题，应用仿真技术是提供所需信息的唯一令人满意的方法。

②仿真技术有可能对一些难以建立物理模型或数学模型的对象系统，通过仿真模型来顺利地解决预测、分析和评价等系统问题。

③通过系统仿真，可以把一个复杂的系统化降阶成若干子系统以便于分析，并能指出各子系统之间的各种逻辑关系。

④通过系统仿真，还能启发新的策略或新思想的产生，或能暴露出在系统中隐藏着的实质性问题。

同时，当有新的要素增加到系统中时，仿真可以预先指出系统状态中可能会出现的瓶颈现象或其它的问题。

2.简述两个Wardrop 均衡原理及其适用范围。

答：Wardrop提出的第一原理定义是：在道路的利用者都确切知道网络的交通状态并试图选择最短径路时，网络将会达到平衡状态。

在考虑拥挤对行驶时间影响的网络中，当网络达到平衡状态时，每个 OD对的各条被使用的径路具有相等而且最小的行驶时间；没有被使用的径路的行驶时间大于或等于最小行驶时间。

Wardrop提出的第二原理是：系统平衡条件下，拥挤的路网上交通流应该按照平均或总的出行成本最小为依据来分配。

第一原理对应的行为原则是网络出行者各自寻求最小的个人出行成本，而第二原理对应的行为原则是网络的总出行成本最小。

3.系统协调的特点。

答：（1）各子系统之间既涉及合作行为，又涉及到竞争行为。

（2）各子系统之间相互作用构成一个反馈控制系统，通过信息作为“中介”而构成整体（3）整体系统往往具有多个决策人，构成竞争决策模式。

（4）系统可能存在第三方介入进行协调的可能。

6．对已经建立了概念模型的系统处理方式及其特点、适用范围。

答：对系统概念模型有三种解决方式。

1.建立解析模型方式对简单系统问题，如物流系统库存、城市公交离线调度方案的确定、交通量不大的城市交叉口交通控制等问题，可以运用专业知识建立系统的量化模型（如解析数学模型），然后采用优化方法确定系统解决方案，以满足决策者决策的需要，有关该方面的内容见第四、五章。

最优化理论试题及答案一、单项选择题（每题2分，共20分）1. 最优化问题中，目标函数的极值点可能是（）。

A. 最小值点B. 最大值点C. 鞍点D. 所有选项答案：D2. 线性规划问题中，目标函数和约束条件都是线性的，以下说法错误的是（）。

A. 线性规划问题有最优解B. 线性规划问题的最优解可能在可行域的边界上C. 线性规划问题的最优解一定在可行域的边界上D. 线性规划问题的最优解可能在可行域的内部答案：D3. 以下哪个算法不是用于解决非线性规划问题的（）。

A. 梯度下降法B. 牛顿法C. 单纯形法D. 共轭梯度法答案：C4. 在约束优化问题中，拉格朗日乘数法用于（）。

A. 求解无约束问题B. 求解有约束问题C. 求解线性规划问题D. 求解整数规划问题答案：B5. 以下哪个条件不是KKT条件的一部分（）。

A. 梯度为零B. 可行方向C. 对偶可行性D. 互补松弛性答案：B二、填空题（每题2分，共10分）1. 一个最优化问题的可行域是指满足所有_________的解的集合。

答案：约束条件2. 目标函数在点x*处取得极小值，当且仅当在该点处的_________为零。

答案：梯度3. 线性规划问题的标准形式通常包括_________和_________两部分。

答案：目标函数；约束条件4. 拉格朗日乘数法中，拉格朗日函数是原目标函数和_________的和。

答案：约束条件的线性组合5. 非线性规划问题中，牛顿法的迭代公式是x_{k+1} = x_{k} -H(x_{k})^{-1}_________。

答案：∇f(x_{k})三、简答题（每题5分，共20分）1. 简述什么是凸优化问题，并给出一个例子。

答案：凸优化问题是一类特殊的最优化问题，其中目标函数是凸函数，可行域是凸集。

例如，二次规划问题就是凸优化问题的一个例子。

2. 解释什么是局部最优解和全局最优解。

答案：局部最优解是指在目标函数的邻域内比所有其他点都更优的解，但不一定在整个可行域内最优。

最优化理论考试试题一、选择题1. 最优化理论的基本概念是指：A. 在给定条件下寻找函数的最小值或最大值B. 通过不断迭代来逼近函数的极值点C. 利用数值方法求解函数的最优解D. 以上都是2. 关于最优化问题中的约束条件，以下说法正确的是：A. 约束条件可以是等式约束B. 约束条件可以是不等式约束C. 约束条件可以是混合约束D. 以上都是3. 最优化问题分为无约束和约束两种情况，下列哪一种情况不属于最优化问题？A. 无约束最优化问题B. 约束最优化问题C. 反馈最优化问题D. 离散最优化问题4. 最优化理论中常用的优化方法包括：A. 梯度下降法B. 牛顿法C. 共轭梯度法D. 以上都是5. Golden Section Search方法主要用于：A. 精确搜索极值点B. 近似搜索极值点C. 寻找函数的全局最小值D. 寻找函数的局部最小值二、填空题1. 在最优化理论中，目标函数一般被记为_______。

2. 梯度下降法中的步长大小通常由_______确定。

3. 在多元函数优化中，Hessian矩阵是由二阶_______组成的。

4. 拉格朗日乘子法用于处理含有_______的约束最优化问题。

5. 共轭梯度法是解决_______问题的一种有效方法。

三、简答题1. 请简要介绍最优化理论的基本思想和应用领域。

2. 分别说明无约束最优化问题和约束最优化问题的关键特点。

3. 请解释梯度下降法和牛顿法的基本原理，并比较它们之间的异同。

4. 举例说明拉格朗日乘子法在实际问题中的应用。

5. 请解释共轭梯度法的基本原理，并说明其在优化问题中的优势和适用情况。

以上是最优化理论考试的试题内容，希望同学们认真复习，做好准备，祝大家取得优异的成绩！。

2013-2014学年第一学期数学计算经数专业《最优化方法》（课程）期末试卷试卷来源：自拟 送卷人:赵俊英 打印：赵俊英 乔凤云 校对：赵俊英一．填空题（20分）1．最优化问题的数学模型一般为：____________________________， 可行域D 可以表为_____________________________， 若____________________，称*x 为问题的全局最优解.2.()()⎪⎪⎭⎫ ⎝⎛+⎪⎪⎭⎫⎝⎛⎪⎪⎭⎫ ⎝⎛=212121312112)(x x x x x x x f ，则=∇)(x f ，=∇)(2x f .3.设f 连续可微且0)(≠∇x f ，若向量d 满足 ，则它是f 在x 处的一个下降方向.4. 无约束最优化问题：min (),n f x x R ∈，若kx 是不满足最优性条件的第k 步迭代点，用共轭梯度法求解时，搜索方向kd =______________5. 函数R R D f n →⊆:在点k x 沿着迭代方向}0{\n k R d ∈进行精确一维线搜索的步长k α，则其搜索公式为 .6 .举出一个具有二次终止性的无约束二次规划算法： .7.函数2222112313()226f x x x x x x x x =+++- （填是或不是） 严格凸函数.二．（18分）简答题：1. 设计求解无约束优化问题的一个下降算法，并叙述其优缺点.2. 叙述单折线法的算法思想.3. 写出以下线性规化问题的对偶：1234123412341234134min ()2536..873411,762323,324712,0,0,0.f x x x x x s t x x x x x x x x x x x x x x x =-+-⎧⎪-+++=⎪⎪+++≥⎨⎪+++≤⎪≤≥≥⎪⎩三、计算题（52分）1. 解线性规划问题1212121212min ()85..0,61166,210,0,0.f x x x s t x x x x x x x x =+⎧⎪-+≥⎪⎪+≥⎨⎪+≥⎪≥≥⎪⎩.2.用牛顿法求解无约束优化问题22121212min ()24f x x x x x x x =+-+-,取初始点022x ⎛⎫= ⎪⎝⎭.3．用0.618法求解2min ()1f x x x =--,初始区间为00[,][1,1]a b =-（迭代两步）.4. 用FR 共轭梯度法求解无约束优化问题221212min ()21f x x x x x =++-+取初始点0(0,0)T x =，0.05ε=（迭代两步）.5.用有效集法求解下面的二次规划问题, 初始点0(3,0)T x =：2212121212min ()6413..30,0.f x x x x x s t x x x x =+---+≤≥≥四． 证明题(10分).1.证明向量11=0α⎛⎫ ⎪⎝⎭和23=2α⎛⎫⎪⎝⎭－关于矩阵2335A ⎛⎫= ⎪⎝⎭共轭.2．证明凸规划min (),f x x D ∈（其中()f x 为严格凸函数，D 是凸集） 的局部最优解必为全局最优解.。

《最优化方法》（研究生）期末考试练习题答案二.简答题1．;0, ,843 ,2 2-,3 34 s.t. ,95- min 2121212121≤=--≥+≥++y y y y y y y y y y 2．,065 6143≥+x x （以1x 为源行生成的割平面方程） 注意：在1x 为整数的情况下，因为3x ,04≥x ，该方程自然满足，这是割平面的退化情形,2141 41 43≥+x x （以2x 为源行生成的割平面方程）3．6648.31854.1*2)854.1()(2131.01146.1*2)146.1()(854.13*618.00)(618.0146.13*382.00)(382.03,031311111111111=+-==+-==+=-+==+=-+===μϕλϕμλa b a a b a b a 0.927.21.8540]1.8540[854.1,0)()(,*2211=+===≤x b a 近似的最优解：。

，初始的保留区间为即：。

所以，不经计算也可以看出事实上μϕλϕ4．令1.01.0)(4.04.0)(11)(7.27.2)(222222221)2(*111)1(*111)0(*121)1(*11-=-=-=-=-=-=-=-=-------x x x x x x x e x e x x f ex ex x f x e x x f e x e x x f拟合问题等价于求解下列最小二乘问题：∑=412))((mini ix f三.计算题1．分别用最速下降方法和修正的牛顿法求解无约束问题 22214)(min x x x f +=。

取初始点()()Tx 2,21=，.1.0=ε()().1641642,2821121⎪⎪⎭⎫⎝⎛--=⎪⎪⎭⎫⎝⎛=∇=⎪⎪⎭⎫⎝⎛=∇d f x x x f T方向为：从而最速下降法的搜索，在初始点，解：()()()()直至满足精度。

继续迭代方向为：从而最速下降法的搜索，，在从而求解得到：其中满足最优步长,.48/6565/19248/65-65/19265/6,65/96)65/6,65/96((-4,-16)*130/172,2 130,/17.)162(4)42()162,42()()(min )(122221)1(1)1(1*)1(*⎪⎪⎭⎫⎝⎛-=⎪⎪⎭⎫ ⎝⎛=∇-=-=+==-+-=--=++=+d f x x f d x f d x f d x f TTT Tλλλλλλλλλλ()()2-2- 1648/1002/1 8/1002/1,8002 2,21111⎪⎪⎭⎫⎝⎛=⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛-=∇-=⎪⎪⎭⎫ ⎝⎛=⎪⎪⎭⎫ ⎝⎛==--f G d G G x T索方向为：从而修正的牛顿法的搜，在初始点()()()()即为所求的极小点。

最优化方法考试试题一、选择题（每题2分，共20分）1、下列哪个选项不是最优化方法的常见应用场景？A.生产计划优化B.金融投资组合优化C.图像处理优化D.自然语言处理优化正确答案：D.自然语言处理优化。

2、下列哪个算法不是求解线性规划问题的常用算法？A.单纯形法B.内点法C.外点法D.牛顿法正确答案：D.牛顿法。

3、下列哪个选项不是整数规划问题的特点？A.变量取值必须是整数B.问题复杂度较高，通常需要特殊算法求解C.在实际应用中比线性规划更为广泛D.可以使用与线性规划相同的方法求解正确答案：D.可以使用与线性规划相同的方法求解。

4、下列哪个选项不是梯度下降法的优点？A.简单易行，易于实现B.能较快地收敛到局部最优解C.对初值不敏感，易于找到全局最优解D.对于大规模数据处理效率较高正确答案：C.对初值不敏感，易于找到全局最优解。

5、下列哪个选项不是模拟退火算法的特点？A.基于概率的搜索方法，有一定的随机性B.在解空间内随机搜索，可以跳出局部最优解的陷阱C.可以找到全局最优解，但需要设置退火温度等参数D.对于组合优化问题通常比暴力搜索算法更快找到最优解正确答案：D.对于组合优化问题通常比暴力搜索算法更快找到最优解。

二、填空题（每空2分，共20分）6.最优化方法中，通常使用__________来衡量一个解的好坏。

正确答案：目标函数。

7.在使用单纯形法求解线性规划问题时，__________是算法终止的条件。

正确答案：迭代次数达到预设的上限。

8.整数规划问题中，如果所有变量都有上限和下限的约束，则称为__________规划问题。

正确答案：背包。

9.在使用模拟退火算法求解组合优化问题时，__________是算法终止的条件。

正确答案：达到预定的迭代次数或者解的变化小于某个给定的阈值。

10.最优化方法中，__________是一种启发式搜索方法，通常用于解决组合优化问题。

正确答案：遗传算法。

最优化问题在现实世界中随处可见，从解决日常生活中的最佳路线问题，到企业寻求最大化利润和最小化成本，最优化方法都发挥着至关重要的作用。

最优化理论与方法知识点总结最优化理论与方法知识点总结 (1)一、最优化简介： (2)1.1最优化应用举例 (2)1.2基本概念 (2)1.3向量范数 (3)1.4矩阵范数 (3)1.5极限的定义 (3)1.6方向导数存在性和计算公式 (4)1.7梯度定义 (4)1.8海塞矩阵 (5)1.9泰勒展开式： (5)1.10凸集定义 (5)1.11凸集性质 (5)1.12凸函数定义 (6)1.13凸函数判断 (6)1.14矩阵正定与半正定判断 (6)1.15例题（判断矩阵是否正定） (7)1.16凸优化 (7)二、线性规划 (7)2.1线性规划数学模型的一般形式 (7)2.2解的基本定理 (7)2.3解的分类 (8)2.4图解法 (8)2.5例题（图解法） (8)2.6标准型的化法 (9)2.7例题（化为标准型） (9)2.8单纯形法 (10)2.9例题（单纯形法） (11)三、对偶线性规划 (13)3.1对偶问题 (13)3.2单纯形法解对偶问题 (13)3.3对偶单纯形法求解线性规划问题过程 (14)四、无约束优化 (14)4.1无约束优化概述 (14)4.2搜索区间的确定 (15)4.3区间消去法原理 (16)4.4黄金分割法 (17)4.5插值方法 (17)4.6常见的终止准则 (19)4.7最速下降法 (20)4.8牛顿类方法 (20)4.9例题（牛顿类方法） (21)一、最优化简介：1.1最优化应用举例具有广泛的实用性运输问题，车辆调度，员工安排，空运控制等工程设计，结构设计等资源分配，生产计划等通信：光网络、无线网络，ad hoc等.制造业：钢铁生产，车间调度等医药生产，化工处理等电子工程，集成电路VLSI etc.排版1.2基本概念目标函数和约束函数都是线性的，称之为线性规划问题，而有的模型中含有非线性函数，称之为非线性规划。

在线性与非线性规划中，满足约束条件的点称为可行点，全体可行点组成的集合称为可行集或可行域。

《最优化方法》1一、填空题：1．最优化问题的数学模型一般为：____________________________，其中 ___________称为目标函数，___________称为约束函数，可行域D 可以表示 为_____________________________，若______________________________， 称*x 为问题的局部最优解，若_____________________________________，称*x 为问题的全局最优解。

2．设f(x)= 212121522x x x x x +-+，则其梯度为___________，海色矩阵___________,令,)0,1(,)2,1(T T d x ==则f(x)在x 处沿方向d 的一阶方向导数为___________，几何意义为___________________________________,二阶 方向导数为___________________，几何意义为_________________________ ___________________________________。

3．设严格凸二次规划形式为：012..222)(min 2121212221≥≥≤+--+=x x x x t s x x x x x f则其对偶规划为___________________________________________。

4．求解无约束最优化问题：n R x x f ∈),(min ，设k x 是不满足最优性条件的第k 步迭代点，则：用最速下降法求解时，搜索方向k d =___________ 用Newton 法求解时，搜索方向k d =___________ 用共轭梯度法求解时，搜索方向k d =___________________________________________________________________________。

最优化理论、方法及应用试题一、（30分）1、针对二次函数1()2TT f x x Qx b x c =++,其中Q 是正定矩阵，试写出最速下降算法的详细步骤，并简要说明其优缺点?答：求解目标函数的梯度为()g x Qx b =+，()k k k g g x Qx b ==+，搜索方向：从k x 出发,沿k g -作直线搜索以确定1k x +。

Step1： 选定0x ，计算00,f gStep2: 做一维搜索, ()1min k k k tf f x tg +=-,1k k k x x tg +=-.Step3：判别，若满足精度要求，则停止；否则，置k=k+1，转步2。

优缺点：最速下降法在初始点收敛快，算法简单，在最优点附近有锯齿现象,收敛速度慢。

2、有约束优化问题min ()()0,1,2,,..()0,1,2,,i j f x g x i m s th x j l≥=⎧⎪⎨==⎪⎩最优解的必要条件是什么？答:假设*x 是极小值点。

必要条件是f,g ，h 函数连续可微，而且极小值点的所有起作用约束的梯度(*)(1,2,,)i h x i l ∇=和(*)(1,2,,)j g x j m ∇=线性无关，则存在******1212,,,,,,,,l m αααβββ使得()11******1212**(*)*(*)*(*)0*(*)0,1,2,,,,,,,,,00,0lmi i j j i i j j l m i j f x h x g x g x j mαββαααβββαβ==∇-∇-∇===≠>≥∑∑3、什么是起作用约束？什么是可行方向？什么是下降方向？什么是可行下降方向？针对上述有约束优化问题，如果应用可行方向法,其可行的下降方向怎样确定？ 答：起作用约束：若0()0j g x =，这时点0x 处于该约束条件形成的可行域边界上，它对0x 的摄动起到某种限制作用。

可行方向：0x 是可行点，某方向p,若存在实数00λ>,使得它对任意[]00,λλ∈，均有0x p λ+∈可行点集合,则称方向p 是点0x 的可行方向。