（应用数学专业论文）几类非线性凸规划的性质及算法研究.pdf

摘要 本文是关于三类凸规划的性质及算法的研究，全文分两章介绍这三类凸规 划，前一章介绍一层的凸二次规划，后章介绍二层的规划；它们的算法的共性 就是利用弘t 条件转化模型。 本文的创新点有两个：i 用单纯形法解上下层都带约束的二层线性凸规划， 这体现在3 2 节；2 用f r a n k - w 0 1 f e 算法解决了上层为非线性的二层凸规划的求 解，这点体现在3 3 节。 第一章为预备知识；第二章介绍热二次规划的性质及算法，在对凸二次规划 性质的研究的基础上利用k - t 条件将凸二次规划转化，然后利用互补转轴法来求 解凸二次规划；第三章研究的是凸二层规划，在这一章里前面一节主要讲的是线 性二层规划的性质及算法，在性质的研究上利用融零条件将模型转化，然后通过 单纯形法求出平衡点来求解模型；后面一节是非线性二层规划，它与线性规划不 同的是它第一层羁标函数是凸二次函数，还是利用k _ t 条件将模型转化，然后利 用f r a n k - w olf 线性逼近法求解。 关键词：凸规划；二次规划；二层规划；互补转轴法；k - t 条件；f r a n k w o l f 法 a b s t r a c t i nt h i sp 印吼t h ea u t h o ri n t r o d u c e st h ep r o p e r t i e sa n da l g o r i t h m so ft h r e ec l a s s e s o fc o n v e xp r o g r a m m i n g t h ea l g o r i t h m sh a v eac o l i 鞠o nc h a r a c t e r , w h i c ha l lt h e a l g o r i t h mu s et h ek - tc o n d i t i o nt ot r a n s f o r mt h em o d e lo fp r o g r a m m i n g 强o s e c o n t e n ti si n t r o d u c e di nt w oc h a p t e r s 毡m i sp a p e r , i th a st w oi n n o v a t i o n s ：o n ei s 落a t 氇ea u t h o r 璐e st h es i m p l e x m e t h o dt os o l v et h eb i l e v e ll i n e a rc o n v e xp r o g r a m m i n g ；t h eo t h e ri st h a tu s e st h e f r a n k - w o l f ea l g o r i t h mt os o l v et h eh i - l e v e ln o l i n e a rc o n v e xp r o g r a m m i n g 。 i nc h a p t e r1 ，i ti n t r o d u c e st h ep r e p a r a t o r yk n o w l e d g e i nc h a p t e r2 ，i ts t u d i e st h ep r o p e r t i e sa n da l g o r i t h mo fc o n v e xq u a d r a t i c p r o g r a m m i n g f i r s t ，i ts t u d i e st h ep r o p e r t i e s ，a n du s e st h ek t c o n d i t i o nt ot r a n s f o r m t h em o d e lo fc o n v e xq u a d r a t i cp r o g r a m m i n g ，t h e nu s e st h ec o m p l e m e n t a r yp i v o t i n g a l g o r i t h mt os o l v et h ep r o g r a m m i n g i n c h a p t e r3 ，i ts t u d i e st h ep r o p e r t i e sa n da l g o r i t h mo fc o n v e xb i l e v e l p r o g r a m m i n g 。f i r s t l y , i ts t u d i e st h ep r o p e r t i e s ；s e c o n d l y , i ti n t r o d u c e st h ep r o p e r t i e s a n ds t e p sf o rt r a n s f o r m i n gt h em o d e lo fl i n e a rb i l e v e lp r o g r a m m i n g ，a n df i n dt h e s o l u t i o n so fl i n e a rb i l e v e lp r o g r a m m i n gb ys i m p l em e t h o d ；l a s t l y , i ti n t r o d u c e st h e a l g o r i t h mo fac l a s so fn o l i n e a rb i l e v e lp r o g r a m m i n g ，w h i c hi sd i f f e r e n tt ot h el i n e a r b i l e v e lp r o g r a m m i n g ，t h ej u s td i f f e r e n c ei st h a tt h eo b j e c t i v ef u n c t i o ni sc o n v e x q u a d r a t i cf u n c t i o n ，n o tl i n e a rf u n c t i o n s i m i l a r l y , u s et h ek - tc o n d i t i o nt ot r a n s f o r m t h em o d e la n dg e tt h es o l u t i o nb vf r a n k - w - o l f ea l g o r i t h m k e yw o r d s ：c o n v e xp r o g r a m m i n g ；q u a d r a t i cp r o g r a m m i n g ；b i 1 e v e lp r o g r a m m i n g ； c o m p l e m e n t a r yp i v o t i n ga l g o r i t h m ；f r a n k - w o l f ea l g o r i t h t r l n l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名：钾胀签字日期：朋磐年多月夕日 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留、使用 学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权江西师范大学研究生院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存，汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：剑娟久 签字日期：阳劳易月7 日 导师鲐甲钟色 签字日规锄。年月舌日 几类非线性凸规划的性质及算法研究 引言 目标函数和约束函数中至少有个是自变量的非线性函数，则这种规划问题就称 为非线性规划问题( n o n l i n e a rp r o g r a m m i n g ，可简记为n p ) 非线性规划问题作为 运筹学的个十分重要的分枝，最近八十年发展得非常快，在资源分配、最优设计、 管理科学、质量控制等许多领域有着广泛的应用 一般地，解非线性规划问题要比解线性规划问题困难得多，因为它不象线性规划 问题有单纯形法这与宙用方法，而是要根据目标函数和约束条件的具体特点给出不同 解法，因而非线性规划的各种算法大都有自己特定的适用范围 本文要讨论的是三类非线性凸规划的问题：l 、层凸二次规划的相关性质及求解 方法：_ 层无约束凸二次规划的求解方法已有很多，如最速下降法，n e w t o w n 法等， 而带约束的规划解决方法并不多，目前比较好的方法就是可行方向法，如f r a n k - w o l f 法；本文的方法是先讨论此规划的陛质，后转化问题，再利用互补转轴法来求解，通 过实例显示此方法的优越性2 、4 二层凸规划的相关陛质及求解方法：求解二层凸规划 显然要比层的困难，但是它的应用非常广泛，如应用在资源分配、财政预算、金融 投资、价格控制和基本决策等与人们生活息息相关的这些重要领域，这使得近几十年 来对二层凸规划的研究有了很大的进步；凸二层线性规划的解法也有了很多，如“分 枝定界法、“罚函数法【1 h 、等；本文在u a n o e l 2 】的基础上研究上下层都带约束的线 ，_ l 性二层规划的解法，即利用单纯形法求解平衡点来求解；二层非线性规划的研究就比 线性的更难，目前，对它的研究非常的少，本文在研究了线性二层规划的基础上，研 究匕层为非线性的二层规划的算法，并证明了其收敛性，也通过实例显示了其算法的 可行性 江西师范大学2 0 0 8 届硕士研究生学位论文 第l 章预备知识 l 。l 凸规划的相关概念 ，1 ： 定义薹1 设集合dc _ 互”，如果对，x 2 d 及搿( o ，1 ) ，有甜五+ ( 1 一岱) 恐d ， 则称d 为凸第 定义1 2 设d _ ce ”为非空凸集，厂：d 专e 1 。若对沌，x 2 d 及v 掰( o ，1 ) 有： f a x a + ( 1 一g ) 屯】联，( 鼍) + ( 1 一g ) ，( 吃) ： ( 1 。1 ) 则称f ( x ) 为d 上的凸函数，或厂( 力在d 上是凸的 如果不等式( 1 1 ) 对弘，x 2gd ，x t 屯严格成立，即有 f a x + + ( 1 - a ) x 2 o ，则群，肋上的髓函数； ( 2 ) 、石，五：扩_ 占1 是d 上的凸函数，则石+ 五是移上的凸涵数； ( 3 ) 、。设厂( x ) 是定义在凸集d 上的凸函数，对于每一实数p ，则水平截集 n o r ，夕) = x | ，( x ) ，x g d ) 是凸集， 定义1 4考虑如下菲线性规划阂题( 溜 ： m i n f ( x ) a 船h i 三。0 舞乏岩 旺2 ) l ( 曲=( ，= l ，2 ，) 2 几类非线性凸规划的性质及算法研究 记可行域鼯 x e e “l 最( x ) o ，哆( 磅= o = l ，2 ，。，m , j = 1 ，2 ，。，) 如果可行域 x 是凸集，蟊标函数厂o ) 是定义在x 上的凸函数，则非线性规划( n p ) 称为非线性 凸规划，简称凸规划 ， 定理1 2 对予非线性规划( n p ) ，若盛( 力u = 1 , 2 ，m ) 是e “上的凸函数，备 h i ( x ) ( 歹= l ，2 ，。，f ) 是线性函数，并且厂缸) 是x 上的凸蘧数，则非线性规划( 糯) 是 凸删 定理1 3设d e _ e 8 为非空凸集，：d f ，考虑如下问题： 卿厂o ) 设量是_ 局部最优解，则 ( 1 ) 若厂是凸函数，则舅为全局最优解，且露数厂的极小点集是邶集； ( 2 ) 若厂是严袼凸函数，则亨为惟一的全局最优解 定理1 4 设，：昱”寸昱1 为可微凸函数，d e “为鼍# 空凸集，考虑如下凸规 划闷题： 嘧厂( x ) ( 1 ) 舅d 是最优解的充要条件是对觇d ，有夥( 功fx - x - ) 0 ( 2 ) 著d 为开集，则舅d 是最优解的充要条件是夥( 秘= o 。 定义1 5 t 5 l 设厂：f 斗露1 ，p 为刀维菲零向量，若存在万 o ，对v t ( 0 ，回有 ( _ + p ) ( 砷，则称向量p 是厂在点覃处的下降方向。 定理重。5 【5 1设：f 哼昱1 在点 f 燃，若存在尹f 使夥( 矽p ，z = 0 ，w = q + l z o ，即得线心h 问题( 1 6 ) 的初始解 2 线性互补问题的整个求解步骤 步骤i 初始步：引入人工变量z 。形成初始表格1 ，且考虑懋 一吼) = 一吼， 在行和z 0 所在列进行一次旋转，得到表格2 步骤i i 在表格2 中，以与步骤i 中心对应的z 。作为换入变量，而换出变量由 卧比繇贝崃韪蛐 淼) 得至啪的作为换出，嬗血粤 在歹i j 与行之间进行嗽黼，得至l 婊格3 ，其中小，玎吣，p 步骤i i i 重复步骤i i ，直至巾陪z o 换出为止，即可得到系统的解 1 3f r a n k - w o l f e 算法【9 】简介 f r a n k - w 0 1f e 算法是由f r a n k 和w o l f e 于1 9 5 6 年提出来的，用来求解带线性约束 的非线性规划问题( 1 - 7 ) 的方法由于这一方法的个特点是由每步采用了线性 化目标函数的手段，因而也叫近似化法此方法较简单，收敛速度较慢，但可利用线性 规划软件实现计算，故此法常被人们采用 考虑带线性约束的非线性规划问题 m i n f ( x ) f 血b ( 1 7 ) s t 1c 石：d ， 其中x n 铷= ( 4 ，4 ，a m ) r ，c = ( c 1 ，c 2 ，c ，) r ，a 蔓- j m x n 阶矩阵，c 为lx n 阶矩阵，其中4 ( f = 1 ，2 ，m ) 表示矩阵a 的第f 列，c ，( ，= l ，2 ，d 表示矩阵 c 的第列，b = ( 6 1 ，6 2 ，吒) r ，d = ( 吐，d ：，西) r ，记( 1 7 ) 可行域为 j 丘= x e “l a x 6 ，c x = d ) ， 江西师范大学2 0 0 8 届硕士研究生学位论文 予是1 7 可简记为 m i n f ( x ) ( 1 8 ) j 矗r 设目标函数厂在可行域鼍中可微，矿鼍，利用厂( 戈) 在点矿处的一阶t a y l o r 曩式这线性函数，霹怂营匠匿标函数，有 厂( 力( 茗。) + v f ( x 蠢) f ( 石一矿) 由于和w o 。) r 均为定值，于是，在点矿的邻域有一个与问题( 1 7 ) 近似的线性 规划 m i r , v f ( x ) r 茗 ( 1 9 ) 艇五r 设y 未是近似线性规划1 9 的最优解，则有： 定理1 8 设厂：f 。可微，矿e 鼍设广是( 1 9 ) 的最优解，则 ( 1 ) 当夥( x 仕) r l 一f 幻) = o 时，矿是闭题( 1 。7 ) 的k - t 点； ( 2 ) 当w ( 工) f ( y 蠢一x 釉) 喾0 时，向量p 鳓= y 蚣一0 寿是目标函数 ，( 力在点处关于也的可行下降方向 f r a n k - w o l f e 法步骤： 步骤1 选取初燃。驭裙鲶可行点p 置，给定终出误差笤 0 ，令垂：= 0 ； 步骤2 解近似线性规划。解线性规划卿耵( ) f 石，设得到最优解y 量； 步骤3 。构造可行下降方向。若l 夥o ) r 0 2 一) b 嚣，停止迭代输出，； 步骤4 进行有效维搜索。求解m 。蚓i n f ( x + t p 。) ，设得最优解如令 工“- - x + 缸p ，惫：= k + l ，转第2 步 “ 6 几类菲线性髓规划的性质及算法研究 第2 章一层凸二次规划 2 1 凸二衫嗍匠剐的模型及性质 定义2 1二次规划是刍廷特殊的非线性规划，其目标函数是= 次函数，约束 函数是线性函魏 我们考虑以下二次规划模型： m i n i ( x ) = c r x + l ，x r h x f a x b ( 2 。1 ) f u h 雳t lx 0 定义幺2凸二次规划器器在= 次夫贱l 的条终下，要求譬标函数为凸函数，约束为 凸集 定理2 i设s c e 8 是非空开凸集，厂：s _ e 1 在s 艺二阶可微，则厂是s 上 的凸函数的充要条件是：如果每一点j c s ，f 在】【处的h e s s i a n 矩阵日( x ) 在e ”中 是半正定的 定理2 2 设s c e ”是非空开凸集，：s f 在s 上二愀，如果静 点x s ，厂在x 处韵h e s s i a n 矩阵嚣( 在f 中是正定的，则厂是严格凸函数 也即说满足上面规划模型( 2 1 ) 且有( 曲正定或半正定都为凸二次规划。因 为掣( 茗) = c + h x ，面鲈2 = 嚣，h o 或露o 则都为凸函数，又由定理1 i 的( 3 ) 知道模型( 2 1 ) 的约束为凸集 故凸二次规溯如下： n f m f ( x ) = c r x + 妥f h x 聪 篙。 q 心) 其中h 0 或日 0 7 江珏颊熬丈学2 0 0 8 届顼士研究生学位论文 许多舞# 线性规划的书中，对二次规划的求解采用“共轭梯度法0 但是基于凸二 次规划的特殊性质，本文推荐一种新算法，利用互补转轴法来解 2 2 凸二次规划模型的转化及算例 2 2 王。模型的转化 由模型( 2 2 ) ，因为凸二汝删的目标函数为凸函数，约束为线性函数，则烈， 莫 型满足定理1 6 的要求，于是可以将模型( 2 2 ) 转化为k _ t , 掣f c - m 武 首先鲈= c + h x , a g ( x ) = 三 ，且分别设与条件出6 和石。对应的 l a g r a n g e 乘子向量分别用“和v 表示，松弛向量用y 表示，则模型( 2 2 ) 的k - t 条件 可写成如下矩阵形式： 一礅么r 狂+ y = c a x + y 2 b ( 2 3 ) 。茗，y ，嚣，y 0 x r y + u r y = 0 由t 2 中定理3 知，点蔗为最优解的充要条件是存在向量掰，k 皿，共同满足 以上的叩条侉。蠢器求原问题的最优解等份子寻找以上k 一条件的酉行煮羲 令材= a o 舟锝律书z = ：i 脚黼龋为 w m z = q z = 0( 2 4 ) w z 0 于是凸二次规划的求解转化成了线性互蛰问题的求解，用互补转轴算法找出二次 规划的k 川点，由定理1 7 ，从而凸二次规划的最优解就得如来了 ， 2 2 2 。举例 算例乏1 求解以下二次规划的最优解： 8 几类非线性凸规划的性质及算法研究 m i n f ( x ) = 最- - 4 x l x 2 + a 矗- l o x l - 4 x 2 姓 鬻x a + x 2 6 言 解：驰h 一2 x 缸t - 栅4 x 2 ：- 矿1 0 1 + 匕- 8 4 肫y x l ) 批嚣= 匕寻且v 2 ，? = 匕斗蜥函数揪， 显然约束域为凸第 1 且一= ( 三：) ，么r = ( ：；) ，6 = ( 三) ，令据= ( 芝) ，妒= ( 芝) ，y = ( 芰) 其中i t , 沩五鳃瑚辫鲈乘子向量，夕为松弛交量，且u ，v ，y 0 将原n p 问题转化为k - t 条件形式如下： 五+ 屯+ 咒= 6 。4 x a + j c 2 + 魏= 1 8 2 五十4 岛一地一4 u ，+ m = - 1 0 i 4 x a 一8 x 2 一魄一掰2 + 毪= - - 4 m + “2 y 2 + m 毛+ 屹屯= 0 令w = 萋 = 量 ，z = 兰 = 耋 ，晕= f 委 ，膨= ( 2 5 ) 引入肛，赡z o 后穰l ；因为懋溉 = 一q s ，故在坞和之间断次旋 转得到表2 ；因为与鸭对应的为z 3 ，故龟为换入变量，又由最小比值原则 9 l0 o 8 以4 2 4 o o 4 l o o l l 厂 l 江西师范大学2 0 0 8 届硕士研究生学位论文， m i n 辔，警，孚，9 = 吾，选心为换出变量，得到表3 ；因为与w 4 对应盼为气，故z 4 为 换入变量，又由最小比值原则m i n 孵，等焙，书= 譬，选w 2 为换出量，得至恢4 ；因为 与坞对应的为z ：，故z ：为换入变量，又盘剥、比值原则戚毅诺，等，量，参= 善，选强为 换出变量，得到表5 ；因为与对应的为z 。，故z l 为换入变量，又由最小e 匕值原则 m i n 墓，要，姿，参= 妻，选为换出变量， ! 寻至l 婊6 ；e l j 表6 知w 与z 为对互补基可 h蚌1 3 一 l l 行解，它靠j 的馕如下： w = ( m ，嗨，嵋，心) = 魄，y 2 ，k ，吃) 拦( o ，0 ，0 ，z = ( z 1 茗2 ，毛，z 4 ) = ，豁2 ，麓，屯) = ( 4 , 2 ，2 ，2 ) 于是刚示函数的最优解为( 五，屯) = ( 2 ，2 ) ，最优值m i n f ( x ) = - 2 4 以下为计算附表： 蟛 鹕蟛 乏乞 气 气 表1娜 m儿h匕l l“2五而气 lo00oo1l- 16 域 咒 0l00 oo4 ll1 8 嵋蚝 oolo14- 24 ( - 1 ) 1 0 w 3巧 哆 ooo l l_ l4删8一l。4 嵋哟气z 2毛 z o 表2娜 魏y 2巧v 2蚝勰2五屯 z o lolol 4 3_ 3o1 6 磁，麓 ollol46_ 302 8 w 2 蚝 o 0一l o 1 4 2 4l1 0 晦气 嵫 屹 o01lo3 ( 6 ) 1 2o6 1 0 几类非线性凸规划的链质及算法研究 壤w 3 w 4盔乞磊 z 4 弱 表3娜 m y e吁v 2“lu 2五而 z 0 蟛以 l0 工j _ 1 三 0 3 01 3 2 22 嵫魏 ol o 董l1 o ( 9 ) 0 2 2 w 3 z o oo 2 一上 l3o o ，18 、33 w 4 玉 oo 上 上 o 上 12ol 662 咩w ew 3 w 4 气弓 气 表4髑 儿y e 巧y 2 魄u 2恐。 z o 壤魏 薹 上 一毒 一上 2 ( 譬) o9o 1 7 3633 w e吃 o 上 o 工王工 01o 盆 99999 w 3z o o0 量 一工 l3ool8 33 w 4毛 0 王t l 互 1 3 o o 5 3 961 暑91 8 l 9 w lw 2w 3w 4z lz 2z 4 2 0 表5 r h s 强咒屹终掰2玉屯瓦 艿 3l4 l ooo 3 4 拓2 1 31 31 3 1 3 1 3 1 3 屯 一 5 上 4 j o0l0 2 8 3 93 93 93 91 31 3 1 8 6 上 4 ( 蠢) qool 三 鸭 z o 1 3 1 33 93 91 3 w 4五 上 工 0o0olo04 33 j 1 1 江嚣磐范文学2 0 0 8 藩硬女疆究生学位论文 堆w 2w 3w 4龟 毛氛奄 表6郦 砖虼屹羧拓2鼍恐毛 盥 2 上 土 o蔓0 o 42 壤”u 2 l 主善 ； s 21 7 qooo ol- l2 恐3 91 3 w e 强 _ 1 8 6 上。王 l 0 oo1 32 33 鼍 。上 工 o o 0 i0 1oo 4 33 1 2 几类非线性凸规划的性质及算法研究 第3 章二层凸规划的性质及新算法 3 1 二层规划p ) 模型及其相关性质 3 1 1 二层规划模型【1 0 】及解的定义： 模型如下： ( 8 p ) e 蛾 石嚣淼 薏中y ( 曲_ ，“，h ( 3 ，1 ) c?，：黏，(1。x，兰苫，=纛m：in诺f，。舅(x，夕,y；)。； 其中x r ”是七层规划娌，y 。毯r 是下层刊删( 叫：o ) 的变量，函数 ，：彤r 寸r 趾层削示函数，d ：r ”jr ”趾层的约束函数，z ：彤xr _ ； 一 专尺是下层目标函数，g ：r “尺再f - - - ) r 8 是下层约束函数，h ( 力：r ”jr 牖目 标值，i = l ，2 ，n 定义3 1 f 3 】设2 e x c r , 少肿，o = 丽，罗= 眇，) ，称( 冀刃为二 层决策闻鼹b p ) 的最优决策：如果歹为问题( ：。，的解= 两，劝问题( 聊u 的解 3 1 2 二层规划凸性讨论 定义3 2 t 1 2 1 设厂是凸集x c 发”上的实值函数，如果对f 壬何的 ，恐石及 任何的旯【o ，l 】影( 她+ ( 1 一旯) 恐) m a x 矿( 五) ，厂( 心) ) ，则称厂在x 上是拟凸的 定义3 3设厂是凸集并cr ”上的实值函数，如果对任何的五，x 2 芒x ， 1 3 注嚣颤范丈学2 0 0 8 届硕士研究生学位论文 f ( x a ) * f ( x 2 ) 爱对任 玎的名【蛳】，影( 掘+ ( 1 一句恐) m a x 玎瓴) ，厂魄) ， 燹猕，在x 土是酬凸螅 凸函数与拟热函数的关系：凸函数必定是拟凸函数，也必定是严格拟凸函数，但f 拟凸函数和严格拟凸函数都未必是凸函数；拟凸函数和严格拟凸函数是互不包含关系， 器雾拟凸函数未必是严格拟凸函数，严格拟凸螽数也未必是拟魑丞魏 引理3 。薹【1 3 】设xc 掣为凸集，f ( x ，力为r 8x r 4 上的凸函数，g ：x 丰2 为 x 上的凸点集映射，则矿( 砷= 孵m 吣i n ，f ( x ，y ) 为x 上的凸函数- 定理3 1在( b p ) 中，设xc r ”为凸集，的每个分量为拟凸函数，z 为 ， r 凸函数，且列任何x 并，( b ，i 工( ，) 有解，则m ( 曲为x 上的凸函数 证明： 由引理3 1 ，只需证明 ) = y r 吩l ( x ，y ) o ) 是x 上的凸点集 映射。v 石1 ，工2 x ，0 五l ，谚秒a 鬈( z ) + ( 1 一旯) v ( x 2 ) ，即存在爿l ：( x 1 ) ， y ；r ( x 2 ) ，使得y = 名+ ( 1 一名) y ；。由于g ；( 歹= l ，p ) 为拟凸函数，有： 、一 n 彰( 名工1 + o 一旯) x 2 ，名爿+ ( 1 一篇) y ：) m 馘 彰( x ，薪) ，彰0 2 ，奠) ，j f = l ，鼻 由于爿鬈0 1 ) ，y ；写0 2 ) ，器器有彰( ，爿) o ，自i ：、x 2 ，奠) o ，歹= 两。擞有 g ：( 磊f + ( 1 一五) x 2 ，名舅十( 1 一名) z o ，歹= l ，鬈，于是y = 冀爿+ ( 1 一磊) z 毯 z ( 氟1 + a 一名) 茗2 ，因羹乏名誓( x 1 ( 1 一名) 誓( 茗2 ) cl ( 名，+ o - a ) x 2 ) 。 定理& 2 对任筒的f = 蕊设定理3 王的祭d c 4 9 s r _ ，f 为凸函数旦蝴的 x x ，f ( x ，v ( 戈) ) 为定上鼍# 降函数( 即， 协1 ，9 2 只，如果z 1 笼z 2 ，必有 f ( x ，z 1 ) y ( x ，z 2 ) ) ，则( 力= r a i nf ( x ，v ( 呦为x 上的凸函觌 证明：由予对v f = 丽定理3 1 的条僻成立，故有哆( 羔) o = 币汤为x 上的凸函 数，令v ( 曲= ( h ( 曲，h ( 砌，协1 ，茗2gx ，0 五1 ，则有； v ( 名 + ( 1 一力工2 ) 五y ( x 1 ) + ( 1 - 2 ) v ( x 2 ) ， 又因为协f x ，f ( x ，y ( 力) 在r 上是非降的， 1 4 几类非线性凸规划的性质及算法研究 所p a f ( 2 x 1 + ( 卜a 江2 ，v ( z x l + ( 1 一a 虹2 ) ) 在r 上也是非降的，因此， f ( a , x 1 + ( 1 一a ) x 2 ，v ( a x l + ( 1 一名) x 2 ) ) f ( 兄x 1 + ( 1 - 2 ) x l 2 v ( x 1 ) + ( 1 一a ) v ( 支2 ) ) 2 f ( x l , v ( x 1 ) ) + ( 1 一a ) f ( 茗2 ，v ( x 2 ) ) 。 即有矽( 五五+ ( 1 一名) x 2 ) 见矿( 一) + ( 1 一五) ( x 2 ) ， 注：在定理l 。2 的条件下，如果上层约束函数d ( x ) 为凸函数，由凸规划定义，则 问题( 召户) u 是- 个凸规划 3 堇。3 二层规划连续性的讨论 在( 心中，哆( 曲是参数数学规划问题的极值函数，良p 使z 和都连续，( 弗也 不一定连续，自然缈( x ) 也不一定连续，这里用点集映射的概念和性质弘争论它们的连续 性 定义3 4设c c 灭”，g ：c 专2 为点集映射，称g 板是开的：如果舻 c c ， 矿专雾，罗g o 和沙) cr ”，伎褥y 量g ( x ) ，k 膨，渺专罗； 称g 橱c 是闭的：如果 ) c e 专 y g ( x 蠹) ，矿- - 9 , 只必有歹g ( ) ；称 g 在霉c 附近为致紧的：如果存在舅的邻域( 习，使得u 溉掰国g ( 石) 戈紧第 引理3 。2 f 1 4 li 受2excr , 9 7 的每个分量函数在可震 下半连续，则点集映 射誓( x ) = ( y 只吩l g ( x ，o ) 极是闭的 。r j l 理3 3 1 4 】 覃爿c 尺”，在舅尺一连续u = i 而，且存在少灭吩和f 的邻 ， 0 域( 砷，使得垤( 功，彰( 毛y ) 为r “- 上的凸函数和彰( f ，少) ，此时 c r 护= or n 一 毋，再将虿1 = ( o ，0 , 1 0 ，8 ，6 ，3 ) 代入p ( 厨，力中褥劳2 然( o o ，o ，0 ，1 ，o ) ， 将矛2 = ( o ，0 ，0 ，0 ，1 ，0 ) f e , a p ( m ，u - - ) 中得f 2 = ( 4 ，2 ，0 ，0 ，o ，5 ) ，则平衡点为( _ 2 ，虿2 ) ，此 时c r 彳2 = - 4 0 为罚因子，“，沩鳄m 忍g 谦子，为松弛变量 f ，4 墨00 00 、 f ，扛、 令z = o ，j ，拓，砖磁，) f ，d = l 鸣岛 oo o w | ，b 然| 也| l00 霹l 。0o jl b , j 模型，假设z 为( 3 1 0 ) 的任堋点，在z 膏处取f ( z ) 的一阶晰展式，则( 3 1 0 ) 几类非线性凸规划的性质及算法研究 m i n v f ( z k ) ) rz s jd z = b( 3 1 1 ) z 0 求解( 3 1 1 ) 后求出最优解s ( n ，若盯( z 。) r ( s ( 。) 一z ( ) = 0 ，由定理1 8 中( 1 ) 知，s ( 为( 3 9 ) 的k - t 点，而( 3 9 ) 与( 3 7 ) 等价，又由凸规划的性质故s ( 为 ：“ 原规划最优解 步骤瓢若v f ( z ( k ) f ( s 移一z 秘) 0 ，由定理i 8 从z 蠹发，沿s 蠢一z ( k 方向 进行线性搜索，登瑟求，使f z 龌+ t a s 雄一z 辑) ) = 溅，z 嵇+ & s 馥一? 。势， 且取z “1 拳z 往+ s 球- z 惫) ，然后转步骤i v 若汗z z ( s 转一z 仕 = o 总得 不到满足，啦于规划( 3 1 0 ) 的可行域是凸集，故z ( “1 仍是( 3 。l o ) 的可符点，反复 迭代，可以得到越来越接近问题气3