无约束最优化直接方法之单纯形法分析.docx

PAGE  PAGE 8 数学与计算科学学院 实 验 报 告 实验项目名称 无约束最优化直接方法之单纯形法 所属课程名称 最优化方法 实 验 类 型 算法编程 实 验 日 期 2015.11.20 班 级 学 号 2 姓 名 成 绩 一、实验概述：【实验目的】 加深了解无约束最优化直接方法中的单纯形有哪些信誉好的足球投注网站法 培养matlab编程与上机调试能力 【实验原理】 设是某一单纯形的n+1个顶点向量, 则： 对于任意给定初始点z1和正数l，按如下公式取定的单纯形是一个以为z1 顶点棱长为l的正规单纯形。。 其中n 维向量z(i)= ，如:z(2)= ，…， z(n-1)=，其中 正规单纯形是一种特殊的单纯形，还有一种特殊的单 纯形取法：其中= 在中此特殊单纯形即为等腰直角三角形。 单纯形替换法的基本思想就是按上面取特殊单纯形的方法形成初始单纯形。 然后从此出发，每次迭代都设法构造新的以替代旧的，使新单纯形不断向目 标函数的极小点靠近，直到有哪些信誉好的足球投注网站到满意的极小点为止。 单纯形替换法由两步构成：形成初始单纯形和迭代。而迭代过程又包括四项 操作：反射，延伸，收缩和减小棱长。 【实验环境】 Windows7；MATLAB7.0 二、实验内容：【实验方案】 1）设初始单纯形顶点的位置向量为.计算： ,其中分别为此单纯形的最好和最坏顶点。(取正 规单纯形作为初始单纯形比取后一种形式好) 若把顶点去掉，则 剩下的n个顶点 (不含)构成n-1维空间中的单纯形， 按下面公式求其中心： 2）反射。 按如下公式通过反射: , 称为的反射点。因是坏点，则一般 有f()f()，从而得到比更好的点,这时应按3进行伸延，否则进入3进行收缩工作。 3）延伸。 经过反射，若不仅有f()f(),且进一步有f()f()，则说明沿方向还可以向前迈一步，因此计算: = +r()称为的延伸点，r1是延伸系数，常取r=2,也可用直线有哪些信誉好的足球投注网站技术确定r.此时若有f() f(),则以替换，而其余n个顶点不变, 构成新单纯形，转 4）收缩。（如在R中，由图a知以、、为顶点???新单纯形已向极小点靠近了一步。）否则，以反射点替换构成单纯形，转6步（如R中，由图19.1.1 b可知以、、为顶点的新单纯形向极小点靠近了一步） 图19.1.1a 图19.1.1b 若f()f()，即反射点并不比原单纯形的最好点好，则分下列两种情况处理： 若存在一个标点i，使得f()f()，,即除最坏点外，反射点比其他一个顶点好，因而可以用将替换构成新的单纯形，转6步（如中，图c所示，以、、为顶点的新单纯形向极小点迈进了一步） 4.2 若对i=1,2,3--n+1(但)均有f()=f(),则要进 行收缩。 收缩分以下两种情况 4.2.1 若f() =f(),即反射点比原来单纯形的坏点还坏，则舍弃，对方向-v0进行收缩。如图d 计算公式为；其中是的收缩点，而收缩常数常取为： 若f()f()，即收缩点比原单纯形最坏点还坏，因此放弃点，转5步进行棱长减半工作。否则以替换构成新单纯形，转6。 4.2.2 若f()f()，则对向量--进行收缩（如图19.1.1e），计算公式为 若f()f(),即收缩点比反射点还坏，则放弃收缩点，转5进行棱长减半工作，否则以替换构成新单纯形，转6。 图19.1.1c 图19.1.1b 图19.1.1e 5）减小棱长。将原单纯形的最好点保持不动，各棱长减半，计算公式为 6）终止原则。计算，若，则v*为极小点，终止；否则，转1 【实验结论】（结果） 取初始点。为计算方便不取等边三角形为初始单纯形，而取直角三角形为初始单纯形，其顶点为： 相应函数值=45 , =125, =65 故 其中心 先做反射运算（为方便，取=1）因满足延伸条件，进行延伸实验（延伸系数r=2） 因延伸成功。取 此时得三个顶点及函数值为 下面开始第二次迭代 中心 反射 延伸 故以=（4，6）代替。f( )=4代替。转入下一次迭代。如此迭代下去最后可得极小点。 【实验小结】（收获体会）