（应用数学专业论文）非光滑优化与多目标规划算法的研究.pdf

谣安建筑科技大学硕士学位论文 非光滑优化与多目标规划算法的研究 专业：应用数学 硕士生：张俊敏 指导教师：徐裕生教授 摘要 本文旨在获得种求解非光滑优化特殊问题分片光滑问题的新算法，并将其应用于务 目橱规划形成种新的极小极大法。为此，首先研究了非光滑优化的算法及其分类，指出了 各种基本算法的优缺点。在此基础已提出了种求解非光滑优化问题的新思路，形成了新算 法。然后，在研究了多目标规划的算法及其分类后，将新算法应用于多目标规划，形成一种新 的极小极大法。最后，对所提出来的算法进行了数值实验。全文共分五章，内容如下： 第0 章介绍了非光滑优化与多目标规划问题的产生、发展、应闻及目前研究的状况，另 外还指明了非光滑优化与多目标规划的关系； 第1 章介绍了非光滑优化与多目标规划的问题、基本撅念及基本理论。主要是凸分析中 不可微的几种微分概念及有关结论，以及多目标规划中的各种解的概念和相关理论： 第2 章本章是全文的关键部分。研究了非光滑优化问题的两类基本算法：次梯度法和 b u n d l e 法，指出了多种算法的优缺点。在此基础上，着重提出了求解分片光滑函数优化 问题的新算法，给出了新算法的步骤及几种实现方式，也列新算法的收敛性作了说明，并 将新算法与次梯度法和光滑晟速下降法的关系做了分析： 第3 章研究了多目标规划的基本算法，将其按求解过程中决策者参与的情况分为四大类： 无偏法；前部法；后都法；交互法。并将第2 章提出的新算法应用于多目标规划，得到一 种新的极小极大法； 第璋对第2 章所提出的新算法作了数值实验。方面将新算法的收敛速度与其它几种 经典算法进行了比较；另方面，分别从数值结果和图形演示俩个方面对新算法的收敛性、 稳定性作出检验。 关键词；非光滑优化；多目标规划；分片光滑；极小极大法：数值实验 西安建筑科技大学硕士学位论文 r e s e a r c ho nm e t h o d sf o rn o n s m o o t ho p t i m i z a t i o na n d m u l t i o b j e e t i v ep - - 删i n g s l 她u l t y ：a 删m a l t z e m a l l e s n a m e ：刁i a 耀j n r a i n b 蝤如卫d n e p r o t x u y u s b e n g a b s i r a c t t h ep 印口a i m st oo b t a i n e dad wm e t l x x l 姗as p e c i a ln o 耐i f f e r e t r t i a b l ep r o b l e m ，p i e c e w i s e s m o o t h 蝴, a n d p l , l y s i t t o m l | l d 喇吐v cp l 。雩驷m i g 协g e t a i l m m i n m a e m c t h o d f o r t h e p r o p o s e , t h er a m h0 1 1t 1 1 em l 出l o d sa n dt h ed a s r , i f i e a l i o mo fn s m o o t ho p t i n - , i z a t i o n , w i t ht h e i ra d - v a n t a g e sa n dd i 霸小吐a g c sc o m m e n t e d , i sn e e d e d o nt h ei m t s , al i d e a 0 t ls o l v i n gn o n d i f f e r e n t i - a b l ep m b e n - bi sb r o u g h tf d r w a r da n dt h e nt h en c wm e t h o di sp r e s e n t e d a f t e rt h er e s e a r c ho nt h e m c l l 脚sf o rm 1 t i o b j e c d v ep l o 即m m m 昌a n e wm j m t o o h o df o rm u l t i o t j e c t i v ep r o 鲫n m i n gi s p m d c e db yt h ea p p l y i n go ft h el w wm e t h o c l tt h ee n 血j m p o l t a n tn u m e r i c a le , x p e , r i e n c ei sm a d et o s h o w t h e a e h i c v c m e l a t o l t h e n w m e t e t h e p a p e r t s d i v i d e d i n t o f i v e c h a p t e r , a s f o l l o w s ： 血t h e f i r s t 曲a p 自骂f b c h t s t o r y o f t h e b o t h p r o b l a b o v e i sr e v e a l e d a n d t h er d a t i o m h i pb c 眦e r i 】m i s p o i n t e d o u t t h es e c o n d 曲a p 时m a i n l yp r e s e n t st h eb a s i cc 0 e p 担a n dt h e o r i e s , w h i c ha r cr e l a t e dt o 1 v e x a n a l y s i s ，r t s m o o t h d i t f e r e n t i a b l e t h e o r y a n d k i n d s o f , s o l u t i o n s o f m u l t i o b j e c t i v e p r o g r a m m i n g n e t h i r dc h a p t e r i s d e v o l e d t o t h ec r u c i a l p 眦o f t h e p a p t w o c 妇o f b a s i c m 砒l o d s f o rr t o n - s m o o t h o p t i m i z s f i o n , s u b g r a d e n t m e o l a d a n d b u n d e 月i e d 白d a r e 删d u r i n g t h ec o u r s e , t h ea d - v 蝴g 骼a a d 幽鞠小嘲妇盼a mo o r 加a e t e d 锄，w 城c hh i 咿1 1 3al 跚i d e a 幻s o l v et i l ep i e c e w i s e 姗删s u b s c q u m t l yan wa l g o r i t l m ai s 曲妇h l e dw i t hs e v e r a lw a y st oi m p l e m e n t m o r e o v e r , t h ec o m 罾m o ff i l en e wr l l c t h o di ss h o w na n dt h er e l a l i o n s h i pb e t w e e nt h et w od a e so fb a s i c m e t h o d s a n d t h e n w r r t e l h o d i sr e f e r r e d t o n m e t h o d sf o rm u l t i o b j e c t i v ep r o g r a m m i n ga f cc o n s i d e r e di nc h a t ) t e rf o u r a c c c , r d i a gt ot h e p a r i i d p a d o 璐o ft h ed e c i s i o n m a k e r , t h ei n c t h t ) d sm d i v i d e di n t of o u rg r o u p , n op r e f e r e n c em e t h o d s ， p o s t e r i o r im 酬1 吨i 酬m e t h o d s , i m c m c t i ”em e t h o d 8 w i t ht h eb e l po ft h en e wm e t h o di nc h a p t e r t 1 1 i i d o n c c a n g c t a n e w m i n m a x a l g o r i t h m t h el a s t 曲a p 嘧o o n c e 删a a l e s t h ea u m e f i e a l 咖w i t ht h er e s u l t s , t h ep a p e rc o m p a r e st h e l l e w a l g o r l t t m a w i t h s e w m a l c l a m i c a la l 鲫t b m s o n t h e c o n v e r g e a c er a t e o a t h e o t l a e r h a n d , w i t h f i g u r e s a n da n o t h e r n u m e r i c a lr e s u l t s ，t l a e p a p e r t c s l s t h e c o n v e r g e a e e 锄d t h e s t a b i l i t y o f t h e n e w m e t h o d k e y w o t d l s ：n 叫圈n 啪q 砌m i z a 酏珥m u t t i o a j e e l i v ep l d 日锄m i d 岛p i e 础 w i s es m i t h ，m i n m a x m e t h o d , n u m e r i c a le x p e r i e n c e 声明 y8 4 1 5 8 0 本人郑重声明我所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含本人或其他 人在其它单位已申请学位或为其它用途使用过的成果。与我一同工作的同 志对本研究所做的所有贡献均己在论文中作了明确的说明并表示了致谢。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名 p 伍札 关于论文使用授权的说明 日期： 。审j j 扣日 本人完全了解西安建筑科技大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布 论文的全部或部分内容，可以采用影印、缩印或者其它复制手段保存论文。 ( 保密的论文在论文解密后应遵守此规定) 论文作者签名： 注：请将此页附在论文首页。 导师魏7 轴斑噍秭卅f 。a 塑童堡堡坠垫奎兰堡圭童堡垒塞 第0 章引言 0 1 问题的产生、发展及应用 在g b d a 地畦提出线性规划单纯形法的第= 年，也就是1 9 4 8 年，a t u c k e r 同 h 碌l b l l ，d - g a l c 就开始了对非线性规划的研究。这一理论的初步形成约在1 9 5 1 年，其标志是与 f r j 坛- j o l m 条件( 1 9 4 8 ) 相关的k u h n - t u c k e r 条件的提出。非线性规划是最优化问题中的重要 类。由于受至q 数学分析工具的限制，6 0 年代前的非线性规婀究不自觉地假定所涉及的函数 是平滑的，但实际中的问艇却不总是平滑的，凸规划( m n v e xp r 唧a m m l n g ) 理论首先打破了 这一限制，对数学分析的微分理论作了推广，从而开始了非光滑规划的研究。但是只对凸的情 况下的非光滑规划的研究还不能满足实际的需要，因而进。步开展了对非凸规化的研究。近三 十年来，非光滑规划为许多学者所关注，其中r o c k f d l a r 、c l a r k e 属于这领域领军人物。而 非光滑优伲的应用主要在控制、经济、金融及非线性规划的几乎所有领域。 早在1 7 2 年，h a 玎l d j n 就提出了多目标问题矛盾如何协调的问题。1 8 8 3 年，c o u n m t 从经 济学角度提出了多目标闻题的模型，1 8 9 6 年，p m 协首次从数学角度提出了多目标最优决策问 题。1 9 4 4 年，b nh m mh 对镱论角度奠定了经济行为理论的基础。1 9 5 1 年，l ( 0 唧a n s 从再生产和分配问题中提出有效向量的概念，与此同时，i r m l m 等人给出了向量极值问题有效 解的必要条件。1 9 5 3 年，a r l m r 等人提出了有效点的 9 e 忿。至此，多目标规划逐渐受到人们的关 注。但就学科而亩。多目标规划起源于在经济学中f ：硼巳d 群w 删瞄1 9 7 4 ) 和v v a r e t o ( ：9 0 6 拱于均 衡竞争和经济福利的研究以及在数学中g c m 科1 8 9 分和f 鹕d o r 厨1 9 0 6 ) 的有序空闾理论的 建立，从5 0 年代宋到6 0 年代末，o 臁s ，k 龇妯，z a d c h ，i n 舸，p o l 如e e r _ i ：l c y ，c m o 伍d o n 等人先后作出了较有影响的工作。自1 9 7 2 年y u 提出了支配结构等重要概念后，多目标规划理 论的研耀是引a 拄日。从7 0 年代中期起，每年都有若干个以多目标决策或多目标规划为题 的国际性学术会议召开。越来越多的人在致力于把多目标决策作为工具去解决经济、管理、t 程、军事和社会等领域中出现的复杂问题。而且多目标规匀j 理论中的不少问题不仅刺激了运筹 学中其他分支的研究，也为这些分支的理论研究提供了新的思路、新的方法和广泛的应用前景。 也就是宣到上个世纪7 珥8 0 年代，经过众多学者的共同努力才使它成为应用数学的一个新的学 科分支。与其相关的成果可参阅文 1 1 2 l 文 2 。在这蘸个文献中对效用理论、对策论、序关系 和向量范数的数学研究、线性生产理论和非线性规划基础知识以及多目标规划历史做了阐述。 仅从1 9 8 6 - 1 9 9 5 年约有5 0 0 篇文章研究了多目标规扭睦不同领域的应用，覆盖了关于军事、农 业、银行业、健康保护、能源、s f _ _ q k 、水资源与野生动植物保护等。毫不夸张地说多目标规 西安建筑科技大学硕士学位论文 划已成为运筹学的重要分支。 对非光滑优化的研究主要集中在三个方面：1 ) 基础理论的研究。包括凸分折、非线性分 析等；2 ) 优化理论的研究。主要包括各种最优性条件的研究、算法收敛性的研究等；3 ) 对方 法的研究。主要分为n 4 ；k - 类：次梯度法和捆绑( b u l l a l e ) 法( 详情见第二章) ，主要集中在文 【3 1 。值褥注意的是，现在已有利用菲光滑函数的结构特点寻求新算法的成果，见文【4 】一【6 】。 随着其应用理论基础及算法的快速发展，这领域网益呈现出其活力，星现三个特点； 第一非光滑优化问题范弱组广。不仅包括目标和约束函数不可微的优化问题，而目 包括那些目标和约束函数是一阶可微但不是二阶可微的问题。此外非光滑变分 不等式问题、半定规划、非光滑方程、集值问题、双层规划等均在非光滑9 t h s 范围之列。而这样宽广的范围也使得解析工具和算法有了广阔的应捌e 第二非光滑分析的迅速发展。非光滑分析起源于凸分析，现在也包括广义二阶微分， 集值分析，广义凸性和其他许多论题。一方面，非光滑分析现在自身就是一门 学科，另一方面，它源源不断地为非光滑优化提供了有力的工具。 第三非光滑优化新算法的发展。这一领域，从收敛性分析到数值执行都重新焕发出 壮观的场面。 对多目标规划的研究主要集中在三个方面；1 ) 基础理论的研究。包括集值分析、序的理 论、非线性分析等：2 ) 优化理论的研究。主要包括各种最优性条件的研究；3 ) 对方法的研究。 按决策者在求解过程中的参与情况可分为：无偏好法，前部法，后都法，交互泫。文研【8 】均 对多目标算法作了较详尽的介绍。 多目标规划一般可分为两类；娄是不确定性韵，如模糊目标规划、随机规划、进化算 法等：一类是确定性的，如第四章提到的所有算法。 若按线性性质分类：线性多目标规划和非线性多目标规划。 若按数域分类：整数多目标规划和实数域多目标规划。 若按状态分类：静态多目标规划和动态多目标规划。 ( 本文研究的是确定性非线性多目标规划算法。) 需要指出的是：到目前为止并没有完美的分类，通常情况下，类与类之间或多或少都会有 些交叉。随着这顿域的快速发展，多目标规划新算法的不断增多，新的分类也会不断涌现。 些交叉。随着这顿域的快速发展，多目标规划新算法的不断增多，新的分类也会不断涌现。 西安建筑科技大学硕士学位论文 0 3 多目标规划与非光滑优化的关系 一方面，在多目标闻题的研究中会涉及非光滑函数，非光滑多目标问题的研究已成为优化 问题研究的话题期文【9 】 1 0 5 另一方面，在求解多目标规划的过程中，经常会牵扯到种非光 滑问题极小极大问题。因此，研究非光滑问题极小极大闻题的算法，对发展多目标规 划的算法有着重要意义。 西安建筑科技大学硕士学位论文 1 1 1 基本闯题 第一章基本概念及理论 第一节非光滑优化基本概念及理论介绍 设有下列形式的优化问题： ( p k r m i n ，( g x ) 其中，：矗一r 是在g c 旯上局部l i p s c h i 函数。如果f 是连续可微的，那么就称问题 ( p ) 是光滑优化问题。着g = 时，则称是无约柬的；否则，则称( p ) 是有约束的。若f 为凸 函数，g 为凸集，则称( p ) 为非光滑的凸规划问题。 1 1 2 基本概念及理论 凸分析和非线性分析是非光滑优化的基础知识。鉴于此，下面首先将其中的关键基本船识 作部分介绍详情见文 i l l 、x 1 2 。 1 1 2 1 凸分析基本概念及基本理论 定义1 设有醢数，：r “_ r ，如果对所有 【o 埘和z 。，j ：月“且屯， ： ，( 缸，+ ( 1 一x ) x ：) 硝0 ，) + ( 1 一 ) ，0 ：) 成立， 那么称，：胄一r 为凸丞数。如果严格不等式成立，则称为严格凸函数。 定义2 设有函数，：r 。一胄，如果对每一个有界子集b c 詹4 ，存在常数l 一工) 使得对 所有置，x ：月。，l i ( x ，) 一，o ：工k x ：l 成立，那么称，：月“一r 为局部李普希兹函数， - 工佃) 称为局部李普希兹常数。若曾r ”，则称，：r 4 一r 为李普希兹函数。 定义3 设f ：r 一一胄为局部李普希兹函数，z 为b c r 4 的”个内点，d 为z 处任意方向。 那么称 ，- 如d ) 1 抑丝掣匕塑 ” i 为，：r 4 一r 在x 处关于d 方向的方向导数。 定理1 设，：r 。一足是凸函数，且在x 处其有局部李普希兹常数r ，则 1 ) ，o ，d ) 作为d 的函数是正齐次的和次可加的，且满足 i ，( z ，d ) js 篁； 2 ) ，缸，d ) 作为d 的函数是局部李酱希兹的； 3 ) ，o ，d ) 作为k d ) 的函数是上半连续的； 4 西安建筑科技大学硕士学位论文 4 ) ，k - d ) 1 - f 1 0 。d ) 。 定义4 设，：r 1 一r 是凸函数，x r “，则集合 营f l ，o ，d ) 7 d ，v d 尺4 ， 称为，：r ”一r 在x 处的次微分，记作d 。，0 ) ，称 a 。，0 ) 为在x 处的次梯度。 定义5 设，：r “一月是凸函数，那么v x e 尺“，有 1 ) ，0 ，d ) m h 售7 d 拉a 。，o ) j ，v d e r “： 2 ) a 。f ( x ) - 留r 4 i ，( y ) ，扛) + 亭7 ( y x ) ，b r “ ； 3 ) d 。，o ) 是非空，凸的和使得a 。f ( x ) cb ( o , k ) 的紧集，其中k 为f ( x ) 在x 处的局 部李普希兹常数。 定理2 如果，：r “一r 在j 尺”处是凸的且可微的，那么 1 ) a 。( x ) 一 v r o ) ； 2 ) ，0 ，d ) w “) 7 d 定理3 设，：r 8 一r 是凸函数，那么 e e r ” ，( y ) 一m a x f ( x ) + 宇( y z ) k r 1 ，；d 。，( x ) 。 1 1 2 2 一般函数的可微性概念及理论 这部分将就不做凸特征要求函数的可微性理论作以介绍，本部分详情及最新进展见文 【1 2 】 1 5 】- 定义6 设，：r 一r 在x 娃为局部李普希兹函数，且j 为b c r 4 的个内点，d 为x 处 任意方向，那么称 ，- 0 ，d ) t i m s u p 地型幽 一l t 1 0 为，：r “一r 在x 处关于d 方向的广义方向导数。 注；方向导数是广义方向导数的特殊情况，y - z 时的情形。 定义7 设有函数，：r “一r ，如果对所有d r ”。，7 0 ；d ) 存在且 ，0 ；d ) 一，6 似d ) ，那么，：彤一月在z 处是正则的。 定理q h 设，：r “一r 在x 处为局部李普希兹函数，那么如果，是凸的，那么 ，：r 4 一尺在x 处是正则的。 定义7 设，：rn r 在x 处为局部李普希兹函数，则集合 苫r 。i ，。( 置d ) 每孝7 d ，v d 矗4 西安建筑科技大学硕士学位论文 为，：r 一r 在x 处的广义次微分，记作a ，( 砷，称 矽0 ) 为在x 处的次梯度。 定理5 设，：r “一r 在x 处为局部李普希兹函数，k 为李普希兹常数，那么 1 ) 矿o ) 是非空、凸的、使得可0 ) cb ( o , k ) 的紧子集： 2 ) ，。o ，d ) 一m a x 告7 d 陆矿0 ) ，v de r 4 。 定理6 设，：r - 一r 在z 处为局部李普希兹函数，那么 ，仁，d ) s ，。0 ，d ) 。 定理7 设，：r 一r 在x 处为局部李普希兹函数且在x 处可徽，那么 w 。0 ) a ，0 ) a 定理9 设r ：r 一一r 在x 处是连续可微的，那么 矿扛) 一 v ，0 ) j 。 定理1 0 如果设，：r * 一r 是凸函数，那么 1 ) ，缸，d ) ，o ，d ) ： 2 ) a 。，0 ) - a ，0 ) 。 定理i i 1 3 设，：r 。一r 在x 邻近是李普希兹的，假定s 是勒贝格测度为0 的任意集合 那么 可o ) 一c m 硒v ，晦牡i 一五毛隹s 萑。， 其中q ，表示，的不可微点集。 1 1 2 3 凸函数的# 一可微性 定义8 设，：r 一一r 是凸函数，则称 ，i ，o ，d ) 噶坦型华 为，：r “一r 在x 处于d e r “方向的s 一方向导数。 定理1 2 设，：r 一一r 是凸函数，则在每一点x e r “处： 1 ) 函数d 哼( 蔫d ) 是正齐次、在拧“上次可加的且1 融d ) 【s k ； 2 ) f o ；d ) 作为( z ；d ) 的函数是上半连续的，作为d 在掣上的函数是常数为k 的 李普希兹函数； 3 ) 一( x ；- - d ) sf 0 ，d ) 。 定义9 设s 0 ，：曰一一r 在t 处是凸函数，则称集合 a 。厂o ) 一苫掣i ，o ) = ，o ) + f o 一j ) 一，v x 。月“j 为，：r “一r 在z 处的g 一次微分。称 d 。，0 ) 为，：r “一只在x 处的s 一次梯度。 定理1 3 ，：r 。一r 在x 处是凸函数，那么 西安建筑科技大学硕士学位论文 = = j = 茸i z = ；= ；# = = = = = = ；= = = = = = = = = = = = = = = = = = = = = = = = = = = = = t = = = = = = = = = = = = = ! = = = ! = = = = = = = = = = = = = = 1 ) 8 0 ，0 ) ia 。，o ) ； 2 ) 如果f 。s ：，那么a 。，0 ) co 。，扛) ； 3 ) f o ，d ) 。m “悟d 浯a ，0 ) ，y dc r ”； 4 ) a ，o ) 是非空的，使得对所有 a ，0 ) 都有s k 成立的凸紧集i 5 ) a 。，0 ) 一管r ”i o ；d ) # t d ，v d r ”i o 1 2 1 同犀【及解 第= 节多目标规划纂本概念及理论介绍 设 ：r 1 h r ，剡问题 ( m o p ) r a i n i ，1 0 ) ，f 2 ( x ) ， o ) s t x e s 一蕾r 4 k o 。一( 自如) 9 2 0 ) ，乳o ) ) 0 j 称为多目标规划问题， 其中t z2 ，f 0 ) 称为目标函数，g ，o ) 称为约束函数。另外，如果 0 ) - g ，0 ) 均为线性 函数，则阔题称为线性多目标规划问题：如果上扛) ，g j 扛) 中存在非线性函数，则问题称为 非线性多目标规划问题。 定义1 如果对工i ，茸2 r 4 ，当 z 2 时，正0 1 ) 墨五0 2 ) ，则称：r “h r 为增函数。 类似，如果此时 0 ，) 工0 ：) ，那么称 ：r ”卜r 为减函数。 定义2 如果对工。，x ：只“当工：( f l 2 ，h ) 目存在x ：z ：时，正 。) t ，：0 。) 成立，那么称函数五：r 4 卜r 是强增函数。相应地，如果此时丘o 。卜f a x ：) 成立，那么称 f ：r “b - - y r 为强减函数。 定义3 对j 5 ，如果不存在另一个使得五o ) s ，f 扛+ ) 和至少有一个，o ) t ，0 ) 成 立的j s ，那么称z + 为p a m o 最优解。所有选种解组成的集合记作e ( f ，s ) 。 如果不存在另一个使得2 2 7 ( - l 2 ，k ) 和至少有一个z jcz ：成立的目标向量 z z ，那么称z 是p a r e t o 最优向量值。换句话说，如果相应于z 的决簟向量是p a r c t o 最优 解，那么称z 是f a r e t o 最优向量值。 如果将上面解理解为全局解( 向量值) ，那么可引入以下定义。 定义4 如果存在6 0 使x 为s n 丑扛，6 ) 内的最优解，盟嘛并s 为局部p a r e t o 最优解。 类似，可以定义局部p a r e t o 最优向量值。 西安建筑科技大学硕士学位论文 定理1 如果( m o p ) 问题为凸问题，那么每一个局部p a r e t o 最优解也是( 全局) p a r c t o 晟优 解。 定义5 如果不存在另一个x s 使得，f o ) c o 。) ( i - 1 ，2 ，t ) ，那么称x 1 s 为弱 p a r c t o 最t b 樨。所有这种解组成的集合记作e 。( ，s ) 。 定义6 设s 胄8 是( m o p ) 问题的约束集，若存在j s ，使得v x e s ，( z ) s ，( x ) 成立，则称x s 为绝对最优解。所有这种解组成的集合记作s ( ，5 ) 或s 。 类l 蚵定义弱p m 嘲t o 最优向量值，局部弱p a r c t o 最优解，局部弱p a r e a o 最优向量值。注： 几种解的情况，如下图示 s ( 1 2 1 ) j斟 ( 1 2 2 ) h e 0 2 e ( 1 2 3 ) j 州 - + 一 k ( 1 2 4 ) 这几种解之间的关系通过e 图可以大体看出，下面再给出进一步结论。 定理2 如果s 只5 是凸集，l ( x ) e r 是s 上的严格凸函数则 e ( f ，s ) 一e 。( ，s ) 。 上述定理表明，在目标和约束均具有凸性的条件下，( m o p ) 的p a m t o 最优解和弱p a r c t o 最优解时等同的。 定理3 设s e r “，：zb - r 。若s ( ，s ) * 妒，则占( ，s ) 一s + ( ，s ) 。 定理4 设z ? 为各对应单目标在约束s 彤上的攮优解集，则 i 1 ) 下述关系总成立：e u i = ：x l c _ e 。； 2 ) 若s r 4 为凸集，f ( x ) 为s r “上的严格凸函数，则 雌 西安建筑科技大学硕士学位论文 k e u 【：= ：f 卜e w 。 1 0 0 值函数 研究多目标规划问题的个基本途径，是把它转化为与之相关的单目标( 数值) 最优化问 题。通常把这一单目标称为值函数。在多目标最优化的研究中，这种值函数计：论在理论中还是 求解中都有着基本重要的意义。 定义7 在目标向量中，表示决策者偏好的函数u ：r t - r 成为值函数。 值函数一般具有下面形式 ( u p ) r a i n u ( ，o ) ) s t z s 。 设z 1 ，z 2c z 且= 1 # z 2 ，如果u ( z t 卜u ( z 2 ) ，那么就表示决策者相对于z 2 偏好z ，；如果 u ( z 。) - v ( z ：) ，那么表示决策者同等看重这两个目标。要指出的是值函数完全是一个以来决 策者的概念，不同决策着可髓有不同韵值函数。有时，也用效用函数代替值函数。通常遵循的 方式是：在确定性问题中称值函数，在随机问题中称效用函数。 咀下给出( m o p ) 问题与问题解之间的一些关系。 定理5 设s r “，f ：z 卜r ，u ：r 。卜r ， 1 ) 若u o ) 关于y e r 是强增函数，f 是( u p ) 的最优解，4 z e e ( f ，s ) ； 2 ) 若u o ) 关于y e r 是严格增函数- i 是( u p ) 的最优解，则童e ，( ，s ) 。 本定理指出：只要取问题椰砷中的u ：r 卜r 是单调增函数，由( u p ) 得到的最优解便是 ( m o p ) 的p a r e t o 最优解或弱p a m t o 最忧解。 曼详尽盼讨论既文【1 6 t - 【1 7 】。 西安建筑科技大学硕士学拉论文 第二章非光滑优化算法 非光滑优化算法是非光滑优化中最主要的研究领域之一，目前为止其确定性基本算法已芨 展为两个主要的大类：次梯度法和捆绑( b c 驰# 击。本章首先对这两种基本算法作了一定分 析，并在其基础上提出了一种处理一种特殊非光滑函数问题的方法。 典型的优化方法是迭代法从个培定的点xe r 4 开始构造个意在收敛得到要求解的 序列“) ：c 置“，一般的迭代算法如下： 基本冀法1 t 0 ( 开始) 找一个可行起始点x ，c g 并令t - 1 ； 1 ( 拽方向) 寻找个可行下降方向d 。c r 8 使对某一个f 0 有f ( x 。+ t d 。) c ，( 而) 和 “+ t d e g ； 2 ( 停机标准) 如果斗离要求解足够近，那么停止； 3 ( 直线搜索) 找一个步长f 。，0 ，使 f _ a r g m i n t ，o i + 掰 ) 和 + 以g ； 4 ( 选代) 令+ l - x i + t d t ，女一t + 1 并返回1 ： 最简单的算法是针对具有形式( p ) 的光滑无约束问蘧所构造的。最有效的方法像共轭梯度 法和拟牛顿法等，都用到问题中函数微分的信息。在步1 中一个下降方向可能通过这样事实 而产生：梯度反方向是局部最遮下降方向。在每一个局部处，由局部最优性必要条件知，在每 个局部解处梯度必为零向璧。由连续性知= 梯度范数在接近最优点时会副、，这样在步2 中就 获得个停止标准。在光滑问题的方法中，童线搜索通常用到些有效的单变量光滑优化方法 或些多项式内插法。但非光滑性产生了根多困难，几乎在每一步中，都要求额外的工作。由 于任意次梯度的反方向不一定是下降方向，故最困难的问题在步1 。这个事实也迫使鍪玎门调整 t 述经典线性搜索过程。另外，停l 条件也不再清楚。在非光滑情形中，最筒单的例子是实数 域上的绝对标准函数，它在0 处达到全周最小值丽在0 处，1 是其一个非零的次梯度。 非光滑优化方法可以被分为两个主要的大类：次梯度法和捆绑国u n d 助法。它们都假定 了问题函数是局部l p 连续，而且能计算每个点处任意次梯度。这些假定已经在实际中被证 实是十分自然的。耍注意的是：问题函数不需要是可墩的。次梯度法起源于上世纪六十年代， 其基本方法就是用任意次梯度代替梯度采推广光滑问题的各种方法。这个简单的想法提出了两 个关键的问题：我们如伺选择步长和是否由某种可以执行韵停l e 标准? 虽然有多种不同的提法 来回答这个问题。僵可执行的停i e 标准的缺乏仍然是次梯度法主要的困难。而虽任意次梯度反 方向不需要获得下降，这事实意味着次撵度法不是下降法。次梯度法主要在前苏联发展起来 的，其综述参阅【1 8 】。 1 0 西安建筑科技大学硕士学位论文 第一节基本算法介绍及分析 考虑问题 c p ， ：掣 其中，：r “一r 是在g c r ”上局部l i p s c h i 函数。 在下面算法中均假定：在每个z r “处可以计算 至少一个次梯度和蘑数值； 对b u n d l e 法则还具有下面两个特征： 1 ) 把前面迭代中次梯度的信息集成柬； 2 ) 迭代中的两个概念，重要步和空步：对某一t 。，0 和。o f ( y 。) - 令 y i h 。i 耳+ f i 畋，那么 如果对某一以 0 ，f r y i 。) sr ( x 。) 一以，那么执行重要步：。y 。：否则，执行 空步：以i - 坼。 下面简短地给出对问题( p ) 的b u n d l e 法的演变过程。 2 1 1 光滑极小化方法 首先假设目标函数f 是二次连续可微且点札掣是非最优点，即v ，) t0 且存在de r “ 使得，魄；d ) t 0 。显然，求解问题回的关键就是寻求个方向d 。使得 ，魄+ d 。) c ，( 以) 。从而可以将问题口游化为下面问题 m i nf ( x 。+ d ) 一，o 。) s td e r “ 其有一非零解d 。 又由泰勒展式可以将问题进一步化为两个等价的逼近问题 m i n ，( k - a ) r a i n v ，瓴) 1d s t i 俐1s t 粒i s l 岱1 1 ) 显然后者有唯解以一一v m , ) l l v m 。) i | ，从而得到了最速下降法盼f 降方向 d 。- 一w k ) 但最速下降法有两大缺陷：是下降收敛速度慢，一是出现所谓的锯齿现象。为了解决这些缺 陷，导致共辘梯度法所采用的方向出现 d 一一w h ) + d 其中 的生成有多种方法最一般的方法是下面形势 西安建筑科技丈学硕士学位论文 = = ；= = ；= = e = = ；= 目e ；= ；= = = = ；= = = ；：= = = = ：= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ! = = 一! 篡 f凡一0 i 一d “a v ，。0 1 ) d n a d “ a 可取目标薅数的正定的海森矩阵。 共轭梯度法是相当有效的方法，特别适合大规模问题。 为了更精确，进一步引入二阶泰勒展式结果可以将( f d p ) 转化为下面近似问题 f m i l l v ，( ) + d v 2 f ( x 。y i，d r ” 求解此问题可以得斟其解 d 。一- v 。，o 。) “v ，o 。) 。 这也就是牛顿法的搜索方向。( 这里要求海森阵可逆) 由于海森矩阵计算复杂故导致了拟牛顿法的出现。这种方法中用一个和海森矩阵逅1 以的 i 麟阵来代替它得到搜索方向 d i 一- h i v ，饥) n 五1 2 次梯度法 这种方法是光滑问题瑷速下降法的直接推广它直接用次梯度 ，o 。) 代替梯度，采用规 范化的搜索方向砍i 氩月臣 要指出的是：次梯度方向并不一定是下降方向，i 蝴极小化线性搜索问题不现实，而且 停机标准也发生改变这导致为避免线性搜索和上述停机条件，而使用了颈院给定的搜索步长。 而下一个迭代点的获 弛变为如下形式 卜：一。靠州最i 这里邑可0 。) if 。 0 ( 适当的) 其步长选择可以参阅文 1 9 】。 为了加速收敛，人们也将其它光滑法作了推广。拟牛顿法是种比较好的方法，但利用标 准的d f p 和b f g s 法直接推广，其收敛效果并不好。目前最有效的方法是椭球法和空间膨张 法( 律晴见文 1 8 】) 及变矩阵法( 详情见文脚i ) 。要指出的是：踟睇度法的收敛效果并不理想， 但在某些特殊情况下却是十分有效的方法。 乞1 3 f 一最速下降法 由于最速下降法的直接推广不能给出满意的结果，故自然想到要从式( 2 1 1 ) 开始推广梯 度法的整个演变过程。但w 幽艰9 7 5 ) 举出反倒说明这种想法可自漩凋撵法执行了无限步却役 西安建筑科技大学硕士学位论文 有明显下降的后果。为了解决这一问题，l e m a m c h a l 提出了一最速下降法。 这一方法引入s 一方向导数及p 一次梯度，通过分析和构造的手段将选取方向的问题转化 为下面形式的问题 0 3 ) m i n 酬驴，0 2 “ 酗。；钱 弘“氲。 和o 对所有7 ，。 其中 为辅助点y 处次梯度，a ； ，o 。) 一f ( y ，) 一 ，7 “一y i ) ，而 j c 缸，t 且 非空。 如果设 t ，是此问题的解，那么取搜索方向为 小一荟t 岛 注：此方法中的主要困难是逼近容度# 。的选取； a ) 如果。取得太大，那么逼近效果差； b ) 如果气取得太小，那么下降效果差。 因此，一般情况下r 给出选择 。的确切规则是报困难的。 2 1 4 广义割平面法 广义劓平面法是k i w i e l ( 1 9 8 5 ) 在蒯m 1 9 卿的害怦面法的基i 牡发展而来的，它将选 取方向的问题转化为下面形式的问题 其中岛为辅助点y ， ，。c 札2 ，t 且j 。非空。 如果设 对 是此问题的解， 曲叫黔h 巾j “ 善2 j “ 为。 a ，0 对所有诈j 。 处次梯度，a ：- ，“) 一f ( y ) 一岛7 瓴一y ，) ，而 那么取搜索方向为 ”一荟t ， 西安建筑科技大学硕士学位论文 注；一最逮f l 蜂= i 去与广义截平面祛的关系： a ) 相同之处是两种方法均用至性性化逼近，且如果 硝 是( d ( 了) 的最优解，那么当 铲磊纠时，它也是勘的解， b ) 但背景及演化过程完全不同：前者用的是一方向导数及一次梯度，后者用的是方向 导数和次梯度；前者将d p ) 逼近为 叫吉馏 而后者则首先将何陇 逼近为 f r a i n ，o 。+ d ) 一，o 。) 1s j d 肜 其中，- m ，o ，) + 亭；o y ，) l j j ， ，然后加罚项( 1 ，2 牡8 2 转化为 ( 2 1 3 ) j r a i n ，魄+ d ) 一，限) + ( 1 冲5 2 lsd6r。 另外，( d ( 翟) 不需要选择逼近容度“，但它对目标尺度相当灵敏。 为了避免t 述两种方法中的缺陷，k i w i e ( 1 9 如) 提出了p r o x i m a l 捆集法，s d a m a a m ( 1 9 8 9 ) 和z o w e ( 1 9 8 8 ) 提出了捆集信赣域法。 这两种方法都是将问题( 2 1 3 ) 中的罚项( 1 ，2 i p 8 2 作为害i 怦面模型的约束。他们引入数 o 后，将闻题( 2 1 3 ) 改为下面形式 ，o 。+ d ) 一f ( x 。) o 2 ) 1 p 1 2s 吼 然后在此基础上，经过一系列的转化将寻求方f f 唾闽题归结为 曲峪酬2 盏巾： “ 荟- “焦。 f 0 对所葡j i 西安建筑科技大学硬士学位论文 其中，0 ，其他i n 上。 如果设 越 是此问题的解，那么取搜索方向为 畋一专磊砖印“t 越。 注：a ) 问题( b ) 与问题( p b t ) 有如下关系： 1 ) 如果小是问题( b ) 的盛优解，“( e t ) 是相应于约束a j c t , jss t 的乘子， 那么r 也是( p b t ) 当h 。t h ( 。) 时的最优解； 2 ) 如果r 是问题( p b t ) 的虽优解a b 么才也是( b ) 当t 。t a ；刊的最优 解。 b ) 广义害怦匝法中问题( d c p ) 是问题( p b t ) 当- 1 时的特剜情况： c ) p r o x i