（应用数学专业论文）preinvex函数及其推广.pdf

内容提要 本文的主要由两部分组成第一部分。首先，引入了一个新的概念散射点。 并利用它来刻画i n v e xs e t 及其与一般集合。凸集之间的关系同时，还利用散射点 来分析规划问题m i n x e sf ( z ) 的最优解的特征，其中( z ) 是可行域s 上的p r c i n v c x 函数；接下来，在这一部分还把与凸函数有关的上境图等概念弓i 入到p r e i n v e x 函数 中得到了与p r e i n v e x 函数相等价的刻画。并利用这一刻画来分析p r e i n v e x 函数的性 质 第二部分，介绍一类由p r e i n v e x 函数变形而来的函数s e m i s t r i c tp r c i n v e x 函数及s t r i c tp r e i n v e x 函数，讨论了s e m i s t r i c tp r e i n v e x 函数与其它广义凸函数之间 的关系 关键词：i n v e xs e t ，p r e i n v e x 函数，p r e - i n v e xs e t ，散射点，俨凸包，s e m i s t r i c y p r e i n v e x 函数，s t r i c tp r e i n v e x 函数，o 条件 a b s t r a c t l l t h i sa r t i c l em a i n l yc o n s i s t e so ft w os e c t i o n s ：i nt h ef i r s ts e c t i o n ，t h es t r u c t u r e o fi n v e xs e t sa n dt h er e l a t i o na m o n gg e n e r a ls e t s c o n v e xs o t sa n di n v e xs e t sa r e r e s p e c t i v e l yc h a r a c t e r i z e db ym j i so ft h es c a t t e r i n gp o i n t sw h i c hw i l lb ed e f i n e d i nt h i sp a p e r ，a n dt h ec h a r a c t e r i s t i co ft h eo p t i m a ls o l u t i o no ft h ep r o g r a m m i n g m i n z e s ，( z ) i sa n a l y s e dn s e i n gt h es c a t t i n gp o i n t ，w h e r ef ( x ) i sap r e i n v e xf u n c t i o n o nt h ef e a s i b l ef i e l ds p r e i n v e xf u n c t i o n sa r ec h a r a c t e r i z e db ye p i g r a p hw h i c hi s d e f i n e di nt h ef o l l o w i n g ，a n dt h ep r o p e r t i e so fp r e i n v e xf u n c t i o n sa s eg i v e nb yt h e c h a r a c t e r i z a t i o n i nt h es e c o n ds e c t i o n ，s o m i s t r i c tp r e i n v e xf u n c t i o n sa n ds t r i c tp r e i n v e xf u n c t i o n s a r ei n t r o d u c e da n dt h er e l a t i o nb e t w e e ns e m i s t r i c tp r e i n v e xf u n c t i o na n do t h e rg e n e r a l c o n v e xf u n c t i o n sa r ea l s og i v e n k e yw o r d s ：i n v e xs e t ，p r e i n v e xf u n c t i o n ，p r e - i n v e xs e t ，s c a t t e r i n gp o i n t ， ，卜i n v e xh u l l ，s o m i s t r i c tp r e i n v e xf u n c t i o n ，s t r i c tp r e i n v e xf u n c t i o n ，c o n d i t i o nc 第一章引言 第一章引言 凸规划是非线性规划中非常重要的一类，它有许多很好的分析性质。因此，它在 最优化理论，经济数学。工程，管理科学中都有着广泛的应用但在现实生活中出现 的许多规划问题并不满足凸性条件，与此同时人们对凸性( 包括凸函数，凸集等等) 的分析与研究也已达到相对比较完备的程度了【1 1 因此在近几十年来人们开始关注 比凸函数更广的函努r 类一广义凸函数于是，许多类形的广义凸函数。如r 伪凸函 数，拟凸函数，c o n v e x l i k e 函数等等便应运而生由于它们是比凸函数类更广的函 数类，因此，它们具有更广泛的应用空间。从而，这些函数类都得到了不同程度的研 究在众多的广义凸函数类中，i n v o x 规划所涉及到的广义凸函数类虽然提出较迟。 但是，其良好性质和广泛的应用前景却倍受关注因此本文将对它们进行介绍与分 析 现实中有一类规划问题虽然不一定是凸规划，却保持了凸规划的局部最优解为 全局最优解等重要特征。同时又可把可微凸规划视为这一类规划的特倒这类便是 被称为i n w x 规划的规划问题 设d 为彤的开集，g ：d 一月”是开集d 上的可微函数，q ：彤r n 一册 是一个向量值函数则g 是可微凸函数当且仅当 9 ( 茹) 一g ( u ) 一扛一u ) 7 v g ( u ) 0( 1 0 1 ) 式( 1 , 0 1 ) 称为g 的凸性条件 1 9 8 1 年，h a n s o n 2 j 引入函数的r - 凸性条件事实上，将式( 1 0 1 ) 中的0 一t ) 用q ( z ，u ) 代替，就得到g 的中凸性条件- 对任意。，u d ，有 g ( x ) 一g ( u ) 一q ( 。，u ) t v g ( u ) 0( 1 0 2 ) 满足咿凸性条件的函数称为俨凸函数( 或关于”的i n v e x 函效) 若，：d r 和g ：d j p 都是开集d 上的十凸函数。则规划 ( p ) m i n 印肝， s t g ( x ) s0 被称为i n v e x 规划 c r a v e n i s 讨论了在可微可逆的坐标变换下性质不变的规划问题( p ) ，这类规划及 函数就被称为i n v ( 这是英文i n v a r i a n tc o i l v o x 的缩写) ，又由于两位作者的缘故其 第一章引言 2 亦称为h c - i n v e x r i t a ”1 及b m o n d 等人嗍研究表明，一个函数为i n v e x 函数当 且仅当这个函数的每个稳定( 驻) 点都是全局最小点因此，i n v e x 规划的每个可行 k t 点为全局最小点，问题( p ) 和它的w o l f e 对偶之间的弱对偶定理成立后来， m a r t i n n 根据上述两个性质分别把h c - i n v e x 减弱为k t - i n v e x ，w d - i n v e x 再分别进 行研究另外，s c h a i b l e 1 q 及y a n g 等人【1 m 把可微凸函数与广义单调映射的关系推 广到i n v e x 函数，并研究了一般i n v e x 函数与一般不变单调映射之间的关系 k a u l 等人嘲把卜凸函数减弱为，卜拟凸函数或叩_ 伪凸函数等等m o h a n n 及w e i r 等 人m 研究了与十凸函数相关联的还有另一类重要的函数p r e i n v 镊函数它是 般凸函数的推广，因此，类似于一般凸函数的定义域为凸集，p r e i n v e x 函数的定 义域是i n v e xs e t ，因此，先介绍i n v e xs e t 的定义l 定义1 1 1 n对于集合a r “，若存在向量值函数q ：形r “一舻，使得 对任意，y a ，0 a 1 ，有y + 蛔( 茹，y ) a ，则称a 是关于q 的i n v e xs e t 现在再给出p r e i n v e x 函数的定义。 定义1 , 1 2 n设 为彤上关于q 的个i n v e xs e t ，设，：a r 是一个函 数，若对任意，y r “，有 ( y + 加0 ，) ) a ，( 甸+ ( 1 一a ) f ( y )( 1 0 3 ) 成立，则称，为关于7 7 的p r e i n v e x 函数 由定义易知，若，是可微的关于”的p r e i n v e x 函数，则，是”一凸函数；反之 则需要满足条件c i s 才成立 条件c ：设t 7 ：r nx 舻一舻是一个向量值函数，若对任意，y 胛， 0 s 冬1 ，有 q ( f ，y + a q ( $ ，y ) ) = 一a ”( o ，y )( 1 0 4 ) 与 r ( x ，y + a q ( z ，y ) ) = ( 1 一a ) v ( x ，y )( 1 0 5 ) 同时成立，则称町满足条件c p r e i n v c x 函数是介于一般凸函数与c o n v e x l i k e 函数之间的类函数 z l ，即它比一 般凸函数弱，但比c o n v e x l i k e 函数强它除了具有般的i n v e x 规划函数所具有的局 部最优解是全局最优解等性质外，还有自身所特有的性质，如t 在凸性条件下成立的 “综合定理”在p r e i n v e x 函数的假设下也成立州正由于p r e i n v e x 函数有许多好的 性质。因此有许多人开始从各个方面研究p r e i n v e x 函数，或是研究其与上，下半连 续函数等各种函数的关系及其自身的各种性质【6 】【7 1 【，或是把p r e i n v e x 函数和i n v e x 函数定义中的太于零的条件用一个正锥k 来代替而形成了向量值的p r e i n v e x 函数 第一章引言 3 与向量值的i n v e x 函数，然后，再对其对偶等性质进行研究1 1 5 i 1 q l ”】因此，作为一 般凸函数推广的p r e i n v e x 函数在多且标规划中也起了重要的作用【7 1 y a n g 1 0 1 及t e o 等人i n 则更介绍了两类由p r e i n v e x 函数变形而来的函数一8 e i n i s t r i c tp r e i n v e x 函 数及s t r i c tp r e i n v e x 函数，并给出s e m i s t r i c tp r e i n v e x 函数与p r e i n v e x 等函数之间的 一系列互相转化的关系及它们的一些性质总之。p r e i n v e x 函数类是个重要的函 数类 本文将从i n v e xs e t 的研究入手给出一类规划的解的特征及算法。并给出p r e i n v e x 函数的等价条件，进而给出p r e i n v e x 函数的某些运算性质最后，给出s e m i s t r i c t p r e i n v e x 函数与i n v e x 函数及s t r i c tp r c i n v e x 函数之间的关系 为了后面的叙述方便，我们还要给出s t r i c tp r e i n v e x 函数和s c m i s t r i c tp r e i n v e x 函数的定义 定义i i 3 【1 0 】设a 为j p 上关于叩：彤彤_ 舻的一个非空i n v e xs e t ， 设，：a r 是一个函数，若对任意。，”a ，( ) ，( 可) ，有 f ( y + a q ( z ，f ) ) r l o ) ，把 s 分成四个子集； & = ( z l ，写2 ) si 霉l o ，z 2 o ， 岛= ：“。l ，x 2 ) sx l 0 ，茹2 o ) ， 岛：= ( 。l ，z 2 ) s3 ：1s0 ，z 2 0 ，z 2 0 ) 易知，当r - = 孚r 2 时，s l ，s 2 ，s 3 ，& 的散射点分别为a = ( 乎r 。，孚r 2 ) ，b = ( 一乎r 2 t 乎r 。) ，c = ( 一乎r 2 ，一乎r 2 ) ，d = ( 乎7 2 ，- - q r 2 ) 若取 in y ，当岛 l 6 一，当 q ( z ，y ) = c y ，当y s 3 ld y ，当s 4 i 口，当掣车s 易证，当r 2 c o s ： r r 2 c o s 嚣i 时，s 至少要分成n + 1 个子集之并才能使得每 个子集都有一个散射点，其中n 为大干j 的整数由此可见，当n r 2 时，子集 数n 一当r l = r 2 时，集合s 由圆环变成圆周。这时s 是无散射集 从另一个角度去看，若上述圃周是关于某个向量值函数p 的 b 钟z3 踮则对任 意，”s ，必定有芦( z ，”) i0 ，否则，若p ( z ，) 0 对某些z ，矿s 成立。则砷 任意a 【0 ，1 有矿+ a p ，v 7 ) s ，与s 是圆相矛盾因此圆周是弱i m s e t 当 r = 0 时，s 是圃盘，它是强i n v e zs e 我们把弱i n v e x8 e t 和强i n v e xs e t 统称为平凡i n v e xs e e 以下我们所讨论的i n v e x s e t 均是非平凡的 定理2 1 2 设0 s = u l z + 最r n ，且每个子集至少含有一个散射点1 ) i 则s 是一个关于某个非零向量值函数”：r ”j p _ 尼。的讥u e zs e t 第二章关于p r e n v e x 函数的性质 6 证明对任意。，y s ，由s = u 拒尉& 知，存在i z + 使得v & ，则 k l y 瓯 0 ，取j = m i n k i y 最) ，令 ”c z ，v ，= 一”誊i i s 由s 为不可列集知，存在i 使得s i 中至少有两个不同元素，因此叩不会恒等于零 于是对任意一，s ，a 【0 ，1 ，有 y + q ( 一，y 7 ) = y + a ( v l 一矿) = + ( 1 一a ) 矿s l s s 其中1 = m i n k l y 瓯) ，则s 是一个关于町的i n v e xs e t 口 为了更好地看出散射点的作用先看下面的例子t 例子2 1 2 设s = s l u 岛，其中 s l = ( 。1 ，x 2 ) i - 1s 茁l 1 ，- i x l i 善2 茎1 ) ， 耻( - 5 x l + x 2 _ - 4 ) u ( 。：) - 8 _ x l + x z _ 0 ，使得对于任意 z 肛( z 。) ns ，有，( 口。) ，( z ) ，其中札( $ 。) 表示。的e 邻域若z 。不是 m i n 。e s f ( x ) 的全局最优解。则一定存在虿s 使得， ，( z 。) 由s 是关于q 的 i n v e xs e t 可知，对每个a 0 ，1 】，有z 。+ 蛔( 茁，：g o ) s 又由于f ( x ) 是p r e i n v e x 函 数，则对于a ( 0 ，1 1 ，有 f ( x 。+ a 叩( 虿，z 。) ) a f ( - ) + ( 1 一a ) f ( x 。) ，( 司( 2 3 1 ) 其中s 。是s 的内部因为m i n e 彤，( z ) 的最优值是一o o ，或者其最优解在可行域s 之外。所以一定存在一点一形s 使得，( 一) ，( 习由于，是凸函数，所以在 矗叶1 中( 奢，( 动) 与( 。，( 一) ) 的连线定在e p i f ( f 的上境图) 中，即对任意a l o ，1 】， 有 a ( 一，( z ) ) 十( 1 一a ) ( 夏，( 动) e p i f , 则 ，( a 一+ ( 1 一a ) 动墨a ，( 一) + ( 1 一a ) ，( 动 a + ( 1 一a ) ，( 习= ，( 动 不妨设线段 妇7 + ( 1 一 ) za 【0 ，1 ) 与s 的边界相交于点岔，则有，( ) ，( 习， 与( 2 3 1 ) 矛盾所以，最优点定在边界上d 若s 是舻的有界闭子集，是舻上的可微凸函数，则可用下列方法求出规 划r a i n 。sf ( x ) 的最优解 首先，求出函数，的梯度，再判断在r n 上，是否存在梯度为零的解。若不存 在或是存在但不在可行域中，则可在其边界上求出最优点；否则，在s 中存在梯度 为零的点。即规划的最优解 例子2 3 1 考虑下列两个规划。 竺t 掣1z y 2 穿9 协s 锄 s 0 2 + 1 第二章关于p r e i n v e x 函数的性质 1 5 竺搿笔4 r c z 删 5 t 1 z 2 + 2 9 、 函数0 1 ) 2 + 0 + 2 ) 2 的梯度为零的点n ，- 纠在规划俾只纠的可行域内。所 以规划俾j 纠的最优解为一，一砂；函数扣一4 ) 2 + 0 + 4 ) 2 的梯度为零的点在规划 俾只剐的可行城内之外，则规划俾只印的最优解在可行城的边界上。因此需要对 边界进行一维搜索，将规划俾只到转化为下列两规划- ”伽= ( 。8 目一4 ) 2 + ( s i n 0 + 4 ) 2 4 ) s t 口1 0 ，2 叫 与 r a i n 缎2 璺刚“) 2 + ( 3 s i n 9 + 4 ) 2 ( 2 3 5 ) s t 口f 0 ，2 州 、7 则可得到规划的最优解( 警，一学) 啻l i 子2 3 2 考虑下列规划。 r a “i n 芝善羔学尸 偿s q s 2 2 2 9 ” 0 ，是关于”的p r e i n v e x 函数且满足l i p s c h i t z 条件 第二章关于p r e i n v e x 函数的性质 1 7 针对规划( 2 3 1 0 ) ，具体的邻域算法如下：设l i p s e h i t z 条件中的常数为k ，q ( 。，) 不是散射点与v 之差 第一步取充小的正数e2o ( 可取= 去，n 为足够大的自然数使得击 d d ) ，并设最优解为矿，k = 1 ，s = ( z l ，x 2 ) l d 2 5 + z ；s d 2 ) ； 第= 步用一维搜索分别解下面二个规划t m i n 妒( ! j 。璺m 刚，删仰) ( 2 3 1 1 ) s t 0 f 0 ，2 州 、 和 l l l i n 妒( 9 j 2 璺8 瞄9 ，幽n 8 ) ( 2 3 1 2 ) 8 t 0 【0 ，2 叫 、 得最优解吼和如设z ( 1 ) = ( d c o s 8 1 ，d s i n o i ) ，。( 2 ) = ( d c o s e 2 ，d s i n 0 2 ) ，取虿 z ( ”，z ( 2 ) ) 使得f ( x ) = r a i n f ( x ( 1 1 ) ，( z ( 2 ) ) 暮= ( _ 1 x 2 ) 再求解方程 ( - l + c o s o ) 2 + ( _ 2 + e s i n 0 ) 2 = d 2 或 ( 面l + s c o s 0 ) 2 + ( _ 2 + es i n 0 ) 2 = d 2 ， 得两个解o l 和不妨设o l 吒，若( _ l + s c o s 笃韭，- 2 + s i n ! i ) s ，则取 i = 暇，矧否则，取1 = 慨，斯+ 钟j 对下列规划进行一维搜索 m i n 妒竺) = ，( ( _ l + s c o s 口，_ 2 + e 8 1 n 口) ( 2 _ 3 1 3 ) s t 0 i 、 得最优解矿设矿= ( - 1 + e c 0 8 0 i _ 2 + e s i n o ) 若f ( u ) ，( 动，则z 。= 面，i l e a l ； 否则，取k = 1 ，“ = i ，c k = “+ 一_ 第三步设k = ( 讥l ，u 2 ) ，q = ( c k l ，c k 2 ) ，求解方程 ( u k l + 1 ) 2 + ( u 2 + a 2 ) 2 = d 2 与 ( u k l + a “1 ) 2 + ( u k 2 + a q 2 ) 2 菡d 2 ， 得到至少两个正实数解，设它们中的最小者为”用一维搜索解规划问题 ：m 妒旦、2 5 + a “ (2314)t 0 o a ” 、7 第二章关于p r a i n v e x 函数的性质 得最优解 ( ) 取t + l = = u k + a 非) c k ，e i = t + l 第四步设e k = ( e k l ，e k 2 ) ，取 “= m i n 毛d 一、甄，、瓢一d ) 对下列规划进行一维搜索 r a i n p ( ! j 亍! 8 k + 。k 。8 8 ，8 2 + 2 k8 1 n8 ) ( 2 3 1 5 ) s t 0 o ，2 f 1 、7 得最优解设e + 1 = ( e k l + k c o s 砹，e k 2 + l ks i n 0 , ：) 着f ( e k ) f ( e e + 1 ) ，则矿= e b 退出；否则，= e k ，“= e k + l 一。k ，= + 1 ，转第三步 取s = 击时，当n 一十o o ，算法所得到的点的值则可以无限接近于最优值 例子2 3 3 考虑目标函数为非凸函数的规划； 椭l ，( 蟊) 5 焉丽1 s 1 s0 2 + y 2 4 ( 2 3 1 6 ) 解： 由目标函数易知最优解集为t ( ，”) i 善2 + v 2 = 4 ) ，而这时的最优值为i 1 若用上述算法来解。则有。 令s = ( z ，v ) i x 9 2 + v 2 4 ) ，显然， s = u e z o ，2 , 0 ( a c o s o ，a s i n o ) ia f 1 ，2 】) 且( 2 c o s 0 ，2 s i n o ) 是集合 ( a c o s o ，a s i n 0 ) la 【i ，2 】) 的散射点 若f 7 l ：舻r 2 _ r 2 满足对任意茁= ( k c o s o = ，a = s i n 0 = ) ，v = ( c o s o y ，s i n e y ) s ，有玑0 ，y ) = ( ( 2 一a f ) c o s 如，( 2 - a f ) s i n ) ，其中1 兰k ，2 ，os 如， 0 时是凸的，则有 f ( y + a t _ h ( z ，) ) = 入j i = 1 ”叫击 = a f ( x ) + ( i x ) f ( y ) 丽岵 上”卜 一+ + 西j 呵 第二章关于p r e i n v a x 函数的性质 1 9 所以，由算法之前的叙述可知散射点为最优解； 缈若) 2 ：r 2 t t 2 _ r 2 满足对任意z = ( kc 0 5 0 z ，k8 i n 以) ，v = ( c o s o v ，s i n o y ) s ，有r n ( z ，) = ( k 一) ( c o s 0 f ，s i n a ”) ，其中1 k ，s2 ，0 如，钆 l 如果g 满足下列两个条件，则称其为关于叩的p r e i n v e x s e t 印对任意k r ”1 ，如果玎1 ( k ) n g 0 ，则 名= t 忱( 茹) r i l p i l ( ) a g ) 有下界，其中p i l ( ) = 扣r “i 妒1 0 ) = ) j 圳对任意。，“口，有忱( ”( 蜀u ) ) s i n f i 。扣) 一i n f p 。扣) 。 定理2 4 2 口j 设，为定义在非空的关