为了提高求解二阶锥规划问题的效率, 提出一种新的求解二阶锥规划问题的非单调信赖域算法. 基于Fischer-Burmeister光滑函数, 对二阶锥规划问题的最优性条件进行转化, 得到与其等价的无约束优化问题的非线性可微的光滑方程组, 构造信赖域子问题, 利用非单调信赖域算法求解. 算法在求解信赖域子问题时, 提出了一个新的自适应选取信赖域半径机制, 搜索到全局最优解. 数值实验结果表明, 该算法运行速度快、迭代次数少, 比内点算法和不可行内点算法优越.
Abstract
In order to improve the efficiency of solving the problem of second-order cone programming problem, a new nonmonotonic trust region algorithm is proposed for solving SOCP. Based on the Fischer-Burmeister smoothing function, the optimality conditions of second-order cone programming problem are transformed into unconstrained optimization problem and the trust region subproblem is constructed, a new adaptive mechanism for the trust region radius is presented, the global optimal solution can be got. The numerical results show that the algorithm runs faster and requires fewer iterations, it is superior than the traditional interior-point algorithm and the infeasible interior-point algorithm.
关键词
二阶锥规划 /
非单调信赖域算法 /
光滑函数 /
内点算法 /
不可行内点法
{{custom_keyword}} /
Key words
second-order cone programming (SOCP) /
nonmonotonic trust region algorithms /
smooth function /
interior-point algorithm /
infeasible interior-point algorithm
{{custom_keyword}} /
中图分类号：
O221.2
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Lobo M S, Vandenberghe L, Boyd S. Application of second-order cone programming[J]. Linear Algebra Applications, 1998, 284(1-3): 193-228.
[2] Alizadeh F, Goldfarb D. Second-order cone programming[J]. Mathematical Programming, 2003, 95(1): 3-51.
[3] Nemirovskii A, Scheinberg K. Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems[J]. Mathematical Programming, 1996, 72(3): 273-289.
[4] Qi L Q, Sun J. A nonsmooth version of Newton's method[J]. Mathematical Programming, 1993, 58(3): 353-367.
[5] Fang L, He G P, Hu Y H. A new smoothing Newton-type method for second-order cone programming problems[J]. Applied Mathematics and Computation, 2009, 215: 1020-1029.
[6] 汤京永,贺国平.二阶锥规划的一步光滑牛顿法[J].数学物理学报, 2012, 4: 768-778. Tang Jingyong, He Guoping. A one-step smoothing Newton method for second-order cone programming[J]. Acta Methematica Scientia, 2012, 4: 768-778.
[7] 芮绍平,张杰.一种具有全局收敛性的求解二阶锥规划的非精确光滑算法[J].系统科学与数学, 2012, 3: 257-264. Rui Shaoping, Zhang Jie. A globaliy convergent inexact smoothing algorithm for second-order cone programming[J]. Journal of Systems Science and Mathematical Sciences, 2012, 3: 257-264.
[8] 汤京永,贺国平.一个新的求解二阶锥规划的非内部连续化算法[J].应用数学, 2012, 25(1): 26-31. Tang Jingyong, He Guoping. Non-interior continuation method for second-order cone programming[J]. Mathematica Applicata, 2012, 25(1): 26-31.
[9] Yuan Y X. Conditions for convergence of trust region algorithms for nonsmooth optimization[J]. Mathematical Programming, 1985, 31: 220-228.
[10] 李改弟.一个自动确定信赖域半径的信赖域方法[J].工程数学学报, 2006, 23(5): 843-848.Li Gaidi. A trust region method with automatic determination of the trust region radius[J]. Chinese Journal of Engineering Mathematics, 2006, 23(5): 843-848.
[11] 欧宜贵,侯定丕.一种约束非光滑优化的非单调信赖域算法[J].应用数学, 2005, 18(1): 60-65.Ou Yigui, Hou Dingpi. A new nonmonotonic trust region algorithm for a class of constrained nonsmooth optimization[J]. Mathematica Applicata, 2005, 18(1): 60-65.
[12] Monteiro R D C, Tsuchiya T. Polynimial convergence of primal-dual algorithms for the second-order cone programming based on the MZ-family of directions[J]. Mathematical Programming, 2000, 88(1): 61-83.
[13] Chi X N, Liu S Y, Mu X W, et al. Inexact infeasible interior point algorithm for second-order cone programming[J]. Chinese Journal of Engineering Mathematics, 2006, 23(4): 625-631.
[14] Chi X N, Liu S Y, LI B J. An infeasible interior point algorithm for the seeond-order cone programming[J]. Journal of Lanzhou University (Natural Sciences), 2007, 43(4): 136-139.
[15] 曾友芳,白延琴,简金宝,等.二阶锥规划两个新的预估-校正算法[J].应用数学和力学, 2011(4): 497-508.Zeng Youfang, Bai Yanqin, Jian Jinbao, et al. Two new predictor-corrector algorithms for second-order cone programming[J]. Applied Mathematics and Mechanics, 2011(4): 497-508.
[16] 曾友芳.二阶锥规划的理论与算法研究[D].上海:上海大学, 2011. Zeng Youfang. Research on theory and algorithms for second-order cone programming[D]. Shanghai: Shanghai University, 2011.
[17] Sun D F, Sun J. Strong semismoothness of the Fischer-Burmeister SDC and SOC complementarity functions[J]. Mathematical Programming, 2005, 103: 575-581.
[18] Fukushima M, Luo Z Q, Tseng P. Smoothing functions for second-order-cone complimentarity problems[J]. SIAM Journal on Optimization, 2002, 12: 436-460.
[19] 王剑平,吕毅斌,张晓鹏.无约束优化的一类新的非单调信赖域算法[J].科学技术与工程, 2012, 14: 3291-3294. Wang Jianping, Lü Yibin, Zhang Xiaopeng. A new nonmonotone trust region algorithm of unconstrained optimization[J]. Science Technology and Engineering, 2012, 14: 3291-3294.
[20] Zhang X S, Zhang J L, Liao L Z. An adaptive trust region method and its convergence[J]. Science in China (Scries A), 2002, 45: 620-631.
[21] Sturma J F. Using Sedumi 1.02, a Matlab toolbox for optimization over symmetric cones[J]. Optimization Methods and Software, 1999, 11(1): 625-653.
[22] Bai Y Q, Wang G Q, Roos C. Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions[J]. Nonlinear Analysis: Theory, Methods and Applications, 2009, 70(10): 3584-3602.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
教育部高校博士学科科研基金联合资助项目(20132121110009)
{{custom_fund}}
PDF(488 KB)
