15.093最优化方法 期末考试 说明： 1、本试委共5道思，每题20分，共100分. 2、贝可以参考课堂笔记、作业及答案、课本Bertsimas and Tsitsiklis. 3,考其时间为3小时， 4、解路过程要详图。 5、祝你好运！ 0
15.093 最优化方法 期末考试 说明： 1、 本试卷共 5 道题，每题 20 分，共 100 分。 2、 只可以参考课堂笔记、作业及答案、课本 Bertsimas and Tsitsiklis。 3、 考试时间为 3 小时。 4、 解题过程要详细。 5、 祝你好运！ 0
问题1(20分) 判断正误，不需要解释说明。回答正确得2分，不曰答得0分，国答储误得】分。 1,求解一个定义在可行域为多面体上的分段线性凸函数的最大值的问可以化为一个线 性规划间题。 2、函数minx sL X0 x4,8≥0 的对钙问题有非退化的最优解， 3、如果一个问题有非退亿的最优解，则其一定有唯一的最优基。 4、一个最优基本可行解是严格互补的。 5、原-对偶障碍内点法的收数性受见化性影响： 6、已知非线性最优化月题的同部最优点x。如果紧约来的梯度和等式约束的梯度在点x线 性粒立时，x裤足Kuhn-Tucke世条件， ?、在一个有多重解的线性最优化问题中，原对偶障得法总能找到最优基可行解。： 8、在整数的最小费用流问题中，所有基本可行解的分量都是整数。 9、二次函数mnf(x)=xQ:的最速下降法的收敛性与矩阵Q的条件数有关。条件数总 多收敛速度越慢， 10、最速下降法的收效性与起始点有关
问题 1（20 分） 判断正误，不需要解释说明。回答正确得 2 分，不回答得 0 分，回答错误得-1 分。 1、 求解一个定义在可行域为多面体上的分段线性凸函数的最大值的问题可以化为一个线 性规划问题。 2、 函数 min x1 s.t. x1=0 x1,x2 ≥0 的对偶问题有非退化的最优解。 3、 如果一个问题有非退化的最优解，则其一定有唯一的最优基。 4、 一个最优基本可行解是严格互补的。 5、 原-对偶障碍内点法的收敛性受退化性影响。 6、 已知非线性最优化问题的局部最优点 x ，如果紧约束的梯度和等式约束的梯度在点 x 线 性独立时， x 满足 Kuhn-Tucker 条件。 7、 在一个有多重解的线性最优化问题中，原-对偶障碍法总能找到最优基可行解。 8、 在整数的最小费用流问题中，所有基本可行解的分量都是整数。 9、 二次函数 min f ( ) x x = Qx 的最速下降法的收敛性与矩阵 Q 的条件数有关。条件数越 多收敛速度越慢。 10、 最速下降法的收敛性与起始点有关。 1
问题2(20分) 令为四函数。考虑下面的问愿： minimize f,) subject to Ax=b x20 P-{xeR|A-b,x20刚 ()正明如果存在最优解，则最优解为P的极点。 b)制如，假设增加约束x,e{0,}al方ie,问题就变为0！非线性整数最优化问 题。说明这个问题也可以转化成线性整数最优化月题。 问题3(30分) Q、三为n×n矩库，￡半正定. minimize e+2r0r subject to d'x+5x'Σx≤a 2 (a)写出Kuhn-Tucker条件， (b)在Kuhn-Tucker条件的基健上写出本置的一个算法. ()假设矩库Q也是半正定的。将本题政写为率正定优化问题
问题 2（20 分） 令 f (•)为凹函数。考虑下面的问题： 0 subject to minimize ( ) 1 ≥ = ∑= x Ax b f x n j j { | , } n P x = ∈ R Ax = b x ≥ 0 (a) 证明如果存在最优解，则最优解为 P 的极点。 (b) 例如，假设增加约束 {0 1} . . j x ∈ ， for all j，i e ，问题就变为 0-1 非线性整数最优化问 题。说明这个问题也可以转化成线性整数最优化问题。 问题 3（30 分） Q、∑为 n×n 矩阵，∑半正定。 d'x x' x a c'x x'Qx + ∑ ≤ + 2 1 subject to 2 1 minimize (a) 写出 Kuhn-Tucker 条件。 (b) 在 Kuhn-Tucker 条件的基础上写出本题的一个算法。 (c) 假设矩阵 Q 也是半正定的。将本题改写为半正定优化问题。 2
问短4(21分〕 )己知点(x),i=1K,m,其中，为R上的向量，g为0成1这里说明一下点 属于0或1的范斯。我们要讨论的是，是南可以找到一个超平而了x=1将多分离，使 得所有值为0的点满足fx≤1，值为1的点沫足了x21,设计一个线性址优化问避找 到这样的向量了。 b)己知点(，乃)，i=1,K,m,x为上的向量，另eR为相应的变量。 要找到一个超平面ax=1,使得对所有点aX≤L儿元耳x,我者ax≥1上耳x·更 严格的，对所有使αx】的点X,选得月，使 三以一瓜收行压木值：同理 对所有使得>1的点找到及，求，一风的最小值。 设引一个黎数规划可愿找到向量位，民，耳： 间思5(20分)
问题 4（20 分） (a) 已知点( ) 1 i i x， ，a i = ，K ，m，其中 i x 为 n R 上的向量，ai 为 0 或 1。这里说明一下点 i x 属于 0 或 1 的范畴。我们要讨论的是，是否可以找到一个超平面 ' f x =1将 i x 分离，使 得所有值为 0 的点满足 ' f x ≤1，值为 1 的点满足 ' f x ≥1。设计一个线性最优化问题找 到这样的向量 f 。 (b) 已知点( ) 1, , i i x， ，y i = K m ， i x 为 n R 上的向量， i y ∈ R 为相应的变量。 要找到一个超平面 ' α x =1，使得对所有点 ' ' 1 1, i i i α x ≤ ≈ y β x ，或者 ' ' 2 1, i i i α x ≥ ≈ y x β 。更 严格的，对所有使 的点 ' 1 i α x ≤ i x ，选择 β1，使 ' 1 : ' 1 i i a x y β ≤ − i ∑ x 取得最小值；同理 对所有使得α' xi >1的点 i x ，找到 β 2 ，求 ∑≤ − : ' 1 ' 2 i a x i i y β x 的最小值。 设计一个整数规划问题找到向量 1 2 α, , β β 。 问题 5（20 分） 3
考地下面问圈： Z'=min cx s.1 ax2b axzb *E0 其中a,a,c20我用Z女示LP的松熟创置的伯. a)考虑下面的站可题： Z=maxz min cx-(b2-ax) xt axzb x∈0.， 简述如何计算Z的值。Z,Z,Z之问有什么联系？证明你的结论。 b)过计·个动念赛划方法计算∠
考虑下面问题： { }n ' ' x , a x b s.t. a x b Z c'x 01 min 1 1 1 1 * ∈ ≥ ≥ = 其中 a a 1 2 , ,c ≥ 0 我们用 ZLP 表示 LP 的松弛问题的值。 (a) 考虑下面的松弛问题： { }n ' ' λ x s.t. a x b Z c'x λ b a x 0,1 max min ( 2 ) 1 1 1 0 2 ∈ ≥ = ≥ − − 简述如何计算 Z1 的值。 * Z ， ，Z1 ZLP 之间有什么联系？证明你的结论。 (b) 设计一个动态规划方法计算 * Z 。 4