（运筹学与控制论专业论文）单调全局最优化问题的凸化方法.pdf

2 0 0 3 年上海大学硕士学位论文 全局疑优化主要研究如何寻找一个非凸优化问题的垒局最优解由于 全局最优化在工业，经济以及管理中的广泛应用，全局最拢化在数学规划 中占有十分重要的地位一个一般的全局最优化问题可描述如下： r a i n ，( ) 8 t g i ( x ) 饥，i 一1 ，m z d ， 程这里，口鸯黔中一非空闭子集，舔，i = 1 ，m ，必定义在妇上的实 值连续函数( 不一定为凸黼数) 由于，g i 的非凸性，形如上述的全局最优 化问题则为多极馕全局优纯问题，逮使得全局最优也成为极具挑战性的潆 题 本文的主要工作是研究一类特殊的全鼹捷化一单调优化问题。所谓单 诵优纯是指目标豳数与约束函数均为单调函数的全局优化问题通过我们 提出的的凸化变换可以把雄调函数化为凸函数，进而把一类单调优化问联 化为等价的凸极大或凹极小问题然后采用h o f f m a n 的外逼近方法求得问 题的最优解本文把这种凸化方法同t u y 的p o l y b l o c k 外逼近方法佟了数德 比较，并把该凸纯方法成功地应用于解决可靠住最优化问题 本文共有六章组成第一章是前言部分，对全局最优化作了一些简要 奔绍第二章叙述了鹫极，j 、佬算法及其牧毅性在文章的第三部分，我们 给出了单调函数的凸化变换，通过变量替换我们可以把一个严格递增函数 或递减函数纯残凸涵数第图章泠蹬了单溺全局最优纯酌凸亿变换方法并 证明了问题的等价性第五章给出的数值例子说明我们的凸化方泼与t u y 的p o l y r b l o c k 方法穰比翁筑逮性，然后给出了蔫叠化方法解决可靠往闷题豹 数值例子第六章是结论部分，总结了本文所做的工作以及将来的研究方 向。 关键词：全局最优化，单调最优化，凸化方法，凹极小化方法，p o l y b l o c k 方法，分支定弄，可靠性簸优化， 2 0 0 3 年上海大学硕士学位论文 i i a b s t r a c t g l o b a lo p t i m i z a t i o nm a i n l ys t u d i e sh o wt of i n dag l o b a lo p t i m a ls o l u t i o n o fan o n c o n v e xo p t i n i i z a t i o np r o b l e m b e c a u s eo fi t sw i d ea p p l i c a t i o ni ni n d u s - t r y , e c o n o m i c sa n dm a n a g e m e n t ，g t o b a io p t i m i z a t i o np l a y sa ni m p o r t a n tp a r t i nm a t h e m a t i c a lp r o g r a m m i n g ag e n e r a lg l o b a lo p t i m i z a t i o np r o b l e mc a nb e d e s c r i b e da sf o l l o w s ： o b a l l yr a i n ，扛) s t ，g ( g ) sb i ，i = 1 ，m o d h e r edi san o n e m p t yc l o s e ds e ti n 黔a n d ，a n d 虫，i = l ，m ，a r er e a l v a l u e dc o n t i n u o u sf u n c t i o n sd e f i n e do nd ( n o tn e c e s s a r i l yc o n v e x ) d u et ot h e n o n c o n v e x i t yo fsa n d9 i ，m u l t il o c a lo p t i m a ls o l u t i o n st h e r em a y e x i s ta n dt h i s m a k e s g l o b a lo p t i m i z a t i o n ag r e a tc h a l l e n g e t h em a i np u r p o s eo ft h i st h e s i si st os t u d yas p e c i a lg l o b a lo p t i m i z a t i o n - m o n o t o n eo p t i m i z a t i o np r o b l e m t h ei n o n o t o n eo p t i m i z a t i o ni st om a x i m i z e am o n o t o n eo b j e c t i v ef u n c t i o nc o n s t r a i n e db ym o n o t o n ef u n c t i o n s t h i st h e s i s p r o p o s e san e wc o n v e x i f i c a t i o nt r a n s f o r m a t i o nm e t h o dt oc o n v e r tam o n o t o n e f u n c t i o ni n t oac o n v e xf u n c t i o n t h em o n o t o n eo p t i m i z a t i o np r o b l e mc a nt h e n b ec o n v e r t e dt oa n e q u i v a l e n tc o n v e xm a x i m i z a t i o n o rc o n c a v em i n i m i z a t i o n p r o b - l e m t h u sw ec a na d o p tt h eh o f f m a n so u t e ra p p r o x i m a t i o nm e t h o dt of i n dt h e g l o b a lo p t i m a ls o l u t i o n ，w ec o m p a r et h ep r o p o s e dc o n v e x i f i c a t i o nm e t h o dw i t h t u y sp o l y b l o c ko u t e ra p p r o x i m a t i o nm e t h o d m o r e o v e r ，w ea p p l yt h ec o n v e x i f i c a t i o nm e t h o dt os o l v e8c l a s so fm o n o t o n eo p t i m i z a t i o np r o b l e m sa r i s i n gf r o m r e l i a b i l i t yo p t i m i z a t i o np r o b l e m s t h i sd i s s e r t a t i o ni so r g a n i z e da sf o l l o w s + i nc h a p t e rl ，w eg i v es e i n eb r i e f i n t r o d u c t i o nt og l o b a lo p t i n f i z a t i o n h ic h a p t e r2 ，w ei n t r o d u c ec o n c a v em i n i m i z a t i o na p p r o a c h e sa n dt h e i rc o n v e r g e n c e 。w e p r e s e n tt h ee o n v e x i f i c a t i o nt r a n s f o r m a t i o nm e t i l o di nc h a p t e r3 a ni n c r e a s i n go rd e c r e a s i n gf u n c t i o nc a nt h e n 2 0 0 3 年上海大学磺士学位论文 i i i b ec o n v e r t e di n t oae o b v g xf u n c t i o nv i av a r i a b l et r a n s f o r m a t i o u + i nc h a p t e r4 。 w ed i s c u s st h ec o n v e x i f i e a t i o nm e t h o df o rt h em o n o t o n eg l o b a lo p t i m i z a t i o na n d t h e e q u i v a l e n c eb e t w e e nt h et r a n s f o r m e dp r o b l e m a n dt h e o r i g i n a lp r o b l e m ；t m i l l u s t r a t i v ee x a m p l e si nc h a p t e r5s h o w sc l e a r l yt h a to t l rc o n v e x i f i c a t i o nm e t h o d 蟪s u p e r i o rt ot u y $ m e t h o di ns o l v i n gt k m o n o t o n ep r o b l e m s 。n u m e r i c a lr e - s u i t sa r er e p o r t e di nc h a p t e r5f o rr e l i a b i l i 秽o p t i m i z a t i o np r o b l e m s f i n a l l y , w e s u n u n a _ 】r i z et h et h e s i si nc h a p t e r6a n ds u g g e s ts o m ef u t u r er e s e a r c hd i r e c t i o n s ， k e yw o r d s ：g l o b a lo p t i m i z a t i o n ，m o n o t o n eo p t i m i z a t i o n ，c o n v e x i f i c a t i o nm e t h o d c o n c a v em i n i m i z a t i o nm e t h o d p o i y b l o c l cm e t h o d ，b r a h e h - a n & b o u n dm e t h o d ，r e - l i a b i t i t yo p t i m i z a t i o n 第一章前言 1 1 善| 言稳定义 在经济管蠼与工程设计中，很多阍题的数学模型都可归结为求一个全局优化问 题的最优解全局最优化已被广泛应用刹各个不同领域，其中包括经济横型、金融， 网络与运输、数字集成设计、图像处理、化学工程设计与控制，分子生物学等由 于其广泛应用，已成功发展起许多理论和方法蹋于解决多极值众局优化问题 我们知道，多极值全局优化问题是求解一个实值目标函数的全局最傀解，丽非 局部觳侥解我们称x 8 为，( # ) 在s 中的一个局部极小点，怒指存在e 0 ，使对 任何en ( x + ，e ) ，有s ( x + ) 兰，( 。) 若对于任一zes ，( ) s ，( 。) 成立，则称矿 为，( * ) 在s 审的一个全弱投小点( s 为全弱激优问题的可行域) 虽然非线性规划 在解决局部极值上是非常成功和有效的，但并不能成功地用于解决多极值全局优化 闻题狠据k - k - t 条捧，我稍可求一个全蜀最挽纯闻戆的蜀部檄小点毽没有一定 的准则米判断这个局部极值点就是全局极值点如何在搜索过稷中从一个局部极值 点踺凄，然后帮赘下一个更努麴蘑部投篷点，赢嚣我到全局最优点，这难是多极僮 全局优化问题所研究的课题之一全局优化算法总的来说可以分为两大类：一类是 随凝算法移启发式算法，舅一粪是是确定瞧算法，确定瞧算法戮究静跑较多静怒具 有特殊结构的搬局优化问题，熟中包括凹极小、反凸规划、d a 规划、单调规划， l i p s c h i t z 凌毒i ：阉瑟等与魏嚣瑟尊，二次艋翅与多矮式援麓壶予箕广泛鹣瘦蘑曹黎遣 得到重视并取得了一系列成果当目标与约束函数均为非凸函数时，一般的数学规 怒款全嚣霞纯阏题仍然楚全鼹傻纯孛簸爨撬我穗戆瀑瑟在奔缨全蜀最饶匏阉熬帮 算法之前，先对用到的些概念作一些简要描述 定义1 1 1 称dc 辩建一凸募是指如暴磅搬l ，。2 d 秘a 衩0s 鬟1 ，有 a 茹l + ( 1 一a ) x 2 d 定义1 1 2 如暴d c 鼗札建一爨，：d - 9 琏秀凸簿，藏数是搬如果靖如i 。2 d 和 媳0sa i 有 ，( a o l 十( 1 一a ) x 2 ) ( ) a ，( z 1 ) + ( 1 一 ) ，( t 2 ) 2 0 0 3 年上海大学疆士学位论文2 定义1 1 3 如蓑dc 黔为一穗案，海数，：d 叶鼹称为d 土姆d 。c - 辔数，即f d i f f e r e n c eo ft w oc o n u e x f u n c t i o n s ) 是指如果存在两个凸函数p ：d - r ，q ：d _ 瓞，满 足： ，( o ) 一p ( z ) 一q ( x ) v x d 如果，在辩土d c ，嬲稚，d 。o 若，是p e 的，笨等式f ( z ) 0 我们称为d ，o 不等式 定义1 1 。4 募合dc 辩，函数，：黧匏_ r 拣旁d 上的l i p s c h i t z 函数楚指如果存在 一个实数l = l ( i ，d ) 0 ，满足： | ，z ) 一，( 口) | s 二 | 一“v x ，y d 若，# ) 是d 上的l i p s c h i 虹函数，不等式，。) s0 称为l i p s c h i t z 不等式 定义1 1 5 ，楚p 。酞的凸函数，不等式，( m ) 0 称为凸的，而，( ) o 我们称 为反凸的 定义1 1 6 设，：孵- 4 醍称，( z ) 是递增矗黾缄j 函数连指当xsy ，即柳轨，i = 1 ，牡，时，( z ) s ( ) ，( ，) 警当。y 且z g 时，( z ) ) ，国) ，则称，如) 为 严格递增瘁羲减，函戴若，( 。) 为单调函数，和) 兰0 或，( z ) 0 ，我们称之为单调 不等式 特殊结 笥全局最傀亿问题静可行城或哥稀函数可黼会属于下述情况中酌装一 种： 可手亍城d ： 有限个凸不等式和反凸不等式组成的集合 寄限个l i p s c h i t z 不等式组成魏集合 有限个单调不等式组成的集合 蓄标番数，： 凸函数 鹜蕊数 d c 函数， l i p s c h i t z 溺数 单调函数或严格单调函数 摄据嚣据丞数秘约束毯数懿特辣洼凑，众焉簸傥纯藏邋可翅分为很多类喇，冀中包 括凹极小、反幽规划、d c 规划、单调规划，l i p s c h i t z 优化同题等， 2 0 0 3 年上海夫学硬士学往论文3 定义1 1 7 盟搬小是操极小化一个目姆函数为辫函数势且受约束于线蠛或凸不等式 组成的集合的全局优化问题 定义1 1 。8 反凸规划楚搪极小化一令函数，并且约束是由有限个凸不等式或反凸 不等式组成的集合 定义1 1 9d a 规划是指优化问题中的函数零可以表示成两个凸函数之差 定义1 1 1 0 一个全局翻二化问题称作l i p s c h l t z 优化问题是指问题中的目标函数和约 束函数均为l i p s c h i t z 函数 定义1 1 1 1 单调优化建指优纯问题中的目标瓣数和约束函数均为单调函数 l ，2 一般形式豹全舄羲德纯嗣黻和萋法 对于一般形式幻全局最德纯闻题， r a i n ，( ) s ，岳f o ) s 堍，i 。1 ，。，m z d d 为静中一非空闭子集，g i ，i = l ，m ，为定义在d 上的一般的实值函数 对于戴类全局援亿闻题，常见鳃算法衣积分拳乎巢方法、填充蛹数法，隧提算法程 启发式算法 1 2 1 获势承平纂方法 积分型求总极值算法具有很好的收敛准则，并且该算法仪需要计算目标溺数 值，放适焉予较大蓬甏的总极蘧闯惩，觅( 2 7 1 1 2 8 2 9 ) 但在一般情况下，水平巢并 不易求得，所以其实现算法尚有一定的难度谯求这类优化问蹶时，我们须假设， 在可行域s 上是连续鳃，劳量存在一个实数c ，使得水平集 改一扛舻 f ( x ) 基c 和s 的交集非空而且紧积分水平集的概念性算法表避如下： s t e p j 。敬。s ，给定一令充分小瓣歪数，令强= ，( z 。) ，甄。= 缸嗣f ( x ) s c o ，k = 0 s t e p 童警芦臻；= 0 ，裘c k 鸯葸较篷，甄。为慧缀篷点巢，转s t e ps ；答粪蓦懿 话，进行s t e p3 2 0 0 3 年上海大学硕士学位论文 4 且令 s t e p3 ，计葵均褒 1厂 蝴2 高厶；八砷咄 h c = z s 1f ( x ) c k + l 若c n l = c 置，则+ l 为总极蓬，j k + 。为总极值赢集，转s t e p6 ；否辩转s t e p4 ， s t e p4 计算均方莲 v 肚南厶。扛卜户如 s t e p5 。著v f ，辩令k - _ k + 1 、转s t e p2 ；香赠转s t e p 矗 s t e p6 令f + = c k 上l 且h + = h c 。，终止h 4 为，g ) 在s 上的近似总极值 点集，4 鸯橱应静近织总裰馥 1 2 2 填充函数法 填充函数法可以解决这样一类全髑优化问题， 其中毯标丞数，为二除连续皴函数，照潢足条l 孛 f ( 2 ) _ + 。，l 吲l 一十o 。 那么，一定存在一个有界闭集xc 瞅包含f ( x ) 的全部局部极小点我们假定x 是已知的，且假定x 只有有黢个局部极小点 定义1 2 1f ( x ) 在孤立局部极小点z ：的盆域嚣；是一个连通域，x i 嚣；，而凰从 b ；钓任意一点出发的f ( z ) 的最速下降轨迹趋向亏z i ，但从b ；外面的点出发砖最 速下降轨迹均不趋向千z i 填充函数的主要思想是：露先用一个求局部极篷闷题救方法，解出f ( z ) 农x 中的一个局部极小值点z i ；然后设法找出，( z ) 的另一个局部极小值点z ；，该点要 满足如下不等式： ，( z i ) ，( 嚣：) 2 0 0 3 年上海大学硕士学位论文5 那么，妇僻根据。；来每找z ；啜? 其想法是拯造一秘辘勋丞数，它能壤潆f ( x ) 提。； 处的盆域曰；和其它简于b ：的f ( x ) 的盆域，并且z i 是辅助函数的局部极大点， b ；是辅助函数的山丘的一部分此外，在高予b ；的，( 。) 的忿域中麓髓函数没有 局部檄小点或平稳点，而在低于b ? 的一个盆域中，如果辅助丽数的局部极小点存 在的滔，沿着方向。i 可以极，j 、化辅毁函数，见( f 5 1 1 2 5 1 2 6 1 ) 1 2 3 随机算法和启缴式算法 最具挑战性的全蜀优化闻题之一是没有能被使角的任筒甚知特殊结构的闻题， 亦称为“黑箱”优化问题也就是说：众局极小化定义在一紧集dc 瞅上的连续函 数。隧撬冀：法正好逶_ 爨于解决诧类问熬这些方法一般在德纯闯题中仅需非常稻的 假设，而且至少能够撼供依概率收敛的框架随机算法主要分成三类；二阶段法， 夔撬援索方法搬逮援豢数法， 随着对数学模型及最优化方法的堂视，二十世纪八十年代初兴起的现代优化算 法在今天薅到了匿大瓣发展。瑷 弋使豫葵法通鬻是透过攘叛生物进匏、人工瞽糍、 数学与物理科学、神经系统和统计力学镎概念，以直观为基础构造的此类算法我们 髂之为塞发式算法骧着科学技术的发展，现农懿诤多算法已不能潢蹙解决复杂闻 题的需要，而启发式算法正开始体现其作用启发式算法主要包括禁忌搜索( t a b u s e a r c h ) 、模拟退火( s i m u l a t e da n n e a l i n g ) 、遗传算法( g e n e t i ca l g o r i t h m ) 神经隧 络( n e u r a ln e t w o r k s ) 及拉格期日松弛等算法 1 3 特殊结构的全局最优化问题和算法 述蠢谗多具毒符臻簿祷赘众焉最後纯瓣题，羹：方说辈极小、d c 魏翊、蕈澜蕊 划，二次规划和多项式规划以及l i p s c h i t z 优化问题等对于此类优化问题，我们常 用的箕法舂外逼近方法秘势支迩秀方浚 1 3 1 凹极小问题 当日标函数和约束函数均为凸函数时，此粪数学规划问题已有非常有效的算 法，因为凸规划问题的局部最傥解就是众局最优鼹，所以可用传统的菲线性起娥方 法求解但当目标函数和约束函数至少有一个不是凸函数时，该问题就变得相当复 杂了，屐至今没有一个有效的解决方法一类非常僮碍研究的全局优化阅题之一巍 带有线性约束的、目标函数为凹的凹极小问题，即凹规划问题凹规划的所有线性 2 0 0 3 年上海大学硕士学位论文 6 约轰鳃残了一个凸多露瘁。 由凹函数的定义，凹函数总是在凸多面体的顶点上取到全局最小值，所以可比 较容易建求褥闯题懿全局最谯解，当醒巍魁的约寒为一般凸巢时，逛露一些残骞翡 算法可求得问题的全局最优解，常见的算法有割平面方法和外逼近方法 1 3 2 d 。c 规划 当优化问题中的目标函数和约束函数都可以表示成两个凸函数之麓时，这类趣 划问题我# 疆为d ，c 规划阉蹶下面简单介绍一下dc 规翊中的一臻性质： 任意一个定义在瓞n 的紧曲泉上的二次可微函数为dc 函数 任意一个定义在辩上的二阶连续可徽函数为d g 函数 设，l ( z ) ， 。( z ) 是d c 函数，则函数翟l k ， ( 。) ( ；哟，h 暑l ( 。) ，i n “1 i s 。 江敬芨m i n i 。a ( x ) 稳为d c 函数， d c 规划问题可用外逼近方法来解外逼近方法最早是应用于解凸规划问题 戆，詹密叉被戏秘逶瘦瘸子鹜疑怒，爱国觳划及d ，c 怒翔阕题簿多 遗近方法酌主 要思想是通过建立一系列的凸多面体投 ，) r 不断逼近可行域s ，使得用问题 n x i n ，妇) | 。晟 懿黪逼近于x n i n ，( 。) | 。s 麓解 1 3 3 。单调全局最优化 单调优化是具有特殊结构的一类垒局优化问题在很多数学模型中，对某些变量 或所有变量函数往往具骞一定酶单调性，函数单调性鼷的分辑对于求鼹全局傀化耀 题的最优解是很有帮助的单调优化在缎济与工程中有很广泛的应用，例如最优淡源 配置问题，可靠性网络中的最优化问题等都是擎调全局最优化闽题，见( t 2 1 2 0 2 2 ) ； 本文所考虑的单调优化问题可叙述如下t 彳= qsz ，茎幻，j = 1 - ( 1 3 ，1 ) 其中，：黔_ r ：虢：孵- 鲢都是二除连续可微觞函数，豆满足下述单调性鼷： ( i ) ，( z ) ，g i ( z ) ，i = 1 _ n ，都魑严格递增的函数，或者( i i ) ，( z ) m ( z ) ，i = 1 ， 川。 部是严壤递减的函数，在这里0 a j o ，j ，) 。对于所有js4 ， 著护d ，爨旷= a r g m i n f ( v j ) 藏楚蹶闯蓬酶最凌繇否劐豹活，登套d 中戆菜 约柬不满足a i t ”a 墨， v ，满足c 唆0 并且v j t d ，把该约束添加进去 鼹可褥裂凝戆楚多蓉绺，劳量霹末褥耨基多瑟薅懿璜患重复上瑟豹多骤，瑟露，萼 到问题的最优解或近似最优解具体算法见 4 _ 定理2 1 。3f a l k 每h o f f m a n 的綦于上述螅下 蠢诗函数方法，雾法巽莠m 步毒踉终 止 2 1 。2 ，】芟患辩淳方法 顶点排序方法主矮有两大步：第一步是如何建立，的线性下估计函数。第二步 是在选好下估计函数翳，如何谆我下待计函数在包含可行域d 的区域上的次最好 点 考虑问题： ( c p r a i n ，( 。) ，s t 。d 其中d 为有界多面体，f 为d 上的凹函数令v = 1 ，”2 ，毗，k n + l ，c 觥 并显c o w ) dd ，逶避这些囊 患我们霹建立，鳇线睦下凭诗菌数： g ( x ) = c t x 十b ，c r ”，b r 2 0 0 3 年上海大学硕士学位论文 满足g ( z ) 在c o ( v ) 上下估计，且满足在y 的至少n + 1 个顶点上g ( v i ) s ，( ”。) ，i = 1 ，2 ，等式成立，也就是要满足： m 咖i n 三( ，。1 如。) 1 s t g ( v i ) s ，( 吐) i = 1 ，2 ，k 这样，的一个线性下估计函数9 ( z ) 就可通过解一个关于c ，b 的线性规划得到记 ( l p ) r a i n g ( z ) x c o ( v ) 性质2 1 1 如果x 0 是仁p 的一个最优解，+ 是r g 引的一个最优值，则g ( x o ) ，+ ，( z o ) ，也就是说9 ( z o ) 是，的一个下界，( z o ) 是，的一个上界 性质2 1 2 对于，+ 的任意一个上界凡，记 。 为似纠中满足g ( x e ) s ，u 的所有 顶点，则r c 驯的最优解满足z + f z 女 顶点排序方法的具体算法： s t e p 通过解( l p ) 线性规划得到o ，取，fzg ( x o ) 作为，+ 的一个下界 s t e p2 取丘= ，( z o ) 作为，+ 的一个上界，则z o 作为原问题( c p ) 的一个目前 最好的解 s t e p3 取9 ( z ) 的一个次最好点x k ，如果9 ( x k ) f u ，则算法停止，x o 就是原 问题( c p ) 的最优解，+ = 凡= f ( x 0 ) 反之，令 = g ( x k ) s t e p4 如果，( ) ，则令 = f ( z k ) ，目前最好的解变为x k 反之，则保持 最优解为z o 不变，转s t e p3 总结：在最坏的情况下，上面的顶点排序方法可能会列举完凸多面体的所有顶 点，所以当问题规模很大时，顶点排序方法也不是很好的方法 2 2可行域为一般凸集的凹极小问题 2 2 1 割平面方法 割平面方法可用来解决可行域为一般凸集的凹极小问题在众多的割平面方法 中，最常用的就是凹割方法凹割方法在解决可行域为一般凸集的凹极小问题上是 非常有效的，见( 2 ) 具体步骤： s t e pj 首先找一个以x o 为顶点的包含可行域的锥k ，并且假定这个锥由，。个 线性无关的向量峨一x o 组成，其中v 。属于可行域的边界，i j = 1 ，2 、r z v 。 在凹割算法中一般是比较容易求得的 2 0 0 3 年上海大学硕士学位论文 1 2 s t e p2 驭了= m i n ( z o ) ，f ( v 1 ) ，”。) ，对任意豹le ，遽取盈，其孛z 嫂于 x o + o ( v i z o ) ) 上且满足，涵) 三7 s t e p3 对于在s t e po 中选取鲍n 个z i ，可构造个平嚣通过爨蠢戆盂 ( e t z 一，。o ) = 1 其中z 是自n 个列向爨z i 一o 组成的n n 缎阵，e 是“维列向量 s t e p 记d 为黻极小越题的可霉亍域。由锺标函数，的鹫性，可褥 ，( z ) 7 ，v z d n k n 茁p l ( e f z 一1 ，一2 9 0 ) 茎l 若d 中的所有点都包禽在d n k n z 引黔i e t z 一，z 一2 9 0 ) 1 ) 中，则7 就是最优 值落在s t e p1 中我们选取的啦；i j 均满足，( 。) s ，泓) ，则。就是问题的凝优 解褥则的谣，转s t e p2 ，重复上述步骤 蒜j z d ，满足，( ) 2 。， d = i n f d zv 2h ( x ) d iz x ，i i d t l 2 = 1 一0 0 i i i ) t 为严格递增的凸函数 i v ) t ：，i = 1 ，n 严格递增且满足 器r 咖m 则存在有限数p o 0 ，当p p o 时，h p ( y ) 为y p 的任一凸子集上的凸函数 1 7 2 0 0 3 年蔓鸯大学硬学泣论支 1 8 注3 1 1 设 z ) 为x 上的严格递减函数，则 ( 一z ) 为一x 上的严格递增函数，蘼 以陋j 纠中的凸他变换我们可写为： 话，一z ( p h ( 一；t 一砖e 功) ) 砖于 ( 。) 严格递减时，当定理只 1 中的 ( 2 ) 和t 分葶 l 替换为 一# ) 和t ，定理 3 j 也是适用的另外，我们逊可把这一结论推广到 ( # ) 对于菜些变蚤严格递增， 而对另砖一些变量严格递减的情况 文【2 4 】中推广的凸化变换如下： ) 一马f h ( t p ( ) ) ) f 3 1 ，劭 在这擞，p 是一大于零的参数，t p ：爬1 + 琏1 为实鲻数并且t p ( y ) ：桫- 桫可 分离，郎对于y = ( y l ，y n ) ，如( 们= ( t l ，p ( 9 1 ) ，t 2 十( 船) ，t n ,