Lipschitz函数全局优化的区间算法.pdf

第3 6 卷第5 期中国矿业大学学报 V 0 1 ．3 6N o ．5 2 0 0 7 年9 月J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g ＆T e c h n o l o g yS e p ．2 0 0 7 文章编号1 0 0 0 1 9 6 4 2 0 0 7 0 5 0 7 1 1 一0 6 L i p s c h i t z 函数全局优化的区间算法 孙靖1 ’2 ， 1 ．中国矿业大学理学院，江苏徐州 2 2 1 1 1 6 ；2 ． 曹德欣1 淮海工学院数理科学系，江苏连云港2 2 2 0 0 5 摘要利用广义梯度讨论了目标函数是L i p s c h i t z 连续的非光滑优化问题的区间算法，给出了求 二维函数广义梯度的区间算法，提出了利用广义梯度估计L i p s c h i t z 常数的方法．定理和数值算 例表明，通过随算法的进行而不断修正L i p s c h i t z 常数，算法的收敛速度得到了一定的提高． 关键词非光滑优化问题；区间算法；广义梯度 中图分类号O2 2 1 ．4文献标识码A A nI n t e r v a lA l g o r i t h mf o rL i p s c h i t zG l o b a lO p t i m i z a t i o n S U NJ i n 9 1 “．C A OD e - x i n l 1 ．S c h o o lo fS c i e n c e s ，C h i n aU n i v e r s i t yo fM i n i n g ＆T e c h n o l o g y ，X u z h o u ，J i a n g s u2 21 1 16 ，C h i n a ； 2 ．M a t h e m a t i c sa n dS c i e n c e ，H u a i h a iI n s t i t u t eo fT e c h n o l o g y ，L i a n y u n g a n g ，J i a n g s u2 2 2 0 0 5 ，C h i n a A b s t r a c t A ni n t e r v a la l g o r i t h mf o rs o l v i n gan o n s m o o t ho p t i m i z a t i o nw a sd i s c u s s e d ，w h o s eo b je c t i v ef u n c t i o ni sL i p s c h i t zc o n t i n u o u sb yg e n e r a l i z e dg r a d i e n t ．A ni n t e r v a la l g o r i t h mf o rc o r n p u t i n gg e n e r a l i z e dg r a d i e n to ft W O d i m e n s i o nf u n c t i o na n dam e t h o df o re s t i m a t i n gL i p s c h i t z c o n s t a n tb yg e n e r a l i z e dg r a d i e n tw e r eg i v e n ．T h et h e o r ya n dn u m e r i c a lr e s u l t ss h o wt h a tt h e c o n v e r g e n ts p e e do ft h ea l g o r i t h mi si m p r o v e dd u et ou p d a t i n gt h eL i p s c h i t zc o n s t a n tw i t ht h e a l g o r i t h mp r o c e e d i n g ． K e yw o r d s n o n s m o o t ho p t i m i z a t i o n ；i n t e r v a la l g o r i t h m ；g e n e r a l i z e dg r a d i e n t 由于区间优化方法具有对非线性函数比较容 易处理及算法的可靠性、收敛性均有保证的特点， 区间优化方法成为求解L i p s c h i t z 函数优化问题的 一个有效方法．文献[ 1 ] 提出了用区间数学方法求 解非光滑优化问题，并在该领域的研究取得了一些 成果，文献[ 2 ] 将两阶段法与区间方法结合，并利用 广义梯度求解非光滑优化问题，文献[ 3 4 ] 用区间 方法分别讨论了无约束连续M i n i m a x 问题和带约 束的离散M i n i m a x 问题，文献[ 5 ] 则将区间数学方 法和极大熵方法结合构造了求解非光滑优化问题 的区间极大熵法，文献[ 6 ] 利用广义梯度求解了单 变量的L i p s c h i t z 函数全局优化问题，本文考虑下 面L i p s c h i t z 函数全局优化问题 m i n 厂 z ，∈X O 其中X ‘o ’一{ z 一 z 1 ，z 2 ，⋯，z 。 ∈ R ”I 1 z i ∈[ 口i ， b i ] cR ，i 一1 ，2 ，⋯，竹 ；， z X ∞’cR ”一R 在 X ‘0 ’上是 秩K L i p s c h i t z 连续的，而且是正则的． 本文利用广义梯度给出了求解问题 1 的区间 算法，同时构造目标函数的区间扩张，并建立加快 算法收敛的两个删除检验原则，对于广义梯度的区 间扩张的计算，将重点讨论二维L i p s c h i t z 函数，该 算法不难推广到多维情形． j R 表示R 上所有有界闭区间所构成的集 合，则J X ∞’ 一{ X ∈J R IX ∈X ‘0 ’ ．m X ， Ⅳ X ，I n t X 和R X 分别表示X ∈， X ∞’ 的 收稿日期2 0 0 6 一1 1 1 0 基金项目国家自然科学基金项目 6 0 5 7 5 0 4 6 ；中国矿业大学科技基金项目 A 2 0 0 4 1 0 ；淮海工学院科研基金项目 Z 2 0 0 4 0 2 9 作者简介孙靖 1 9 7 5 一 ，女，江苏省沐阳县人，讲师，理学硕士，从事计算数学方面的研究． E - m a i l s u n j i n 8 r h h i t ．e d u ．c nT e l 1 3 1 5 1 7 7 8 7 8 6 万方数据 7 1 2中国矿业大学学报 第3 6 卷 中点、宽度、内部及半径．如果函数， z 与区间函 数F X 满足厂 z 一F z ，厂 z ∈F X Vz ∈ X ，则称F X 为， z 的区间扩张．其他区间数 学的相关概念和内容可参阅文献E 7 3 ．下面给出非 光滑分析中的几个定理，其他与非光滑分析相关的 知识可参见文献E 8 3 ． 定理1 [ 8 ]设厂 z 在z 点 秩K L i p s c h i t z 的， 则对O f x 中的任何f 都有 』钏．≤K ． 说明1 定义B x ；￡ { Y ⋯x - - yI I ，V 口∈X ． 3 共轭空间X ’的范数』驯。定义为I | 钏。 s u p { 善，u J 可∈X ，0 口I I ≤1 ． 定理2 [ 8 ] L e b o u r g 设X 是B a n a c h 空间， z ，Y ∈X ，f 在包含线段[ z ，y ] 的开集上L i p s c h i t z 连续，则存在点U ∈[ z ，y 3 ，使得 厂 y 一， z ∈ ． 定理3 C 8 1 设X l ，X 2 是B a n a c h 空间，如果厂 在z z l ，z 2 ∈X l X 2 处是正则的，则 a f x l ，z 2 ca l f x l ，z 2 a 2 f x l ，z 2 ． 1 广义梯度的区间扩张及有关定理 设， z 是X ‘0 ’c Ⅳ上 秩K L i p s c h i t z 连续 的函数，定义 a F X c o n v { Ua f x 一[ 口，仞． 则a F X 是a f x 的区间扩张，其中口一 口。，口2 ， ⋯，％ T ，卢一 届，岛，⋯，晟 T ，X 一 X 1 ，X 2 ，⋯， X 。 T ∈j X ∞’ ，X 。一[ z i ，五] ．特别地，引进以下 记号J x { 歹∈{ 1 ，2 ，⋯，行} I Ⅳ 墨 ≠0 ； 0a F X I Ix m a x { I 口；I ，l 晟I } ．由定理1 可知， l ∈J X 0O F X I Ix ≤K ，因此Ia F X 8x 可以作为 L i p s c h i t z 常数的一个估计． 设一维函数， z 在X ∈I X ‘0 ’ 上是 秩 K L i p s c h i t z 连续的，则厂 z 在z 点的广义梯度可 表示为 a f x 一[ 1 i mi n f { I f x 一f x 一艿 ] ／艿 ， 1 ．i m ． s u p { [ ， z 占 一厂 z ] ／艿 ] 垒[ 虬，位] ． 则、口一m i n { ％ ，卢 m a x { 位 ． 2 z ∈Xz e 五 下面考虑二元函数f x l ，z 2 X 1 ，X 2 cR 2 一R 的广义梯度的区间扩张． 由定理3 可知，二元函数f x 。，z 。 的广义梯 度可利用文献[ 6 ] 中计算一维函数广义梯度的方法 来计算．二元函数的广义偏梯度可表示为 a l f x l ，z 2 D 。i m ．i n f { [ 厂 z 1 ，z 2 一f x l 一艿，z 2 ] ／d ， l 。i m ． s u p { [ 厂 z l 艿，z 2 一f x l ，z 2 ] ／占 ] 垒 d00 [ a l v 。，J 9 l 叩。] ， a 2 f x l ，士2 一 [ 1 i mi n f { [ ， z 1 ，z 2 一f x 1 ，z 2 一艿 ] ／艿 ， d ‘0 1 ．i ．ms u p { [ 厂 z l ，z 2 艿 一f x l ，z 2 ] ／a ] 垒 a ‘0 一 [ 口2 饷，屉甲] ． 定义 a 1 F X l ，z 2 c o n v { Ua l f x l ，z 2 ， z l e 1 a l F X 1 ，X z c o n v { U 。a 1 F X 1 ，z 2 垒[ 口l ，J 9 1 ] ， z 口t o a 2 F x l ，X 2 ；e o n v { Ua 2 f x l ，z 2 } ， z 2 e Z a 2 F X l ，X 2 c o n v { U ，a 2 F x 1 ，X 2 } 垒[ 口2 ， ] ， ，1 t 1 O F X 1 ，X 2 一a 1 F X l ，X 2 a 2 F X 1 ，X 2 ． 则 口1 2 卟珊∈x 2 ‰心} ，。l ∈x l t ’∈x 2 ‘‘ 肛水嚣禁x 。帆’h 3 ，l ∈X I t 。2 ∈X 2 1‘ ，叠、 a z2 卟艘∈x 2 { ％- 屯 ， 2 1 ∈x l ，’∈x 2 ‘‘ 屉2 1 ∈m a x ∈x 。眠巳 。l ∈x l ，屯∈x 2 1‘ 易证a l F X 1 ，X 2 ，a 2 F X 1 ，X 2 ，a F X l ，X 2 分别是a l f x l ，z 2 ，a 2 f x l ，z 2 ，o f x l ，z 2 的区 间扩张． 首先讨论计算广义偏梯度a 。F X ，，X 。 的算 法过程． 设将X 。分为愚等分，节点分别为 z - 』一c ．f 一1 生尹 _ 『一1 ，2 ，⋯，忌 1 ． 分别计算 a l F X 1 ，z l 』 垒[ 口1 蔚，届蔚] ． 且设 a l 一m i n { a l 蔚 ，J 8 1 I m a x { ‰ ． 4 则下列定理成立． 定理4 当志一∞时，口l I 一口l ，岛I 一届． 证明 由式 4 ，存在z 2 ，使得口l I a 。F X 1 ， z z ，对于该z z ，存在足及歹∈{ 1 ，2 ，⋯，志 1 使得 z z f _ 『一1 } 产，由式 2 ，存在z ，使得％ 万方数据 第5 期孙靖等L i p s c h i t z 函数全局优化的区间算法7 1 3 2 口I x l 。2 对于任意的y l ∈X l ，y 2 ∈X z ，0 1 1 ，，如∈ a - F X - ，y z ，所以由式 4 可知，a l ，，也≥口l ，即 口1 ，。恐≥口1 工1 工2 ．由式 3 有口l 一口l ，。々．故当忌一∞ 时，口l I 口1 ． 类似可以证明当五一∞时，角。一角． 证毕． 其次讨论计算广义偏梯度a 。F X 。，X z 的算 法过程． 设将X 。分为惫等分，节点分别为 z 让 口 _ 『一1 丁b - - a ， ．『 1 ，2 ，⋯，惫 1 ． 分别计算 a 2 F 巧2 ，X 2 垒[ 口2 灯，岛蚵] ． 且设 口2 m i n { 口2 衄 ，岛 m a x { 忍酊} ． 则同理可有下列定理成立． 定理5当惫一o 。时，口2 I a 2 ，陬一岛． 2 L i p s c h i t z 函数的区间扩张及有关定理 ’利用定理2 定义如下4 个区间函数 I E l F X 厂 m X Kf | R X l f 。。[ 一1 ，1 ] ， 5 I E 2 F X ， 优 X 0a F X I | xI lR x | l 。[ 一1 ，1 ] ， 6 I E 3 F X 一厂 优 X O F X T X m X 。 7 I E 4 F X 厂 c O F X T X f ， 8 P 屈≤o ， 其中c 一{ 童 ％≥o ， 9 I 氅[ 堕 口{ ≤0 ≤屈 ， 【屈一l l i ⋯～⋯ l 生 屈≤o ， 或f 一 0 ，j 五，使得 Vk 五 有 0 ≤m i n f x 一以 五 ． 6 ‘ W t 云 O ≤m i n f x 一以 e ． 证毕． 3 区域删除检验原则 删除检验原则1E 1 0 一 赋值检验 设F I X ∞’ 一f R 是厂 z 的区间扩张，7 是问题 1 的一个上界，如果对x ∈I X ∞’ 有7 0 ，则除边界 X l ，⋯，X 扣l ，a i ，X 斗l ，⋯，兄 T 之 外，X 上无， z 的最小点．如果届 0 ，对Vz z l ．．．’z 卜1 ，X i ， z 斗l ，⋯，X “ T ，y z l ，⋯，X 卜l ，Y z “1 ，⋯，X H T ∈X 且X ； y t ．由定理2 有厂 z ， y ，即厂 z 在X 上关于z 。方向是严格单增的，所以，， z 只 可能在边界 X l ，⋯，X 卜l ，n ；，X 汁l ，⋯，X 。 T 上取得 最小点．故除所述边界外，X 上无最小点． 屈 0 ，则可将X 缩减为 X 1 ，⋯，X 卜1 ，a 。，X 件1 ，⋯， X 。 T ．如果且 7 成立，则令 y 厂 z o 一f ／K X ， X ，一 I x 2 妇，⋯，[ z 刀 T 1 9 那么，X ，的内部i n t X ， 中无极小点． 证明 V Y ∈i n t X ， ，由式 1 9 可知I f ．2 7 0 YI | 。 f x o 一K x ， 7 ． 所以Y 不是问题 1 的极小点． 证毕． 由定理9 可得到 删除检验原则3 L i p s c h i t z 检验 设K x | f3 F X l Ix ，7 是问题 1 的上 界，设y 一 ， 一 一7 ／K X ，如果y 大于R i X 的分量中第二大值，则可将区域X ， I x 2 门， ⋯，[ z 士阳 T 的内部i n t X ， 从x 中删除． 4 算法 4 ．1 二元函数广义梯度的区间算法 算法I 计算a 。F X 。，X 。 的区间算法 步骤1 X l r a ，6 ] ，X c ，d t ，计算a ，F o a l F X l ，c 金[ 口1 。，届。] ，a 1 F l a l F X l ，d 全 [ 口1 1 ，届1 ] ，口l m i n { a l o ，口1 1 ，届 m a x { 届o ，J 9 1 1 ，w d c ；令X ；”一X 2 ，k 一0 ． 步骤2二分X ；”X ∥’UX ∥’ _ f 1 ，2 ， ⋯，2 ‘ ，则步长为h w ／2 ，计算a - F z ，t a 1 F X l ，C 2 s 一1 ，I 垒[ a l m ，1 ，卢1 删，1 ] ，口3 m i n { a Ⅲ2 ，1 ，岛一m a x { 角眦，1 5 0 ，1 ，⋯，2 ‘ ， 口2 一m i n { a l ，a 3 } ，岛一m a x { ／冤，岛 ． 万方数据 第5 期孙靖等；L i p s c h i t z 函数全局优化的区间算法7 1 5 步骤3如果I 口。一口1I ￡，且l 屉一展I ￡， 转步骤4 ；否则令弼孙- ” X ∥’，粥知’一X ∥’ s 1 ，2 ，⋯，2 ‘ ，愚 愚 1 ，W h ，口l 一口2 ，岛 屉， 转步骤2 ． 步骤4输出广义梯度的值[ 口。，岛] ． 步骤5结束． 算法Ⅱ 计算a F X 。，X 的区间算法 步骤1x 。一[ 口，6 ] ，X 2 一[ f ，d ] ，计算a 。F o a 2 F a ，X 2 垒[ 口0 2 ，岛2 ] ，a 2 F 1 a 2 l F b ，X 2 垒 ■1 2 ，届2 ] ，q m i n { a 0 2 ，a 1 2 ，岛一m a x { 儡2 ，届2 ， W b a ；令X i 一X 1 ，愚 0 ． 步骤2二分X ；”X P ’UX ∥’ 歹一1 ，2 ， ⋯，2 ‘ ，则步长为h w ／z ，计算a 2 F z ，。一a 2 F a 2 s 一1 h ，X 2 垒[ 口2 删，1 ，恳靴，1 ] ，口3 一 m i n { a 2 砌，1 ，届 m a x { 乜砌，1 s 0 ，1 ，⋯，2 ‘ ， 口2 一m i n { a 1 ，口3 ，恳一m a x ／届，恳 ． 步骤3 如果I 口2 一qJ ￡，且J 尼一届J 0 或屈 0 是否成立，如果均不成 立，进行步骤3 ；否则，按单调性检验原则进行区域 删除，删除后的区域仍记为X ，然后转1 ． 步骤3 计算f ，R i n f F X ，7 s u p F X ， 兀 7 ，B 。一1 0 1 0 或最大正机器数 ；将 x ，F ，，7 按照R 从小到大的顺序存入表L 中． 步骤4从表L 中取出第一项 x ，F f ，7 ，并 将该项从表L 中删除；令B { B 。，R ． 步骤5判断7 一B 0 ，届” 五的 项 X ，F t ，， ． 步骤1 1判断表L 是否空的，如果空，进行步 骤1 4 ；否则，进行步骤4 ． 步骤1 2输出最小值的区间值[ R ，7 ] ；最 小值区间X ． 步骤1 3判断L 是否空的，如果空，进行步骤 1 4 ；否则，令B 。 B ，然后进行步骤4 ． 步骤1 4结束． 5 数值算例 算法Ⅲ在P I V 微机上用f o r t r a n 编程计算实 现，下面给出部分数值实例．其中￡，惫分别表示精 度和区域分半次数． 例1f x l ，z 2 Iz lI z 2 ，z l ∈[ 一1 ，1 ] ， z z ∈[ 一1 ，1 ] ． 该函数在z ’ O ，一1 点取得全局最小值 l ’一一1 ． 对￡ 1 0 ～，使用算法Ⅲ经过二次区域分半 可得该函数的精确解． 例2f x 1 ，z 2 Iz 1 z 2 1I ，z 1 [ 一1 ， 1 ] ，z z [ 一1 ，2 ] ． 该函数在z 。 z 。一1 点取得全局最小值厂 一0 ． 对￡ 1 0 一，使用算法Ⅲ产生的最后的表L 中 的第一个元素如下 K 5 8 万方数据 7 1 6中国矿业大学学报第3 6 卷 z 一[ O ．0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ， 1 ．9 0 7 3 4 8 6 3 2 8 1 2 5 0 0 1 0 川 ， 9 ．9 9 9 9 8 0 9 2 6 5 1 3 6 7 2 1 0 ～， 1 ．0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 } 。 f [ 一1 ．9 0 7 3 4 8 6 3 2 8 1 2 5 0 0 1 0 一， 5 ．7 2 2 0 4 5 8 9 8 4 3 7 5 0 0 1 0 _ 6 ] ． 参考文献 [ 1 3S H E NZ u - h e ，Z H UY u ．A ni n t e r v a lv e r s i o no fS h u b e r t ’Si t e r a t i v em e t h o df o rt h el o c a l i z a t i o no ft h e g l o b a lm a x i m u m [ J 3 ．C o m p u t i n g ，1 9 8 7 3 8 2 7 5 2 8 0 ． [ 2 ] C H R I S T I A N EG ，H E L M U TR ．G l o b a li n t e r v a l m e t h o d sf o rl o c a ln o n s m o o t ho p t i m i z a t i o n [ J ] ．J o u r h a lo fG l o b a lO p t i m i z a t i o n ，1 9 9 9 1 4 1 5 7 1 7 9 ． [ 3 ]曹德欣，李苏北，吴彦强，等．求连续m i n i m a x 问题整 体解的区间算法[ J ] ．高等学校计算数学学报，2 0 0 2 ， 2 4 4 3 5 9 3 6 5 ． C A OD e - x i n ，L 1S u b e i ，W UY a n - q i a n g ，e ta 1 ．I n t e r - v a lm e t h o df o rg l o b a ls o l u t i o n so fc o n t i n u o u sm i n i m a x p r o b l e m [ J ] ．N u m e r i c a lM a t h e m a t i c saJ o u r n a lo f C h i n e s eU n i v e r s i t i e s ，2 0 0 2 ，2 4 4 3 5 9 3 6 5 ． [ 4 ] 孙靖，金花，曹德欣．一种求带约束的离散 M i n i m a x 问题的区间算法[ J ] ．华东地质学院学报， 2 0 0 3 ，2 6 2 1 4 7 - 1 5 0 ． S U NJ i n g ，J I NH u a ，C A OD e - x i n ．A ni n t e r v a la l g o - r i t h a mf o rac o n s t r a i n e dd i s c r e t em i n i m a xp r o b l e m [ J ] ．J o u r n a lo fE a s tC h i n aG e o l o g i c a lI n s t i t u t e 2 0 0 3 ，2 6 2 1 4 7 一1 5 0 ． [ 5 ]曹德欣，叶帅民，王海军．～类约束不可微优化问题 的区间极大熵方法[ J ] ．运筹学学报，1 9 9 9 ，3 4 5 5 6 4 ． C A OD e - f i n Y ES H u a i m i n 。W A N GH a i - j u n ．A n i n t e r v a lm a x i m u m - e n t r o p ym e t h o df o rac l a s so fc o n s t r a i n e dn o n d i f f e r e n t i a b ho p t i m i z a t i o np r o b l e m s [ J ] ． O rT r a n s a c t i o n s 。1 9 9 9 ，3 4 5 5 6 4 ． [ 6 ]S U NJ i n g ，C A OD e - x i n ．A ni n t e r v a la l g o r i t h mf o r u n i v e r i a t eL i p s c h i t zg l o b a lo p t i m i z a t i o n [ J ] ．南京大 学学报半年刊，2 0 0 4 ，2 1 2 2 6 6 - 2 7 3 ． [ 7 ] 沈祖和．区间分析方法及其应用[ J ] ．应用数学与计 算数学，1 9 8 3 2 1 - 2 9 ． S H e nE L I - h e ．I n t e r v a la l g o r i t h ma n di t sa p p l i c a t i o n [ J ] ．C o m m u n i c a t i o no nA p p l i e dM a t h e m a t i c sa n d C o m p u t a t i o n ，1 9 8 3 2 1 - 2 9 ． [ 8 3C L A R K EFH ．O p t i m i z a t i o na n dn o n s m o o t ha n a l y s i s [ M ] ．N e wY o r k J o h nW i l e y8 LS o n s ，1 9 8 3 2 4 5 0 ． [ 9 3S H E NZ u - h e 。E I E R M A N NMC 。F R E I B U R GlB ． I n t e r v a l m a j o r a n t m e t h o da n d g l o b a lo p t i m i z a t i o n [ J ] ．C o m p u t i n g ，1 9 8 9 4 3 8 5 9 2 ． [ 1 0 ] A S A I T H A M B INS ，S H E NZ u - h e ，M O O R ERE ． O nc o m p u t i n gt h er a n g eo fv a l u e s [ J ] ．C o m p u t i n g ， 1 9 8 2 2 8 2 2 5 2 3 7 ． 责任编辑邓群 万方数据