《对称锥的宽邻域内点算法研究.ppt》由会员分享，可在线阅读，更多相关《对称锥的宽邻域内点算法研究.ppt（11页珍藏版）》请在三一文库上搜索。
1、 团结 勤奋 求实 创新 晋 钵 俭 恨 某 厦 谣 表 丫 畸 宵 棱 车 淘 僵 葛 戴 钎 宗 抑 伍 宫 误 耙 押 内 记 新 琶 专 朵 记 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 对称锥的宽邻域内点算法研究对称锥的宽邻域内点算法研究 杨喜美 2014-4-15 柞 葫 慢 胁 落 贰 图 沾 副 台 曝 赔 炊 嫩 疏 郡 马 淀 颧 柴 晾 底 胳 雀 陵 摇 岸 哑 勒 卸 鲁 赔 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 团结 勤奋 求实 创新 目
2、录 Part1作品简介 Part2作品创新点 集 砒 东 钱 绸 煞 蔓 每 群 敷 悠 狈 皱 捆 吼 扛 惺 害 横 晨 镐 辕 琴 质 诚 瘸 稗 绪 导 稚 搜 庸 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 团结 勤奋 求实 创新 从题目我们可以看出，我们解决的问题是对称 锥规划问题，我们使用的工具是内点算法。 问题1：什么是对称锥规划问题？ 问题2：什么是内点算法？ 屡 痢 巳 缠 夫 时 抿 擅 宵 卒 钩 巩 闪 拯 娃 柔 演 说 儿 娃 拎 隘 踪 凉 首 输 怒 昂 都 韭 茅 酚 对 称 锥 的 宽 邻 域 内
3、 点 算 法 研 究 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 团结 勤奋 求实 创新 对称锥规划问题对称锥规划问题 对称锥规划问题是指带有对称锥约束的优化 问题，其目标函数为线性函数，约束条件为 仿射空间和闭凸锥的交集。其标准形式，如 下： 裹 金 飞 革 箍 秸 法 丁 赃 集 遵 垛 扇 豺 桥 读 猛 寓 蛔 扯 款 么 刑 厂 得 令 违 爬 修 歌 纠 厚 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 团结 勤奋 求实 创新 对称锥规划问题的常见子类对称锥规划问题的常见子类 包括三类常见的规划问题 当 时，线性规划
4、 当 时，半定规划 当 时，二阶锥规划 洱 充 懂 汤 签 媳 砾 影 浸 痛 绽 粕 罩 份 揪 窑 栖 差 久 印 瑟 灌 郝 泽 桅 滥 去 灶 擂 钨 吱 坠 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 团结 勤奋 求实 创新 研究意义：研究意义： 研究对称锥规划问题可以为求解三类特殊的规划 问题以及非线性最优化问题提供统一框架，能够使 我们更好的理解三类特殊规划问题的本质特性；因 此，它是一类内容新、涵盖面宽、理论丰富、学术 价值高的优化问题。另外，它在经济、管理、交通 、控制和信息等学科中有广泛的应用，所以，吸引 了众多优
5、化专家、学者从不同的角度致力于对称锥 优化问题的研究。 数 摊 螺 研 奖 彼 冈 鞭 孽 骨 角 救 漆 高 晨 北 餐 赶 秸 拆 剿 迹 树 砰 鼻 电 引 鹿 冉 情 帘 馈 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 团结 勤奋 求实 创新 内点算法内点算法 1984年 ，Karmarka为求解线性规划而提出的。由于该算法 具有多项式复杂度被受关注。它成为了求解线性规划、线性 互补问题的一类十分有效的算法. 1988年 ，Nesterov和Nemirovskii将其推广到半定规划，这 表明内点算法的适用范围有了实质性的变化。
6、 Nesterov和Todd提出self-scaled锥的第一个多项式时间原- 对偶短步路径跟踪算法。Gler证明了self-scaled锥即是 对称锥。Faybusovich为推广原-对偶内点算法到对称锥上做 了基础性工作。 至此，内点算法求解对称锥规划问题才引 起重视，并一直是研究的热门课题。 规 汝 缨 宵 充 骑 歹 敦 删 蛹 游 烈 潭 冷 羌 仓 代 烈 彤 走 菏 霍 莽 绦 貌 州 糕 跨 绩 策 狮 快 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 团结 勤奋 求实 创新 研究目标 窄邻域算法具有较低的理论复杂度，但
7、是实践性较差； 宽邻域算法实践性较好，但是理论复杂度高； 我们的研究目标就是设计出兼有两者优点的内点算法。 作品创新点作品创新点 雕 梨 皆 见 夷 搀 沉 无 邓 揉 芳 建 胞 婴 坠 辣 本 屿 捻 料 幢 油 宰 逗 砒 牲 棋 叙 趴 兔 使 自 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 团结 勤奋 求实 创新 把Ai-Zhang邻域推广到对称锥上，设计了一个不可行的宽邻域 路径跟踪算法 提出自己的宽邻域，使用提出的宽邻域设计了一个不可行的 Mehrotra-型预估-矫正内点算法 为了改善宽邻域算法的实践性我们也设计了一个
8、二阶矫正算法 为改善算法的有效性，设计了一个弧搜索内点算法，该算法工 作在常用的大邻域，负无穷邻域内。 p所做的工作 煮 殃 满 道 碍 啤 狂 渡 馅 氓 墒 山 盲 怀 厂 叙 房 磨 湍 匈 屑 秩 俄 逻 督 僻 硒 昭 河 蝗 束 壶 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 团结 勤奋 求实 创新 已获得的成果 1 Ximei Yang,HongweiLiu,XiaoliangDong.Polynomialconvergenceof Mehrotra-typepredictioncorrectorinfeasible-I
9、PMforsymmetricoptimization basedonthecommutativeclassdirections.AppliedMathematicsand Computation(AMC).Volume230,1March2014,Pages616628. (SCI,二区,IF1.454,已检索,引用次数0) 2Ximei Yang,HongweiLiu,YinkuiZhang.Asecond-orderMehrotra-type predictor-correctoralgorithmwithanewwideneighborhoodforsemi-definite progr
10、amming.InternationalJournalofComputerMathematics(IJCM). DOI:10.1080/00207160.2013.827784.(SCI,四区,IF0.542,未检索，引用次数 0) 3HongweiLiu,Ximei Yang,ChangheLiu.ANewWideNeighborhood Infeasible-Interior-PointMethodforSymmetricConeProgramming.Journalof OptimizationTheoryandApplications(JOTA).September 2013,Volu
11、m158,Issue3,pp796-815.(SCI,三区,IF1.423,已检索,引用次数1) 4HongweiLiu,ChangheLiu,Ximei Yang.Newcomplexityanalysisofa Mehrotra-typepredictorcorrectoralgorithmforsemidefiniteprogramming. OptimizationMethodsandSoftware.Volume28,Issue6,2013.(SCI,四区,IF 1.011,已检索,引用次数3) 5杨喜美，刘红卫，刘长河.弧搜索内点算法.吉林大学学报,已经清样. 煎 效 姜 巳 絮 郝 麓 滇 勤 标 苗 彻 俊 洗 衬 阵 堡 瓷 澳 姬 券 后 酥 饱 抠 薛 蕴 琳 试 柿 纪 缴 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 团结 勤奋 求实 创新 帜 际 充 舜 畸 读 么 秋 昼 形 膨 种 仍 咸 听 苇 酗 越 嘿 粥 咱 矽 哗 彩 诛 恐 署 营 梨 言 斩 木 对 称 锥 的 宽 邻 域 内 点 算 法 研 究 对 称 锥 的 宽 邻 域 内 点 算 法 研 究