清华大学最优化PPT及其作业答案教学教材.ppt

《清华大学最优化PPT及其作业答案教学教材.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、清华大学最优化PPT及其作业答案例：线性规划问题与实例一个线性规划问题的实例是指矩阵和向量组(A,b,c)的某一特定取值，这些参数按照如下的结构关联在一起，描述了问题（解）所需要满足的特性。线性规划问题是对具有上述结构的所有实例的一种抽象描述。算法算法：是一组含义明确的简单指令。一个问题是算法可解的(solvable)：存在一个求解该问题的算法，只要让算法运行足够长的时间，并且保证满足算法在运行过程中所需要的存储空间，它就能求解该问题的任何一个实例。停机问题：不可能构造出一个程序来确定任意给出的程序是否

2、会陷入无限循环。算法复杂性算法复杂性(algorithmcomplexity):描述算法的存储要求和运行时间要求，分为算法的空间复杂性和算法的时间复杂性。----利用算法需要的初等运算次数来表示算法的时间复杂性。多项式时间算法与指数时间算法输入规模(inputsize)：表示一个实例所需要的字符串长度。一般的，使用位二进制就可以表示任意整数r。线性规划的输入规模为：多项式时间算法与指数时间算法把算法求解输入规模不超过k的实例时最多的运算次数称为该算法关于输入规模k的复杂性。定义:多项式时间算法与指数时间

3、算法多项式时间算法(polynomial-timealgorithm)或优良算法(goodalgorithm):对于某算法的复杂性函数，其增长速度是输入规模的多项式函数。指数时间算法(exponential-timealgorithm):对于某算法的复杂性函数，其增长速度是输入规模的指数函数。多项式时间算法的优点：（1）随着问题输入规模的增加，算法的计算量（即算法复杂性）呈多项式增长；（2）一个多项式时间算法利用另一个多项式时间算法作为其“子程序”，构造一个新的复合型算法，则新算法仍是多项式时间算法。单

4、纯性算法的复杂性单纯性算法需要2n-1次迭代。定理：当θ>2时，用单纯行算法求解上述问题时需要2n-1次迭代。椭球法第一个可以在多項式时间內解决一般线性规划问题的解法。根据(P)与(D)的对偶关系,我们可将两者的最优解以一组最优性条件联结起来:只要能有效的解决最优性条件的线性不等式,就能夠同时的解决一个线性规划问题(P)以及它的对偶问题(D)。椭球法正是一种专门解决线性不等式的方法。介绍如何以椭球法來解一组线性不等式Mu≤vMu≤v的解集合是一个凸集：假设S≠Ø,以原点u1为圆心,足夠大的半径做一圆E1

5、,使得S∩E1≠Ø。否则,因为S∩E1是一个凸集,所以经过圆心,可以切掉不含S∩E1的半个圆,而只剩下包含S∩E1的半个圆(以1/2E1表示)。对1/2E1而言,可以做出一个最小的椭圆E2,使得1/2E1⊆E2，椭圆的圆心记u2。S∩E1⊆E2,若Mu2≤v成立,则u2∈S∩E1必为其解。否则经过u2又可切去半个E2,而使S∩E1包含在另一半椭圆1/2E2之中。在p维空间中,每次做出的椭球体积都会逐渐缩小。以V(Ek)及V(Ek+1)来表示前后两个椭球的体积,那么可以证明V(Ek+1)

6、1)V(Ek)。所以V(Ek+1)0。可行內点解集合：F0={x∈Rn

7、Ax=b,x>0}。假设F0非空。內点法可粗略的分为三个步骤:步骤一:找一个可行內点x1∈F0。置k=1。步骤二:决定现有解xk是否为(P)的最优解。若是,则输出x∗=xk。否则就寻找一个好的移动方向,以及适当的步长>0。PrimalA

8、ffineScaling内点法假想(P)的可行解集合位于第一象限的一个球,而现行解xk落在球心上,此球的半径是r>0。最优解为：将(P1)变得稍微复杂一些,将球改为第一象限来考虑下列问题:定义映射：在上述转化之下,(P2)的近似问题在y空间中就可写成:应用(P1)的解答技巧,在y空间中的近似最优解为：在x空间中(P2)的近似最优解为：在y空間中(P)变成下列的近似问题:与(P’2)相比较,(P’)多了一些等式约束条件ADky=b。为了保持这些等式的继续成立,原来在(P’2)中的移动方向−Dkc便需要投影

9、在(ADk)这个矩阵的零空间(nullspace)之中，即经过投影后的方向应是Pk(−Dkc)，其中Pk是一个投影矩阵，定义为：所以(P’)的近似最优解是(P)的近似最优解是PrimalAffineScaling內点法的重要步骤:Dualaffinescaling内点法迭代公式Karmarkar投影尺度算法两个基本事实：（1）如果一个内点居于多面体的中心，那么目标函数的负梯度方向是比较好的可行方向；（2）在不改变问题基本特性的条件下，存在一