《最优化复习材料》由会员分享，可在线阅读，更多相关《最优化复习材料（13页珍藏版）》请在金锄头文库上搜索。
1、最优化复习材料最优化复习材料1. 单纯形法：单纯形法：例题：单纯形法求解12121212326.50,0Max wxxxxst xxxx 解：将 LP 问题化为标准形：121231241232326.5,0Min zxxxxxst xxxx x x x 列出表格：满足，但不满足，6 56min , 2 12（做法：比较底行中最小的负元素，比较最右列元素与此列中的非负元素的比值，去 最小者对应的此列中的元素，即圈出的元素。注意只比较非负的元素。 ） （注：四个条件：）-12106110151-3000-1/211/2033/20-1/212-1/203/209121311 23rrrrr2123
2、22 3 1 2 1 2rrrrr标准 LP 问题的最优解为min4 1129( ,0,0) ,3 23Txz 原 LP 问题的最优解为* max4 1129( ,) ,3 23Txw 2. 对偶单纯形法对偶单纯形法课件 0924 对偶 LP 及对偶单纯形法 28-37 例 5 例 6，其中的一道。 LP 对偶变换规则如下图：对偶单纯形法的迭代步骤： 1)将原问题化为标准形，写出相应的表格； 2)利用容许的运算建立满足三个特点的单纯形表； 3)检查右列元素，若全非负，即表格满足四个特点，结束运算；进行第四 步；4)确定离基变量。取右列中最小的负元素所在的行是第 行。l5)确定进基变量。观察该行
3、竖线左边的元素，若则此问题没lja0,1, .ljajn L L有可行解，结束运算；否则按如下规则从负系数中选择一个记为，lkamax0jk lj ljlkccaaa 所在的列对应的变量取为进基变量；lkakx011/31/311/310-1/32/34/3004/31/329/36)进行旋转运算 。利用容许的运算将变为 1，该列其它元素变为 0，从而实现将lka变为基变量的目的。kx7)观察得到的新表（满足）若右列元素均非负，则已经得到最优解，结束运 算；否则，返回第 4）步。例题：求下面的问题：（教材 P79 例 5.4）用对偶单纯形法求解123123123min345235. .2260
4、,1,2,3jzxxxxxxs txxxxj 解：引入松弛变量得到标准型线性规划12312341235min345235. .2260,1,2,3,4,5jzxxxxxxxs txxxxxj 构造对偶单纯性表，选取离基变量12312341235min345235. .226zxxxxxxxs txxxx 对偶单纯形表：上表中-6 是离基变量，选择办法为：。-2 对应的列就是进基变量选 择办法：在上图中的右下角。是此线性规划的最优解。最优值为：11。(1,2,0,0,0)Tx 一直提到的那四个条件是：3. 黄金分割法（黄金分割法（0.618 法）：法）：计算步骤：设为允许的最后的搜索区间长度，令
5、，则 0.618 法的计算步骤如下：00.6181.计算令 k=0。0000001000(1)(), ()(), ()abaaba 2.若，则计算结束，最优解，可取；否kkba*,kka b*(1/ 2)()kkba则，若，则转 3，若，则转 4。()()kk ()()kk 3.令，再令，计算，1+1,=kkkkabb+1+1111=()kkkkkkaba，1()k 转 5。4.令，再令，计算1+1,=kkkkaa b+1+1111=(1)()kkkkkkaba，转 5。1()k 5.令，返回 2。1kk例题：用 0.618 法求解，初始区间为，要求迭代2( )xMin f xex00, 2,
6、3a b 四次后，取近似极值点。解：第一次迭代：000000002,32(1 0.618) (32)0.09,20.618 (32)1.09()1.1023,()1.5243,()()abffff 第二次迭代：111111112,1.090.09,20.382 (1.092)0.81962()2.9414,()1.1023,()()abffff 第三次迭代：222222220.81962,1.090.09,0.81962+0.618 (1.090.81962)0.36053()1.1023,()0.82723,()()abffff 第四次迭代：33333333440.09,1.090.3605
7、3,0.090.618 (1.090.09)0.63924()0.82723,()0.93627,()()0.09,0.63924abffffab 所以，近似解为*440.27452abx4. 牛顿法（一元）牛顿法（一元）与之前数值计算中学过的牛顿法相似：迭代公式为： 1“() ()k kk kfxxxfx例题：用 Newton 法求解，初始点为，误差精432( )46164f xxxxx03x 度取310解：32“2( )4121216( )122412fxxxxfxxxNewton 迭代公式为：321“2()4121216 ()122412kkkk kkk kkkfxxxxxxxfxxx取
8、初始值为03x 0 101“ 0 1 212“ 1 2 323“ 2 3 434“ 3 4 545“ 4()5.167,()153.413()()4.335,()32.330()()4.040,()3.418()()4.001,()0.084()()4.000,()0()fxxxfxfxfxxxfxfxfxxxfxfxfxxxfxfxfxxxfxfx所以，极小点为*5 min4,(4)156xxff 5. 牛顿法（多元）牛顿法（多元）222 11122 1212222 2212( ,)( ,)fff xxx xf x xf x xfff xx xx 算法：1.给出，取0,01,0nxRk0 0
9、()df x 2.计算，如果，停。否则计算，并令()kf x()kf x2()kf x（注：成为牛顿方向）21()()kkkdf xf x 21( )( )df xf x 3.令，返回 2。1,1kkkxxdkk例题：用牛顿法求解： 22 1219min( )22f xxx0(9,1)Tx 解：12 129ffxxxx222222 1221121,9,0ffff xxx xx x 所以12210( ),( )909xf xf xx代入得，020910(),()909f xf x 所以， 1020101()()9109 10999109 101/990 0xxf xf x 而 ，故12( )9x
10、f xx1()0f x所以迭代终止，最优点为：*1(0,0)Txx6. DFP 算法（拟牛顿算法，变尺度算法）算法（拟牛顿算法，变尺度算法）牛顿方向：21()()kkkdf xf x DFP 算法：1.给出，取0,01,0nxRk0 0()df x 2. 若，停，此时取；否则，进行精确线搜索，即()kf x*kxxk，并令。argmin()kk kf xd1kkkxxd3.1 1kk kxx 1 11111 1 111111 1()()()kk kTT kkkkkk kkTT kkkkkkk kf xf xHHHHHdHf x 4. 令，返回 2.1kk例题：用 DFP 算法求解：7. K-T
11、 点判断点判断例题：考察问题判断可行点min () =(1 3)2+(2 2)2. 1() = 21+ 22 5 0 2() = 1 0 3() = 2 01() = 1+ 22 4 = 0?是否是该问题的 K-T 点。0= (2,1) 解：（1）计算点的紧约束:0易验证对而言，只有是紧约束。01(0) 0（注：判断紧约束只是对于不等式约束而言。将给定的点带入不等式约束条件中，如果等号成立则是紧约束，否则不是。例如是1() = 21+ 22 5 = 22+ 12 5 = 0紧约束，不是紧约束，不是紧约2() = 1= 2 0，2= 0，3= 0所以，K-T 条件中（b）和（c）式也成立；综上可
12、知，是一个 K-T 点。0= (2,1)(注：K-T 条件 a) ()+ = 1 () + = 1 ()= 0b) ()= 0, = 1,2,c) ) 0, = 1,2,如果在求解 Lagrange 乘子时候，无解或是求解出的是小于零的，那么，所给的点就不是iuK-T 点。例如可以计算对于例题中的二次规划问题点 就不是 k-T 点。1(0,2)Tx 8. 凸二次规划凸二次规划什么是二次规划：指变量在受线性等式或不等式的约束下,求二次函数的极值问题. 即 目标函数为二次函数、约束函数为线性函数的数学规划问题。 研究问题： 1min12 .0,0,TTT iiT iiq xx Gxg xs ta xbiEa xbiI L L L L其中为的对称阵，、是列向量， ，Gn ngiaibR 1,2,1,2,EmImmp L LL L注： (1) 若 Hesse 阵 G 是半正定的, 则称为凸二次规划，它的任何局部最优解都是全局最优 解 (2) 若 Hesse 阵 G 是正定,则成为严格凸二次规划，它若有全局最优解，则最优解唯 一 等式约束的严格凸二次规划求解。求解方法为：Lagrange 方法。 一般形式： 1min2 .(3)TTTq xx Gxg xs tA xb L L L L其中正定，假设是满秩的。n mGR
