清华大学最优化PPT及其作业答案.pptVIP

清华大学最优化PPT及其作业答案;;例：线性规划问题与实例

一个线性规划问题的实例是指矩阵和向量组(A,b,c)的某一特定取值，这些参数按照如下的结构关联在一起，描述了问题（解）所需要满足的特性。;算法;算法复杂性;多项式时间算法与指数时间算法;多项式时间算法与指数时间算法;多项式时间算法与指数时间算法;;单纯性算法的复杂性;定理：当θ2时，用单纯行算法求解上述问题时需要

21次迭代。;椭球法

第一个可以在多項式时间內解决一般线性规划问题的解法。;2021/1/4;2021/1/4;只要能有效的解决最优性条件的线性不等式,就能夠同时的解决一个线性规划问题(P)以及它的对偶问题(D)。椭球法正是一种专门解决线性不等式的方法。;否则,因为S∩E1是一个凸集,所以经过圆心,可以切掉不含S∩E1的半个圆,而只剩下包含S∩E1的半个圆(以1/2E1表示)。对1/2E1而言,可以做出一个最小的椭圆E2,使得1/2E1?E2，椭圆的圆心记u2。;2021/1/4;在p维空间中,每次做出的椭球体积都会逐渐缩小。以V()及V(1)来表示前后两个椭球的体积,则可以证明V(1)e?1/2(1)V()。所以

V(1)e?2(1)V(E1)。

表明在多项式时间內,新的椭球体积便可缩减至零,否则原问题无解。;n维空间的椭球;步骤：;2021/1/4;内点法;称x∈为一个可行內点()如果=b,x0。

可行內点解集合：F0={x∈,x0}。

假设F0非空。;內点法可粗略的分为三个步骤:;内点法;将(P1)变得稍微复杂一些,将球改为第一象限来考虑下列问题:;定义映射：;2021/1/4;在上述转化之下,(P2)的近似问题在y空间中就可写成:;在y空間中(P)变成下列的近似问题:;与(P’2)相比较,(P’)多了一些等式约束条件=b。为了保持这些等式的继续成立,原来在(P’2)中的移动方向?便需要投影在()这个矩阵的零空间()之中，即经过投影后的方向应是(?)，其中是一个投影矩阵，定义为：;2021/1/4;2021/1/4;2021/1/4;內点法的重要步骤:;内点法;2021/1/4;2021/1/4;2021/1/4;迭代公式;投影尺度算法;基本思想：

（1）选定一个内点解作为迭代过程的初始点，利用可行域的投影尺度变换，将当前的内点解置于变换??的可行域的中心；

（2）在变换后的可行域中沿着目标函数最速下降方向的正交投影移动，获得新的可行内点，并通过投影尺度逆变换将新的可行内点映射到原来的可行域，作为新的迭代点。

（3）重复这一过程，直至求出满足一定精度的近优解。;标准形;单纯形;向量的投影;单纯形S的投影尺度变换;变换T的性质;势函数;2021/1/4;求解方法;2021/1/4;2021/1/4;2021/1/4;2021/1/4;投影尺度算法;2021/1/4;有关定理;2021/1/4;2021/1/4;一般线性规划问题的处理;(P)存在最优解的充要条件是;记;记;;进行如下投影变换：;两个特性：;用投影尺度算法求解如下线性规划：;化为标准型;2021/1/4;路径跟踪法;条件;2021/1/4;2021/1/4;定义原始-对偶可行集;2021/1/4;2021/1/4;移动方向的计算;2021/1/4;步长的确定;计算步骤：;2021/1/4;三种解法比较;ThankYou