文档介绍：最优化理论与算法笔记
在老师的指导下,我学****了最优化理论与算法这门课程。最优化理论与算法是一个重要的数学分支,它所研究的问题是讨论在众多方案中什么样的方案最优以及怎样找出最优方案。
由于生产和科学研究突飞猛进的发展,特别是计算机的广泛应用,使最优化问题的研究不仅成为了一种迫切的需要,而且有了求解的有力工具,因此迅速发展起来形成一个新的学科。至今已出现了线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。
整个学****安排如下,首先介绍线性与非线性规划问题,凸集和凸函数等基本知识及线性规划的基本性质;然后再这个基础上学****各种算法,包括单纯形法、两阶段法、大M法、最速下降法、牛顿法、共轭梯度法等,以及各种算法相关的定理和结论;最后了解各种算法的实际应用。
主要学****的基础知识:
一般线性规划问题的标准形式
学会引入松弛变量将一般问题化为标准问题;同时掌握基本可行解的存在问题
,通过学****容易发现线性规划问题的求解,可归结为求最优基本可行解的问题。
熟练掌握单纯形法、两阶段法和大M法的概念及其计算步骤。
单纯形法是一种是用方便、行之有效的重要算法,它已成为线性规划的中心内容。其计算步骤如下:
1)解求得,令计算目标函数值;
2)求单纯形乘子,解,得到;
3)解,若,即的每个分量均非正数,则停止计算,问
题不存在有限最优解,否则,进行步骤(4);
4)确定下标r,使,得到新的基矩阵B,返回第一
步。
两阶段法:第一阶段是用单纯形法消去人工变量,即把人工变量都变换成非基变量,求出原来问题的一个基本可行解;第二阶段是从得到的基本可行解出发,用单纯形法求线性规划的最优解。
大M法:在约束中增加人工变量,同时修改目标函数,加上罚项,其中是很大的正数,这样,在极小化目标函数的过程中,由于的存在,将迫使人工变量离基。
3、掌握最速下降法的概念及其算法,并且能够讨论最速下降算法的收敛性。掌握牛顿法,能够熟练运用牛顿迭代公式: ,掌握共轭梯度法及其相关结论,以及其收敛性的讨论,掌握最小二乘法及其基本步骤。
最速下降法:迭代公式为。
计算步骤:1)给定点,允许误差置;
2)计算搜索方向;
3)若,则停止计算,否则,从出发,沿进行一维搜索,求,使;
4)令,置,转步骤(2)。
共轭梯度法:共轭梯度法是把共轭性与最速下降法相结合,利用已知点处的梯度构造一组供各方向,并沿这组方向进行搜索,求出目标函数的极小点,根据共轭方向的基本性质,这种方法具有二次终止性。
具体求解方法:首先,任意给定一个初始点,计算出目标函数在这点的梯度,若,则停止计算;否则,令,沿方向搜索,得到点。计算在处的梯度,若,则利用和构造第二个搜索方向,再沿搜索;若已知点的搜索方向,得到,再从出发,沿方向搜索。
结论:由共轭梯度法产生的方向,,…,是A共轭的,经有限步必达到极小值。注:初始方向比为。
牛顿修正法:对于原始牛顿法和阻尼牛顿法都有共同缺点,一是可能出现Hesse矩阵奇异的情形,因此不能确定后继点;二是即使非奇异,也未必正定,因而牛顿方向不一定是下降方向,这