（应用数学专业论文）非线性约束优化问题的仿射投影既约hessian修正梯度路径内点方法.pdf

中文摘要 非线性约束优化问题的 仿射投影既约h e s s i a n 修正梯度路径内点方法 摘要 最优化技术在国民 经济的许多 领域， 如国防、工 农业生产、交通 运输、 金融、贸易、 管理、 科学研究中 有广泛的应用. 非线性规划是最一般的优化问 题，当变 量受到一些条件的限制时，寻求目 标函数的最 优解称为约束最优化， 反之，当变量不受任何约束的限制时，寻求最优解称为无约束最 优化，在本文中， 我们研究的 是一个带等式约束和有界变量约束的非线性规划问 题。 最优性条 件是指最 优化问 题的最优解( 局部的 或全局的) 所必须满 足的条件， 常见并 常用的有一阶必要条件和二阶必要条件.由于最优性条件不仅对于最优化理论的研究具 有重要意义，而 且对最优化算法的 设计和终止条件的 确定起重要作用， 所以本文中 我们 首先从最优性条件出 发，通过构建一个目 标函数的二次近似模型来提出 一种基于仿射投 影既约h e s s e 阵的修正梯度路径内点算法. c o l e m a n 和 l i 在同中 提出 了 一 种 信 赖域内 点 算法， 称为 “ 双信赖域法 ”。 其中 一 个很有启发性的想法是构建了 一个仿封尺度矩阵， 在 “ 双信赖域法”中，利用仿射内点 变 换，在取合理的信赖域半径时迭代所得的方向均落在严格可行区 域内，使解信赖域子 问 题时不用考虑有界约束。在本文中， 对于 有界变量约束这一难点， 我们根据最优性条 件，也构造了 一个相应的仿射尺度矩阵。对于仿射空间中的等式约束，我们采用了 既 约h e s s e 矩阵算法.既约h e s s e 矩阵算法是目 前较流行的解决非线性等式约束优化问 题的 有效 方 法 之 一， 朱 德通 在!2 0 ! 中 利 用 信 赖 域 投 影 h e s s e 阵 算 法 成功 解决了 线 性约 束 最 优 化 问 题.利用等式约 束系 数矩阵的q r分 解的既 约h e s s e 阵思想将原问 题分解成值空问 和零 空间中的两个通常的信赖域子问 题，更易于 数值求解和实 现. 线搜索 技术和信赖域策略是解非线性 优化问 题的两 种基本逗近方法， 这两 种技术都能 用来保证算法的 整体收敛性. 无论对于无约束最 优化还是约 束最优化， 信赖域方法都 是 一种行之有效，常用的方法.信赖域方法是首先定义当 前迭代点的某个部域， 假定在此 部域 ( 称为 “ 信赖域”) 内， 二次模型 是目 标函 数的 一个合适的近似， 则在这个部域内 极小化二次模型， 得到一个近似极小点. 信赖域方法不仅能保证算法的整体收效性，而 且不要求目 标函 数的h e s s e 矩阵 ( 或其近似) 是正定的。信赖域方法也可以通过构造适当 的路径， 在路径上搜索满足信赖域约束的 二次模型最小值。弧线路径方法有很多，如折 线 路径、 最 优路径、 共4f e ,梯度路径、 修正 梯 度 路径 等( 见#， 1 5 和 1 8 ) . 本文 是在近 似二次模型的墓础上，采用修正梯度路径代替信赖域方法获得迭代方向.修正梯度路径 可以 通 过 用 h e s s e 阵 的 特 征 值和 特 征向 量 表 示( 见 b u l t e a u 和 v i a l 4 ) . 对于 传 统的 信赖 域方法， 要获得可接受的迭代步可能 要通过重复计算多次信赖域子问 题才能获得，因 此 每完 成一 次迭 代的 整 个 计算 会比 较大 . n o c e d a l 和 y u a n 1 司提出 了 信赖域 和线 搜索两 种 技 术相结 合的 方法， 称为回代法( b a c k t r a c k i n g ) .当由 信赖域子问 题求得的 搜索 方向不 被 接受时， 利用 线 搜索 技术 得到 接受步 长， 定义 新的 有 足够下 降 量的 迭 代点. 在! 1 8 中 ， 朱 第j j ， 页 中文摘要 德通成功地用其来解决无约束最优化问题，并取得了满意的数值结果，这个方法也引导 我们在修正梯度路径算法中，当某个试验步不被接受时，此时因为试验步已经提供了 一 个充分下降方向， 我们可以采用回代法进行线搜索. 在 同和 t o 中 ， 分别 在线 搜索 和 信赖 域方 法中 利 用非 单 调技术 来 解决 无约束 最 优 化 问 题。在线搜索求迭代步长的过程中，我们利用非单调技术得到使目 标函 数非单调下降 的迭代点，一方面非单调的搜索技术可以克服m a r a t o s 效应，另一方面可以克服高度非 线性化函数 ( 称为病态) 的求解问 题，从而避免了 只使用单调搜索在 “ 峡谷”现象局部 最优解被卡的情况，比 单调搜索 有更快的收 敛进程， 特别是在函数的抖率非常陡的情况 下，显得更为突出。数值实 验的结果也证明了 在解r o s e n b r o c k问 题时，非单调技术提高 了 计算速度， 优于单调搜索。 一个好的算法应具备的典型特征是: 迭代点二 、 能 稳定地接近局部极小点二 . 的邻域， 然后迅速收敛于x , .本文通过详尽的分析，提供了完善的理论证明，验证了所提供的算 法具有整体收敛性和较快的局部收敛速率。同时也利用计算机编程对算法进行数值实 验， 通过数值实 验进一步说明了算法的 有效性. 关健词: 非线性约束规划;仿射投影变换;非单调技术;内点法;q r 分解;既 约b e s s e 阵; 修正梯度路径;整体收敛性; 局部收敛速率。 分类号: 0 2 2 1 . 2 第i v 页 英文摘要 ab s t r a c t o p t i m i z a t i o n h a s t h e w i d e a p p l i c a t i o n s i n m a n y fi e l d s o f n a t i o n a l e c o n o m y s u c h a s n a t i o n a l d e f e n c e , i n d u s t r i a l a n d a g r i c u l t u r a l p r o d u c t i o n , t r a f f i c a n d t r a n s p o r t a t i o n , fi n a n c e , t r a d e , m a n a g e - me n t a n d s c i e n t i fi c r e s e a r c h . n o n l i n e a r p r o g r a m m i n g i s t h e m o s t c o m m o n o p t i m i z a t i o n . t h e p r o b l e m i s n a m e d c o n s t r a i n e d o p t i m i z a t i o n i f t h e v a r i a b l e s a r e s u b j e c t t o s o m e c o n d i t i o n s , v i c e v e r s a , t h e p r o b l e m i s n a m e d u n c o n s t r a i n e d o p t i m i z a t i o n i f t h e v a r i a b l e s h a v e n o a n y c o n s t r a i n t c o n d i t i o n . t h i s t h e s i s i s f o c u s e d o n a n o n l i n e a r p r o g r a m m i n g s u b j e c t t o a n e q u a l i t y c o n s t r a i n t a n d b o u n d a r y c o n s t r a i n t . t h e o p t i m a l c o n d i t i o n s a r e t h e c o n d i t i o n s t h a t t h e o p t i m u m s o l u t i o n ( l o c a l o r g l o b a l ) m u s t s a t i s f y , a m o n g w h i c h fi r s t - o r d e r n e c e s s a r y c o n d i t i o n a n d s e c o n d - o r d e r n e c e s s a r y c o n d i t i o n a r e m o s t c o m m o n . t h e o p t i m a l c o n d i t i o n i s n o t o n l y o f g r e a t s i g n i fi c a n c e f o r t h e r e s e a r c h o f o p t i m i z a t i o n t h e o r y , b u t a l s o p l a y s a n i m p o r t a n t r o l e i n d e t e r m i n i n g t h e d e s i g n o f t h e a l g o r i t h m a n d t h e d e c i s i o n o f t e r m i n a t io n c o n d i t i o n , s o w e fi r s t c o n s t r u c t a q u a d r a t i c a p p r o x i m a t i o n i n t e r m s o f t h e o p t i m a l c o n d i t i o n s , a n d t h e n p r o p o s e a n o n m o n o t o n i c r e d u c e d p r o j e c t e d h e s s i a n m e t h o d v i a a n a ffi n e s c a l i n g i n t e r i o r m o d i fi e d g r a d i e n t p a t h m e t h o d . c o l e m a n a n d l i p r o p o s e a t r u s t r e g i o n i n t e r i o r a l g o r i t h m n a m e d d o u b l e - t r u s t r e g i o n m e t h o d i n 5 . t h i s a l g o r i t h m c o n s t r u c t a n a ffi n e s c a l i n g m a t r i x w h i c h i s a n i n n o v a t e d a n d i n s t r u c t i v e h i g h l i g h t . i n t h e d o u b l e - t r u s t r e g i o n m e t h o d , t h e i t e r a t e d d i r e c t i o n w i l l d e fi n i t e l y l i e i n t h e s t r i c t f e a s i b l e r e g i o n a f t e r a p p r o p r i a t e t r u s t r e g i o n r a d i u s i s t a k e n 勿 t h e a i d o f t h e a f fi n e i n t e r i o r t r a n s f o r m, w h i c h a l l o w s u s t o i g n o r e t h e b o u n d a ry c o n s t r a i n t i n s o l v i n g t r u s t r e g i o n s u b p r o b l e m. i n t h e t h e s i s , w e c o n s t r u c t a c o r r e s p o n d i n g a ffi n e s c a l i n g m a t r i x a c c o r d i n g t o t h e o p t i m a l c o n d i t i o n s s o a s t o o v e r c o m e t h e d iff i c u l t o f b o u n d a r y c o n s t r a in t . a n d w e t a k e re d u c e d h e s s i a n a lg o r it h m t o s o l v e a n o t h e r d i f fi c u l t o f e q u a l i t y c o n s t r a i n t . r e d u c e d h e s s i a n a l g o r i t h m h a s b e c o m e o n e o f t h e m o s t p o p u l a r a n d e ff e c t i v e m e t h o d s f o r s o l v i n g n o n l i n e a r e q u a l i t y c o n s t r a i n e d p r o g r a m m i n g . p r o f . z h u s u c c e e d e d i n s o l v i n g l i n e a r e q u a t io n c o n s t r a i n t o p t i m i z a t io n 场 r e d u c e d h e s s i a n t r u s t r e g i o n t e c h n i q u e i n 2 0 . t h e i d e a o f r e d u c e d h e s s i a n , w h i c h u s e s t h e q r d e c o m p o s i t i o n o f t h e m a t r i x i n a f fi n e e q u a t i o n c o n s t r a i n t , d i v i d e s t h e o r i g i n p r o b l e m i n t o t w o g e n e r a l s u b p r o b l e m s i n t h e r a n g e s u b s p a c e a n d n u l l s u b s p a c e , w h i c h i s o f g r e a t v a l u e t o t h e n u m e r i c a l s o l u t i o n a n d r e a l i z a t i o n b o t h l i n e s e a r c h a n d t r u s t r e g i o n a r e w e l l - a c c e p t e d m e t h o d s i n t h e n o n l i n e a r p r o g r a m m i n g t o a s s u r e g l o b a l c o n v e r g e n c e . t h e t r u s t r e g i o n m e t h o d i s a c o m m o n a n d f e a s i b l e m e t h o d f o r b o t h u n c o n s t r a i n e d o p t i m i z a t i o n a n d c o n s t r a i n e d o p t i m i z a t i o n . t h e b a s i c s t e p s o f t r u s t r e g io n a r e a s f o l l o w s : f i r s t , w e s e t t r u s t - r e g i o n r a d i u s a n d fi n d t h e q u a d r a t i c a p p r o x i m a t i o n o f t h e o b j e c t f u n c t i o n . a n d t h e n w e g e t a t r i a l s t e p p r o d u c e d勿 m i n i m i z i n g t h e q u a d r a t i c a p p r o x i m a t i o n i n t h e t r u s t r e g i o n . t h e t r u s t r e g i o n m e t h o d a s s u r e s t h e g l o b a l c o n v e r g e n c e o # t h e a l g o r i t h m , a n d i t d o e s n o t r e q u i r e t h e h e s s i a n ( o r i t s a p p r o x i m a t i o n ) t o b e i n d e fi n i t e . t h e t r u s t r e g i o n m e t h o d c a n 第v 页 英文摘要 a l s o c o m b i n e w i t h t h e c u r v i l i n e a r p a t h , t h a t i s , w e c a n s e a r c h t h e mi n i m u m a l o n g t h e c u r v i l i n e a r p a t h i n t h e t r u s t r e g i o n . t h e r e a r e m a n y c u r v i l i n e a r p a t h s s u c h a s d o g l e g p a t h , t h e o p t i m a l p a t h , t h e c o n j u g a t e p a t h a n d t h e m o d i fi e d g r a d i e n t p a t h ( s e e 4 , 1 5 a n d 1 8 ) . t h is t h e s is is a n a t t e m p t t o r e c u r t o m o d i fi e d g r a d i e n t p a t h t o o b t a i n i t e r a t i o n d i r e c t i o n b a s e d o n t h e q u a d r a t i c a p p r o x i m a t i o n . t h e m o d i fi e d g r a d i e n t c a n b e e x p r e s s e d妙 t h e e i g e n v a l u e s a n d e i g e n v e c t o r s o f h e s s i a n ( s e e b u l t e a u a n d v i a l 4 ) . t h e t r u s t r e g i o n s u b p r o b le m n e e d s t o b e r e s o l v e d m a n y t i m e s b e f o r e a n a c c e p t e d s t e p i s o b t a i n e d f o r t h e t r a d i t i o n a l t r u s t r e g io n m e t h o d . n o c e d a l a n d y u a n 1 3 s u g g e s t e d a c o m b i n a t i o n o f t h e t r u s t r e g i o n a n d l i n e s e a r c h m e t h o d f o r u n c o n s t r a i n e d o p t i m i z a t i o n . t h i s m i x e d t e c h n i q u e i s c a l l e d b a c k t r a c k i n g . o f c o u r s e , t h e p r e r e q u i s i t e f o r m a k i n g t h is s h i f t i s t h a t a l t h o u g h t r i a l s t e p i s u n a c c e p t a b l e a s n e x t i t e r a t i v e p o i n t , i t s h o u l d p r o v i d e a d i r e c t i o n o f s u f fi c i e n t d e s c e n t . t h e p l a u s i b l e r e m e d y m o t i v a t e s u s t o s w i t c h t o t h e l i n e s e a r c h m e t h o d b y e m p l o y i n g t h e b a c k t r a c k i n g s t e p s a t a n u n s u c c e s s f u l t r i a l s t e p i n t h e m o d i fi e d g r a d i e n t p a t h a l g o r i t h m i n r e f e r e n c e s 司a n d 1 0 , t h e n o n m o n o t o n i c t e c h n i q u e i s u s e d t o s o l v e u n c o n s t r a i n e d p r o b l e m i n l i n e s e a r c h a n d t r u s t r e g i o n m e t h o d r e s p e c t i v e l y . we u s e t h e n o n m o n o t o n i c t e c h n i q u e t o o b t a i n t h e s e q u e n c e o f s u c c e s s f u l i t e r a t i o n p o i n t w h i c h m a k e s t h e o b j e c t f u n c t i o n m o n o t o n i c a l l y d e c r e a s i n g i n t h e p r o c e s s o f t h e l i n e s e a r c h . f o r p r o b l e m s w h o s e o b j e c t i v e f u n c t i o n o r c o n s t r a i n t f u n c t i o n s h a v e s h a r p c u r v e s o n t h e r e c o n t o u r m a p s ( s u c h a s t h e r o s e n b r o c k s f u n c t i o n ) , m o n o t o n i c i t y m a y c a u s e a s e r i e s o f v e r y s m a l l s t e p s a n d t h e n c a u s e a h u g e n u m b e r o f i t e r a t i o n t o r e a c h t h e i r i t e r a t i o n . t h e r e s u l t o f n u m e r i c a l e x p e r i m e n t v e r i fi e s t h a t t h e l i n e s e a r c h w i t h n o n m o n o t o n i c t e c h n i q u e m a y i m p r o v e t h e c a l c u l a t i n g s p e e d a n d i t i s b e t t e r t h a n t h e l i n e s e a r c h w i t h m o n o t o n i c t e c h n i q u e , e s p e c i a l l y f o r r o s e n b r o c k s f u n c t i o n a g o o d a l g o r i t h m s h o u l d h a v e t h e f o l l o w i n g r e p r e s e n t a t i v e c h a r a c t e r i s t i c s : t h e i t e r a t i o n x k c a n a p p r o a c h s t a b l y t h e n e i g h b o r h o o d o f l o c a l m i n i m u m a n d t h e n c o n v e r g e t o二 。 q u i c k l y . t h i s t h e s i s p r o v i d e s a b e a u t i f u l t h e o r e t i c a l a r g u m e n t t h r o u g h d e t a i l e d a n a 妙 s i s a n d s h o w t h e g l o b a l c o n v e r g e n c e a n d q u i c k l o c a l c o n v e r g e n c e r a t e o f t h e a l g o r i t h m . t h e n u m e r i c a l e x p e r i m e n t i s a l s o m a d e b y t h e c o m p u t e r p r o g r a m m i n g , w h i c h v e r i fi e s t h e v a l i d i t y o f t h e a l g o r i t h m. ke y w o r d s : n o n l i n e a r c o n s t r a i n e d p r o g r a m m i n g ; a f fi n e s c a l i n g ; n o n m o n o t o n i c t e c h n i q u e ; i n t e r i o r p o i n t m e t h o d ; q r d e c o m p o s i t i o n ; r e d u c e d p r o j e c t e d h e s s i a n ; m o d i fi e d g r a d ie n t p a t h ; g l o b a l c o n v e r g e n c e ; l o c a l c o n v e r g e n c e r a t e . ams 1 9 9 1 s u b j e c t cl a s s i fi c a t i o n : 0 2 2 1 . 2 第v i 页 致 谢 致 谢 本文是在导师朱德通教授的 精心指导下顺利完成的。 在论文选题， 论文研究 及撰写的 各个阶段，朱老师都给予了极为细心的指导，毫不保留地把他的研究成果和研究体会与 我分享.朱老师还介绍了一些具有引导性、 创新性的重要文献，并提出了 很多具有启发 性的宝贵建议.在此期间，我深深折服于朱老师渊博的数学知识和对数学的满腔热忱， 朱老师严谨细致的治学态度，求真务实的学术作风， 孜孜不倦的工作态度也让我深受感 动和鼓舞.在短短的三年时间中，朱老师传授给我的，不仅是他渊博的专业理论和续密 的 数学 逻辑思维，更 重 要的 是一 种乐 观向上， 积 极进 取的为 人处 事态 度。 在以 后的工 作 和生活中，这些都将成为我最宝贵的财富，时刻指引 我努力学习，不断进步。在此，谨 向朱老师表示我最诚挚的感 谢和最崇高 的敬意， 并以 此文来答 谢我的 导师。 衷心感谢上海师范大学数理信息学院和研究生院所有的老师，感谢他们在我读研期间 为我提供了良 好的学习和科研环境;衷心感谢我的任课老师张寄洲教授，曾六川教授， 丛玉豪教授，击荣先教授，汤 银才教授，向新民教授，郑炼教授，从他们身上我学到很 多宝责的知识。 特别感谢我的师兄顾益明和师 姐张乐 瑛在三年的学习 生活中 给予我的帮助和鼓励;感 谢曾与我一起努力，共同分享快乐与忧愁的同窗王云娟;感谢我的师妹林涛和沈爱玲在 完成论文期间 对我的支 持. 最后， 衷心感谢我的家 人、 我的朋友对我的支 持和关心， 是他们的鼓励让我不断 进 步，勇 往直 前， 是他们的无私奉献 让我实 现了自己 的梦想。 我的 每一点成绩都凝聚了 他 们全心全意无私的爱， 他们的殷切期望是我努力奋斗的动力源泉， 我会继续不断奋斗， 努力成为他们的骄傲。 第1 1 页 序言 序 ， - j一 -碑卜 1 最优化问题是运筹学数学理论中一个重要分支。它研究在有限种或无限种可行方案 中， 挑选最优方案，构造寻求最优解的方法。随着科学研究和计算机突飞猛进的发展， 最优化理论和算法在近五六十年中也有了迅速的发展，在卖际应用中发挥着越来越大的 作用。 当 最优化问 题的目 标函数和约束函数均为线性函数时， 称为线性规划;当目 标函数和 约束函数中至少有一个是变量的非线性函数时，称为非线性规划。当变量受到一些条件 的限制时，寻求目 标函数最优解称为约束优化;反之，当变量不受任何约束的限制时， 寻求最优解称为无约束最优化，无约束最优化问 题是最优化研究的基础。本文研究的是 带等式约束和有界变量约束的非线性最优化问 题。 在本文 所给出 的 模型中， 含 有 等式约 束 和有界变量约 束。 c o l e m a n 和l i 在5 中 对有 界变量约束问 题提出了一种信赖域内 点算法， 称为 “ 双信赖域法”，其中一个很有创新 性和启发性的亮点是构建了一个仿射尺度矩阵，此举启发我们在本文中应从最优性条件 出发，构建一个仿射变换矩阵以克服有界约束这一难点。对于仿射空间中的等式约束， 我们采用了既约h e s s e 矩阵算法。既约h e s s e 矩阵算法是目 前较流行的 解决非线性等式约束 优 化问 题的 有效方 法之一， 朱德 通 在2 0 中 利用信 赖域 投影 h e s s i a n 算 法 成功地 解决了 线 性 约束最优化问题。本文利用等式约束系数矩阵的q r分解的既约h e s s e 阵思想，将原问题 分解成值空间和零空间中的两个通常的信赖域子问题，更易于 数值求解和实现。通过以 上对两个约束条件的转换，本文所构建的算法所给出的信赖域子问题是一个最常用的信 赖域子问 题， 它只是在仿射等式约束系数矩阵的零空间中的 椭球约束下，最小化一个二 次近似函数。 信赖域方法不仅能保证算法的整体收敛性，而且不要求目 标函数的h e s s e 矩阵 ( 或 其近似)是正定的。信赖域方法也可以通过构造适当的曲 线路径，在路径上搜索满足信 赖域约束的二次模型最小值。曲 线路径方法有很多，如折线路径、最优路径、共扼梯度 路 径、 修正 梯 度路 径等( 见 叫， 1 5 和 1 8 1 ) 。 本 文 是 在 近 似二 次 模型 的 基 础 上， 采 用 修 正 梯度路径获得迭代方向。修正梯度路径可以 通过用h e s s i a n的特征值和特征向 量表示 ( 见 $ u l t e a u 和 v i a l 四) 。 在 本文中 ， 我 们 将 证明 修正 梯 度路 径具 有 一些 优良 性 质， 这 些 性质是仿 射变换既约 h e s s e 阵修正 梯度路径内点 算法的理 论基础。 n o c e d a l 和 y u a n 1 3 提出了 信赖域和线搜索两种技术相结合的方法。这个方法引导我们在修正梯度路径算法 中，当某个试验步不被接受时，此时因为试验步己 经提供了一个充分下降方向，我们可 以 采用回代法进行线搜索。在线搜索的过程中，我们还结合了 非单调技术，对一些特殊 的问 题， 将起到加快收敛进程的作用。 一个好的算法应具备的典型特征是;迭代点x k 能稳定地接近局部极小点 x 。 的邻域， 然后迅速收敛于二 ， 。一个算法的收敛速率是迭代方法的一个重要性质。对于一个不可能 在有限步内找到最优解的最优化方法，我们不仅要求它收敛，还要求它有较快的收敛速 度，这是因为对于一个收敛很慢的方法，往往需要很长的时间才能得到满足精度要求的 最优解的近似，因而不是一个有效的方法。 在最优化方法中，牛顿法和拟牛顿法都具有 很好的局部超线性收敛速率。本文的第三章就全面分析了 修正梯度路径内点算法的收敛 性，并给出了一套完善的收敛性证明。 第1 页 序言 论文概述 第一章回顾了最优化方法的基本理论，尤其 对最优性条件， 信赖域和线搜索方法进行 了阐述，为下面各章的研究提供了理论来源:在第二章中，我们构造了一个只受仿射等 式约束系数矩阵零空间中椭球约束的信赖域子问题，构建和分析了仿射修正梯度路径， 在此基础上，描述了非单调仿射变换修正梯度路径的既约h e s s e 阵内点算法:第三章，在 一定的假设条件下，我们证明了此算法所具有的整体弱收敛性，进一步，结合非退化性 和其它一些更强的假设条件，给出了算法的强收敛性和局部收敛速率。第四章中给出了 修正梯度路径算法的数值实验的结果，验证了算法的可行性和有效性。第五章对本文工 作进行总结，同时提出了目 前尚 存在的问 题以 及进一步研究的方向。 符号缩写 为了避免符号混淆， 我们对本文中的 符号做以 下说明: r n n 维实向量空间 r n x m。x二维实矩阵 ii” ， “ :e u c l i d , 数 “ 11- co一范 数 x二 维决策变量 x ，目 标函 数的局部极小值点 f目 标函 数 c ( x )约束函 数 s 1可行集 i n t ( q )严格可行集 i ( x )约束 优化问 题在 可 行点 x 处的 有效不 等式约 束 集 合 a ( x )约束 优化问 题在 可 行点 x 处的 有效 集 8 ( x ) f 在x 处的 梯 度， 即 o f ( x ) h ( x ) =v 2 f ( x ) f 在 二 处的 h e s s e 阵 a , 。 ， 。l a g r a n g e 乘 子 斌 x , a , u , 的等 式 约 束 优 化 问 题 的 l a g r a n g e 函 数 f k f 在当 前迭代点 x k 处的函 数值 4 k ( d )目 标函 数在x k 处的 局部二次近似 *信 赖域 半 径 p r e d ( d k )信 赖域 子问 题的 预 计下降 量 a r e d ( d k )信赖 域子问 题的 实际下 降 量 l ( x o ) = x e r n l f ( x ) o , i =。+1 , , p , ( 1 . 1 . 1 ) 其中 x = ( x l , x z , . . . ， x n ) t e r , f: r n *r 1 ， c: $ 2 *r l ( i =1 ， 2 , . . p ) 为连续函 数， 通常还要求连续可微。 p 是一正 整数， m是介于 。 与 p之间的整数。 二 称为决策变 量 ， f (x ) 为目 标函 数， 其 中 c ; ( x ) , i = 1 , 2 . . . , p 为 约 束 函 数 ， c, ( x ) = 0 , i = 1 , 2 ， 二 ， 二 为 等 式约 束， c , 劝0 , i =m+1 ， 二， p 为 不 等式约 束。 如果 、二 p ， 则问 题( 1 . 1 . 叻 被 称为 等式约束优化问题。 m i n和s .t . 分别为英语单词 m i n i m iz e( 极小化) 和s u b j e c t t o( 受约 束)的缩写。 根据实际问题的不同 要求， 最优化模型有不同的形式， 但经过适当的变换都可以 转化 成 上述一 般的形式。 只要在问 题( 1 .1 . 1 ) 中 存在 任何约 束条件， 就称为约 束最 优化问 题。 只有等式约束时，称为等式约束最优化问题。只有不等式约束时，称为不等式最优化问 题。 如果 既 有等式约束， 又有不 等式 约 束， 则 称为混 合约束问 题。 如果问 题( 1 . 1 . 1 ) 中 无 任何约束条件，则称为无约束最优化问 题。无约束最优化问题是最优化的基础，一则很 多实际问 题的最优化问题本身就是无约束最优化问 题，二则许多约束最优化方法都是通 过变换，把约束最优化问题转换成无约束最优化问题后，用适当的无约束优化方法求 解。 当 模型( 1 . 1 .1 ) 的函数中 有一个 是 关 于 x 的 非线 性函 数时， 称为非 线性 最优化问 题。 若 在 问 题 ( 1 . 1 . 1 ) 中 ， .f ( x ) 是 二 次 函 数， q ( x ) ( s = 1 , 2 , . . . , p ) 都 是 线 性函 数， 则问 题( 1 .工 1 ) 称 为二次规划问题，二次规划是最简单的约束非线性规划问 题。非线性最优化问 题是最一 般的最优化问题，而二次规划问 题却是相当重要的特殊的最优化问题，这是因为在实际 中形成的许多最优化问题爪次规划问题，而且在用迭代法求非线性最优化问题的最优解 第3 页 第一章 最优化问题的概念、性质和主要方法 第一章最优化问题的概念、性质和主要方法 1 . 1最优化问题简介 最优化技术在国民经济的许多领域，如国防、工农业生产、交通运输、金融、贸易、 管理、科学研究中有广泛的应用。所谓最优化就是在众多可 一 行的方案或方法中找到最好 的方案或方法。例如在确定投资项目 时， 希望选择期望受益最大或风险最小的项目;空 间飞船的设计要求在有限的空间放置尽可能多的设备;一个建筑在满足设计要求的条件 下建筑费用应尽可能少;两地之间的输送管道或运输路线在满足要求的条件下应尽可能 短。为应用最优化技术确定最优的方案，需要针对具体的实际问题建立相应的最优化模 型，再根据模型的具体形式和特性选择适当的最优化方法求解。 最优化问题的数学模型一般形式为: m in f ( x ) s .t . c ( x ) 二0 , i =1 , 2 ， 一 ， 。 ， c ; ( x ) o , i =。+1 , , p , ( 1 . 1 . 1 ) 其中 x = ( x l , x z , . . . ， x n ) t e r , f: r n *r 1 ， c: $ 2 *r l ( i =1 ， 2 , . . p ) 为连续函 数， 通常还要求连续可微。 p 是一正 整数， m是介于 。 与 p之间的整数。 二 称为决策变 量 ， f (x ) 为目 标函 数， 其 中 c ; ( x ) , i = 1 , 2 . . . , p 为 约 束 函 数 ， c, ( x ) = 0 , i = 1 , 2 ， 二 ， 二 为 等 式约 束， c , 劝0 , i =m+1 ， 二， p 为 不 等式约 束。 如果 、二 p ， 则问 题( 1 . 1 . 叻 被 称为 等式约束优化问题。 m i n和s .t . 分别为英语单词 m i n i m iz e( 极小化) 和s u b j e c t t o( 受约 束)的缩写。 根据实际问题的不同 要求， 最优化模型有不同的形式， 但经过适当的变换都可以 转化 成 上述一 般的形式。 只要在问 题( 1 .1 . 1 ) 中 存在 任何约 束条件， 就称为约 束最 优化问 题。 只有等式约束时，称为等式约束最优化问题。只有不等式约束时，称为不等式最优化问 题。 如果 既 有等式约束， 又有不 等式 约 束， 则 称为混 合约束问 题。 如果问 题( 1 . 1