目 录
第一章 绪论… … … … … … … … … … ...… … … … … … … … … … … 1
§1.1 多目标最优化简介… … … … … … … … … … … … … … … … … … … … ...1
? §1.2 多目标最优化的数学模型… … … … … … … … … … … … … … … … … ...2
? §1.3 多目标最优化的研究方向… … … … … … … … … … … … … … … … … ...3
§1.4 信赖域算法简介… … … … … … … … … … … … … … … … … … … … … ...4
? §1.5 多目标规划直接算法研究现状及本文的研究内容… … … … … … … ...6
预备知识… … … … … … … … … … … … … … … … … … … … 8
§2.1 基本概念及基本定理… … … … … .… … … … … … … … … … … .… … … 8
§2.2 基本算法简介… … … … … … … … … … … … … … … … … … … … … … .13
第三章 非光滑凸多目标规划信赖域算法… … … … … … … … … … 20
§3.1 基本概念及基本定理… … … … … … … … … … … … ..… ...… … … … … 20
§3.2 非光滑凸多目标规划信赖域算法具体步骤… … … … … … … … … … .24
§3.3 多目标规划信赖域子问题… … … … … … … … … … … … … … … … … .26
§3.4 信赖域算法的收敛性… … … … … … … … … … … … … … … … … … … .30
§3.5 算例及几点说明… … … … … … … … … … … … … … … … … … … … … .33
第四章 可微凸多目标规划信赖域算法… … … … … … … … … … … 34
§4.1 基本概念及基本定理… … … … … … … … … … … … … … … .… … … … 34
§4.2 强相容可微凸多目标规划信赖域算法… … … … … … … … … … … … 35
§4.3 可微凸多目标规划信赖域算法… … … … … … … … … … … … … … … .38
§4.4 算例及结论… … … … … … … … … … … … … … … … … … … … … … … .40
总 结… … … … … … … … … … … … … … … … … … … … … 43
致 谢… .… … … … … … … … … … … … … … … … … … … … … … .45
参考文献… … … … … … ..… … … … … … … … … … … … … … … … … 46
摘 要… … … … … … … … … … … … … .… … … … … … … … … … … I
ABSTRACT… … … … … … … … … … … … … … … … … … … … … … III
第一章 绪 论
本章中我们主要讲述多目标最优化问题的由来、数学模型、研究方向;信赖
域算法的由来、基本思想、现状;以及多目标最优化直接算法的研究现状和本文
所作的主要工作。
§1 - 1 多目标最优化简介
多目标最优化是近三十年来迅速发展起来的一门新兴学科。作为最优化的一个重要分
支,它主要研究在某种意义下多个数值目标的同时最优化问题。由于现实世界的大多数最优
化问题都要涉及许多目标,因此,自 70年代以来,对于多目标最优化的研究,在国际上引
起了人们的极大关注和重视。特别是近二十多年来,理论探索不断深入,应用范围日益广泛,
研究队伍迅速壮大,多目标最优化已显示出勃勃生机。
多目标最优化的起源可追溯到经济学中 A.Smith(1776 年 )关于经济平衡和
F.Y.Edgeworth(1874年)对均衡竞争的研究。特别是著名经济学家 V.Pareto(1896年,1906 年)
在经济福利理论的著作中,不仅提出了多目标最优化问题,并引进了 Pareto最优化的概念,
这对于多目标最优化学科的形成起着十分重要和深远的影响。此外对策论、有序集理论、有
关序型理论都为促使多目标最优化的产生提供了基本的理论工具和条件。现代多目标最优化
学科的正式形成乃始于本世纪 50年代。众所周知,T.C.Koopmans(1951年)[10]从数量经济角
度对多目标最优化所作的基本工作,以及 H.W.Kuhn和 A.W.Tucker(1951 年)[11]关于向量极值
的一些研究为这一学科的建立奠定了重要的基础。稍后,L.Hurwicz(1958 年)把多目标最优
化问题的研究推向了一般的拓扑向量空间,终于使这一学科的抽象理论为数学家们所广泛接
受。但是,多目标最优化的真正兴旺发达时期,并且正式作为一个数学分支进行系统地研究,
是本世纪七十年代以后的事情。1975 年,M.Zeleny[12]写了第一本关于多目标最优化问题的
论文集。从 1972年开始,以多目标决策命名的国际学术会议已召开多次。到现在为止,多
目标最优化不仅在理论上取得很多重要成果,一套平行于单目标最优化的理论正在形成和日
益完善,而且在应用上其范围也越来越广泛,多目标决策作为一个工具在解决工程技术、经
济、管理、军事和系统工程等众多方面的问题也越来越显示出它的强大生命力。
§1- 2 多目标最优化的数学模型
用现代方法解决实际问题时,第一步就是建立数学模型。这宛于机械加工中
的毛胚一样,没有它别的工序就无法进行。从应用数学的角度来看,有了数学模
型以后,不仅为定量地解决问题提供了必要的前提,而且也为定性地研究问题指
出一条统一的途径,沿着这个途径,不仅可以做理论上的分析,还可以给出各种
计算方法,从而又可在更广泛的意义上指导实践。
作为多目标最优化问题也是一样,也应该要建立其数学模型。为此,首先需要确定出问
题中所涉及的已知量,并设出未知量,也叫决策变量,简称变量;然后按要求寻找所要求的
目标函数及各量之间所满足的限制条件,即约束函数。为了得到一般多目标最优化问题的数
学模型,我们以有n个变量, p个目标函数,m个不等式约束, s个等式约束为例来说明。
首先是决策变量,一般的决策变量取作 n维欧氏空间 nR 中的一个点,即假设决策变量
为 ),,,( 21 nxxxx ??
nR? ;其次是目标函数,我们将目标函数取作 p个,都是决策变量 x
的函数,设为 Tp xfxfxf ))(,),(),(( 21 ? ,其中T
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示转置;最后是约束条件,实际上约束
条件是由决策变量构成的一些函数组成,其中一些为不等式,另一些为等式,对于m个不
等式, s个等式,设为 mixci ,,2,1,0)( ??? , sixhi ,,2,1,0)( ??? 。
如果所有目标都是求最小值,那么这时多目标最优化问题便可用下式描述:
T
p xfxfxfxf ))(,),(),(()(min 21 ?? (1.2.1)
?
?
?
??
??
sjxh
mixc
ts
j
i
?
?
,2,1,0)(
,2,1,0)(
.. (1.2.2)
我们称它为多目标最优化问题的数学模型。
实际上,在现实中很多问题并不是都求最小值,也可能求最大值,也可能既有求最大
值的,又有求最小值的。这些均可以通过变换得到(1.2.1)、(1.2.2)。这之中可能不含不等式
约束或者不含等式约束,甚至两种约束均不存在的情况。以后除特别声明外,总是从(1.2.1)、
(1.2.2)式出发讨论来问题[1]。
§1- 3 多目标最优化的研究方向
多目标最优化问题涉及的范围十分广泛,我们仅从以下几个方面加以阐述,
并着重介绍本文所涉猎的部分。
要研究多目标规划问题,必须先要解决如何衡量目标函数的好坏问题。因此界定多目标
最优化问题解的概念变为一首要问题。为此人们引进了各种意义下的有效解定义。例如:有
效解、弱有效解、G-真有效解、B-真有效解、Pareto较多有效解[13]等等。关于解的一般性质
的研究是很多的。对于解的存在性研究就有各种不同的方法,例如:1974 年 P.L.Yu [14]用紧
性条件在 Banach空间上的研究[15、19];1982 年陈光亚[16-17]和 1984 年 J.Jahm[18]先后用标量化
的方法来研究;此外还有用选择公理和不动点原理来研究的。对于解的最优性条件的研究主
要限于在一定的约束规格上给出一般多目标最优化的 K— T 条件。而对于解的连通性和稳定
性的研究[20、39]相对来说较少。
我们把上述关于解的概念及其性质的研究归为多目标最优化问题的第一个
研究方向。而第二个研究方向就是关于多目标最优化问题的解法。
随着研究的深入,社会经济的发展,各种大型的多目标最优化问题需要我们
去解决,而且一门科学的发展必然要为应用服务。进入八、九十年代后,随着计
算机技术的迅猛发展,各种最优化算法像雨后春笋般的出现,多目标最优化算法
也有了长足的发展。在此,特别提出的是单目标最优化算法更加成熟。从大的方
面看,多目标最优化问题的算法又大致可以分为两类,一类是直接算法、另一类
是间接算法。所谓直接算法是指:像单目标规划那样,针对规划本身直接去求解。
到目前为止,直接算法的研究还比较少,或者说只研究了几种特殊的算法,例如,
单变量多目标规划算法、线性多目标规划算法,以及可行集有限时的优序法等等。
而间接算法则指:根据实际问题的实际背景和具体容许性,在某种意义下将多目
标最优化问题化成单目标最优化问题来求解。如果细分还可以分成转化为一个单
目标问题的求解、转化成多个单目标问题求解以及非统一模型来求解。这些算法
所求的解依赖于构造单目标问题的方法,从而使得其具有一定的局限性。
多目标最优化问题的第三个研究方向是对偶理论,同单目标对偶类似,总的来说可以将
其对偶分为 Lagrange对偶和共轭对偶[1]。此外还有对称对偶以及自身对偶[21-24]。作为第四个
研究方向,我们要说一下不可微多目标规划的研究。而这主要归功于非光滑分析[25-26 ]的发
展,其直接刺激了不可微优化的研究。
当然,在当今的世界潮流中,运筹学教育和应用是非常活跃的。随着社会的
进步和科学的发展还会出现许多新的问题,新的研究方向。作为运筹学的一个分
支,多目标最优化也越来越引起人们的关注,肯定会产生许多新的研究方向,而
应用作为多目标最优化产生的“导火索”也势必成为多目标最优化的一个重要研
究方向。
§1-4 信赖域算法简介
对于一般的非线性规划问题,现有的算法大致可以分为两类。一类是线搜索
方法[2-9]、另一类就是信赖域方法[2-8]。下面将着重解释信赖域算法的由来及其基
本思想。
线搜索方法是一种传统方法,其基本思想是:给定初始迭代点,判断其是否满足收敛条
件,否则进行下一次迭代,在每次迭代中先确定下降方向,再寻找出该方向上的最优解,进
而得到下一次迭代点,然后判断其是否满足收敛条件,否则进行下一次迭代。而信赖域算法
的由来正是由于线搜索方法在解非线性规划问题(牛顿法)中遇到了下面的问题:
牛顿法的基本思想是在迭代点 kx 附近用二次函数
dGddgxfd k
TT
kk
k
2
1
)()( ???? (1.4.1)
逼近 )(xf ,并以 )(dk? 的极小点 kd 修正 kx ,得到
kkk dxx ???1 (1.4.2)
但是,这种方法只能保证算法的局部收敛性,即只有当 d充分小时 )(dk? 才能逼近 )(xf 。
为了建立算法的总体收敛性,我们在采用的一维搜索方法中,保持同样的搜索方向,而选择
一个缩短了的步长。虽然这种策略是成功的,但它有一个缺点,即没有进一步利用 n维二次
模型。信赖域算法就是基于此而提出的一种保证算法总体收敛的方法。它不仅可以用来代替
一维搜索,而且也可以解决Hessen矩阵 kG 不正定和 kx 为鞍点等困难。这种方法首先选择
一个缩短了的步长,然后利用 n维二次模型选择搜索方向。即先确定一个步长上界 k? ,并
由此定义 kx 的邻域 )( kx? ,
}{)( kkk xxxx ????? (1.4.3)
假定在这个邻域中 )(dk? 与目标函数 )( dxf k ? 一致,即二次模型是目标函数 )(xf 的一个
合适的模拟,然后用 n维二次模型 )(dk? 确定方向 kd ,并取 kkk dxx ???1 。这种方法既
具有牛顿法的快速局部收敛性,又具有理想的总体收敛性。由于步长受到使 Taylor 展式有
效的信赖域的限制,故方法又称为限步长方法。
信赖域方法的基本思想是:给定初始迭代点,判断其是否满足收敛条件,否则进行下一
次迭代,在每次迭代中有一个信赖域,它是以当前迭代点为中心的一个小邻域,并在此邻域
上求解一个子问题,该子问题的解作为试探步,用评价函数来决定是否接受该试探步,如果
接受则得到下一个迭代点,否则仍然以当前迭代点作为下一个迭代点,并确定下一个迭代点
的信赖域,进行下一次迭代。
虽然信赖域方法不如线搜索方法成熟,但是近三十年来,尤其是进入八十年
代后信赖域方法有了突飞猛进的发展,而且其应用也日益广泛。目前信赖域算法
在有约束非线性规划方面也取得了一定的结果,例如线性约束[27、28]、非线性约
束[29— 32]、等式约束[30— 34]等等。特别是信赖域方法同各种线搜索方法相结合而产
生了许多有效的求解非线性规划算法,这些算法在实际应用中也取得了很大的成
效。这主要是归于信赖域算法的强收敛性和可靠性。
§1-5 多目标规划直接算法研究现状及本文
的研究内容
1.5.1 多目标规划直接算法研究现状
到现在为止,多目标最优化问题的求解方法中的直接算法的结果还较少。只是有一些特
殊的多目标最优化问题的直接算法(在§1.3节中我们已经简单的介绍了在此就不多讲了),下
面我们将主要介绍一下一般的多目标规划的直接解法。
对于一般的多目标规划来讲其解法主要有以下几种:一、线性加权和改变权系数的方法
(这种方法只是从原则上给出求解多目标规划弱有效解集的一种途径,实际上实施起来是很
困难的)[1];二、合适等约束法(这种方法的基本思想是在多目标规划的约束集上再添加 1?p
个等式约束 1,,2,1,)( ??? piaxf ii ? ,其中诸 ia 为常数;然后在新的约束集合上求解极
小化问题 )(min xf p ,当诸 ia 满足一定的条件时,所求得的最优解就是多目标规划的有效解。
其实质是:逐步去掉不可能成为有效解的解,最后留下的就是有效解的全体)[35];三、自适
应法(这是一种求有效解的逼近算法) [36 ]。
1.5.2 本文的研究内容和主要结论
本文所做的主要工作是:通过对一般多目标最优化直接算法的研究,并在此基础之上结
合信赖域方法给出求解一般多目标最优化问题的直接算法。我们将之称为多目标规划的信赖
域算法(Multiobjective Programming Trust Region Algorithm),简记为MPTR算法。特别
指出的是,本文从简单到复杂、从无约束到有约束给出了几个MPTR算法。
在第一章中,我们主要讲述多目标最优化问题的由来、数学模型、研究方向;
信赖域算法的由来、基本思想、现状;以及多目标最优化直接算法的研究现状和
本文所作的主要工作。
在第二章中,为了后面算法的需要给出了多目标规划的基本定义、有效解(弱有效解)
的定义、关于凸多目标规划的有效解(弱有效解)的性质一些基本定理(其中大部分是我们提
出的,即那些没有给出参考文献的定理及推论)以及后面要用到的一些基本算法。
在第三章中,给出了不可微的凸多目标规划的信赖域算法,提出了多目标规划的信赖域
子问题,证明了该算法的收敛性,并给出了一个简单算例。
在第四章中,我们在第三章的不可微的理论基础之上,分别给出了可微情况下 Slater
条件下和一般条件下的凸多目标规划的信赖域算法,并通过两个简单算例比较了所给出的多
目标规划信赖域算法同间接求解一般的无约束多目标规划算法的优越性。
第五章为总结部分,主要给出了本文中所给出的算法的不足、改进建议以及多目标规划
信赖域算法的可能的几种研究方向。
第二章 预备知识
本章中,为了后面的需要将给出凸多目标规划的基本定义、有效解(弱
有效解)的定义、关于凸函数的一些基本性质以及利用次梯度和次微分给出
的凸多目标规划的有效解(弱有效解)的充分性条件以及后面要用到的一些
基本算法。
§2-1 基本概念及基本定理
多目标规划及其有效解(弱有效解)在文献[1]中有较为详细的论述,我们在
此仅仅给出其基本定义。
定义 2.1.1[ 1 ] Tp xfxfxfxf ))(,),(),(()(min 21 ?? (2.1.1)
n
T
s
T
m Rx
xhxhxhxh
xcxcxcxc
tsCVP ?
??
?
?
?
??
??
0))(,),(),(()(
0))(,),(),(()(
..)(
21
21
?
?
(2.1.2)
其中 )(xf i (i=1,2,3,⋯,p)和 )(xc i (i=1,2,3,⋯,m)分别为凸函数和凹函
数, )(xhi (i=1,2,3,⋯s)是线性函数。记 },0)(,0)({
nRxxhxcx ????? ,容易验证 ? 是
一个凸集。我们称(CVP)为一般的凸多目标规划问题的数学模型,将上述模型简记为:
)(min)( xfCVP
x ??
(2.1.3)
当 1?p 时,(CVP)就是通常的凸规划(单目标)。今后我们总假设 2?p 。在此指出
其Lagrange函数为:
)()()(),,,( xhvxcuxfvuxL TTT ??? ?? (2.1.4)
其中 smp RvRuR ??? ,,? 称为 Lagrange乘子。以后,我们称向量函数
)(),(),( xhccxf 不可微、凸等均指函数的每一分量函数为不可微、凸等等。
定义 2.1.2[ 1 ] 设 ???x ,如果不存在 ??x 使得
)()( ?? xfxf 或( )()( ?? xfxf ) (2.1.5)
成立,则说 ?x 是(CVP)的有效解(或弱有效解)。
定义 2.1.3[ 1 ] 设 ???x , 若 存 在 *x 的 一 个 ? >0 邻 域 )( *x? , 记
)( *x? =? ???? *xxx ,使得不存在 ?? ?)( *xx ? 使下式成立:
)()( ?? xfxf (或 )()( ?? xfxf ) (2.1.6)
则称 *x 是(CVP)的关于 )( *x? 的局部有效解(或弱有效解)。
定义 2.1.4[ 1 ] 设 ???x ,若存在 smp RvRuR ??? *** ,,? ,使
0),,,( **** ?? vuxLx ? (2.1.7)
0)( ** ?xcu T (2.1.8)
0,0 ** ??? u? (2.1.9)
同时成立,则称 *x 是凸多目标规划问题(CVP)的一个 Kuhn-Tucker点,简称 K-T点,式
(2.1.7),(2.1.8)和(2.1.9)为K-T条件。
定理 2.1.5 对于凸多目标规划问题(CVP),其局部有效解(或弱有效解)也是其有效
解(或弱有效解)。
证明 设 *x 是(CVP)的关于 )( *x? 的局部有效解,则由定义可知,不存在
?? ?)( *xx ? ,使得
)()( ?? xfxf (2.1.10)
成立。
令y是? 中任一点,对于充分小的? >0,0 <1,就有
???? ?)()1( ** xyx ??? (2.1.11)
从而
)())1(( ** xfyxf ??? ?? (2.1.12)
不成立。
由于 )(xf 为凸函数,故而有
)()()1())1(( ** yfxfyxf ???? ????? (2.1.13)
将式(2.1.12)与式(2.1.13)相结合,有
)()()()1( ** xfyfxf ??? ?? (2.1.14)
不成立。
整理式(2.1.14),有
)()( *xfyf ? (2.1.15)
不成立。
由 y的任意性可知 *x 是(CVP)的有效解。同理可证当 *x 为弱有效解的情形。
定义 2.1.6[ 7] 设 )(xf 为在凸集 nRD ? 上定义的凸函数, Dx ?* ,称使
sxfsxf T???? )()( ** )( * Dsx ??? (2.1.16)
成立的任何 nR?? 为 )(xf 在 *x 处的次梯度,又称在 *x 处的全体次梯度集合为 )(xf 在 *x
处的次微分,并记作
})()(,{)( *** sxfsxfRxf Tn ??? ?????? )( * Dsx ??? (2.1.17)
定理 2.1.7 设 )(xf 为在凸集 nRD ? 上定义的正常凸函数,则 )(xf 在D上连续。
证明 我们用反证法来加以证明。设 Dx ?* 为 )(xf 的不连续点。由多元连续的定义可
知,必存在以 *x 为极限的点列 Dxxx k ?,...},...,,{ 21 使得
)()( *xfxf k ? )( ??k (2.1.18)
不成立。我们不妨设
bxf k ?)( )( ??k , axf ?)( * , (2.1.19)
其中 ab ? 。
由极限的定义可知,对于 0?? ? ,必存在正整数K,使得当k>K时, ??? bxf k )( 。
对于点列 },,{ 1 ??KK xx ,其中必存在点 Dx M ? 和 121 ,, ?KnKK xxx ? ,(取n个点是因为这
是在n维空间中)使得
*11
2
2
1
1 ... xxxxx n
Kn
n
KKM ???? ????? ?? , (2.1.20)
其中 1?? i? , 10 ?? i? , (由高等代数的知识可知这是可以做到的),这时
??? ?????
?
?
bxfxxf Mn
Ki
n
i
i )()(
*
1
1
, (2.1.21)
anbxfxf n
n
i
in
Ki
n
i
i ????? ????? ??
?
?
?
?
)1()()(
1
1
*
1
1
)()1( abnb n ????? ?? (2.1.22)
显然当 0?? 时式(2.1.21)大于式(2.1.22),这与凸函数的定义矛盾,定理结论成立。
定理 2.1.8 设 )(xf 为在凸集 nRD ? 上定义的凸函数,并且是 Lipschitz的,则对任
何 Dx ? , Dh ? , 1?h ,
t
xfthxf
hxf
t
)()(
lim);(
0
??
?
??
? , (2.1.23)
t
xfthxf
hxf
t
)()(
lim);(
0
??
?
??
? (2.1.24)
都存在,且
);();();( hxfhxfhxf ???? ??? ??? 。 (2.1.25)
它们分别称为 f 在 x点沿方向h的右导数和左导数。如果
);();( hxfhxf ?? ? ?? (2.1.26)
即
t
xfthxf
hxf
t
)()(
lim);(
0
??
?
?
? (2.1.27)
存在,那么 );( hxf? 称为沿方向h的导数。
证明 由定理 2.1.7及本定理假设可知函数 )(xf 是 Lipschitz连续的,容易证明式
(2.1.23)和式(2.1.24)极限都存在且有限,因此, 函数 )(xf 在 x上沿方向 h的右导数和左
导数都存在。
定理 2.1.9 设 )(xf 为在凸集 nRD ? 上定义的凸函数,并且是 Lipschitz的,则对任
何 Dx ? , Dh ? ,
hghxf T
xfg )(
max);(
??
? ?? (2.1.28)
hghxf T
xfg )(
min);(
??
? ?? 。 (2.1.29)
关于这个定理的证明可以参看任何有凸集及凸函数性质的书。
为以后需要,我们把定义2.1.4中的式(2.1.7)中的梯度用某一次梯度来代替时我们得
到次微分意义下的K-T条件。定义如下。
定义 2.1.10设 ???x ,若存在 smp RvRuR ??? *** ,,? ,使
0),,,( ***** ?? vuxLx ? (2.1.30)
0)( ** ?xcu T (2.1.31)
0,0 ** ??? u? (2.1.32)
同时成立,其中式(2.1.30)中的 ),,,( ***** vuxLx ?? 表示 Lagrange式的某一次梯度,只要
存在一个即可。则称 *x 是凸多目标规划问题(CVP)的一个次微分Kuhn-Tucker点,简称次
微分K-T点,式(2.1.30),(2.1.31)和(2.1.32)为次微分K-T条件。
定 理 2.1.11 对 于 凸 多 目 标 规 划 问 题 ( CVP ),若 存 在
???x , smp RvRuR ??? *** ,,? 使得 *x 满足次微分意义下的 K-T条件即式
(2.1.30),(2.1.31),(2.1.32),即 *x 为次 K-T点,那么, *x 是(CVP)的有效点(或弱有效
点)。
证明 我们先就单目标情况加以分析,不妨设目标函数只有 )(0 xf 。
设 x是满足式(2.12),即 ??x 的任一点,于是
??
??
???
s
j
jj
m
i
ii xhvxcuxfxf
1
*
1
*
00 )()()()( (2.1.33)
将次微分的性质应用于函数 0f , ic , jh ,并利用上式,我们得到
?
?
?????
m
i
ii
T xcuxfxxxfxf
1
***
0
**
00 )()()()()(
??
??
????
s
j
jj
m
i
T
i xhvxcxxu
1
**
1
**** )()()(
?
?
???
s
j
j
T
j xhxxv
1
**** )()( (2.1.34)
重新排列上式,就得到
??
??
???
s
j
jj
m
i
ii xhvxcuxfxf
1
**
1
***
00 )()()()(
?
?
?
?
?
?
??????? ??
??
s
j
jj
m
i
ii
T xhvxcuxfxx
1
***
1
****
0
** )()()()( (2.1.35)
由已知条件便可得到
)()( *00 xfxf ? 。 (2.1.36)
下面我们再考虑多目标的情形。
我们构造单目标规划
*)( ?SP )(min
* xf
T
x
?
??
, (2.1.37)
其中 0
*
?? 。因为 )(xf 是凸向量函数, 0
*
?? ,故知 )(* xf
T
? 也是凸函数,因此将 *)( ?SP
应用上面的证明,我们可以得出定理的结论。
这个定理给出了非光滑凸多目标规划的有效解(或弱有效解)的充分条件。
§2-2 基本算法简介
下面我们给出本文中将要用到的几个基本算法。
算法 2.2.1(单纯形算法(Simplex算法))
单纯形算法是应用于求解线性规划问题的基本算法,本文中将利用此算法求解出线性方
程组的解。在此我们以极小化问题为例给出该算法。具体算法及细节详见参考文献[3]、[4]、
[5]、[6],首先设初始基为 B,然后计算下列几个步骤:
1. 解 bBx B ? ,求得 bbBxB ??
?1 ,令 0?Nx ,计算目标函数值 BB xcf ? 。
2. 求单纯形乘子 w,解 BcwB ? ,得到
1?? Bcw B 。对于所有非基变量,计算判别
数, jjjj cwpcz ??? 。令
jj
nIj
kk cwpcz ???
?? },,2,1{
max
?
(2.2.1)
若 0?? kk cz ,则对于所有的非基变量 0?? jj cz ,对应基变量的判别数总是零,因此停
止计算,现行基本可行解是最优解。否则,进行下一步。
3. 解 kk pBy ? ,得到 kk pBy
1?? ,若 0?ky ,即 ky 的每个分量均非正数,则停止
计算,问题不存在有限最优解。否则进行4.。
4. 确定下标 r,使得 }0min{ ?? ik
ik
i
rk
r y
y
b
y
b
, Brx 为离基变量, kx 为进基变量。用
kp 替换 Brp ,得到新的基矩阵 B,返回步骤1.。
对于极大化问题,可给出完全类似的步骤,只是确定进基变量的准则不同。对于极大化
问题,应令
jj
nIj
kk cwpcz ???
?? },,2,1{
min
?
(2.2.2)
算法 2.2.2(逐步二次规划算法)[2,8]
在此,我们给出求解约束非线性规划问题的一个逐步二次规划方法
(Wilson-Han-Powell方法)。对于约束非线性规划
?
?
?
???
??
?
mmixc
mixc
ts
xf
ei
ei
Rx n
,,1,0)(
,,2,1,0)(
..
)(min
?
?
)5.2.2(
)4.2.2(
)3.2.2(
我们给出如下的算法:
步1 给出初始点 1x , 0?? , 0?? ,
nnRB ??1 , 1?? ,令 1?k 。
步2 求二次规划问题
?
?
?
???
???
?
?
Iixcdx
Eixcdx
ts
dBddg
ki
T
ki
ki
T
ki
k
TT
k
Rd n
,0)()(
,0)()(
..
2
1
min
?
?
)8.2.2(
)7.2.2(
)6.2.2(
的解 kd 。如果 ??d 则算法结束,求 ],0[ ?? ?k 使得
kkkkkk dxPdxP ????? ?? ???? ?? ),(min),( 0 )9.2.2(
其中
T
kkmkkk xcxxxxA )()](,),(),([)( 21 ??? ??? ? , )()( kkk xfxgg ???
},,2,1{ emE ?? , },,2,1{ mmmI ee ???? ,
nn
k RB
?? 。
步3 令 kkkk dxx ????1 ,计算 1?kB ; 1?? kk ,转步2。
对于上面的算法作如下的说明:
1. 在(2.2.9)中,罚函数 ),( ?xP 是 1L 精确罚函数
),( ?xP )()()( )(
1
xcxf
m
i
ik
?
?
??? ? )10.2.2(
其中 ik )(? 0? , )(
)( xc ? 及罚系数 ik )(? 分别由下面的式子所定义:
mmixcxc
mixcxc
eii
eii
,,1)},(,0min{)(
,,2,1),()(
)(
)(
?
?
???
??
?
?
)12.2.2(
)11.2.2(
1,,,2,1]},)()[(
2
1
,)(max{)(
,,2,1,)()(
1
11
????
??
? kmi
mi
ikikikik
ii
?
?
????
??
)14.2.2(
)13.2.2(
k? 是一非负数列且满足?
?
?
???
1k
k? 。
2. 记 k? 为(2.2.6)—(2.2.8)的Lagrange乘子,其定义为:
Iidxxc
Ii
xAdBg
k
T
kikiik
ik
kkkkk
???
??
??
,0])()([)(
,0)(
)(
??
?
?
)17.2.2(
)16.2.2(
)15.2.2(
3. 关于上述算法中 1?kB 的计算,我们取
k
T
k
T
kk
kk
T
k
T
k
T
kkk
kk ys
yy
sBs
BssB
BB ????1 )18.2.2(
其中
?
?
?
??
?
?
?? ?
否则。
如果
,)1(
,2.0,
1
kkkkk
kk
T
kk
T
kk
k
kkk
sBy
sBsysy
y
xxs
??
)21.2.2(
)20.2.2(
)19.2.2(
这里 ?
?
?? ??????
m
i
kikiikkkk xcxcggy
1
11 )]()([)(? ,
k
T
kkk
T
k
kk
T
k
k yssBs
sBs
?
?
8.0
? 。
算法 2.2.3(罚函数法(Penalty Function Method))
罚函数法是解带约束非线性规划问题的一种行之有效的方法,其中包括外罚
函数法和内罚函数法(又称障碍罚函数法)两种,这里我们只对带等式约束和不
等式约束均有效的外罚函数法加以介绍。
考虑约束问题:
)(min xf
.,,2,1,0)(
,,,2,1,0)(..
sjxh
mixcts
j
i
?
?
??
??
)22.2.2(
其中 ),,1)((),,,1)((),( sjxhmixcxf ji ?? ?? 是
nE 上的连续函数。
罚函数法的基本思想是,利用目标函数和约束函数组成辅助函数
)()(),( xPxfxF ?? ?? )23.2.2(
),( ?xF 具有这样的性质:当点 x位于可行域以外时, ),( ?xF 取值很大,而且离可行域越
远其值越大;当点在可行域内时,函数 )(),( xfxF ?? 。这样,可将原来的问题转化成关
于辅助函数 ),( ?xF 的无约束极小值问题:
)()(),(min xPxfxF ?? ??
?
)24.2.2(
在极小化过程中,若 x不是可行点,则辅助函数中的第二项 )(xP? 将取很大的正值,其作用
迫使迭代点靠近可行域。因此求解问题 )24.2.2( 能够得到约束问题 )22.2.2( 的近似解,而且
? 越大,近似程度越好。通常将 )(xP? 称为罚项,? 称为罚因子, ),( ?xF 称为罚函数。
罚函数可以有不同的定义方法。 )(xP 的一般形式为:
? ?
? ?
????
m
i
s
j
ji xhxcxP
1 1
))(())(()( )25.2.2(
? 和? 是满足下列条件的连续函数:
当 0?y 时, 0)( ?? y ;
当 0?y 时, 0)( ?? y 。
当 0?y 时, 0)( ?? y ;
当 0?y 时, 0)( ?? y 。
实际计算中,罚因子的选择很重要。如果? 太小,则罚函数的极小点远离约束问题的
最有解;如果? 太大,则给计算增加困难。一般是取一个趋向无穷大的严格递增正数列 ? ?k? ,
从 1? 开始,对每个k求解无约束问题:
)()(min xPxf k?? )26.2.2(
得到极小点的序列? ?kx ?* ,在适当条件下,这个序列收敛于榆树问题的最优解,如此通过求
解一系列无约束问题来获得约束问题最优解的方法称为序列无约束极小化方法,简称为
SUMT方法。
计算步骤:
(1) 给定初始点 0x ,初始罚因子 1? ,放大系数 1?c ,允许误 0?? ,置 1?k 。
(2) 1?kx 为初点,求解无约束问题 )26.2.2( ,设其极小点为 kx 。
(3) 若 ?? ?)( kk xP ,则停止计算,得到点
kx ;否则,令 kk c?? ??1 ,
并置 1?? kk ,返回(2)。
算法 2.2.4(信赖域算法(TR算法))
绪论中我们已经简单的介绍了信赖域算法,在此我们将给出单目标规划的信
赖域算法模型。
步1 给出初始值 1,0, 11 ???? kRx
n ;
步2 判断 kx 是否满足收敛条件,若满足则算法结束,否则计算一个满足 kkd ??
的试探步 kd (其中 ? 为范数运算,可以是 ?2 范数, ?1 范数, ?? 范数。);
步3 如果 kd 满足某种下降条件,则置 kkk xdx ???1 ,否则,令 kk xx ??1 ;
步4 以某种方式给出 1,1 ??? ? kkk ,转步2。
在上述算法中 k? 称为信赖域半径,一般试探步 kd 的计算是在信赖域 }|{ kdd ?? 上
求解原优化问题的逼近问题,常常称之为信赖域子问题。在此我们以拟牛顿法为例来说明 kd
的求法。
在线搜索方法中,拟牛顿法的搜索方向 kkk gBd
1??? 可视为
dBddg k
TT
k
Rd n 2
1
min ?
?
(2.2.27)
其中( ? ?kkkk xfBxfg 2),( ???? )的解。基于此,对于无约束优化问题 )(min xfnRx? 的信赖
域子问题(拟牛顿型)可取为:
dBddgd k
TT
kk
Rd n 2
1
)(min ??
?
? (2.2.28)
kdts ??.. (2.2.29)
其中 )(dk? 就是此时原优化问题的逼近问题。
对于 kd 应满足的下降条件,以及 1?? k 是如何给出的,将在此做一些简单的说明。取 kd
为信赖域子问题的解,则
)()0(Pr ded kkk ?? ?? (2.2.30)
是目标函数的预估下降量,因为我们有 )()( dxfd kk ??? 。目标函数的真实下降量为
)()( kkkk dxfxfAred ??? (2.2.31)
真实下降量与预估下降量的比值为
k
k
k ed
Ared
r
Pr
? (2.2.32)
比值 kr 对 1?kx 以及 1?? k 的选取起关键性的作用。粗略的讲, kr 越大说明目标函数下降的越
多, )(dk? 越逼近 )( kxf ,新的迭代点 kk dx ? 也越好,故将 1?kx 取为 kk dx ? ,而且 1?? k 也
可以考虑扩大;否则, kr 越小说明目标函数下降的越少,甚至上升, )(dk? 逼近 )( kxf 的
程度越小,新的迭代点 kk dx ? 也越差,故将 1?kx 仍取为 kx ,且 1?? k 相应的考虑缩小(例如
当 0?kr 时, )()( kkk xfdxf ?? ,显然 kk dx ? 不如 kx ,故 1?kx 应仍取为 kx 。
信赖域算法的关键组成部分之一就是试探步 kd 的计算,即是对于信赖域子问题的求解。
关于信赖域子问题的求解有许多方法,其思想是将二次规划子问题同信赖域技巧结合起来,
并利用二次规划方法来求解该子问题。其中比较典型的有零空间方法[31、34]、CDT子问题[37、38]、
Powell—Yuan方法[33](以上的方法均是对于等式约束问题来讲的)等等。
关于信赖域算法的更详细的论述可详见参考文献[2]、[8]、[27~38、40~60 ]等等。本
文所给出的信赖域算法是将此思想同多目标规划的解的特征相结合而给出的。在这儿我们需
要特别指出的是:信赖域算法的两个要点(实际上这也是所有优化算法的两个要点)所在,第
一收敛准则的给出,第二试探步 kd 的求取以及信赖域半径 1?? k 的选取,而其关键就是第二
步。所谓信赖域,我认为就是在 }{ kdd ?? 这个超球内所给出的逼近问题与原问题的逼近
程度是否可以接受。
第三章 非光滑凸多目标规划信赖域算法
在本章中,我们将给出非光滑凸多目标规划的信赖域算法,提出其信赖域子问题,并
证明该算法的收敛性。
§3-1 基本概念及基本定理
为了对非光滑问题加以处理,在本节中我们将给出一些基本概念和基本定理
作为预备知识。
定义 3.1.1 对于定义域为 n 维空间的函数 )(xf ,设其自变量为 ),...,,( 21 nxxx ,
我们称只有第 i )1( ni ?? 个分量为 1,而其他分量均为 0的向量为 ix 方向。
定义 3.1.2 设 )(xf 是定义于凸集 nRD ? 中的 Lipschitz凸函数,那么我们分
别称
? ?);(),...,;(),...,;(),;()( 21 ni xxfxxfxxfxxfxf ????? ?? ???? (3.1.1)
? ?);(),...,;(),...,;(),;()( 21 ni xxfxxfxxfxxfxf ????? ?? ???? (3.1.2)
为函数 )(xf 在点 Dx ?? 的右梯度和左梯度。
由第二章的知识可知,对于定义于凸集 nRD ? 中的 Lipschitz凸函数是连续
的,而且沿任何方向都存在有限值的左,右方向导数,所以以上所定义的左梯度
和右梯度是存在的,而且当函数在 x可微时左梯度和右梯度相等,也就是我们通
常所说的梯度,我们将其记为 )()()( xfxfxf ?? ????? 。
为了能用已有的知识来解决非光滑凸多目标规划问题,我们首先给出以下几
个引理及定理,为了证明的方便,我们假设以下几个引理均是在一维的情况,而
多维的情况我们只要加以推广即可。
引理 3.1.3 (类费尔马定理)
若(1)函数 )(xf 在点的某邻域 ),( 0 ?xO 内有定义,并且在此邻域内恒有:
)()( 0xfxf ? (此时 0x 为局部极大值点), (3.1.3)
或者
)()( 0xfxf ? (此时 0x 为局部极小值点); (3.1.4)
(2)函数 )(xf 在点 0x 左,右可导。
那么则有:
)(0)( 0
'
0
' xfxf ?? ?? (此时 0x 为局部极大值点), (3.1.5)
或者
)(0)( 0
'
0
' xfxf ?? ?? (此时 0x 为局部极小值点)。 (3.1.6)
引理 3.1.4 (类拉格朗日定理)
若函数满足:
(1) 在闭区间? ?ba, 内连续;
(2) 在开区间? ?ba,