最优化理论与算法

最优化理论与算法笔记

在老师的指导下，我学习了最优化理论与算法这门课程。最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多方案中什么样的方案最优以及怎样找出最优方案。

由于生产和科学研究突飞猛进的发展，特别是计算机的广泛应用，使最优化问题的研究不仅成为了一种迫切的需要，而且有了求解的有力工具，因此迅速发展起来形成一个新的学科。至今已出现了线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。

整个学习安排如下，首先介绍线性与非线性规划问题，凸集和凸函数等基本知识及线性规划的基本性质；然后再这个基础上学习各种算法，包括单纯形法、两阶段法、大M法、最速下降法、牛顿法、共轭梯度法等，以及各种算法相关的定理和结论；最后了解各种算法的实际应用。

主要学习的基础知识：

1、 一般线性规划问题的标准形式

mincxjj1nj

s..taxijj1njbi,i1,...,m,j1,...,n.xj0,

学会引入松弛变量将一般问题化为标准问题；同时掌握基本可行解的存在问题，通过学习容易发现线性规划问题的求解，可归结为求最优基本可行解的问题。

2、 熟练掌握单纯形法、两阶段法和大M法的概念及其计算步骤。

单纯形法是一种是用方便、行之有效的重要算法，它已成为线性规划的中心内容。其计算步骤如下：

1）解

BxBb,1xBbb，令xN0,计算目标函数值fcBxB； B求得

1cBBcBB ，得到2)求单纯形乘子，解；

3)解Bykpk，若yk0，即yk的每个分量均非正数，则停止计算，问

题不存在有限最优解，否则，进行步骤（4）；

4)确定下标r，使

brbmin{ryrk0}yrkyrk，得到新的基矩阵B，返回第一

步。

两阶段法：第一阶段是用单纯形法消去人工变量，即把人工变量都变换成非基变量，求出原来问题的一个基本可行解；第二阶段是从得到的基本可行解出发，用单纯形法求线性规划的最优解。

大M法：在约束中增加人工变量，同时修改目标函数，加上罚项

xaMeTxa，其中M是

很大的正数，这样，在极小化目标函数的过程中，由于M的存在，将迫使人工变量离基。

3、掌握最速下降法的概念及其算法，并且能够讨论最速下降算法的收敛性。掌握牛顿

(k1)(k)2(k)(k)xxf(x)(xx) ，掌握共轭梯度法及其相关法，能够熟练运用牛顿迭代公式：

结论，以及其收敛性的讨论，掌握最小二乘法及其基本步骤。

最速下降法：迭代公式为

x(k1)x(k)kd(k)。

(1)n计算步骤：1）给定点xR，允许误差0,置k1；

(k)(k)df(x)； 2）计算搜索方向

3）若

d(k)0，则停止计算，否则，从x；

(k)出发，沿d(k)进行一维搜索，求k，使

f(x(k)kd(k))minf(x(k)d(k))4）令

x(k1)x(k)kd(k)，置k:k1，转步骤（2）。

共轭梯度法：共轭梯度法是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组供各方向，并沿这组方向进行搜索，求出目标函数的极小点，根据共轭方向的基本性质，这种方法具有二次终止性。

具体求解方法：首先，任意给定一个初始点x，计算出目标函数f(x)在这点的梯度，

(1)若

g10，则停止计算；否则，令

d(1)f(x(1))g1，沿方向d搜索，得到点x。计算在

(1)(2)x(2)处的梯度，若g20，则利用g2和d(1)构造第二个搜索方向d(2)，再沿d(2)搜索；若已知

(k)(k)点x的搜索方向d，得到x(k1)x(k)kd(k)，再从x(k1)出发，沿方向d(k1)搜索。

结论：由共轭梯度法产生的方向d，d(1)(1)f(x)。 d小值。注：初始方向比为

(1)(2)，…，d(m)是A共轭的，经有限步必达到极

牛顿修正法：对于原始牛顿法和阻尼牛顿法都有共同缺点，一是可能出现Hesse矩阵

2奇异的情形，因此不能确定后继点；二是即使 f(x)非奇异，也未必正定，因而牛顿方向

不一定是下降方向，这就可能导致算法失效。

2(k)(k)(k)(k)(k)f(x)df(x)，阻尼牛顿法所用搜dxx牛顿修正法的策略，记，得到

(k)2(k)1(k)2(k)1df(x)f(x)f(x)存在。解决索方向是上述方程的解：，这里假设逆矩阵

2(k)2(k)f(x)f(x)，构造一个对称矩阵Gk，得Hesse矩阵非正定问题的基本思想是，修正

(k)1(k)(k)dGGkd(k)f(x(k))f(x)，再沿kx到方程，解此方程，得到在点处的下降方向

此方向作一维搜索。

最小二乘法：（1）线性最小二乘问题

F(x)fi2(x)(Axb)T(Axb)i1m，求F(x)平稳点，

TTTT令F(x)2AAx2Ab0，则F(x)的平稳点满足AAxAb，所以F(x)的平稳点为

x(ATA)1ATb，由于F(x)为凸函数，所以x比为全局最小点。

（2）非线性最小二乘 基本思想是通过解一系列线性最小二乘问题求非线性问题的解。基本步骤如下：

(1)1）给定初点x，允许误差0，置k1；

f1(x(k))(k)f(x)2fk........(k)(k)fm(x)，再计算一阶偏导数2）计算函数值fi(x)(i1,2,...,m)，得到向量

fi(x(k))aij,xii1,...,m;j1,...,n,得到矩阵

Ak(aij)mn。

3）解方程组

T(k)AkTAkdAkf，求得Gauss-Newton方向d(k)。

4）从x出发，沿d(k)(k)作一维搜索，求步长k，使得

F(x(k)kd(k))minF(x(k)d(k)).

令

x(k1)x(k)kd(k)).

5）若

x(k1)x(k)(k1)xx，则停止计算，得解，否则置k:k1，返回步骤二。

在整个学习过程中，我们学习的侧重点都是以应用为主，尤其是对各种相应的算法。而这个内容的学习除了可以解决很多实际问题外，对学习数值计算这门课程的帮助也是非常大的，其中所讨论的各种算法，对数值计算中求解线性方程组的解也能适用，这就将两门课程有机的结合在一起。

当然在学习过程中，有很多问题也是我没人理解透彻的，需要今后继续努力改进的。比如像各种算法的收敛性的讨论，以及在计算机中的编程实现等都将是我以后长期的课题。