无约束优化问题

郭勋诚

【摘要】为提高最优化问题中的求解效率找到最佳求解路径，在认识、学习和初步研究了最速下降法和牛顿法后，大致了解了其求解原理及求解规律，对其进行了进一步的思考和研究，试图探究在一定的条件范围或某种特定的条件下，能否将二者相结合，从而达到更高的求解效率和更好的求解途径。经过我的思考和研究，个人认为在解决较为简单的最优化问题时，我们可以在初始阶段使用最速下降法，在接近极值点时可以运用牛顿法，将两者结合起来从而提高求解效率和求解途径。

【关键词】最优化问题  最速下降法  牛顿法

【中图分类号】G63 【文献标识码】A 【文章编号】2095-3089（2018）40-0157-02

1.引言

最优化方法主要应用于各种管理问题以及生产经营活动中遇到的需要进行优化的各类问题[1]。只要存在资源有限的限制，就需要对资源做合理配置和规划，所以需要用到最优化方法。最优化方法主要是通过合理利用如人力、物力等各类资源，不断提升系统的运行效率，并最终使其达到最优的状态。在最优化问题中其常见思路一般为目标函数f（x）求极值，并求解出对应极值点x及f（x）的最大或最小值。一般情况下，我们将最优化问题分为两类：无约束的优化问题，即对自变量x不进行限制;有约束的优化问题，即自變量x有约束，其中包括不等式约束和等式约束问题。

本文主要讨论无约束问题，在第2节讨论和分析最速下降法（第2.1节）和牛顿法（第2.2节）的求解过程、求解原理和求解规律，并针对两个算法来进行比较，试图讨论出在一定条件范围或某种特定的条件下的最优方法。

2.算法原理

本文主要研究无约束优化问题中的两种基本算法——最速下降法和牛顿法。

2.1最速下降法

最速下降法主要是运用了多元函数求导的数学原理，在无约束最优化问题的多个解法中属于较为原始也是较为简单易行的[2]。对于一个给定的优化函数，其负梯度方向总是当前位置的最快方向，故选取该方向作为我们进行更新迭代的方向，这就是梯度下降法也就是我们常说的“最速下降法”的主要思想。 在高中的学习中，我们可以知道对f（x）求导函数的基本定义式。我们以一元函数为例，推导最速下降法。设一元函数为f（x），自变量x的取值范围为（-∞，+∞），求函数f（x）的极小值。若需要进行求最大值时，可运用转换的思想将其变成-f（x）进行运算。对函数f（x）求导，

f '（x）=■■               （1）

即在Δx→0的情况下，由（1）近似有

f（x+Δx）-f（x）=f '（x）Δx             （2）

令x'=x+Δx，则f（x'）-f（x）=f '（x）Δx，若Δx=-ηf '（x），其中η表示学习率，则

f '（x）-f（x）=f '（x）Δx=-η（f '（x））2 ≤0       （3）

所以，以负梯度方向作为我们每一次更新迭代的方向可以保证函数单调递减，并最终可以趋近函数f（x）的极小值。

在最速下降法的数学原理基础上，可以得到应用该方法求解极值的步骤。以一元函数求极小值为例。

Step0：随机初始化x0，并求出f '（x0）;

Step1：令x1=x0-ηf '（x0），并求出f（x1），f '（x1）;

……

Step（k+1）：令xk+1=xk-ηf '（xk），并求出f（xk+1），f '（xk+1）。

以此类推，算法停止条件有多种。明确最大迭代次数、极值的精度都可以用来确定算法的停止。

2.2牛顿法

牛顿法作为近似求解方程的一种方法[3]，一般首先将函数f（x）进行泰勒展开，最高次为二次，并且寻找方程f（x）=0的解。牛顿法相较于最速下降法，由于考虑了二阶导数，所以收敛速度更快。下面就是牛顿算法的基本求解原理和过程。

我们由泰勒展开式可得

f（x）=f（xk）+f '（xk）（x-xk）+■f ''（xk）（x-xk）2+…+■f（n）（xk）（x-xk）n+ο（xkn），                               （4）

但在一般情况下，只需要取

f（x）≈f（xk）+f '（xk）（x-xk）+■f ''（xk）（x-xk）2     （5）

由（5）对自变量x求导，令其为0可得：

f '（xk）+f ''（xk）（x-xk）=0                     （6）

并看成连续迭代可得

xk+1=xk-η■ （7）

2.3算法的比较及其联系

首先就最速下降法来说，这是一种较为原始的算法，在最优化问题的几种解题方法上是被选频率较高的。其最主要的优点有：每次迭代的计算量较小，储存的变量少，对初始点的要求不高;但其缺点也较为明显，如在接近极值点时，收敛速度会急剧下降，有时甚至不能够找到极值点[4]。而对于牛顿法来说，二者几乎是相反的。牛顿法收敛速度快，但对初始点的要求很高，几乎要求在所求极值点附近，并且牛顿法的步骤较为繁杂，结构复杂。打个很简单的比方，这两种方法就似两个人去爬同一座山，最速下降法永远都是去找坡度最陡的那块台阶，而不去管这样走的路程是多少;牛顿法会去找坡度不那么陡，但是在所有方法中效率最高的那条路。也就是说最速下降法的目光在当下，牛顿法的目光在未来。

正如前面所说，牛顿法需要一个极其精准的初始点，而在现实生活中，這样的初始点往往是很难找到的，但是其收敛速度较快;最速下降法不需要一个精准的初始点，但是其收敛速度较慢。对此我认为，可以将二者结合起来使用。在开始计算时，可以先使用最速下降法，这样对初始点的要求不是那么高，在用最速下降法计算的过程中，若发现其收敛速度急速下降，设这个点为x，我们可以换用牛顿法，并且将所得的x看作是一个初始点，然后用牛顿法继续进行运算。这样就可以使整个计算过程相比其分开计算时效率更高，操作更为简单。

3.应用

最优化问题在实际生活中有着十分广泛的应用[5]，如交通运输、计算机计算、资源分配等等。在高中的数学学习中，我们就曾学过相类似的数学知识——线性规划。

某市的车辆生产厂准备甲、乙两种汽车，生产一批甲汽车需要A钢材400kg，B钢材150kg，生产一种乙种汽车的主要原料是A种钢材100kg，B种钢材150kg，现汽车生产场中存A种钢材1000kg，B种钢材660kg，若生产一批甲汽车可以得到10000元利润，生产一批乙汽车可以得到5000元利润，为使得该汽车厂的利润达到最大化，应该如何安排甲乙两种汽车的生产计划？

设该汽车厂生产A汽车x辆，生产B汽车y辆，可获得z万元利润，所以可以求得目标线型函数z=x+0.5y再用线性规   划画出相应的图形即可进行求解。

z=x+0.5y400x+100y≤1000且x≥0，y≥0180x+150y≤660         （8）

根据不等式可作出可行区域图，根据图形可以看出在（2，2）处目标函数取得最大值。

4.总结

本篇论文中主要是对无约束优化问题中的两种解法——最速下降法和牛顿法进行了研究，具体地解释了两种算法的基本定义，求解中运用到的数学原理。并且简要地阐述了两种算法的优缺点及其异同，自我得出了在算法的开始使用最速下降法，在收敛速度急剧下降的那个点使用牛顿法的结论，在理论上可以将两种算法相结合起来，从而提高求解速率及效率。并且在全文的最后也进行了应用上的举例说明。

值得注意的是，在实际生活中，在资源有限的现实条件下，我们时时刻刻都在解决着最优化问题，在这个方面的研究我们应当更为深入，从而可以让生活贴近数学，数学改变生活。

参考文献：

[1]陈宇.基于物流配送路径优化问题的最优化方法研究[J]. 今日南国旬刊，2008（12）：8-9.

[2]刘颖超，张纪元.梯度下降法[J].南京理工大学学报，1993（2）：12-16.

[3]黄海，林穗华.几种修正拟牛顿法的比较[J].广西民族师范学院学报，2011（3）：8-11.

[4]郭跃东，宋旭东.梯度下降法的分析和改进[J].科技展望， 2016，（15）.

[5]孙娅楠，林文斌.梯度下降法在机器学习中的应用[J].苏州科技学院学报（自然科学版），2018（2）.