(1)一维搜索法:是优化方法中最基本、最常用的方法。所谓搜索,就是一步一步的查寻,直至函数的近似极值点处。其基本原理是区间消去法原则,即把搜索区间[a,b]分成3段或2段,通过判断弃除非极小段,从而使区间逐步缩小,直至达到要求精度为止,取最后区间中的某点作为近似极小点。
(2)坐标轮换法:又称降维法。其基本思想是将一个多维的无约束问题转化为一系列一维优化问题来解决。基本步骤是,从一个初始点出发,选择其中一个变量沿相应的坐标轴方向进行一维搜索,而将其它变量固定。当沿该方向找到极小点之后,再从这个新的点出发,对第二个变量采用相同的办法进行一维搜索。如此轮换,直到满足精度要求为止。若首次迭代即出现目标函数值不下降,则应取相反方向搜索。该方法不用求导数,编程简单,适用于维数小于10或目标函数无导数、不易求导数的情况。
但搜索效率低,可靠性较差。
(3)单纯形:是指在n维空间中具有n+1个顶点的多面体。其基本思想是,在n维设计空间中,取n+1个点,构成初始单纯形,求出各顶点所对应的函数值,并按大小顺序排列。去除函数值最大点Xmax,求出其余各点的中心Xcen,并在Xmax与Xcen的联线上求出反射点及其对应的函数值,再利用“压缩”或“扩张等方式寻求函数值较小的新点,用以取代函数值最大的点而构成新单纯形。如此反复,直到满足精度为止。
(4)梯度法:又称一阶导数法,最速下降法。其基本思想是以目标函数值下降最快的负梯度方向作为寻优方向求极小值。该方法中,相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向,因此相邻两个搜索方向互相垂直。梯度法虽然比较古老,但可靠性好,能稳定地使函数值不断下降。适用于目标函数存在一阶偏导数,精度要求不高的情况。该方法的缺点是收敛速度缓慢。
(5)鲍威尔法(Powell):是直接利用函数值来构造共轭方向的一种共轭方向法。其基本思想是不对目标函数作求导数计算,仅利用迭代点的目标函数值构造共轭方向。该法收敛速度快,是直接搜索法中比坐标轮换法使用效果更好的一种算法。适用于维数较高的目标函数。但编程较复杂。
(6)牛顿法:其基本思想是,首先把目标函数近似表示为泰勒展开式,并只取到二次项。然后,不断地用二次函数的极值点近似逼近原函数的极值点,直到满足精度要求为止。该法在一定条件下收敛速度快,尤其适用于目标函数为二次函数的情况。但计算量大,可靠性较差。
(7)变尺度法:又称拟牛顿法,它在牛顿法的基础上又作了重要改进。变尺度法综合了梯度法和牛顿法的优点,使其迭代公式中的方向随着迭代点位置的变化而变化。在远离最优点时与梯度法的迭代方向相同,计算简单且收敛速度快。随着迭代过程的进行,不断修正迭代方向,以改善在最优点附近时梯度法速度减慢的缺点。当迭代点逼近最优点时,利用牛顿法速度加快的优点,迭代方向就趋于牛顿方向,因而具有更好的收敛性。这种方法是求解高维数(10-50)无约束问题的最有效算法。
(8)网格法:其基本思想是,在设计变量的界限区内作网格,逐一计算网格点上的约束函数值和目标函数值,舍去不满足约束条件的网格点,而对满足约束条件的网格点比较目标函数值的大小,从中求出目标函数值为最小的网格点,这个点就是所要求最优解的近似解。该法算法简单,对目标函数无特殊要求,但对于多维问题计算量较大,通常适用于具有离散变量(变量个数≤8个)的小型的约束优化问题。
(9)复合形法:是一种直接在约束优化问题的可行域内寻求约束最优解的直接解法。其基本思想是,先在可行域内产生一个具有大于n+1个顶点的初始复合形,然后对其各顶点函数值进行比较,判断目标函数值的下降方向,不断地舍弃最差点而代之以满足约束条件且使目标函数下降的新点。如此重复,使复合形不断向最优点移动和收缩,直到满足精度要求为止。该法不需计算目标函数的梯度及二阶导数矩阵,计算量少,简明易行,工程设计中较为实用。但不适用于变量个数较多(大于15个)和有等式约束的问题(10)罚函数法:又称序列无约束极小化方法。是一种将约束优化问题转化为一系列无约束优化问题的间接解法。其基本思想是,将约束优化问题中的目标函数加上反映全部约束函数的对应项(惩罚项),构成一个无约束的新目标函数,即罚函数。
(简答题)
试述几种常用优化方法及其基本思想?
正确答案
答案解析
略