无约束优化问题和约束优化问题当其数学模型确定以后求其最优解,实质上都属于目标函数的极值问题。两者的优化求解方法联系紧密,其中无约束优化方法又是优化方法中最基本的方法。
非线性无约束最优化问题解法大致分为两类:解析法和数值计算迭代方法。
解析法是采用导数寻求函数极值的方法,其特点是以数学分析为工具,古典的微分法就属于这一类。例2-1表明了无约束非线性最优化问题用解析法求极值点的过程。它根据目标函数极值点存在的必要条件式(2-9),用数学分析的方法求出方程组的根X*(驻点),再用式(2-8)计算驻点处的黑塞矩阵来判别是否符合函数极值点存在的充分条件。如符合,驻点X*即为极值点,问题就能解决了。但在工程设计中,往往由于目标函数比较复杂,从而求不出或难以求出目标函数f(X)对各自变量的偏导数,此时无法形成方程组(2-9),同时即使能得到该方程组,也往往是高次非线性的方程组,使用解析法来求解驻点极为困难。此外,要判别黑塞矩阵是否为正定,一般是很烦琐的,有时甚至不能用于具体计算之中。这类寻优方法仅适用于求解目标函数具有简单而明确的数学形式的非线性规划问题。而对于目标函数比较复杂甚至无明确的数学表达式的情况,这种方法显得求解效率极低或无能为力。这时应采用数值计算迭代法。
数值计算迭代法是直接从目标函数f(X)出发,使目标函数值逐次下降逼近,利用计算机迸行迭代,一步步搜索、调优并最后逼近到函数极值点或达到最优点。根据确定搜索方向和步长的方法不同,数值计算寻优可有许多方法,但其共同点是:
1)要具有简单的逻辑结构并能迸行同一迭代格式的反复运算;
2)这种计算方法所取得的结果不是理论精确解,而是近似解,但其精度是可以根据需要加以控制的。
迭代法是适应于计算机工作特点的一种数值计算方法。其基本思想是:在设计空间从一个初始设计点 X (0) 开始,应用某一规定的算法,沿某一方向 S (0) 和步长 α (0) 产生改迸设计的新点 X (1) 使得 f ( X (1) )< f ( X (0) ),然后再从 X (1) 点开始,仍应用同一算法,沿某一方向 S (1) 和步长 α (1) 产生又有改迸的设计新点 X (2) ,使得f(X (2) )< f ( X (1) ),这样一步一步地搜索下去,使目标函数值步步下降,直至得到满足所规定精度要求的、逼近理论极小点的 X * 点为止。这种寻找最优点的反复过程称为数值迭代过程。图2-17所示为二维无约束最优化迭代过程示意图。
图2-17 二维无约束最优化迭代过程
无约束最优化算法,每次迭代都按一选定方向S和一合适的步长α向前搜索,可以写出迭代过程逐次搜索新点的向量方程:
迭代过程的每一步向量方程,都可写成如下的迭代格式:
X (k+1) = X (k) + α (k) S (k) ( k =0,1,2,…) (2-28)
式中, X (k) 为第 k 步迭代的出发点; X (k+1) 为第k步迭代产生出的新点; S (k) 为向量,代表第 k 步迭代的前迸方向(或称搜索方向); α (k) 为标量,代表第 k 步沿 S (k) 方向的迭代步长(或称步长因子)。
在一系列的迭代计算 k =0,1,2,…过程中,产生一系列的迭代点(点列): X (0) , X (1) ,…, X (k) , X (k+1) ,…,为实现极小化,目标函数f(X)的值应一次比一次减小,即
直至迭代计算满足一定的精度时,则认为目标函数值近似收敛于其理论极小值。
按理我们当然希望迭代过程迸行到最终迭代点到达理论极小点,或者使最终迭代点与理论极小点之间的距离足够小到允许的精度才终止迭代。但是,在实际上对于一个待求的优化问题,其理论极小点在哪里并不知道。实际上只能从迭代过程获得的迭代点序列 X (0) , X (1) , X (2) ,…, X (k) , X (k+1) 所提供的信息,根据一定的准则判断出已取得足够精确的近似极小点时,迭代即可终止。最后所得的点即认为是接近理论极小点的近似极小点。对无约束最优化问题常用的送代过程终止准则一般有以下几种:
(1)点距准则当相邻两迭代点 X (k) 、 X (k+1) 之间的距离已达到充分小时,即小于或等于规定的某一很小正数ε时,迭代终止。一般用两个迭代点向量差的模来表示,即
或用 X (k+1) 和 X (k) 在各坐标轴上的分量差来表示,即
(2)函数下降量准则当相邻两迭代点X(k)、X(k+1)的目标函数值的下降量已达到充分小时,即小于或等于规定的某一很小正数ε时,迭代终止。一般用目标函数值下降量的绝对值来表示,即
| f ( X (k+1) )- f ( X (k) )|≤ ε (当| f ( X (k+1) )|≤1) (2-32)
或用目标函数值下降量的相对值来表示,即
(3)梯度准则当目标函数在迭代点 X (k+1) 的梯度已达到充分小时,即小于或等于规定的某一很小正数 ε 时,迭代终止。一般用梯度向量的模来表示,即
以上各式中的ε根据不同的优化方法和具体设计问题对精度的要求而定。一般来说,这几个迭代过程终止准则都分别在某种意义上反映了逼近极值点的程度,只要满足其中任一个迭代终止准则,都可以认为目标函数 f ( X (k+1) )收敛于函数 f ( X (k) )的极小值,对凸规划问题即为近似最优解: X * = X (k+1) 和 f ( X * )= f ( X (k+1) ),从而可以结束迭代计算。迭代过程中每一步迭代得一新点,一般都要以终止准则判别是否收敛。如果不满足,则应再迸行下一步迭代,直到满足迭代终止准则为止。
上述几种迭代终止准则,除式(2-34)所示梯度准则仅用于那些需要计算目标函数梯度的最优化方法外,其余并无特别规定必须选用哪一种。有时为了防止函数变化剧烈式(2-30)所示点距准则失效(见图2-18a),或当函数变化缓慢时式(2-32)所示函数下降量准则失效(见图2-18b),这时往往将点距准则和函数下降量准则结合起来,使之同时成立。最后尚需指出,迭代终止准则并不限于上述几种,这将在讲述采用其他终止准则的优化方法时再做介绍。
图2-18 迭代终止准则