基于尺度中心路径的求解SCLP的非单调光滑牛顿算法

数学物理学报 ›› 2014, Vol. 34 ›› Issue (2): 378-392.

基于尺度中心路径的求解SCLP的非单调光滑牛顿算法

倪铁¹, 刘晓红²

1.辽宁工程技术大学工商管理学院辽宁葫芦岛 125105;
2.天津大学理学院数学系天津 300072

收稿日期:2012-03-06 修回日期:2013-09-18 出版日期:2014-04-25 发布日期:2014-04-25
基金资助:
国家自然科学基金(10471126, 10371109)、浙江省自然科学基金(101016)和浙江省哲学社会科学规划常规性课题(06CGYJ21YBQ)资助.

Non-Monotone Smoothing Newton Algorithm for SCLP Based on a Scaled Central Path

NI Tie¹, LIU Xiao-Hong²

1.College of Business Administration, Liaoning Technical University, Liaoning Huludao 125105;
2.Department of Mathematics, School of Science, Tianjin University, Tianjin 300072

Received:2012-03-06 Revised:2013-09-18 Online:2014-04-25 Published:2014-04-25
Supported by:
国家自然科学基金(10471126, 10371109)、浙江省自然科学基金(101016)和浙江省哲学社会科学规划常规性课题(06CGYJ21YBQ)资助.

摘要/Abstract

摘要：

基于CHKS光滑函数的修改性版本, 该文提出了一个带有尺度中心路径的求解对称锥线性规划(SCLP)的非单调光滑牛顿算法. 通过应用欧氏若当代数理论, 在适当的假设下, 证明了该算法是全局收敛和超线性收敛的. 数值结果表明了算法的有效性.

关键词: 线性规划, 对称锥, 欧氏若当代数, 光滑算法, 尺度中心路径, 非单调线搜索

Abstract:

Based on a modified version of the Chen-Harker-Kanzow-Smale (CHKS) smoothing function, this paper investigates a non-monotone smoothing Newton algorithm with a scaled central path for solving linear programming over symmetric cones (SCLP). By using the theory of Euclidean Jordan algebras, we show that the proposed algorithm is globally and locally superlinearly convergent under suitable assumptions. Some preliminary numerical results is shown that our algorithm proposed is promising.

Key words: Linear programming, Symmetric cone, Euclidean Jordan algebra, Smoothing algorithm, Scaled central path, Non-monotone line search

中图分类号:

90C05

倪铁, 刘晓红. 基于尺度中心路径的求解SCLP的非单调光滑牛顿算法[J]. 数学物理学报, 2014, 34(2): 378-392.

NI Tie, LIU Xiao-Hong. Non-Monotone Smoothing Newton Algorithm for SCLP Based on a Scaled Central Path[J]. Acta mathematica scientia,Series A, 2014, 34(2): 378-392.

参考文献

[1] Faraut J, Kor\'{a}nyi A. Analysis on Symmetric Cones. Oxford Mathematical Monographs. New York: Oxford University Press, 1994

[2] Faybusovich L. Euclidean Jordan algebras and interior-point algorithms. Positivity, 1997, 1(4): 331--357

[3] Faybusovich L, Tsuchiya T. Primal-dual algorithms and infinite-dimensional Jordan algebras of finite rank. Mathematical Programming, 2003, 97(3): 471--493

[4] Schimieta S H, Alizadeh F. Associative and Jordan algebras, and polynomial time interior-point algirithms for symmetric cones. Mathematics of Operations Research, 2001, 26(3): 543--564

[5] Schimieta S H, Alizadeh F. Extension of primal-dual interior-point algirithms to symmetric cones. Mathematical Programming, 2003, 96(3): 409--438

[6] Liu X H, Huang Z H. A smoothing Newton algorithm based on a one-parametric class of smoothing functions for linear programming over symmetric cones. Mathematical Methods of Operations Research, 2009, 70(2): 385--404

[7] Liu X H, Ni T. Smoothing Newton algorithm for linear programming over symmetric cones. Transactions of Tianjin University, 2009, 15(3): 216--221

[8] Kor\'{a}nyi A. Monotone functions on formally real Jordan algebras. Mathematische Annalen, 1984, 269(1): 73--76

[9] Yuan Y X. A scaled central path for linear programming. Journal of Computational Mathematics, 2001, 19(1): 35--40

[10] Chen B, Harker P T. Smooth approximations to nonlinear complementarity problem. SIAM Journal on Optimization, 1997, 7(2): 403--420

[11] Wang Q G, Zhao J L, Yang Q Z. Some non-interior path-following methods based on a scaled central path for linear complementarity problems. Computational Optimization and Applications, 2010, 46(1): 31--49

[12] Chen B, Harker P T. A non-interior-point continuation method for linear complementarity problem. SIAM Journal on Matrix Analysis and Applications, 1993, 14(4): 1168--1190

[13] Kanzow C. Some noninterior continuation methods for linear complementarity problems. SIAM Journal on Matrix Analysis and Applications, 1996, 17(4): 851--868

[14] Smale S. Algorithms for Solving Equations. In: Proceeding of International Congress of Mathematicians, edited by Gleason, A. M., Providence, Rhode Island: American Mathematics Society, 1987: 172--195

[15] Huang Z H, Ni T. Smoothing algorithms for complementarity problems over symmetric cones. Computational Optimization and Applications, 2010, 45(3): 557--579

[16] Gowda M S, Sznajder R, Tao J. Some P-properties for linear transformations on Euclidean Jordan algebras. Linear Algebra and Its Applications, 2004, 393(1): 203--232

[17] Yoshise A. Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones. SIAM Journal on Optimization, 2006, 17(4): 1129--1153

[18] Qi L, Sun D, Zhou G. A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems. Mathematical Programming, 2000, 87(1): 1--35

[19] Huang Z H, Sun D, Zhao G Y. A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming. Computational Optimization and Applications, 2006, 35(2): 199--237

[20] Huang Z H, Xu S W. Convergence properties of a non-interior-point smoothing algorithm for the P_* NCP. Journal of Industrial Management Optimization, 2007, 3(3): 596--584

[21] Huang Z H, Zhang Y, Wu W. A smoothing-type algorithm for solving system of inequalities. Journal of Computational and Applied Mathematics, 2008, 220(1/2): 355--363

[22] Ni T, Wang P. A smoothing-type algorithm for solving nonlinear complementarity problems with a non-monotone line search. Applied Mathematics and Computation, 2010, 216(7): 2207--2214

[23] Mifflin R. Semismooth and semiconvex functions in constraint optimization. SIAM Journal on Control and Optimization, 1977, 15(6): 957--972

[24] Qi L, Sun J. A nonsmooth version of Newton's method. Mathematical programming, 1993, 58(1/3): 353--367

[25] Qi L. Convergence analysis of some algorithms for solving nonsmooth equations. Mathematics of Operations Research, 1993, 18(1): 227--253

[26] Sun D, Sun J. Semismooth matrix valued functions. Mathematics of Operations Research, 2002, 27(1): 150--169

[27] Sun D, Sun J. L\"owner's operator and spectral functions in Euclidean Jordan algebras. Mathematics of Operations Research, 2008, 33(2): 421--445

[28] Toh K C, T\"ut\"unc\"u R H, Todd M J. On the implementation and usage of SDPT3 - a MATLAB software package for
semidefinite-quadratic-linear programming, version 4.0, Jul 2006, available from http://www. math.nus.edu.sg/mattohkc/guide4-0-draft.pdf.

[29] Zhang H C, Hanger W W. A nonmonotone line search technique and its application to unconstrained optimization. SIAM Journal on Optimization, 2004, 14(4): 1043--1056

[30] Huang Z H, Liu X H. Extension of smoothing Newton algorithms to solve linear programming over symmetric cones. Journal of Systems Science and Complexity, 2011, 24(1): 195--206