对称锥互补问题的内点算法及在传感器网络定位中的应用研究.pdf

申请代码 A011201 受理部门 收件日期 受理编号 国家自然科学基金国家自然科学基金 申申 请请 书书 (2 0 1 0(2 0 1 0版版)资助类别：青年科学基金项目 亚类说明：附注说明：项目名称：对称锥互补问题的内点算法及在传感器网络定位中的应用研究 申 请 人：王国强 电话：654210201504 依托单位：上海工程技术大学 通讯地址：上海市松江区龙腾路 333 号 邮政编码：201600 单位电话：021-67791237 电子邮箱：guoq_ 申报日期：2010年3月16日 国家自然科学基金委员会 国家自然科学基金申请书 2010 版 第 2 页 版本 1.006.271 基本信息基本信息 xo/Y+HZF 申申 请请 人人 信信 息息 姓名 王国强 性别 男 出生 年月 1977 年 8 月 民 族 汉族 学位 博士 职称 讲师 每年工作时间（月）10 电话 654210201504 电子邮箱 guoq_ 传真 国别或地区 中国 个 人 通 讯 地 址 上海市松江区龙腾路 333 号 工作单位 上海工程技术大学 主 要 研 究 领 域 锥优化及锥互补问题的内点算法及应用研究 依托单位信息依托单位信息 名称 上海工程技术大学 联系人 刘月波 电子邮箱 电话 021-67791237 网站地址 合作研究单位信息合作研究单位信息 单 位 名 称 项项 目目 基基 本本 信信 息息 项目名称 对称锥互补问题的内点算法及在传感器网络定位中的应用研究 资助类别 青年科学基金项目 亚 类 说 明 附注说明 申请代码 A011201:线性与非线性规划 基地类别 研究年限 2011 年 1 月 2013 年 12 月 研究属性 应用基础研究 申请经费 16.0000 万元 摘摘 要要 (限限 400400 字字)：对称锥互补问题是对称锥规划的推广，它是一类重要的均衡优化问题，广泛应用于通信、工程、经济管理等领域，内点算法是求解该问题的有效算法之一.核函数在内点算法的设计和分析中起着重要的作用，它不仅可以定义新的搜索方向，而且可以度量当前迭代点与中心路径的距离.本项目将研究新的核函数的构造技术及其基本性质，借助欧几里德若当代数技术，基于新的核函数设计和分析求解对称锥非线性互补问题的内点算法，有效缩减大步校正和小步校正内点算法在理论与实践之间的间隙；基于核函数的局部 SC 性质，揭示核函数在内点算法的复杂性中的性态；设计和分析求解对称锥线性互补问题的全 NT 步不可行内点算法；应用对称锥规划或对称锥互补问题松弛方法研究传感器网络定位问题，建模、编写内点算法程序求解.该项目旨在设计和分析求解对称锥非线性互补问题的有效内点算法，为研究线性互补问题、半正定互补问题及二阶锥互补问题提供统一的框架.关关 键键 词词(用分号分开，最多 5 个)对称锥互补问题；对称锥规划；内点算法；核函数；传感器网络定位.国家自然科学基金申请书 2010 版 第 3 页 版本 1.006.271 项目组主要项目组主要参与者参与者（注:项目组主要参与者不包括项目申请人，国家杰出青年科学基金项目不填写此栏。）编号 姓 名 出生年月 性别 职 称 学 位 单位名称 电话 电子邮箱 项目分工 每年工作时间（月）1 岳玉静 1980-10-30 女 讲师 硕士 上海工程技术大学 65421020 算法设计和分析 8 2 蔡新中 1971-9-17 男 讲师 硕士 上海工程技术大学 65421020 算法设计和分析 8 3 何冰洁 1981-11-15 女 讲师 硕士 上海工程技术大学 65421020 he- 算法设计和分析 6 4 王保存 1965-9-5 男 讲师 硕士 上海工程技术大学 67791190 建模及数值算例 6 5 樊庆端 1976-7-22 男 讲师 硕士 上海工程技术大学 67791190 编程及数值算例 6 6 7 8 9 总人数 高级 中级 初级 博士后 博士生 硕士生 6 0 6 0 0 0 0 说明:高级、中级、初级、博士后、博士生、硕士生人员数由申请人负责填报（含申请人），总人数由各分项自动加和产生。国家自然科学基金申请书 2010 版 第 4 页 版本 1.006.271 经费申请表经费申请表 （金额单位：万元）科目 申请经费 备注（计算依据与说明）一一.研究经费研究经费 12.8000 1.科研业务费 9.8000 （1）测试/计算/分析费 2.0000 购买数学软件、数学模型测试等：约 2 万（2）能源/动力费 0.0000 （3）会议费/差旅费 3.2000 国内会议 4 次：0.3 万/次；国际会议 4 次：0.5 万/次，合计 3.2 万（4）出版物/文献/信息传播费 2.8000 资料费：0.4 万/年，3 年计 1.2 万；版面费：0.2万元/篇，8 篇计 1.6 万（5）其他 1.8000 上网费，订购学术刊物，邮费及通讯费等：0.6 万/年，3 年计 1.8 万 2.实验材料费 0.0000 （1）原材料/试剂/药品购置费 0.0000 （2）其他 0.0000 3.仪器设备费 3.0000 （1）购置 3.0000 购买打印机、移动硬盘等电脑耗材及办公用品，每年约 1 万，3 年合计 3 万（2）试制 0.0000 4.实验室改装费 0.0000 5.协作费 0.0000 二二.国际合作与交流费国际合作与交流费 2.4000 1.项目组成员出国合作交流 0.0000 2.境外专家来华合作交流 2.4000 邀请国外专家来华短期交流 2 次：1.2 万/次，合计2.4 万 三三.劳务费劳务费 0.0000 四四.管理费管理费 0.8000 按学校规定收取 5%的管理费，合计 0.8 万 合合 计计 16.0000 与本项目相关的 其他经费来源 国家其他计划资助经费 0.0000 其他经费资助（含部门匹配）16.0000 其他经费来源合计其他经费来源合计 16.0000 国家自然科学基金申请书 2010 版 第 5 页 报告正文报告正文（一）（一）立项依据与研究内容立项依据与研究内容 1.1 项目的立项依据项目的立项依据 对称锥互补问题是对称锥规划的推广，它一类重要的均衡优化问题，包括线性互补问题、半正定互补问题及二阶锥互补问题，广泛应用于通信、工程、经济管理等领域，与变分不等式、组合规划、鲁棒规划、均衡理论等有着密切的联系.内点算法是求解该问题的有效算法之一，对该问题的研究可为一般的非线性规划提供统一的框架.近期，借助欧几里德若当代数技术，对称锥互补问题的内点算法的研究得到突破性进展.时至今日，对称锥互补问题的内点算法的研究已成为国际优化领域的热点问题.无线传感器网络定位问题在灾后搜索、目标跟踪、环境监测以及现场监控等中具有重要的应用，实质上它是欧几里德距离矩阵完全问题和图实现问题的变形.近年来，该问题的研究得到较快发展，但对于大规模传感器网络节点定位仍缺乏行之有效的方法，因而研究该问题具有重要的现实意义.本项目主要研究基于核函数设计和分析求解对称锥非线性互补问题的有效内点算法，并应用对称锥规划或对称锥互补问题松弛方法研究传感器网络定位问题，该项目的研究不仅具有重要的理论意义，而且具有丰富的应用价值.近年来，借助欧几里德若当代数技术，对称锥规划和对称锥互补问题的内点算法的研究得到较大进展.线性规划和(非)线性互补问题的内点算法 自从 1984 年卡玛卡尔提出第一个具有多项式时间复杂性和实用性的内点算法以来.由于其对大规模规划问题求解的有效性，激起优化界对内点算法的研究.2002 年，Peng 等26引入self-regular(SR)核函数的概念，并基于 SR 核函数设计和分析了求解线性规划的原始-对偶内点算法，得到迄今为止大步校正和小步校正内点算法最好的理论迭代界，有效缩减了二者在理论与实践之间的间隙.随后，白延琴等5基于 Eligible 核函数（相比 SR 核函数的条件要弱）设计和分析了求解线性规划的原始-对偶内点算法，得到与文26相同的迭代界.互补问题与变分不等式有密切联系，何炳生等在变分不等式领域取得一些深刻的结果13.线性规划和凸二次规划的 KKT 系统等价于线性互补问题，线性互补问题是线性规划和凸二次规划的推广.艾文宝等1研究了求解单调线性互补问题的宽领域大步校正原始对偶内点算法，得到迄今为止最好的理论迭代界.Peng 等26中将基于 SR 核函数的线性规划的内点算法推广到非线性)(*P互补问题，并得到迄今为止最好的理论迭代界.赵云彬等42设计和分析了求解非线性)(*P互补问题的路径-跟踪内点算法.Tseng36 国家自然科学基金申请书 2010 版 第 6 页 研究了单调非线性互补问题的不可行路径-跟踪内点算法.其它求解互补问题的方法还有光滑牛顿法等，如：马昌风等22研究了求解 P0-NCP 的一步光滑牛顿法的收敛性.半正定规划和半正定互补问题的内点算法 半正定规划广泛应用于组合优化2、传感器网络定位33等，内点算法是求解该问题的有效算法之一.Nesterov 和 Todd24首次设计和分析了基于 self-scaled 锥的线性规划的内点算法，特别地，推广到半正定规划.Peng 等26基于 SR 核函数设计和分析了求解半正定规划的原始-对偶内点算法，并得到迄今为止基于大步校正和小步校正内点算法最好的理论迭代界.Toh35研究了求解凸二次半正定规划的非精确路径-跟踪内点算法，并给出了求解大规模算例的数值结果.半正定规划的 KKT 系统等价于半正定互补问题，即半正定互补问题是半正定规划的推广.理论上来说，求解半正定规划问题的内点算法均可求解半正定互补问题.Kojima 等16首次提出半正定线性互补问题并给出求解半正定单调线性互补问题的内点算法.Shida 等31研究了求解半正定线性互补问题的内点算法的搜索方向的存在性及唯一性，并设计了基于AHO搜索方向的预测-校正内点算法.Sim等32引入偏离路径的概念并研究了半正定单调线性互补问题的内点算法.孙文瑜等将文38中求解非线性规划的原始-对偶内点滤子算法推广到非线性半正定规划，并证明其全局收敛性.目前，对于半正定线性互补问题的内点算法的研究较多，对于半正定非线性互补问题的内点算法的研究较少.其它关于非线性半正定规划的结果：黄学祥等13研究了非线性半正定规划的低阶罚方法.Sun 等34研究了非线性半正定规划的增广拉格朗日方法.二阶锥规划和二阶锥互补问题的内点算法 二阶锥规划广泛应用于投资组合3、传感器网络定位37等，内点算法是求解该问题的有效算法之一.Nesterov 和 Todd24两人做了奠基性的工作.Peng 等26基于 SR 核函数设计和分析了求解二阶锥规划的原始-对偶内点算法，并得到迄今为止基于大步校正和小步校正内点算法最好的理论迭代界.Alizadeh 等3介绍了二阶锥规划的内点算法及其应用.Yamashita 等40设计和分析了求解非线性二阶锥规划的原始-对偶内点算法.潘少华等25研究了凸二阶锥规划的内近端类算法.目前，求解二阶锥规划及二阶锥互补问题的算法主要还是各种光滑化方法，如：刘三阳等7介绍了求解二阶锥规划的光滑牛顿法.Hayashi 等11研究了求解二阶锥单调线性互补问题的光滑法和正则化法的组合方法.Kanzow 等15证明了线性和非线性二阶锥规划的半牛顿光滑法的局部收敛性.对于二阶锥非线性互补问题的内点算法的研究还比较少.对称锥规划和对称锥互补问题的内点算法 对称锥规划包含线性规划、半正定规划及二阶锥规划等.2006 年国际数学家大会上，国际著名的优化专家 Nemirovski 被邀请做题目为“Advances in convex optimization:conic programming”国家自然科学基金申请书 2010 版 第 7 页 一小时大会报告，更加推进了锥规划的研究.国内，清华大学方述诚教授、北京交通大学修乃华教授等邀请国际优化领域专家举办了锥规划研究进展及其应用的研讨班，为推动我国优化界在锥规划领域的研究起到重要的推动作用.近期，借助欧几里德若当代数技术，Faybusovich8基于凸对数障碍函数将 Nesterov 和 Todd 设计的 self-scaled 锥规划的内点算法推广到对称锥规划，这一开拓性工作为对称锥规划的内点算法的研究奠定了坚实的基础.Muramastu23基于对称锥线性规划的KKT 系统分析了可交换的搜索方向类，并分别给出基于短步长、半长步长及长步长内点算法的复杂性.Schmieta 等29借助欧几里德若当代数技术，将基于三种尺度化技术得到可交换的搜索方向的求解半正定规划的原始-对偶内点算法推广到对称锥规划，并给出算法的复杂性分析.袁亚湘等39研究了求解带线性约束与对称锥约束的非凸二次规划的信赖域内点算法.Schurr30设计和分析了锥规划的带有非精确罚的多项式时间内点算法.对称锥互补问题是对称锥规划的推广.Yoshise41在 Andersen4的工作基础上给出了求解单调对称锥非线性互补问题的一个齐次模型，该模型的内点轨道是中心路径的推广，基于短步长、半长步长及长步长分别设计和分析了求解单调对称锥非线性互补问题的内点算法.Gowda 等10研究了对称锥线性互补问题的全局唯一性和可解性.近期，国内在对称锥互补问题的研究上也取得较大进展.修乃华等20首次设计和分析了求解对称锥*()P线性互补问题的路径-跟踪内点算法.随后，他们在文21中基于 CHKS 光滑化技术设计和分析了求解对称锥单调线性互补问题的不可行内点算法.张立卫等18介绍了非线性对称锥规划的增广拉格朗日方法.黄正海、韩继业等14研究了求解对称锥互补问题的具有非单调线搜索的光滑化算法的收敛性.修乃华等17研究了求解对称锥互补问题的正则光滑化牛顿法.综上，不难看出国内外关于综上，不难看出国内外关于对称锥对称锥线性互补问题的内点算法的研究较多，对于对称锥非线性互线性互补问题的内点算法的研究较多，对于对称锥非线性互补问题的补问题的内点算法的内点算法的研究还比较少研究还比较少.然而现实生活中，非线性的情形比比皆是然而现实生活中，非线性的情形比比皆是.因而，研究因而，研究对称锥对称锥非线性互补问题的内点算法显得非线性互补问题的内点算法显得尤其尤其重要重要.申请者于 2002 年开始在导师白延琴教授的指导下着手研究对称锥规划的内点算法及其应用，在线性规划、半正定规划、二阶锥规划及对称锥规划的内点算法及应用方面取得一定的成果.近期，一直关注对称锥互补问题的内点算法的国内外研究进展，在对称锥线性互补问题的内点算法的设计和分析中也取得一些结果，这为本项目的开展奠定了坚实的工作基础.从计算的角度来看，路径-跟踪内点算法较其它内点算法更为有效，它包括大步校正和小步校正内点算法，二者在理论与实践之间存在间隙.如何缩减二者之间的间隙，具有重要的理论意义.最近，Peng等26基于SR核函数设计和分析了求解线性规划、半正定规划及二阶锥规划的原始-对偶内点算法，并得到迄今为止基于大步校正和小步校正内点算法最好的理论迭代界，有效缩减了二者之 国家自然科学基金申请书 2010 版 第 8 页 间的间隙.随后，白延琴等5基于Eligible核函数（相比SR核函数条件要弱）设计和分析了求解线性规划的原始-对偶内点算法，应用新的分析方法得到文26中相同的迭代界.核函数在内点算法的核函数在内点算法的设计和分析中起着重要的作用，一般而言，只要给出一个核函数就可以设计一个新的内点算法设计和分析中起着重要的作用，一般而言，只要给出一个核函数就可以设计一个新的内点算法.它它不仅可以定义新的搜索方向，而且可以度量当前迭代点与中心路径的距离不仅可以定义新的搜索方向，而且可以度量当前迭代点与中心路径的距离.因而本项目拟研究新的核函数的构造技术，基于新的核函数设计和分析求解对称锥非线性互补问题的内点算法，有效缩减大步校正和小步校正内点算法在理论与实践之间的间隙.Dayzay7介绍了一种新的方法来定义搜索方向，如果选取合适的函数，可得到与文5,26相同的搜索方向.Dayzay在文7中基于一类新的搜索方向，设计和分析了求解线性规划的全牛顿步原始-对偶内点算法，得到迄今为止基于小步校正内点算法最好的理论迭代界.Roos28研究了求解线性规划的全牛顿步不可行原始-对偶内点算法，每步迭代中主要包括一个可行步和有限次中心步，得到不可行原始-对偶内点算法迄今为止最好的理论迭代界.DayzayDayzay介绍的新的定义搜索方向的方法与介绍的新的定义搜索方向的方法与基于核函数设计的内点算法得到的搜索方向具有同等的作用基于核函数设计的内点算法得到的搜索方向具有同等的作用.选取合适的函数选取合适的函数，可为得到新的搜索，可为得到新的搜索方向提供可能方向提供可能.同时，基于函数本身的性质也可得到新的分析结果同时，基于函数本身的性质也可得到新的分析结果.因而本项目拟在Dayzay和Roos工作的基础上，设计和分析求解对称锥规划和对称锥线性互补问题的全NT步不可行内点算法.Ye等33 首次研究了无线传感器网络定位问题的半正定规划松驰方法.Tseng37 研究了无线传感器网络定位问题的二阶锥规划松弛方法，并得到一些非常漂亮的理论结果，数值模拟显示其优于半正定规划松弛方法.由于半定规划松驰由于半定规划松驰方法和二阶锥规划松弛方法方法和二阶锥规划松弛方法是无线传感器网络定位是无线传感器网络定位问题问题的近似算法，因而该松驰解的近似算法，因而该松驰解有有可能不是最优解，甚至不是可行解可能不是最优解，甚至不是可行解.如何进一步优化模型如何进一步优化模型，并并使使其松其松弛解弛解更加接更加接近近于最优解于最优解是一个值得研究的问题是一个值得研究的问题.因而本项目拟研究应用对称锥规划或对称锥互补问题松弛方法求解传感器网络定位问题，并结合.本项目拟以对称锥非线性互补问题的内点算法及在传感器网络定位中的应用为研究内容，通过理论分析和数值试验来证明算法的复杂性及其有效性.与与YoshiseYoshise 4141中基于对称锥互补问题的中基于对称锥互补问题的齐齐次模型设计内点算法不同的是本项目基于核函数设计和分析求解对称锥非线性互补问题的内点算法次模型设计内点算法不同的是本项目基于核函数设计和分析求解对称锥非线性互补问题的内点算法.本项目主要围绕如下关键科学问题进行深入和系统研究：1)进一步探索构造新的核函数的方法和技术，揭示核函数在内点算法的设计和分析中的作用；深入研究欧几里德若当代数的性质，为算法分析提供关键技术.2)考虑如何将对称锥线性互补问题的内点算法的中心路径推广到对称锥非线性互补问题，并研究其存在性及极限唯一性等性质.3)基于核函数设计和分析求解对称锥非线性互补问题的内点算法，有效减少大步校正内点算法的理论迭代界，进一步缩减大步校正和小步校正内点算法在理论与实践之间的间隙.4)在Dayzay和Roos的工作基础上，基于新的搜索方向设计和分析求解对称锥规划和对称锥线性互补问题的全NT步不可行内点算法.5)应用对称锥规划或对称锥互补问题 国家自然科学基金申请书 2010 版 第 9 页 松弛方法研究传感器网络定位问题，建模、编制内点算法程序求得松驰解，以此松驰解为节点的初始位置，并进一步改善这些解，得到节点的位置估计，并验证模型的可靠性和算法的有效性.尽管对称锥线性互补问题和对称锥非线性互补问题有着诸多的共同之处，但后者的非线性将给我们的研究带来重大的技术难点和挑战.例如：对称锥线性互补问题的内点算法的中心路径的存在性及极限的唯一性等性质能否推广到对称锥非线性互补问题？倘若不能，如何调整和改变？对称锥非线性互补问题的 KKT 系统的求解也远比对称锥线性互补问题的 KKT 系统的求解困难的多.近期，申请者及团队成员基于核函数设计和分析了求解线性互补问题、半正定线性互补问题、二阶锥线性互补问题及对称锥线性互补问题的内点算法（详见申请者简介）,这为本项目研究对称锥非线性互补问题的内点算法奠定了坚实的工作基础.本项目的成功实施将有效缩减大步校正和小步校正内点算法之间的理论间隙，为求解对称锥非线性互补问题提供有效内点算法.同时，也可为传感器网络定位技术在灾后搜索、目标跟踪、环境监测以及现场监控等中的应用提供智力支持.主要参考文献：主要参考文献：1 W.B.Ai and S.Z.Zhang,An O(nL)iteration primal-dual path-following method based on wide neighborhoods and large updates,for monotone linear complementarity problems,SIAM Journal on Optimization,16(2):400-417,2005.2 F.Alizadeh,Interior-point methods in semidefinite programming with applications to combinatorial optimization,SIAM Journal on Optimization,5:13-51,1995.3 F.Alizadeh and D.Goldfarb,Second-order cone programming,Mathematical Programming,95:3-51,2003.4 E.D.Andersen,C.Roos and T.Terlaky,On implementing a primal-dual interior-point method for conic quadratic optimization,Mathematical Programming,95:249277,2003.5 Y.Q.Bai,M.EL.Ghami and C.Roos,A comparative study of kernelr functions for primal-dual interior-point algorithms in linear optimization,SIAM Journal on Optimization,15:101-128,2004.6 X.N.Chi and S.Y.Liu,A one-step smoothing Newton method for second-order cone programming,Journal of Computational and Applied Mathematics,223:114-123,2009.7 Z.Darzay,New interior-point algorithms in linear optimization,Advanced Modelling and Optimization,5(1):51-92,2003.8 L.Faybusovich,Euclidean Jordan algebras and interior-point algorithms,Journal of Computational and Applied Mathematics,86:147-175,1997.国家自然科学基金申请书 2010 版 第 10 页 9 L.Faybusovich,A Jordan-algebraic approach to potential-reduction algorithms,Mathematische Zeitschrift,239:117-129,2002.10 M.S.Gowda and R.Sznajder,Some global uniqueness and solvability results for linear complementarity problems over symmetric cones,SIAM Journal on Optimization,18(2):461-481,2007.11 S.Hayashi,N.Yamashita and M.Fukuahima,A combined smoothing and regularization method for monotone second-order cone complementarity problems,SIAM Journal on Optimization,15:593-615,2005.12 B.S.He,L.Z.Liao,D.R.Han and H.Yang,A new inexact alternating directions method for monotone variational inequalities,Mathematical Programming,92:103-118,2002.13 X.X.Huang,X.Q.Yang and K.L.Teo,Lower-order penalization approach to nonlinear semidefinite programming,Journal of Optimization Theory and Applications,132(1):1-20,2007.14 Z.H.Huang,S.L.Hu and J.Y.Han,Convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search,Science in China Series A:Mathematics,52(4):833-848,2009.15 C.Kanzow,I.Ferenczi and M.Fukushima,On the local convergence of semismooth Newton methods for linear and nonlinear second-order cone programs without strict complementarity,SIAM Journal on Optimization,20:297-320,2009.16 M.Kojima,M.Shida and S.Hara,Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices,SIAM Journal on Optimization,7(1):86-125,1997.17 L.C.Kong,J.Sun and N.H.Xiu,A regularized smoothing Newton method for symmetric cone complementarity problems,SIAM Journal on Optimization,19(3):1028-1047,2008.18 Y.J.Lin and L.W.Zhang,On the approximate augmented Lagrangian for nonlinear symmetric cone programming,Nonlinear Analysis,68(5):1210-1225,2008.19 Z.Y.Liu and W.Y.Sun,A primal-dual interior-point filter method for nonlinear semidefinite programming,The 7th International Symposium on Operations Research and Its Applications,Lijiang,China,pp.112-118,2008.20 Z.Y.Luo and N.H.Xiu,Path-following interior point algorithms for the Cartesian*()P-LCP over symmetric cones,Science in China Series A:Mathematics,52(8):1769-1784,2009.21 Z.Y.Luo and N.H.Xiu,An O(rL)infeasible interior-point algorithm for symmetric cone LCP via CHKS 国家自然科学基金申请书 2010 版 第 11 页 function,Acta Mathematicae Applicatae Sinica(English Series),25(4):593-606,2009.22 C.F.Ma and X.H.Chen,The convergence of a one-step smoothing Newton method for P0-NCP based on a new smoothing NCP-function,Journal of Computational and Applied Mathematics,216(1):1-13,2008.23 M.Muramatsu,On a commutative class of search directions for linear programming over symmetric cones,Journal of Optimization Theory and Application,112(3):595-625,2002.24 Y.E.Nesterov and M.J.Todd,Primal-dual interior-point methods for self-scaled cones,SIAM Journal on Optimization,8(2):324-364,1998.25 S.H.Pan and J.S.Chen,A class of interior proximal-like algorithms for convex second-order cone programming,SIAM Journal on Optimization,19:883-910,2008.26 J.Peng,C.Roos and T.Terlaky,Self-Regularity:A New Paradigm for Primal-Dual Interior-Point Algorithms,Princeton University Press,USA,2002.27 B.K.Rangarajan,Polynomial convergence of infeasible-interior-point methods over symmetric cones,SIAM Journal on Optimization,16(4):1211-1229,2006.28 C.Roos,A full-Newton step O(n)infeasible interior-point algorithm for linear optimization,SIAM Journal on Optimization,16(4):1110-1136,2006.29 S.H.Schmieta and F.Alizadeh,Extension of primal-dual interior-point algorithms to symmetric cones,Mathematical Programming,96:409-438,2003.30 S.P.Schurr,D.P.OLeary and A.Tits,A polynomial-time interior-point method for conic optimization,with inexact barrier evaluations,SIAM Journal on Optimization,20(1):548-571,2009.31 M.Shida,S.Shindoh and M.Kojima,Existence and uniqueness of search directions in interior-point algorithms for the SDP and the monotone SDLCP,SIAM Journal on Optimization,8(2):387-396,1998.32 C.K.Sim and G.Zhao,Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem,Mathematical Programming,110:475-499,2007.33 A.M.C.So and Y.Ye,Theory of semidefinite programming for sensor network localization,Mathematical Programming,109(2-3):367-384,2007.34 D.F.Sun,J.Sun and L.W.Zhang,The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming,Mathematical Programming,114(2):349-391,2008.35 K.C.Toh,An inexact primal-dual path following algorithm for convex quadratic SDP,Mathematical Programming,112:221-254,2008.36 P.Tseng,An infeasible path-following method for monotone complementarity problems,SIAM Journal 国家自然科学基金申请书 2010 版 第 12 页 on Optimization,7(2):386-402,1997.37 P.Tseng,Second-order cone programming relaxation of sensor network localization,SIAM Journal on Optimization,18(1):156-185,2007.38 M.Ulbrich,S.Ulbrich and L.N.Vicente,A globally convergent primal-dual interior-point filter method for nonlinear programming,Mathematical Programming,100:379-410,2004.39 L.Ye and Y.X.Y uan,An interior-point trust-region algorithm for general symmetric cone programming,SIAM Journal on Optimization,18(1):65-86,2007.40 H.Yamashita and H.Yabe,A primal-dual interior point method for nonlinear optimization over second-order cones,Optimization Methods and Software,24(3):407-426,2009.41 A.Yoshise,Interior point trajectories a