（应用数学专业论文）优化理论在航空收益管理若干问题的应用研究.pdf

摘要 优化理论在航空收益管理若干问题的应用研究 专业：应用数学 研究方向：人工智能与计算机网络 博士生：黄文强 指导教师：朱思铭教授 摘要 航空收益管理是当今航空业界的热门话题。自四十多年前第一篇关于超售的 文章出版以来，航空收益管理理论正逐步得到发展完善，优化理论与计算机技术 在航空收益管理中得到充分的利用。国外的很多著名大学如麻省理工学院等专门 设置了航空实验室及收益管理博士方向来研究收益管理的理论与实践。今天，航 空公司与其他行业的收益管理系统及相关信息技术已经成为其将来成功的关键 因素，以收益最大化为目标的收益管理理论正在驱动信息技术向新的方向发展， 而信息技术的发展反过来逐步完善收益管理的理论与实践，并促进计算机系统与 其他重要规划、资源优化等功能方面的进一步整合。目前已经有许多关于收益管 理实践与理论的重要文章在一些周刊、杂志、技术报告及会议上发表。主要研究 方向包括，预测、动态定价、超售、库存控制与优化、网络( 起点终点) 收益管 理等等，并与航空公司其他规划领域的互相依赖、密切相关的，特别是定价、价 格产品设计、飞机调配及航线规划等等。 本论文试图在这一重要领域中前人的工作基础上，对航空收益管理中的预 测、优化、定价、竞争等问题进行探讨研究，并将研究结果进行数据试验。 论文首先应用支持向量机方法进行航空运输量预测、航空常旅客分类、持票 不登机旅客分类预测，在此基础上提出了变量可分离支持向量机分类与预测模型 及其算法，并通过实验与应用证明其训练时间较短：从所见文献来看，这是支持 向量机方法首次应用了航空收益管理预测；而变量可分离支持向量机方法也是首 次提出并得到应用。 其次，论文建立了航空公司按航线分配飞机的二层规划模型，将宏观收益管 i 博士学位论文 摘要 理一按航线分配飞机以及微观收益管理一按需求进行座位分配联系起来，上层满 足飞机分配成本最小，下层满足各航线收入最大化。然后，设计了货机调度模型， 利用遗传算法进行分析求解，并在数据模拟中得到较好的结果。 论文还建立了航空公司剩余座位贝叶斯拍卖定价模型及基于遗传算法的航 空公司剩余座位投标竞价模型，以及利用马尔可夫动态决策方法建立航空收益管 理座位分配优化模型。前两种方法，主要针对目前航空市场竞争激烈情况下将剩 余座位拍卖出去以达到收益最大化的目的。另外，通过马尔可夫方法建立动态规 划方程，得到最优定价方案。 最后，论文建立了航空公司竞争的微分方程和时标动态方程两种模型并进行 了参数设计和定性分析。验证了航空公司在竞争激烈的同一航线的竞争趋势。另 外，针对微分方程只能够描述连续情形的缺点，设计了将离散与连续结合的时标 动态竞争方程，并给出了基本性质并提出了定性分析的方法。 关键词：变量可分离支持向量机；航空收益管理；二层规划；马尔可夫决策过程； 贝叶斯拍卖；定价；时标动态方程；竞争模型；遗传算法。 博士学位论文 a b s t r a c t a p p l i c a t i o nr e s e a r c ho fo p t i m i z a t i o nt h e o r yi ns o m ep r o b l e m s o fa i r l i n e sr e v e n u em a n a g e m e n t m a j o r ：a p p l i e dm a t h e m a t i c s n a m e ：h u a n gw e n q i a n g s u p e r v i s o r ：p r o f e s s o rz h us i m i n g a b s t r a c t a i r l i n er e v e n u em a n a g e m e n ti sac o n c e n t r a t er e s e a r c ht o p i ci na i r l i n ei n d u s t r y t h e t h e o r yo fa i r l i n er e v e n u em a n a g e m e n ti sd e v e l o p i n ga n dp e r f e c ts i n c et h ef i r s tp a p e r a b o u ta i r l i n eo v e r b o o k i n gw a sp r o d u c e di nf o r t yy e a r sa g o t h eo p t i m a lt h e o r ya n di t w e r ew i d e l yu s e di na i r l i n er e v e n u em a n a g e m e n t m a n yl a b sa n dr e s e a r c hc e n t e ra r e s e t u p t o p r o c e s st h ep r a c t i c ea n dr e s e a r c ho fr e v e n u em a n a g e m e n ti nm a n y u n i v e r s i t i e sa n di n s t i t u t e sa l lo v e rt h ew o r l d t o d a yt h ep r a c t i c eo fr e v e n u e m a n a g e m e n ta n di t sc o m p u t e rs y s t e ma r eb e c o m i n gt h e i m p o r t a n tt o o l sa n dc r i t i c a l s u c c e s sf a c t o ri na i r l i n ea n do t h e ri n d u s t r y c u r r e n t l yt h e r ea r em a n yp a p e r sa n dt h e s i s t od i s c u s st h ep r a c t i c ea n dt h e o r yo fa i r l i n er e v e n u em a n a g e m e n t t h ef o u rm a j o r r e v e n u em a n a g e m e n tr e s e a r c ha s p e c t sa r ef o r e c a s t i n g ，o v e r b o o k i n g ，s e a ti n v e n t o r y c o n t r o l , a n dp r i c i n g ，w h i c ha r ec a l l i n gm i c r o c o s m i cr e v e n u em a n a g e m e n t t h e m a y o s c o p i c a lr e v e n u em a n a g e m e n tf o c u so nn e t w o r kp l a n n i n g , f l e e ta s s i g n m e n ta n d o t h e ri s s u e sr e l a t e dw i t hd y n a m i cp r i c i n g i nt h i s p a p e r ，w e a r eg o i n gt od os o m ef u r t h e rr e s e a r c ho nf o r e c a s t i n g ，f l i g h t o p t i m i z a t i o n ，p r i c i n g ，c o m p e t i t i o nb a s e do nt h ef o r g o n er e s e a r c h , w i t hs o m ed a t a t e s t i n gt op r o v et h em o d e l t h ef i r s tc h a p t e ri st or e v i e wt h ed e v e l o p m e n to fa i r l i n e s r e v e n u em a n a g e m e n t ，o p t i m a lt h e o r ya n d c o m p e t i t i o nt h e o r y t h es e c o n dc h a p t e ri st oi n t r o d u c et h eu s eo fs u p p o r tv e c t o rm a c h i n ei nc u s t o m e r c l a s s i f i c a t i o na n dt r a n s p o r t a t i o nf o r e c a s t a n dt h e nw eb r i n gf o r w a r dan e wk i n do f i 博士学位论文 a b s u a c t s v mn a m e dv a r i a b l es e p a r a b l es v m ，g i v i n gi t sd e f m i t i o na n da l g o r i t h m w ea l s og o t ac o n c l u s i o nt h a tt h ef o r e c a s tp r e c i s i o na n da c c u r a c yv a r i a b l es e p a r a b l es v ma n dt h a t t r a d i t i o n a ls v mw h i l et h ef o r m e rt r a i n i n gt i m ei sl e s st h a nt h el a t t e r v a r i a b l e s e p a r a b l es v m c a nb ew i d e l yu s ei na 订i i n ed a t ac l a s s i f i c a t i o na n df o r e c a s t i nt h et l l c h a p t e r w es e t u pab i l e v e lp r o g r a m m i n gm o d e lt ol i n kt h em i c r o c o s m i c a n dm a c r o s c o p i c a lr e v e n u e m a n a g e m e n t ，w h i c hu p p e rg o a li st om i n i m i z et h ec o s to f f l e e tc o s tw h i l et h el o w e rg o a li st h es a r i s f yt h em a x i m i z et h et o t a lr e v e n u eo fe a c h c h s so fa l lf l i g h t s w ea l s os e t u pac a r g of l e e ta s s i g n m e n tm o d e lt om i n i m i z et h e f l i g h tc o s t ，u s i n gg e n e t i ca l g o r i t h mt os o l v et h ep r o b l e m t h e r ea r em a n yr e s i d u a ls e a t sl e f ta f t e rt a k i n go f fb e c a u s eo fl o wd e m a n db u t s c o r c h i n gc o m p e t i t i o no fd o m e s t i ca i r l i n e s w es e t u pt w oa u c t i o nm o d e l st os o l v et h e p r o b l e mo fa k l i n cr e s i d u a ls e a t si nt h ef o r t hc h a p t e r w eu s es e a l e d b i da u c t i o n p r i n c i p l et os e tu par e s i d u a ls e a t a u c t i o nm o d e la n ds o l v ei tb a s e do ng e n e t i c a l g o r i t h m w ea l s os e t u pa n o t h e ra u c t i o nm o d e l b a s e do nb a y e sd y n a m i cg a m et h e o r y w i t hl i n e a rs t r a t e g y a tl a s t ，w es e t u pad y n a m i cp r i c i n gp r o g r a m m i n gm o d e lb a s e do n m a r k o vd e c i s i o np r o c e s s a tt h el a s tc h a p t e r w es e tu p 柚a k l i n eo d ec o m p e t i t i o nm o d e la n dd y n a m i c c o m p e t i t i o nm o d e lo nt i m es c a l ew i t hp a r a m e t e r sa n a l y s i sa n dq u a l i t a t i v ea n a l y s i s w eg o tar e a lc o m p e t i t i o nt r e n dw i t ha c t u a ld a t a w h a t sm o r e ，w ed e s i g nad y n a m i c c o m p e t i t i o nm o d e lo nt i m es c a l el i n k i n gt h ed i s c r e t ea n dc o n t i n u o u ss i t u a t i o n ，w h i c h m e e to d e sd i s a d v a n t a g eo fo n l yc o n t i n u o u ss i t u a t i o n w eg o tt h eb a s i cp r o p e r t yo f t h i sc o m p e t i t i o nm o d e lo nt i m es c a l ea n dr a i s et h em e t h o do f q u a l i t a t i v ea n a l y s i s k e y w o r d s ：a i r l i n er e v e n u em a n a g e m e n t ，v a r i a b l es e p a r a b l es u p p o r tv e c t o rm a c h i n e ， b i - l e v e l p r o g r a m m i n g ，p r i c i n g , m a r k o v d e c i s i o n p r o c e s s ，g e n e t i ca l g o r i t h m , c o m p e t i t i o nm o d e l , t i m es c a l e ，d y n a m i ce q u a t i o n s ，b a y e sa u c t i o n 博士学位论文 i i d_ 第1 章综述 第1 章综述 1 1 航空收益管理的起源及基本概念 通俗地说，收益管理就是“将合适的产品以合适的价格在合适的时候在合适 的时间卖给合适的人”【1 j 。即收益管理的目的是收益最大化，显然，这是一个数 学上的优化问题。 收益管理起源于航空领域，很多学者进行了总结，包括p p b e l o b a b a ( 1 9 8 7 a ) 1 2 】，b c s m i t h , j e l e i m k u h l e r 与r m d a r r o w ( 1 9 9 2 ) p 】，r g c r o s s ( 1 9 9 5 ) 1 4 】， h n d u n l e a v y ( 1 9 9 5 ) 1 5 】，b v i n d o ( 1 9 9 5 ) 1 6 l 等。 1 9 7 2 年前，几乎所有的关于航空公司定座控制的文章都着重在讨论超售。 超售的计算基于航班起飞时正常登机旅客数量概率分布的预测结果，因此超售研 究也刺激了关于旅客取消、持票不登机以及机场购票登机等聚合预测方面的研 究。预测与超售控制方面的理论与实践均获得了一定程度的成功，为座位库存控 制建立了一套具有可信度的研究规则。7 0 年代初期，一些航空公司开始提供有 限制的折扣票价产品以便满足不同的顾客需要，这些折扣票价产品允许折扣票旅 客与高票价旅客乘座在同一个机舱中。例如b o a c ( 现在的英国航空) 提供较低 折扣给较早定座的旅客，这些旅客必须至少于航班起飞前2 1 天提前定座。这样 的改革为航空公司从将要浪费的座位中获得潜在的收益；但这种改革也引申出如 何决定保留多少座位给高票价而晚定座旅客的问题。如果保留太少座位，将导致 高收益旅客没有座位；如果保留太多座位，将导致航班起飞后出现座位空余。这 就要求航空公司制定一些简单的规则( 例如根据距离起飞日期的长短保护一定百 分比的座位) ，将这些规则应用到所有航班上，因为旅客定座行为是随着相关票 价、路线、季节、星期、时间以及其他因素的变化而变化的。 显然，对折扣座位进行有效的控制需要对定座历史记录进行详细跟踪，需要 计算机信息系统的扩展支持，以及对座位库存规则进行详细地研究。英国航空公 司的k u t t u ! w o o d ( 1 9 7 2 ) 1 7 】认为只要当前折扣票价定座的价值超过未来全 价定座的预期价值，就应该接受当前折扣票价定座。这种简单的两种票价的座位 库存控制规则( 称为l i t r l e w o o d 规则) 标志着起初称为收益管理( y i e l d 第1 页博士学位论文 第1 章综述 m a n a g e m e n t ) 后来改称为收入管理( r e v e n u em a n a g e m e n t ) 的理论的 诞生。在北美，美国航空公司于1 9 7 7 年4 月推出的超级省钱计划的启动标志着 收益管理技术的强有力诞生，此后不久，美国对国内、国际航空公司的管制开始 放松。 j i m c g i l l 和g j v a nr y z i n ( 1 9 9 9 ) 8 】对航空收益管理运输领域四十年的历 史研究过程与成果进行了回顾，从预测、超售、座位库存管理、定价等方面进行 了总结并进行了进展预测。 过去的2 0 多年来，收益管理控制理论经历了单航节控制、航段控制到最后 的起点终点控制的历程。这些理论发展的每个阶段都需要对复杂的信息系统进行 投入，这些投入的回报也非常好，如b c s m i t h ，j e l e i m k u h l e r 与 r m d a r r o w ( 1 9 9 2 ) 1 3 】，r g c r o s s ( 1 9 9 5 ) 4 1 。到1 9 9 9 年，大部分世界主要航空公司 和许多小航空公司均拥有了不同程度的收益管理系统。在管制刚开放的其他小航 空公司与国际航空公司也正在发展收益管理。在国内，自2 0 0 0 年开始，南航、 国航、东航及一些小航空公司相继引进了收益管理系统。 航空收益管理成功的案例比比皆是，同时也刺激了其他运输领域及其他服务 行业的收益管理的发展。例如租车、旅馆、旅游、能源、铁路等等行业，甚至连 理发店根据季节以及时段进行价格的调整也可以适用于收益管理。 目前，收益管理的主要研究方面包括预测、超售、库存控制、动态定价、拍 卖( r c a l d e n t e y - 与g v u l c a n o 9 】) 等方面。航空市场竞争日益激烈的情况下，在 互联网迅猛发展的今天，人们的购买方式发生了重大改变，航空公司的经营方式 也从传统线性服务向网络服务转变，传统的预测、优化方法对这种新的购买方式 及复杂的网络管理模式，显得越来越不适应。然而，预测、优化的理论也在不断 地发展、更新，使用新的方法去解决新的问题显得越来越迫切。因此，网络收益 管理成为热门讨论的话题。 1 2 最优化理论发展概况 类似航空收益管理的许多科学及工程领域的数学模型都可以用最优化及最 优控制方法解决，也正是这些模型促使了最优化及最优控制理论的形成。在上个 世纪的后半世纪，最优化及最优控制理论得到了迅速了发展，成为自然科学中最 第2 页博士学位论文 第1 章综述 繁荣的分支之一。最优化及最优控制主要内容包括有关数学基础，函数极值、参 数最优化的基本概念，最优控制中的变分法与极大值原理，等式约束和不等式约 束的处理方法，时间最优控制，动态规划，线性系统二次型性能指标的最优控制 问题等【1 0 , 1 1 】等。最新的研究包括随机规划、神经网络等数据挖掘方面的内容及为 解决求解速度问题的遗传算法等。 1 2 1 随机规划与二层规划 随机规划是对含有随机变量的优化问题建模的有效的工具，并已有一个世纪 的历史。第一种随机规划是广泛使用的期望值模型，即在期望约束条件下，使得 期望收益达到最大或期望损失达到最小的优化方法。第二种是由c h a r n e s 和 c o o p e r 于1 9 5 9 年提出的机会约束规划，是在一定的概率意义下达到最优的理论。 第三种即是刘宝碇教授于1 9 9 7 年提出的相关机会规划，是一种使事件的机会在 随机环境下达到最优的理论。它与期望值模型和机会约束规划一起构成了随机规 划的三个分支。继随机规划之后，刘宝碇教授对模糊规划、粗糙规划、随机模糊 规划等做了深入的研究，从而形成了不确定环境下的统一的优化理论，称之为” 不确定规划州1 2 1 。由于市场经济环境下，各种收益管理研究的指标可以认为是随 机，因此这方面的理论在航空收益管理中得到广泛应用。 双层规划，也称二层规划。常常用来研究二级管理系统的优化决策问题 1 3 , 1 4 , 1 5 】。管理层有两层的决策者，上层决策者和下层决策者。下层决策者听从上 层决策者的决策，并要对上层决策者的决策给予一定的反应。下层决策者可给出 一组最优解，也可能给出一个最优值，这与下层决策者对上层决策反应的唯一性 决定。二层规划也称二层决策系统，其特点是： 1 ) 决策系统有两个决策层，上层决策者具有的权力大，进行的决策具有综 合性。 2 ) 上、下层的决策具有相对独立性，决策者各自控制着自己的决策变量，有 各自的目标利益和约束条件。 3 ) 决策的过程是按照自上而下的顺序进行的，上层决策者先作出决策，并 将一定的信息传达给下层决策者o 下层决策者根据上层决策者的信息，按自己 的利益、偏好进行决策，并将决策的结果反馈给上一决策层。 第3 页 博士学位论文 第1 章综述 4 ) 上层决策者要在众多的决策中做出选择，是总体上最优的决策。 上层决策者控制决策变量y e r “，其目标函数为f ( x ，y ) ；下次决策者控制 决策变- 量x e r “，其目标函数为，o ，y ) 。满足彼此不可分离的约束g ( x ，y ) 。当 上层决策者选定了y 后，下层决策者根据y 的选择确定x 值，以优化f ( x ，y ) ，此 时y 作为给定的常数，于是可以对下层f ( x ，y ) 进行一定的简化。 双层规划模型的数学表达如下： ( 删 m i nf o ，y ) y m a xf ( x ，y ) j s t g ( x ，) ，) s0 使用二层规划与随机规划来解决航空收益管理问题，是比较有意义的。 1 2 2 遗传算法 ( 1 1 ) 遗传算法( g e n e t i ca l g o r i t h m s ) 是6 0 年代人们对于模拟生物以及由此开发的 针对复杂优化问题的有效算法。在最优化理论计算中得到广泛的应用。1 9 5 0 s ， 将进化原理应用于计算机科学的初步努力。5 0 年代末到6 0 年代初，h o l l a n d 应 用模拟遗传算子研究适应性。1 9 6 7 年，b a g l e y 的论文中首次提出了遗传算法这 一术语。1 9 7 5 年，h o l l a n d 的经典著作自然和人工系统中的适应性出版，系 统阐述了遗传算法的基本理论和方法。1 9 7 5 年，d e j o n g 的博士论文遗传自适 应系统的行为分析，将h o l l a n d 的模式理论与他的计算试验结合起来。1 9 8 3 年， h o l l a n d 的学生g o l d b e r g 将遗传算法应用于管道煤气系统的优化，取得了很好的 效果。遗传算法维持由一群个体组成的种群( f 代表遗传代数) 。每一个个体均表 示问题的一个潜在解。每一个个体都被评价优劣并得到其适应值。某些个体要经 历称做遗传操作的随机变换，由此产生新的个体。主要有两种变换方法：变异 ( m u t a t i o n ) 的方法是将一个个体改变从而获得新的个体；杂交( c r o s s o v e r ) 的 方法是将两个个体的有关部分组合成为新的个体。新产生的个体( 称作后代 ( o f f s p r i n g ) ) 继续被评价优劣。从父代种群和子代种群中选择比较优秀的个体 第4 页博士学位论文 第1 章综述 形成新的种群。在若干代以后，算法收敛到一个最优个体，该个体很有可能代表 着问题的最优或次优解。 有关遗传算法( 包括进化规划，进化算法和进化策略) 的著作有很多，例如 j h h o u a n d 1 6 1 ，g o d l b e r g 1 ，z m i c h a e l w i c z 1 引，d b f o g e l l l 9 1 ，j r k o z a 2 0 , 2 1 】， t b a c k 2 2 】和m m i t c h e l l 2 3 】等。在解决全局优化问题方面，遗传算法显示了非常广 泛的应用前景，并已经成功地应用于最优控制、运输问题、旅行商问题、作图、 设备选址、统计、模式识别、车辆调度和网络优化等实际问题中。 在航空公司应用中，h s a l k i n 和k m a t h u r 首次提出了航线机组成员调度问题 【2 4 】，玄光男【2 5 1 等使用遗传算法对该问题进行了讨论，得到了较好的结果。使用 遗传算法解决航空收益管理中的规划问题，是一个值得研究的话题。 1 2 3 支持向量机 基于数据的机器学习是现代人工智能技术的一个重要方面，它的基本方法就 是从观测的样本出发，选定特征数据，从中找出规律，建立数学模型和函数依赖 规律，并能根据已知的数据对未知数据或无法观测的数据进行分类、识别和预测， 构造智能化的学习机器模型，文献【2 6 , 2 7 , 2 8 , 2 9 , 3 0 1 都有描述，但是目前最著名的方法 有以下两种： 第一种是人工神经网络( a n n ) 。它主要利用已知样本建立非线性模型，克服 了传统参数估计方法的困难。常见的神经网络结构有：多层感知器( m l p ) ，径向 基函数网( r b f ) 和h o p f i e l d 网等模型，它们已经成功地用于解决模式识别、信号 处理、智能控制等。 人工神经元网络是目前研究较多的交叉学科。由于通过选择适当的隐单元数 和网络层次，前馈网络能以任意精度逼近非线性函数，因此神经网络技术被广泛 应用到工业过程的建模与控制中，并取得了巨大成功。尽管如此，神经网络仍然 存在如下一些缺陷： ( 1 ) 网络结构需要事先指定或应用启发式算法在训练过程中修正，这些启发 式算法难以保证网络结构的最优化。对于多层网络，系统的组合会非常复杂。网 络权系数的调整方法存在局限性，具体表现在训练可能过早结束而产生权值衰 退。神经网络容易陷入局部最优，有些训练算法甚至无法得到最优解。 第5 页博士学位论文 第1 章综述 。 ( 2 ) 过分依赖学习样本，即模型性能的优劣过分依赖于模型训练过程中样本 数据的数量和质量。大多数情况下，样本数据是有限的。另外，许多实际问题中 的输入空间是高维的，样本数据仅是输入空间中的稀疏分布，即使能得到高质量 的训练数据，数据量也必然很大。大量的样本数据势必会大大增加算法的训练时 间；目前尚无一种理论能定量地分析神经网络的训练过程的收敛速度及收敛速度 的决定条件，并对其加以控制； ( 3 ) 神经网络方法的优化目标是基于经验的风险最小化( e r m ，e m p i r i c a l r i s k m i n i m i z a t i o n ) ，这只能保证学习样本点的估计( 分类) 误差最小。实际上， 该误差应对所有可能的点都达到最小，即泛化性能最好。神经网络方法回避了经 验风险能否收敛于实际风险以及收敛条件等重要问题。尽管存在上述问题，神经 网络在原有框架内仍然取得了很多成功应用，其原因就在于这些应用的设计者， 在设计神经网络过程中，有效利用了自己的经验和先验知识。因此，神经网络系 统的优劣是因人而异的。 第二种就是统计学习理论及支持向量机( s v m ) 。作为机器学习的新兴领域， 统计学习理论是由美国科学家v v a p n i k 等人1 3 1 】最早在六、七十年代开始建立的， 它是一种专门研究小样本情况下机器学习规律的理论。到上世纪九十年代中叶， 随着该理论的日渐完善和神经网络等机器学习理论缺乏实质性的进展，统计学习 理论越来越受到人们的广泛重视。在这一理论基础上，v v a p n i k 提出了支持向量 机理论( s v m ) ，这是一种基于小样本的统计学习理论，比传统的统计学习理论和 神经网络理论有更好的泛化推广能力，在国际上成为人工智能技术研究的又一新 的热点【3 2 1 。支持向量机是近年来机器学习研究的一项重大成果。虽然支持向量 机发展时间很短，但是由于它的产生是基于统计学习理论的，因此具有坚实的理 论基础【3 3 。到目前为止，能比较好地解决小样本条件下机器学习问题的理论就 是统计学习理论，支持向量机理论是它的发展和提高。 支持向量机具有严格的理论和数学基础，与基于神经网络的学习方法相比， 支持向量机具有如下特点： ( 1 ) 基于结构风险最小化( s r m ，s t r u c t u r a lr i s km i n i m i z a t i o n ) 原则，保证 学习机器具有良好的泛化能力；巧妙地解决了算法复杂度与输入向量维数密切相 关的问题；应用核技术，将输入空间中的非线性问题，通过非线性函数映射到高 第6 页博士学位论文 第1 章综述 维特征空间中，在高维空间中构造线性判别函数； ( 2 ) 与传统统计学不同，支持向量机专门针对小样本情况，它的最优解基于 已有样本信息，而不是样本数趋于无穷大时的最优解；算法最终转化为一个凸优 化问题，保证了算法的全局最优性，解决了神经网络无法避免的局部最小问题。 ( 3 ) 神经网络、遗传算法等传统方法的实现中带有的很大的经验成分，而支 持向量机具有更严格的理论和数学基础。 近几年涌现出的大量理论研究成果嘲1 ，更为其应用研究奠定了坚实基础。如 关于硬邻域支持向量机学习误差的严格理论界限、支持向量机的泛化性能及其在 多值分类和回归问题的扩展问题、支持向量机一般意义下的损失函数数学描述； 脊回归应用到正则化网络的学习中。随着支持向量机理论上深入研究，出现了许 多变种支持向量机，如用于分类和回归的v 支持向量机。 从支持向量机的数学推导可以看出，支持向量机的最终求解问题归结为一个 有约束的二次型规划( q p ，q u a d r a t i cp r o g r a m m i n g ) 问题。可以利用标准二次型 优化技术来求解这个优化问题，如牛顿法、共扼梯度法、内点法等。但是，这些 方法只适合小样本情况，当样本数目较大时，算法复杂度会急剧增加，而且占用 极大的系统内存。为降低计算资源、提高算法效率，许多研究者提出许多针对大 样本集的训练算法： ( 1 ) 选块算法【3 4 】 选块算法出发点是：删除矩阵中对应于l a g r a n g e 乘数为零的行和列不会对 最终结果产生影响。对于给定的训练样本集，如果其中的支持向量是已知的，寻优 算法就可以排除非支持向量，只需对支持向量计算权值( t i p l a g r a n g e 乘数) 即 可。但是，在训练过程结束以前支持向量是未知的，因此，块算法的目标就是通过 某种迭代方式逐步排除非支持向量。 这种方法可以大大减小算法占用的系统内存。然而，当样本集中的支持向量 数目很大时，其算法复杂度仍然很大。 ( 2 ) 子集选择算法 为加快支持向量机的训练速度，o s u n a ( 1 9 9 7 ) 提出了子集选择算法。该方 法首先将数据集分块( c h u n k i n g ) ，从分块数据中提取支持向量，并加以保留， 然后补充新的样本，反复运算，直至所有的样本都满足k k t ( k a r u s h - k u l m t u c k e r ) 第7 页博士学位论文 第1 章综述 ( v v a p n i k ，1 9 9 5 ) 收敛条件。为采用启发式迭代策略会提高算法的收敛速度， 有学者提出一种称为s v m l i g h t 【3 5 】的支持向量机分解学习算法。该算法实际上是 子集选择算法的推广。 ( 3 ) 序列最小优化算法 微软研究院的j c p l a t t 等人提出并且改进了s m o 算法。这种算法将工作样 本集的规模减到了最小一两个样本，之所以需要两个样本是因为等式线性约束的 存在使得同时至少有两个l a g r a n g e 乘数发生变化。由于子问题的优化只涉及两 个变量，而且应用等式约束可以将其中一个变量用另一个变量线性表示出来，所 以迭代过程中每一步的子问题的最优解可以直接用解析的方法求出来，无需使用 数值分析中的二次规划软件包，提高了子问题的运算速度；此外，j c p l a t t 还设 计了一个两层嵌套循环分别选择进入工作样本集的两个样本，外层循环选择第一 个样本，内层循环选择第二个样本。外层循环首先在整个样本空间循环一遍，决 定哪些样本违反了k o h n t u c k e r 条件。如果找到了不满足k o l m t u c k e r 条件的 样本，它即被选作进入工作集的第一个样本。然后根据第二个启发式规则选择第 二个样本。最后用解析的方法快速对选定的样本进行优化。为了加快算法的运行 速度，外层循环不总是每次检查所有训练样本。内层循环选择第二个进入工作集 的样本，选择的原则是使目标函数靠近最优点的速度达到最快。这种启发式的样 本选择策略大大加快了算法的收敛速度。标准样本集的实验结果证明，s m o 表 现出在速度方面的良好性能。 ( 4 ) 此外，还有其他训练算法如增量式算法等。 1 3 时标理论与竞争模型 1 3 1 微分方程与差分方程 常微分方程( 简称o d e ) 的起源可追溯到牛顿( j n e w t o n ) 和莱布尼兹 ( g l e i n i z ) 在1 6 6 1 年前后创立微积分的时期。十九世纪末，h p o i n c a r e 发表的奠 基性工作“微分方程所定义的积分曲线可以说是微分方程定性理论研究的发端， 一百多年来得到了蓬勃的发展，今天定性的思想和技巧已逐渐渗透到其它数学分 支，例如差分方程，偏微分方程等，其中二维常系数平面系统的定性结构已经研 第8 页博士学位论文 第1 章综述 究得比较完整，在一般常微分方程的著作( 如：王高雄等，张芷芬等，张锦炎等 中均有详细的讨论。但是由于差分方程具有递归迭代的可计算性，任何有限步都 可以直接计算实现，早期的工作主要集中在计算，数值计算误差分析以及保证计 算的精度符合实际的要求等等方面，很少有人系统地去研究差分方程解序列的各 种属性，这很难适应电脑时代科学技术迅速发展的要求，得到了奇点分类，奇点 附近解的定性结构以及解析判别法，该文充分说明了d d e 和o d e 之间的差异。 王联等以及w g k e l l y 和a c p e t e r s o 都讨论了系数矩阵的谱半径小于1 时常系数 线性差分方程的定性行为和稳定性行为。 稳定性问题是人们研究各类动态系统( 工业系统、生物系统、社会经济系统 等) 所面临的最基本最重要的问题之一。稳定性理论已经积累了十分丰富的成果， 特别是1 8 9 2 年李雅普诺夫( l y a p u n o v ) 的著名博士论文“运动稳定性的一般问题 作出了奠基性的工作，越来越吸引着全世界相关学者的广泛关注，在当代科学技 术日新月异变化下，o d e 中的l y a p u n o v 稳定性理论业已推广到了有d d e 描述 的离散动力系统的稳定性，1 9 5 8 年，w h a h n 首次研究l y a p u n o v 函数在差分方 程中的应用问题，第一次将v 函数方法应用到差分方程零解的稳定性研究中， 给出了差分方程零解的各种稳定性定义和判定定理。1 9 6 0 年r e k a l m a n 及 j e b e f t r a n 略有系统地论及d d e 的稳定性问题，但没有严格论证文中的结论。 a h a l a n a y 讨论了微小经常扰动差分方程零解的稳定性问题。1 9 7 1 年，s e g o r d o n 提出并研究了差分方程的l p 稳定性问题。g a s h a n h o l t 推广了d d e 零解稳定性 的概念，提出了d d e 集合稳定性，用l y a p u n o v 函数对集合稳定性进行了研究。 1 9 7 6 年，j e l a s a l l e 在书中建立了差分方程的极限集及不变集理论，并用l y a p u n o v 函数对差分方程的稳定性和不稳定性进行了讨论，推广了以前的部分结果。1 9 8 5 年开始有学者研究d d e 关于部分变元的稳定性，目前关于o d e 和d d e 部分变 元稳定性方面的论文非常的分散，还没有看到这方面的专著。 差分方程在振动理论，周期解和概周期解，分支理论等研究方向上也取得了 许多与o d e 类似的结果，长久以来，对差分方程的研究不仅在内容上而且在研 究方法上都与对微分方程的研究存