投影梯度算法的数值行为研究 - 图文(2)

投影梯度算法的数值行为研究

前言

当今，“优化”无疑是一个热门词。做宏观经济规划要优化资源配置，搞企业经营管理要优化生产计划，作新产品设计要优化性能成本比。就是在人们的日常生活中，优化的要求也比比皆是，消费时，如何花尽可能少的钱办尽可能多的事，出行时，如何走最短的路程到达目的地，等等。总而言之，在经济如此发展，竞争如此剧烈，资源日渐紧张的今天，人们做任何事，无不望求事半功倍之术，以求或提效、或增收、或节约等等之目标。所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化理论和方法，另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同，学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。比较公认的是：“规划论”（包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。

这篇文章中我们将就非线性规划问题中的约束问题进行其中一类算法的讨论，即可行方向法中的投影梯度算法。

可行方向法的典型策略是从可行点出发，沿着下降的可行方向进行搜索，求出使目标函数值下降的新的可行点。搜索方向的选择方式不同就形成不同的可行方向法。而最早的可行方向法是Zoutendijk在20世纪50年代提出的。在Zoutendijk可行方向法中，每迭代一次，需要解一个线性规划问题，然而其目的仅仅为了求得一个下降的可行方向。是否有更简便的办法来求这样的方向呢？对于线性约束问题，这是不难办到的，因为这时过边界点的任一方向在边界上的投影都是可行方向，而负梯度方向的投影将是一个下降方向。当迭代出发点在可行域内部时，沿目标函数的负梯度方向搜索；当迭代出发点在某些约束的边界上时，这些约束称为在迭代出发点处起作用约束，此时将该点处的负梯度投影到R的零空间(R是以在迭代出发点处起作用约束的梯度为行构造成的矩阵)，则此投影方向就是下降可行方向。这就是20世纪60年代初Rosen提出的投影梯度法的基本思想。假设当前迭代的出发点是a，则算法的主要步骤是：首先选择下降可行方向d进行搜索；然后确定沿此方向移动的步长A，求出使目标函数值下降的新的可行点a + Ad。

本文接下来的结构如下：第1章，介绍最优化问题的原理及相关概念；第2章，介绍最速下降法和约束问题的最优性条件；第3章，介绍投影梯度法的相关概念，并且介绍算法；第4章，用投影梯度法进行数值实验，并分析给出总结。

6

投影梯度算法的数值行为研究

第1章 绪论

1.1 最优化问题概述

从数学上比较一般的观点来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”f，以及“自变量”x应满足的一定条件，求x为怎样的值时，f取得其最大值或最小值，它们可以利用数学符号更简洁地表示成：maxf?x?或minf?x?。这里在函数和自变量两个词上之所以打上引号，是想强调它们的含意比中学数学和大学微积分中函数的定义要广泛得多。

求最小值的数学模型用公式表示如下：

minf?x?，x?D?Rn， （1.1）

其中，函数f是定义在Rn上的实值函数。通常，我们称函数发为问题（1.1）的“目标函数”。而x应该满足的条件我们称之为“约束条件”，约束条件一般用一个集合D表示为：x?D。同时，集合D也被称作问题的“可行域”，可行域中的点为“可行点”。如果将函数f视为生产中的某种成本，集合D视为生产过程中的各种可采用的方案所构成的集合，则上述最优化问题可通俗地理解为在众多可行的方案中寻求最佳方案。在实际工作中，最优化还有另一种含义，即使获得的效益最大。此时，相应的模型为：

maxf?x?，x?D?Rn， （1.2）

其中，f为某种效益函数。注意到maxf?x???min??f?，问题（1.2）可转化为形如（1.1）的等价问题。这样，求目标函数f在约束条件x?D下的最小值或最大值问题，就是一般最优问题的数学模型。

解决最优化问题的关键步骤是，如何把实际问题抽象成上述数学模型，也就是构造出目标函数与约束条件。一但这一步完成，对于简单问题，可借图形或微积分来求解。遇到比较复杂的课题，可先搞清它属于运筹学哪一分枝，并在此基础上尽量利用现有的数学软件或最优化软件，比如 Matlab，Mathematica， Lindo， Lingo等，来计算。

在问题（1.1）中，若D?Rn，则称问题（1.1）为“无约束最优化问题”（简称“无约束问题”）；否则称问题（1.1）为“约束最优化问题”（简称“约束问题”）。 无约束问题通常记为：

minf?x?，x?Rn。

约束问题的一般形式为：

7

投影梯度算法的数值行为研究

min f?x?

s.t. gi?x??0,i?I??1,...,m1?，

hj?x??0,j?E??m1?1,...,m?， （1.3）

其中gi,hj:Rn?R,i?I,j?E。约束问题（1.3）中，函数gi,i?I,hj,j?E称为“约束函数”。不等式组gi?x??0,i?I和等式组hj?x??0,j?E分别称为“不等式约束条件”和“等式约束条件”，统称为约束条件。显然，问题（1.3）的可行域

D为

D??xgi?x??0,i?I,hj?0,j?E?。

最优化的一个主要研究内容就是求问题（1.1.1）的解。最优化问题的解分为“局部最优解”和“全局（整体）最优解”。其定义如下：

定义1.1.1 设点x*?D。若存在x*的一个邻域U??x*??x?Rnx?x*??，使得如下不等式成立：

??fx*?f?x?，?x?D?U?x*， （1.4）

则称x*是问题（1.1）的一个局部最优解，或简称为问题（1.1）的一个“最优解”。若不等式（1.4）对所有x?D?U?x*\\x*成立严格不等式，则称x*是问题（1.1）的一个“严格局部最优解”。若不等式

????????fx*?f?x?，?x?D， （1.5）

成立，则称x*是问题（1.1）的一个全局（整体）最优解。若不等式（1.5）对所有x?D\\x*成立严格不等式，则称x*是问题（1.1）的一个“严格全局（整体）最优解”。

约束最优化问题中有两类重要的问题。当目标函数f和约束函数

????gi,i?I,hj,j?E都是线性函数时，约束问题（1.1）称为线性规划。当目标函数f是二次函数且约束函数gi,i?I,hj,j?E都是线性函数时，约束问题（1.1）称为二次规划。此外，若函数f是Rn中的凸函数且D是凸集时，问题（1.1）称为凸规划。有关凸集和凸函数的一些概念和基本性质我们将在下一节中进行介绍。

在结束本节之前，我们回顾一下多元函数的Taylor展开式以及向量和矩阵范

8

投影梯度算法的数值行为研究

数。

设f:Rn?R二次连续可微。我们用?f?x?和?2f?x?分别表示f在x处的梯度向量和Hessian矩阵，即

??2f?x??2f?x????...2T?x?x?x?1n?1??f?x??f?x??2?f?x???::?。 ??x,...,?x??，?f?x?????2f?x?1n???2f?x????2??x?x...?xn??n1?多元函数的一阶Taylor展开式（中值定理）如下： f?x??f?y???f?y???x?y???x?y?

T ?f?y???f?y??x?y????x?y?，

T其中???0,1?。

多元函数的二阶Taylor展开式如下：

1TTf?x??f?y???f?y??x?y???x?y??2f?y???x?y???x?y?

212TT ?f?y???f?y??x?y???x?y??2f?y??x?y???x?y，

2??其中???0,1?。

向量值函数有类似的中值定理。设F??F1,...,Fm?:Rn?Rm连续可微。

TF??x?表示F在x处的Jacobi矩阵，则有

F?x??F?y???F??y???x?y??d??x?y??F?y??F??y??x?y????x?y?。

10如无特别说明，本文所用到的向量范数均为Euclid范数，即对x?Rn，

x?xTx??12。对矩阵A?Rn?n，A表示由向量范数?导出的范数，即

???Ax?nA?maxAx?max?x?R,x?0?。

x?1???x?我们以?F表示矩阵的Frobenius范数，即

A?n2??????aij??i,j?1?12F，?A?aij?Rn?n。

??9

投影梯度算法的数值行为研究

1.2凸集和凸函数

1.2.1 凸集

定义1.2.1 若集合S?Rn满足：

?x??1???y?S，?x,y?S,????0,1?，

则称S是Rn中的“凸集”。

从集合的角度，凸集S可解释为：若S包含点x，y，则它包含了x与y的连线，如图1.1所示。

图1.1 凸集与非凸集

容易证明，Rn中的凸集有如下性质： 1．若S?Rn是凸集，则对任意??R，集合

?S???xx?S?

是Rn中的凸集。

2．若S1,S2?Rn是凸集，则集合S1?S2，

S1?S2?x?x?1??x?2?x?1??S1,x?2??S2

??和

S1?S2?x?x?1??x?2?x?1??S1,x?2??S2

??都是Rn中的凸集。

10

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库投影梯度算法的数值行为研究 - 图文(2)在线全文阅读。