（运筹学与控制论专业论文）线性性质在数学规划中的一些应用.pdf

西南大学硕+ 学位论文 摘要 线性性质在数学规划中的一些应用 运筹学与控制论专业硕士研究生邵松青 指导教师张俊容副教授 于两要 线性规划与非线性规划是数学规划中的两个对应类别，前者研究得比较完善 了，对后者的研究也取得了巨大成就，但仍然存在大量的不足。利用线性规划求 解非线性问题，一直是研究者们努力的一个方向，本文也尝试着进行了一些工作： ( 1 ) 探讨了最优解的本质属性和映射不变性。如果数学规划建立在r ”上，其 目标函数是( 五，x 2 ，吒) ，记c = 厂( 五，恐，x n ) ，则有隐函数x n = 办( 西，屯，- ，c ) ， 从而最优解是函数族x n = 矗( 五，屯，吒小c ) 中某函数与可行区域的一个交点：在一 一映射下，这个交点不可能丢失，也不可能增生；非线性规划问题如果能被一一 映射为线性规划问题，那么原问题的最优值一定是映射所得线性规划问题的最优 解。 ( 2 ) 提出了保序线性化方法。它是在探讨了换元线性化的作用和不足之后提 出的，其核心是保序一一映射，将某些非线性规划完整、精确地转化为线性规划， 再由逆映射求得原问题全部最优解的精确值。也即是寻找到一种方法，在结构意 义下界定某一个规划问题为线性规划或非线性规划。 ( 3 ) 改善了一类二次约束二次规划问题的求解策略。从序n - 次规划的角度， 具体讨论了某几种二次约束二次规划问题的保序线性化求解。具体给出了若干例 子，包括非凸、非有界的问题，由其本身构造出保序或者保反序一一映射，转化 为线性规划问题，成为凸的、有界的；采用l i n g o l 2 0 软件对转化前后的问题进 行了对比计算。 ( 4 ) 研究了最小p 乘问题的若干线性性质。受到上述启发，特别分析了最小 二乘法与最小一乘法在残差向量空间上的联系，指出了最小一乘原则下最优残差 向量存在的必要条件和充分条件。然后分类给出了求解最小一乘法问题的新的具 体方法。同时随机构造了若干算例，由l i n g o l 2 0 软件用传统算法进行了对比计 算。 【关键词】非线性，非凸，保序一一映射，线性性质，最小一乘法 s o m en e w a p p l i c a t i o n so f l i n e a rp r o p e r t i e s i nma t h e m a t ica lp r o g r a m m i n g m a j o r ：o p e r a t i o n a lr e s e a r c h t u t o r ：p r o f z h a n gj u n r o n g a u t h o r ：s h a os o n g q i n g a b s t r a c t l i n e a rp r o g r a m m i n g ( l p ) a n dn o n l i n e a rp r o g r a m m i n g ( n l p ) a r et w or e l a t i v e c a t e g o r i e so fm a t h e m a t i c a lp r o g r a m m i n g ( m p ) t h ef i r s to n e i sw e l lr e s e a r c h e d ，a n dw e a l s om a k eg o o dp r o g r e s si nt h ejo bo ft h es e c o n do n e _ - n l p b u tw e m u s tb ea w a r eo f t h ed e f i c i e n c i e si nn l pr e s e a r c h u s i n gl pt og e tn l p h a sa l w a y sb e e nad i r e c t i o nf o r r e s e a r c h e r s s ot h i sa r t i c l et r i e st od os o m ew o r kf r o mt h i sa s p e c t ，a sf o l l o w s ： ( 1 ) e x p l a i n e dt h ee s s e n c ep r o p e r t i e sa n dm a p p i n gi n v a r i a n tp r o p e r t i e s o fo p t i m a l s o l u t i o n ( o s ) i f m pi si nr ”，t h eo b j e c t i v eo fm pi s 厂( 葺，x 2 ，) ，m a r k c = 厂( ，恐，) ，s o t oe x i s t 毛= 办( 五，恐，以一1 ) + c ，o so fm pi s a l l i n t e r s e c t i o np o i n to fb o t hs o m e o n eo f 吒= 7 z ( 五，x 2 ，一1 ) + c a n dc o n s t r a i n t s b vb i j e c t i o n s ，t h i si n t e r s e c t i o np o i n tw i l ln o tl o s eo ra p p e a r ；s e c o n d ，i fan l p c a nr e f l e c ti n t oal p ，t h eo so ft h eo r i g i n a lp r o b l e mm u s tb et h eo so fl pg o t t h r o u g ht h er e f l e c t i o n ( 2 ) p r o p o s e dm e t h o do fl i n e a r i z a t i o nw i t hk e e p i n go r d e r , a f t e rw e k n o wt h ea c t i o n a n ds h o r t c o m i n go fm e t h o do fl i n e a r i z a t i o nb ys u b s t i t u t i o n i t sc o r ei sb i j e c t i o n s w i t hk e e p i n go r d e r f i r s tt r a n s f o r ms o m en l pt ol pi n t e g r a l l ya n de x a c t l y n e x t ， t h r o u g hi n v e r s em a p p i n gt og e t e x a c tv a l u eo fa l lo si no r i g i n a lq u e s t i o n i na l l ， t r y i n gt og e tam e t h o d t od e f i n es o m e o n em pa sl po rn l p ( 3 ) i m p r o v e do n ek i n do fs o l v i n gt a c t i c so fq u a d r a t i c a l l yc o n s t r a i n tq u a d r a t i c a l p r o g r a m m i n g ( q c q p ) f r o mt h ea s p e c to fs u c c e s s i v eq u a d r a t i c a lp r o g r a m m i n g ， a n a l y z es o m ek i n d so fq c q v a n dp r o p o s e ds o l u t i o no fl i n e a r i z a t i o nw i t hk e e p i n g o r d e rt ot h e m s p e c i f i c a l l ys o m ee x a m p l e sw e r eg i v e n ，i n c l u d i n gp r o b l e m so f n o n c o n v e x ，u n b o u n d e d ，a n dt h e nf r o mt h e m s e l v e sc o n s t r u c t e db i je c t i o n sw i t h k e e p i n go r d e ro rk e e p i n ga n t i t h e t i co r d e r ，t r a n s f o r mt h e mt o l p a r ec o n v e x ， b o u n d e d ；t h e ns o l v e dt h e m ，i nt h em e a n t i m ec o m p l e t e dt h e mb yl i n g o1 2 0i n t r a d i t i o n a lw a y s ，a n dt h e nc o m p a r e dt h et w or e s u l t s ( 4 ) r e s e a r c h e ds o m el i n e a rp r o p e r t i e so fl e a s tt h ep o w e rpo fa b s o l u t e d e v i a t i o n i v 两南大学硕十学位论文 a b s t r a c t a n df r o mt h a t ，a n a l y z e dt h ec o n n e c t i o no fl e a s ts q u a r ed e v i a t i o n ( l s d ) a n dl e a s t a b s o l u t ed e v i a t i o n ( l a d ) i nr e s i d u a l sv e c t o rs p a c e p o i n t e do u tt h en e c e s s a r y c o n d i t i o no fa n ds u m c i e n tc o n d i t i o no ft h ee x i s t e n c eo fl r e s i d u a l sv e c t o r t h e np r o p o s e dn e w w a y so fs o l v i n gl a d w i t hc l a s s i f i c a t i o n t h e ns o m er a n d o m e x a m p l e sw e r eg i v e na n ds o l v e dw i t ht h en e ww a y s ，i nt h em e a n t i m ec o m p l e t e d t h e mb yl i n g o1 2 0i nt r a d i t i o n a lw a y s ，t h e nc o m p a r e dt h et w or e s u l t s k e yw o r d s ：n o n - l i n e a r , n o n c o n v e x ，b i j e c t i o nw i t hk e e p i n go r d e r , l i n e a rp r o p e r t i e s ， l a d v 学位论文题目： 独创性声明 本人提交的学位论文是在导师指导下进行的研究- 1 - _ 作及取得的研 究成果。论文中引用他人已经发表或出版过的研究成果，文中已加了 特别标注。对本研究及学位论文撰写曾做出贡献的老师、朋友、同仁 在文中作了明确说明并表示衷心感谢。 学位论文作者：影严拟牵签字嘲：m 年午月加日 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权西南大学研究生院( 筹) 可以将学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：口不保密， 口保密期限至年月止) 。 学位论文作者签名：召仁仫毳 导师签名：张雠 签字日期：- 2 , of 。年耷月加日 签字日期：0 。口年月6 日 西南大学硕士学付论文 第1 章绪论 第1 章绪论 1 1引言 线性性质是数学中的一个经典概念，它已经被广泛应用到自然科学和人文社 会科学的各个分支领域。但是什么是线性性质，哪些表现形式在本质上是线性的， 在实践中没有引起人们的足够重视。许多学习者、研究者仅仅是以直观数学的线 性形式作为全部的、唯一的线性形式来考虑。但高等代数与解析几何课程已经深 刻而明确的指出了线性的数学本质和若干表现形式。我们可以发现，许多看似非 线性的问题，经过拆解或和转化后，清晰地是符合线性的数学本质的，即它们在 本质上是线性问题。 众所周知，数学规划有线性规划与非线性规划之分，然而正如前面所述，许 多非线性规划在本质上是线性规划，却没有引起人们的充分重视，特别体现在机 械化、计算机求解过程中，往往反而陷入一种“不能 状态。 本文所想探讨的，就是怎样辨识和还原相当数量的所谓非线性问题，成为线 性问题。基础知识变化万端，应用无穷，本文尝试着为此做了一点工作，并取得 了一点收获。 1 2数学规划的研究历史与现状 数学规划，是研究在某些约束条件下函数的极值问题的学科，它来源于合理 分配有限资源以取得最大效果的生活实践及其数学理论与方法。作为运筹学的最 重要的分支与基础，大量实际问题，如物资调运、场址选择、资源分配、市场销 售、任务指派等都可以归结为数学规划问题来处理2 1 。 它的基本思想出现在1 9 世纪初，至2 0 世纪4 0 年代因为战争的需要，人们开 始深入研究规划问题，先后出版了冯诺依曼的对策论和经营行为、康托洛 维奇的生产组织与管理中的数学方法等书。第二次世界大战后，由于生产发 展的需要和电子计算机的应用，数学规划理论、方法及其实践得到空前发展。5 0 年代，钱学森、许国志等学者将数学规划及运筹学引入我国，而后在以华罗庚为 首的一批中国数学家努力下，我国数学规划及运筹学的研究、教学和应用很快达 到了当时的国际水平。 在数学规划中，通常把需要求极值的函数称作目标函数，并根据是否有约束 条件，或者约束条件是否真正起到作用，分为带约束规划和无约束规划。根据目 标函数与约束条件( 函数) 的特点，又具体分为如下几大类： 线性规划。研究在线性约束条件下线性目标函数的极值问题，是数学规划 的基础。 两南大学硕士学位论文第1 章绪论 非线性规划。是指在约束条件和目标函数中出现非线性关系的规划。 整数规划。规定部分或全部变量为整数的规划。 组合规划。讨论在有限集中选择一些子集使目标函数达到最优的问题。 参数规划。在目标函数和约束条件中带有参数的规划。 随机规划。指某些变量为随机变量的规划。 动态规划。是处理多阶段决策的一种方法。 此外还有多目标规划、几何规划、分数规划、模糊规划等。 在这些众多内容中，线性规划是最基本最重要的分支，它在理论上最成熟、 方法上最完善、应用上最广泛，其他分支都是线性规划的发展和推广。 对各种不同类型的规划，我们主要研究它是否存在最优值，分为最优概念、 必要条件、充分条件以及对偶定理，如果存在又有怎样的最优值，是一个、多个 还是一类，特别考察局部最优与全局最优的关系，然后即是判断以及求解最优的 有效算法，分为精确算法和近似算法等，其中一个重要指标是计算复杂度，进一 步还要考察所谓灵敏度问题。 对于线性规划，上述需要考察的各方面已经比较完善，但对于非线性规划， 尚存在大量的问题需要解决，特别是局部最优与全局最优的关系，精确与近似的 关系，计算简易与复杂的关系。 作为应用科学，理论是基础，算法是核心。传统的算法，限于计算工具的能 力，倾向于直接求解最优解，却是往往不能成功的：随着计算机科学的发展，人 们创新性地提出了所谓序列规划算法，以迭代的方式逐步逼近最优解，同时也在 思维和理论上找到了一个突破口。当今，以序n - 次规划为代表的序列规划算法， 已经被广泛认可和使用，在对许多难题的求解中发挥了重要作用。 1 3数学规划的经典理论与方法综述 本节主要介绍数学规划中的线性规划与非线性规划n 2 1 ，若干定义及定理引用 自运筹学 2 1 。 1 3 1 线性规划 美国数学家g b d a n t i z 于1 9 4 8 年在他的著作线性结构规划中提出了“线 性规划 这一概念，并于1 9 4 9 年给出了著名的、至今仍然是最主要方法的单纯形 法，这一线性规划法也被广泛借用到非线性规划中。 线性规划是特指目标函数与约束条件表达式都是线性形式的条件极值问题。 2 两南大学硕十学位论文第1 章绪论 线性规划问题的标准模型是： m a xz2 c i x l + c 2 x 2 + + 巳吒 a l l + 口1 2 x 2 + + 口l 。矗= 岛 口2 l 五十口2 2 而+ + 口2 n 吒= 6 2 a , n x l + 口2 屯+ + 口。 毛= 6 研 x j o ( j = l ，2 ，n ) 其中6 f 0 、c j 、( = 1 ，2 ，m ，江1 ，2 ，刀) 均为常数；可用矩阵表示为 m a xz = c x “ 笼亏6 其中a = ( ) 。，x = ( 五，x 2 ，_ ) r ，c = ( q ，c 2 ，巳) ，b = ( 岛，如，吒) r 。通常规 定r a n k ( a ) = m ，显然它总是能够达到的。我们简称上述问题为l p 问题。 定义1 3 1 若l p 的决策变量而，x 2 ，x 3 ，毛的某一组取值满足全部约束条 件，则称该组取值为l p 的一个可行解，称可行解的全体构成的集合为l p 的可行 域。 定义1 3 2 若x = ( x l ，x 2 ，x 3 9o 9 x n ) 是lp 的一个可行解，对应于它的目标函 数值是z ，该z 小于等于该lp 的任一可行解所对应的目标函数值，则此 x = ( x i ，x 2 ，x 3 ，毛) 称为lp 的最优解。 定义1 3 3 设c 是一点集，若任取其中二点x 1 和x ，对 o ，1 间任意实数 a ，都有 口( 1 + ( 1 一口) x ( 2 c ， 则称c 为凸集。 定理1 3 1线性规划标准模型的可行域是凸集。 定理1 3 2 有限个凸集之交是凸集。 定义1 3 4 设x 是凸集r 上的一点，若不存在x ( ，x ( 2 t ，x ( 1 x ( 2 及 实数口( 0 ，1 ) 使得成立 x = 口x ( 1 + ( 1 一口) x ( 孙， 则称x 是凸集r 的极点或者称为顶点。 定理1 3 3 ( 线性规划基本定理) ( 1 ) 若l p 存在有限最优解，则某个极点就是最优解。 ( 2 ) 若l p 存在可行解，则必有极点。 至此，线性规划的理论问题基本解决，余下具体算法以单纯形法为主要和最 西南大学硕士学位论文第1 章绪论 优秀的代表，众所周知的，略。 1 3 2 非线性规划 非线性规划问题，是线性规划问题的一种自然推广，但线性规划方法却很难 直接用于求解非线性规划。 我们给出非线性规划的概念形式为： m i n ( m a x ) z = f ( x l ，x 2 ，吒) s d 曩( ，屯，) q fo ( i = 1 ，2 ，聊) 其中至少有一个表达式是非线性表达式；我们简单记其为m p 。 定义1 3 5 若x s ，且对 s 有f ( x ) f ( x ) ，则称x 为m p 的整体 最优解，称f ( x ) 为整体最优值。 定义1 3 6 若x s ，存在x + 的一个领域 虬( x ) = xl x - x 0 o ) ，使得拟 snn 占( x ) ) 满足( x 。) ( x ) ，则 称x 是m p 的局部最优解，f ( x + ) 为m p 的局部最优值。 定义1 3 7 设厂( x ) ，x = ( ，屯，) 7 r ”具有连续二阶偏导数，称向量 函数 v f ( x ) ：( 要，婺，要) r 似l 饿2饿“ 为厂( x ) 的梯度；称矩阵值函数 h ( x ) = v 2 f ( x ) = 盟笪笪 挑2 挑x 2 ”o x i x n 堕旦塑 瓯钆x 2 x l ”纸2呶，m 。呶0 为厂( x ) 的海赛矩阵。 定义1 3 8 设scr ”是一非空凸集，厂( x ) 为定义在s 上的n 元函数，若对 任意的口( 0 ，1 ) 及任意彳( n ，x ( 2 s ，有 f ( a x 1 + ( 1 一口) x 2 ) 口厂( x 1 ) + ( 1 一o o f ( x 2 ) 则称f ( x ) 是s 上的凸函数。 定理1 3 4 若f ( x ) 为定义在开凸集scr “上具有二阶连续偏导数的n 元函 数，则f ( x ) 为s 上凸函数的充要条件是f ( x ) 的海赛矩阵h ( x ) 在s 上处处半正 定。 定理1 3 5 设函数f ( x ) 定义在scr ”上，在点x o s 处二阶可导，如果梯 4 西南大学硕士学位论文第1 章绪论 度向量v ( 五) = 0 ，且海赛矩阵片( 以) j 下定，则是局部极小解。 定理136 设f i x l 为定义在凸集s c r 4 上的n 元凸函数，则f ( x 1 的局部 极小解必然也是s 上的全局最小解。 定义139 设 问题为 黜，( x ) ， 若s 是凸集，( x ) 是s 上的凸函数，则称卵为非线性凸规划问题，简称凸规划。 非线性规划的求解方法主耍有梯度法、牛顿法、可行方向法、制约函数法以 及序列和混合方法等，然而没有任何一种能够确保求解所有的非线性规划，实际 上大量的非线性规划问题仍然远远没有得到求解。 可见，真正的非线性规划与线性规划极为币同，在求觯上往往要艰难得多； 并且，非线性规划已经倾向于主要探讨凸规划，它要求约束点集是凸集，目标函 数是凸函数，对不符合要求的约束与目标，需要转化为凸的，尽管这样做取得了 巨大的成就，但仍然不能很好地满足实际需求，对非凸规划的研究是很有必要的。 14从线性陛质角度对数学规划的一种理勰 线性规划作为首先解扶的问题，其约束( 边界) 的线性性质是主要原因，它 们从无限多个点中迅速确定了有限多个具有特殊性质的点为“顶点”1 训对由目标 的线性性质和约束的凸性，确定了“项点”是最优解的必要条件，从而极大地简 化了问题，并得到一个寻找最优解的相当完善的、统一的高效方法，它首先可以 在理论上沧证解点是否存在，如果存在还能够在理论上得到其精确值的，这与非 线性规划的情况是很不相同的“21 ”。 非线性凸规划，其约束和目标不同时具有线性性质，从而难以确定“顶点” 或“必要条件”，至今也仍然没有建立一个完善、统一、高效的方法。 但我们注意到，若干的非线性约束凸规划，其摄优解，类比于线性约束可行 域的顶点，完全可阻看作其顶点，如图： 最优点在凸曲线相切点 固 最优点在线性凸区域顶点 ( b ) 两南大学硕十学位论文第1 章绪论 它们分别是规划问题 m a x x 2 + j ，2m a x 一z l z 2 + 1 + l s 94 + 1 + l s 49 x 0 y 0 一量z 4 2 一 ! 川 3 2 l ( 1 2 一 关于y 这个维度进行保序一一唑射研? “一“，使得原问题改写形式等价于 r a i n y 一3 x 如幽所示 求解略 y 一( 2 l 0 9 52 ) x 2 l 0 9 52 y 一( 寺l 0 9 53 ) x l 0 9 5 3 y + ( 1 0 9 57 ) x s2 l o g5 7 图4 象图 西南人学硕士学位论文笫2 章线性性质在数学规划中的某些新鹿川 用l i n 9 0 1 20 直接求解原问题，退代4 5 次，得到被认为是局部蛀优值的全局 最优值00 0 0 0 5 3 9 9 8 7 7 ，解点( 20 0 0 0 0 5 ，10 0 0 0 0 4 ) ：对线性化后的问题求解， 迭代1 次，得原问题的全局最优值的象6 以及原问题最优解的象点( 2 ，0 ) ， 逆映射回原l 】j 题即得明确为全局最优的值00 0 0 0 6 3 9 9 8 7 7 ，和其解点( 2 ，1 ) ，并 且显见完全是精确的。 2 3 映射9 i ：x l x l ”1 + x 对平面内各维度进行保序 ( z ，y ) ix 2 + y 2 = i 将被映射为 ( ，r ) 一映射孵：u l u 【_ 十u ，圆状图即点集 【x i + i y | = 1 ，呈正方形状。如图： 原图象圈 图6 进一步，在保反序一一映射婀：u l u l ”1 呻u ( 其中”是负实数) 下，点集 ( z ，y ) l p f l y ”| = l 将被映射为 ( x ，d i l x l + l yj = ”，呈j f ! 方形状。如图： 塑窒垒兰堡圭兰堡堡圣量：至丝兰篁堡垒丝兰些型耋墼蓥： ：窒 原呵象图 图7 显见，上述非单连通的区域，被保反序一一地映射为单连通区域。 所以，当”是非0 实数时，一一映射吼“- + u 将点集 ( t y ) z 4 l + l y “| = 1 ) 映射为 ( ，n ix l + l r | ：1 ，呈证方形状。 上述分析。为我们考察若干规划问题提供了一个新的思路，尽管它类似于换 元，但本质上与换元并不相l 司。 m i n y 一3 x 2 例2 一 “y o 2o l y + x 2 1 s y - z ，s - 0 1 和5 y + z ， - 0 l + 渺等 两南大学硕十学位论文第2 章线性性质在数学规划中的某些新府用 求解略。 值得说明的是，l i n g o l 2 0 不能正确求解此原问题，仅在2 0 次迭代后得到所 谓局部最优值0 和解点( 0 ，0 ) 。 上述把二次多项式映射为两射线相交，在使用导数考察时，很有效果，显见， 若求二次多项式的顶点，由牛顿法容易得到近似点，而映射为射线后，很容易得 精确点，类似地对求解若干奇异问题有帮助。 在下一章中，将对本节内容作展开讨论。 1 7 西南大学硕+ 学位论文 第3 章线性化求解二次规划 第3 章保序线性化求解二次规划 3 1 序n - - 次规划理论概述 3 1 1 二次规划 二次规划是非线性规划中一类特殊的数学规划问题，一般规定它的目标函数 是二次函数，而约束条件是线性的。这样的二次规划的解是可以通过求解得到的， 通常先求解其库恩一塔克条件( k t 条件) ，获得一个k t 对，其中与原问题的变量 对应的部分称为k t 点，根据必要性，即可能是最优解5 “7 1 。 二次规划分为凸二次规划与非凸二次规划，前者的k t 点便是其全局极小解， 而后者的k t 点可能连局部极小解都不是。求解二次规划的方法很多，经典的是沃 尔夫法，它依据库恩一塔克条件，在线性规划单纯形法的基础上加以修改而成。 此外还有莱姆基法、毕尔法、凯勒法等。 但最近以来，人们逐渐关注起二次约束二次规划来，主要源于对序y u - 次规 划的改进，它比线性约束二次规划更加贴近原问题，但难度也要大得多。本章就 尝试对此进行一点研究。 3 1 2 序n - - 次规划 序y i j - - 次规划法又称为二次逼近法，英文缩写为s q p ，它的核心是：给出一个 可行解，然后在此解处对约束条件进行多元一阶泰勒展开得到一个线性表达式， 同时对目标函数( 仅一个) 采用多元二阶泰勒展开得n - 次表达式，从而构造出 一个线性约束二次规划，求解它得到一个解，更正此解为原问题下可行，如果此 解使得原目标函数值更优，则更新之前给出的可行解为此解，重新进行泰勒展开， 进行第二次线性约束二次规划，以此循环，直至达到收敛或停止要求8 “1 0 j 1 1 2 1 。 随着应用的需要，把线性约束改为二次约束的序n - 次规划也被提出来加以 研究，显见，改进后可能使得序列二次规划的求解能力得到加强，但其依赖于对 二次约束下的二次规划的研究。 3 2 保序线性化求解二次约束二次规划 3 2 1 约束与目标都不舍一次项、交叉项的情况 有规划问题n 川1 ： m a x c ( 帆( f ) 2 ，拧z + s j 匹a ( j ，咖( f ) 2 6 ( ) ，= 1 ，2 3 ，m i = 1 两南大学硕十学位论文 第3 章线性化求解_ 次规划 关于所有自变量同时进行保序一一映射贸：“川hw ，将原问题转化为： m a x f ( 圳( f ) i l 刀z + i = 1 h ， s 2 【口( ，f ) i x ( f ) i 】6 ( 办j = 1 ，2 ，3 ，m i = 1 进一步转化为 其中 m a x u t ，k = 1 ，2 ”) = m a x 厂( x ( f ) ) c ( f ) x ( 札玎z + i = 1 厂( z ( 啪口( ，o x ( o 6 ( n j = l ，2 3 ，m ， 似叱冀羔 e ( x ( f ) ，i = 1 ，n ) = ( 厂( x ( z ) ) ，i = 1 ，n ) ( q ，巳) iq = l ，一1 ) ； 1 k 2 “，k z ；k t 饬亡e 。( 水) 吒( 水) 3 2 2 约束与目标都不含交叉项的情况 有规划问题： m a x c ( i ) x ( i ) 2 + d ( 咖( 办，z z + n ， 趴t 以( ，帆( f ) 2 + d ( 埘x ( f ) 6 ( 办j = l ，2 ，3 ，m 它还满足要求： ( 1 ) 当c ( i ) = 0 时有d ( i ) = o 成立，对一切f ： ( 2 ) 当a ( j ，i ) = 0 时有d ( j ，i ) = 0 成立，对一切，； ( 3 ) 对每一个确定的f ，分别记c ( i ) 、d ( i ) 为a ( o ，i ) 、d ( o ，i ) ； 又记 k = ia ( j ，f ) 0 ，j = 0 ，1 ，2 ，3 ，例i ， 我们规定： 嘶，= j 鬻以谚o ， 【0 ，c ( f ) = 0 。 这样，我们作配方： 1 9 两南大学硕士学位论文第3 章线性化求解二次规划 m a x t c ( f ) ( x ( f ) + 去出( f ) ) 2 】 妣buf)(硼)畦dc(i)4。虿1丽d(j,i)-一知) ) 2 】 6 + 丢荟筹 _ ，：11 ，2 ，3 ，州 其中三，= il 口( _ ，i ) 0 ，i = l ，2 ，3 ，1 ) ，j = 0 ，1 ，m 。 显见，记x ( i ) + 去如( f ) 为x ( f ) ，上述可化为 m a x c ( i ) x ( f ) 2 ，l z + “黔川如，毛粉一扣烙从舻刚，+ 去薹筹 i ：1 , 2 ，3 ，研 对任意岛，如k 且墨如，如果成立： d ( 岛，i )d ( 心，f ) 一= 口( 霸，i )a ( k 2 ，f ) 则上述化为 m a x c ( 啦孵，刀z + 盯t p n 力“矿鲥叫卅丢吾筹川幺3 ，川 即可按照3 2 1 的方法“线性化”求解，然后代回上述配方得原问题的解。 3 2 3 约束与目标不含一次项的情况 考察规划问题： m a x c ( 咖( f ) 2 + 2 d ( 尼，啦( 尼) z ( ，) ，玎z + i = 1l k l s n 趾t 口( 棚x ( f ) 2 + 2 d ( _ ，k ，啦( 尼) x ( ，) 6 ( 办j = l ，2 ，3 ，m i = 1 l k l a n 其中c ( k ) 、c ( t ) 、d ( k ，) 做成的矩阵 c ( 1 ) d ( 1 ，2 ) d ( 1 ，行) d ( 1 ，2 )c ( 2 )d ( 2 ，n ) d ( 1 ，1 ) d ( 2 ，刀) c ( ，1 ) 显然可以由正交变换或者一般的非退化的基变换化为对称阵： 2 0 两南大学硕士学位论文第3 章线性化求解：次规划 c ( 1 ) 0 0 0c ( 2 ) 0 00 c ( 刀) 记该变换矩阵为r 。但对每一确定的，其a ( j ，后) 、 a ( j ，1 ) d ( j ，1 ，2 ) a ( j ，1 ，2 ) a ( j ，2 ) a ( j ，) 、 d ( j ，1 ，刀) a ( j ，2 ，z ) a ( j ，1 ，刀) d ( j ，2 ，n ) a ( j ，1 ) 不一定能被上述丁化为对称阵，仅化为： a ( ，1 ) d ( ，1 ，2 ) d u ，1 ，n ) d ( _ ，1 ，2 )a ( ，2 )d i ( ，2 ，刀) d ( ，1 ，刀) d t ( ，2 ，刀) a ( ，z ) d ( j ，k ，) 做成的矩阵 其中d ( ，k ，) 不全为0 ，对所有j = 1 ，m 及k 和，= 1 ，n 。 记旋转得到的新坐标系为缸( f ) ii = l ，2 ，3 ，n ) ，则原问题转化为 m a x c ( 拶( f ) 2 ，珂z + 百 s f 匹口i ( ，i ) x 钟+ 2 d ( ，k ，1 ) x ( 尼) x ( ，) 6 ( ) ，j = l ，2 ，3 ，m 我们总可以记有x ”( f ) 满足 c 协( f ) = ) l 研协 将上述改写为： m a x f ( i ) x ”( f ) 2 ，z z + s 。匹 口( ，i ) f ( i ) x ”( 们+ 2 州，k ，1 ) f ( k ) f ( 1 ) x ”( j j ) x ”( 明6 ( ) ，j = l ，2 3 ，川 其蝴沪翟三暑。显然，女果厂( 归1 或袱归- 1 ，对任鼽那么我 们还可以进一步对规划问题旋转，保持目标函数在实际上不变的同时，化去某些 甚至全部约束中的交叉项，一旦约束也没有交叉项了，就可以按照3 2 1 的方法 求解，然后通过上述变换的逆变换得到原问题的解。 特别地，如果对每一个确定的，其a ( j ，k ) 、a ( j ，) 、d ( j ，k ，) 做成的矩阵能 被e 述r 化为对称阵： 2 l 两南大学硕士学位论文第3 章线性化求解二次规划 则原问题转化为 a ( ，1 ) o o 口( ，2 ) o o 00 口( - ，1 ) m a x c ( f ) x w ，刀z + 扛l n 匹口u ，i ) x - ( f ) 2 6 ( 办= l ，2 3 ，m 然后按照3 2 1 的方法计算，将其解经过上述旋转的逆变换得到原问题的解。 3 3 保序线性化求解一类高次约束高次规划 仿照3 2 1 的情形，我们考察如下的规划问题 j v m a x c ( f ) i x ( f ) l “，n z + ，z r 0 i ) 一 、7 、7 l 、7 f ：l | v “ a ( j ，圳x ( f ) | ”s b ( j ) ，j = l ，2 3 ，m f - l 对其采用一系列保序一一映射： 吼，：x ( f ) | x ( f ) | ”1h x ( f ) ，i = 1 ，2 3 ， 转化得： m a x c ( f ) i x ( f ) n