投影梯度算法的数值行为研究
本科生毕业论文（设计）
1
投影梯度算法的数值行为研究
本科生毕业论文（设计）任务书及成绩评定表
毕业论文（设计）题目投影梯度算法的数值行为研究
2
投影梯度算法的数值行为研究
目录
摘要 .......................................................................................................................................................... 4 ABSTRACT ............................................................................................................................................ 5 前言 .......................................................................................................................................................... 6 第1章 引言 .......................................................................................................................................... 7 1.1 最优化问题概述 .......................................................................................................................... 7 1.2凸集和凸函数 .............................................................................................................................. 10 1.2.1 凸集 .................................................................................................................................... 10 1.2.2 凸函数 ................................................................................................................................ 12 第2章 基本概念 ................................................................................................................................ 16 2.1 最速下降法 ................................................................................................................................ 16 2.1.1 下降方向及下降算法 ........................................................................................................ 16 2.1.2 最速下降法 ........................................................................................................................ 18 2.2 约束问题的最优性条件 ............................................................................................................ 19 2.2.1 可行方向 ............................................................................................................................ 19 2.2.2 约束问题的最优性条件 .................................................................................................... 22 第3章 投影梯度法 ............................................................................................................................ 24 第4章 数值实验 ................................................................................................................................ 28 参考文献 ................................................................................................................................................ 31
3
投影梯度算法的数值行为研究
摘要
本文对投影梯度法的数值行为进行了研究。投影梯度法是可行方向法的一种。在可行方向法的算法中，每进行一次迭代都需要解一个线性规划问题来获得一个可行下降方向。而投影梯度法则简单得多，它可以看成最速下降法在引入投影这个概念后的一种推广。它的基本思想是，当迭代点在可行域的内部时，则以该点的负梯度方向为下降可行方向；而当迭代点位于可行域的边界上且其梯度方向指向可行域外部时，则取它的负梯度方向在边界上的投影为下降可行方向，若这个投影为零向量，则停止迭代，得到问题的极小点。我们可以看到，在迭代的过程中，投影梯度法不需要求解线性规划问题。正文首先介绍了最优化问题，然后对最速下降法的相关概念进行了介绍。接下来，介绍了投影梯度方法。最后，应用投影梯度法进行了数值实验，并对它们的结果进行了分析总结。
关键词：最优化问题；最速下降法；投影梯度法
4
投影梯度算法的数值行为研究
Abstract
This paper investigated the numerical behavior of the gradient projection algorithm. The gradient projection algorithm is one kind of the feasible direction methods. In the feasible direction methods, we need to solve a linear programming problem at every iteration. And it’s much more easy with the gradient projection algorithm. It can be seem as a developed method of the steepest descent method that introduce the concept of projection. Its basic thought is, while a iteration point is in the feasible region, the feasible direction is the negative gradient direction of the point; while a iteration point is on the boundary of the feasible region and its gradient direction points to the outside of the feasible region, the feasible direction is the projection of the negative gradient direction on the boundary of the feasible region, and if the projection is a zero vector, the iteration will be stopped, and the minimum point of the problem is got. We could see that, the gradient projection algorithm needn’t solve linear programming problems while in the iteration process. At first, the paper introduces the optimization problem, then give the concepts on steepest descent method. And then, tell the gradient projection algorithm. At last, do some numerical compute, and analyzes the results to get final remarks.
Keywords: optimization problem; steepest descent method; gradient projection
algorithm
5