北航最优化补考试题（考前老师给的）

《北航最优化补考试题（考前老师给的）》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、北京航空航天大学研究生课程试卷2011－2012学年第二学期《《《最最最优优优化化化理理理论论论与与与算算算法法法B》》》补补补考考考试试试卷卷卷2012年9月20日姓名:学号：说明：•闭卷考试.•共有6个题目，满分100分；考试时间2小时.•您的解答务必详细、清晰.•GoodLuck!题目123456总分分数1.(24分)判断下列每个命题的正误，并说明理由.理由可以是1-3行的解释或者反例；理由不正确的答案不得分.(a)线性规划标准形的可行集总是有界的.(b)如果x和分别是原始和对偶问题的最优解，则

2、由互补松弛性我们有原对偶变量的乘积总是零，即xiλi=0对所有i成立.(c)对偶单纯形法能够检测一个线性规划问题是不可行或者无界的.(d)在最小费用网络流问题中，链路费用是分数，但是需求和供给量是整数，最优基本可行解的每个分量是分数.1(e)凸规划的KKT点是全局极小点.(f)二次规划是凸规划.(g)半定规划是凸规划.(h)ℓ1惩罚函数法是非精确惩罚函数法.(i)二次惩罚函数法中，固定惩罚因子后由该方法得到的近似解是原问题的可行解.(j)对于线性规划标准形问题，如果最优值是−∞，则可以以某种方式调整右端

3、向量b使得最优值有限.(k)两阶段法中，第I阶段的辅助问题的对偶从来不会无界.(l)最速下降法的收敛速率高度依赖于初始点.(m)对于二次函数q(x)=1xTGx，牛顿法的收敛速率依赖于矩阵G的条件数.22.(20分)对于问题minimize5x1−3x2subjectto2x1−x2+4x3≤4,x1+x2+2x3≤5,2x1−x2+x3≥1,x1≥0,x2≥0,x3≥0.(a)以1为转轴元,利用一次转轴运算找到一个基本可行解.2(b)从(a)中找到的基本可行解开始，利用单纯形法求解该问题.(c)对偶问

4、题是什么?(d)给出对偶问题的解.23.(10分)考虑问题minn∥Ax−b∥2，其中A是m×n矩阵，b是m维向量.x∈IR(a)写出最优性的必要条件.这也是一个充分条件吗？(b)最优解唯一吗？理由是什么？(c)你能给出最优解的一种闭合(解析)形式吗？可以规定任何你所需的假设.4.(10分)考虑等式约束二次规划minimize1xTGx+dTx2subjecttoATx=b,其中b∈IRm,A∈IRn×m，且假设A的列a,···,a线性无关。设Z∈IRn×(n−m)是由齐次1m线性方程组ATs=0的基础

5、解系中的向量为列组成的矩阵，x′是方程组ATx=b的特解.请完成以下问题：(a)把原问题化成等价的无约束极小化问题；(b)给出(a)中问题有惟一解的充分条件；在此充分条件下，给出解的显式表达式；此时原问题的最优解是什么？5.(16分)考虑问题minimize−x1x2subjecttox1+2x2−4=0.(a)计算最优解和Lagrange乘子.(b)设罚参数为σ，写出该问题的Courant罚函数(二次罚函数).(c)确定二次罚函数的极小点，由此得到原问题最优解的近似和相应Lagrange乘子的近似.6

6、.(20分)考虑等式约束问题minimizex+xsubjecttox=x2.1221请完成以下问题：(a)写出该问题的KKT条件，并求出该问题的KKT点；(b)以x(0)=0,λ(0)=1为初始点，用解方程组的基本牛顿法解(a)中KKT条件所对应的方程组，迭代一次;(c)以x(0)=0,λ(0)=1为初始点，用SQP法求解该等式约束优化问题，迭代一次，要求用求KKT点的方法解其中的二次规划子问题；(d)将题目中的等式约束条件x2=x21换成x2≥x21，考虑用SQP法求解所得的不等式约束优化问题，写出

7、以x(0)=0,λ(0)=1为初始点时，需要求解的二次规划子问题.3