锥规划中若干内点算法的复杂性研究
|
摘要
在内点法中,理论和实践之间存在着一个矛盾：实际计算效果好的算法在理论上却具有较差的迭代复杂性。本论文旨在研究几类锥规划问题(包括线性规划、半定规划和对称锥规划)中有效的内点算法,讨论它们的迭代复杂性和数值效果。
首先给出了线性规划的两个Mehrotra型预估-矫正算法。它们都是基于宽邻域的原-对偶内点算法,并且宽邻域的定义和常用的-∞邻域有着密切关系。在每次迭代中,该算法比传统的迭代方向增加一个矫正方向。通过证明一些重要引理,给出了算法的O((?)L)迭代复杂性,其中n是问题维数,L是输入数据的长度。这是第一次得到具有O((?)L)复杂性的Mehrotra型预估-矫正算法,这也是目前内点法中最好的复杂性结果。基于线性规划问题的标准测试问题集NETLIB的数值结果显示了该算法具有很好的实际计算效果。随后,把第一个算法推广到了半定规划问题。基于NT方向,证明了算法的复杂性与线性规划的情况是相同的。并且,基于实际问题的数值结果验证了算法的实际有效性.
接着深入研究了线性规划问题的带保障的Mehrotra型预估-矫正算法。该算法把Mehrotra算法和一个保障策略结合起来,以保证迭代既不超出给定的邻域又能获得较大的迭代步长。指出了Koulaei和Terlaky在推广带保障的Mehrotra型预估-矫正算法到半定规划时存在的一个严重证明错误。通过修改预估步中的最大步长的计算方法,给出了半定规划的一个新的Mehrotra型预估-矫正算法。但对于线性规划的情况,由新方法计算的预估步长与Koulaei和Terlaky的方法是完全相同的。基于NT方向,证明该算法的复杂性为O(nL)。然后,利用欧氏Jordan代数作为工具,把该算法进一步推广到对称锥(包含了非负卦限,半正定矩阵锥和二阶锥),并证明了算法的O(r logeε-1)迭代复杂性,其中r是Jordan代数的秩,ε是精度参数。同时提出了一个新的自适应更新中心策略,基于该策略的Mehrotra型预估-矫正算法和带保障的Mehrotra算法具有相同的复杂性。数值结果证实了新算法的有效性。利用类似的技巧,把Salahi和Mahdavi-Amiri提出的二阶Mehrotra型预估-矫正算法由线性规划推广到了对称锥规划。但是,推广的算法在迭代步长的选取方式和保障的使用范围都不同于Salahi(?)口Mahdavi-Amiri的算法。基于NT方向,证明了算法的复杂性与线性规划的情况是相同的。然后,又给出了该算法的一个不可行算法,基于NT方向,不可行算法具有O(r2logε-1)迭代复杂性；若初始点是可行点,则算法的复杂性降低到O(rlogε-1)。
最后,基于艾文宝和张树中的原-对偶路径跟踪算法,提出了对称锥规划的一个新的原-对偶不可行内点算法。基于“可交换类”方向,证明了该算法的多项式收敛性。特别的,对于NT方向,复杂性为O(r1.5logε-1)；对于xs和sx方向,复杂性为O(r2logε-1)。如果算法的初始点是可行点,则对于NT方向,复杂性为O((?)logε-1)；对于xs和sx方向,复杂性为O(rlogε-1)。当取NT方向时,我们首次得到了对称锥上具有和窄邻域相同复杂性的宽邻域内点算法。
In interior-point methods(IPMs), there has been an inconsistency between theory and practice:fast algorithms in practice may actually render worse iteration complexity bounds. This dissertation focuses on the efficient interior-point algorithms for solving conic programming problems, including linear programming(LP), semidefinite program-ming(SDP) and symmetric conic programming(SCP).
We first propose two new Mehrotra-type predictor-corrector interior-point algo-rithm for LP using two wide neighborhoods of the central path. Both neighborhoods are related to the minus infinity neighborhood. At each iteration, the algorithms com-pute a corrector direction in addition to the classical direction, in an attempt to improve performance. We prove O(√nL) iteration complexity of the algorithms, where n is the number of variables and L is the input data length. This is the first Mehrotra-type predictor-corrector algorithm enjoyed the low iteration bound of O(√nL), the same as the best known complexity results for IPMs. The numerical experiences show that the algorithms have a superior practical performance. Subsequently, we extend one of the Mehrotra-type predictor-corrector algorithms from LP to SDP. The polynomial com-plexity is established for the algorithm using the Nesterov-Todd (NT) direction, which is analogous to the case of LP.
Then, we research into the safeguard based Mehrotra-type predictor-corrector algo-rithms for LP. This algorithm incorporates a safeguard in Mehrotra's original predictor-corrector algorithm, which keeps the iterates in the prescribed neighborhood and allows us to get a reasonably large step size. We point out a mistake in the proof of the key lemma in Koulaei and Terlaky, which extend the safeguard based algorithm to SDP. We modify the maximum step size slightly in the predictor step and propose a new Mehrotra-type predictor-corrector algorithm for SDP. However, in the case of LP, the new predictor step size is still identical with that used by Koulaei and Terlaky. Based on the NT direction, we prove O(nL) iteration complexity of the new algorithm. Fur-thermore, using the machinery of Euclidean Jordan algebras, we further extend the modified algorithm to symmetric cones, which include the nonnegative orthant, the positive semidefinite cone and second-order cone as special cases. It is proved for the NT direction that the algorithm stops after at most O(r logε-1) iteration, where r is the rank of the Jordan algebras and ε is the precision parameter. We also present a new variant of Mehrotra-type algorithm using a new adaptive updating scheme of centering parameter, and show that this algorithm enjoys the same order of complexity bound as the safeguard algorithm. Our numerical results also provide us an encouraging evidence that our new algorithms may also perform well in practice. Moreover, we present an extension of the second-order Mehrotra-type predictor-corrector algorithm proposed by Salahi and Mahdavi-Amiri for LP to SCP. In our algorithm the safeguard strategy is not necessarily used when the affine scaling step performs poorly, which is different from the algorithm of Salahi and Mahdavi-Amiri. We extend the new algorithm to symmetric cones and show that, based on the NT direction, the complexity bounds of the algorithm coincide with the case of LP. We also present a new variant of infeasible second-order Mehrotra-type algorithm for SCP. Based on the NT direction, the complexity bounds of the algorithm is O(r2logε-1). If the staring point is feasible, the complexity bound is reduced to O(r logε-1).
Finally, we establish polynomial convergence of a new primal-dual infeasible-interior-point algorithm for SCP using wide neighborhood of the central path. The convergence is shown for the "commutative class" of search directions. In particular, the complexity bound is O(r1.5logε-1) for the NT direction, and O(r2logε-1) for the xs and sx directions. If the staring point is feasible, the complexity bound is O(√rlogε-1) for the NT direction, and O(r logε-1) for the xs and sx directions. When the NT search direction is used, we get the first wide neighborhood interior-point algorithm with the same complexity as small neighborhood IPMs over symmetric cones.
首先给出了线性规划的两个Mehrotra型预估-矫正算法。它们都是基于宽邻域的原-对偶内点算法,并且宽邻域的定义和常用的-∞邻域有着密切关系。在每次迭代中,该算法比传统的迭代方向增加一个矫正方向。通过证明一些重要引理,给出了算法的O((?)L)迭代复杂性,其中n是问题维数,L是输入数据的长度。这是第一次得到具有O((?)L)复杂性的Mehrotra型预估-矫正算法,这也是目前内点法中最好的复杂性结果。基于线性规划问题的标准测试问题集NETLIB的数值结果显示了该算法具有很好的实际计算效果。随后,把第一个算法推广到了半定规划问题。基于NT方向,证明了算法的复杂性与线性规划的情况是相同的。并且,基于实际问题的数值结果验证了算法的实际有效性.
接着深入研究了线性规划问题的带保障的Mehrotra型预估-矫正算法。该算法把Mehrotra算法和一个保障策略结合起来,以保证迭代既不超出给定的邻域又能获得较大的迭代步长。指出了Koulaei和Terlaky在推广带保障的Mehrotra型预估-矫正算法到半定规划时存在的一个严重证明错误。通过修改预估步中的最大步长的计算方法,给出了半定规划的一个新的Mehrotra型预估-矫正算法。但对于线性规划的情况,由新方法计算的预估步长与Koulaei和Terlaky的方法是完全相同的。基于NT方向,证明该算法的复杂性为O(nL)。然后,利用欧氏Jordan代数作为工具,把该算法进一步推广到对称锥(包含了非负卦限,半正定矩阵锥和二阶锥),并证明了算法的O(r logeε-1)迭代复杂性,其中r是Jordan代数的秩,ε是精度参数。同时提出了一个新的自适应更新中心策略,基于该策略的Mehrotra型预估-矫正算法和带保障的Mehrotra算法具有相同的复杂性。数值结果证实了新算法的有效性。利用类似的技巧,把Salahi和Mahdavi-Amiri提出的二阶Mehrotra型预估-矫正算法由线性规划推广到了对称锥规划。但是,推广的算法在迭代步长的选取方式和保障的使用范围都不同于Salahi(?)口Mahdavi-Amiri的算法。基于NT方向,证明了算法的复杂性与线性规划的情况是相同的。然后,又给出了该算法的一个不可行算法,基于NT方向,不可行算法具有O(r2logε-1)迭代复杂性；若初始点是可行点,则算法的复杂性降低到O(rlogε-1)。
最后,基于艾文宝和张树中的原-对偶路径跟踪算法,提出了对称锥规划的一个新的原-对偶不可行内点算法。基于“可交换类”方向,证明了该算法的多项式收敛性。特别的,对于NT方向,复杂性为O(r1.5logε-1)；对于xs和sx方向,复杂性为O(r2logε-1)。如果算法的初始点是可行点,则对于NT方向,复杂性为O((?)logε-1)；对于xs和sx方向,复杂性为O(rlogε-1)。当取NT方向时,我们首次得到了对称锥上具有和窄邻域相同复杂性的宽邻域内点算法。
In interior-point methods(IPMs), there has been an inconsistency between theory and practice:fast algorithms in practice may actually render worse iteration complexity bounds. This dissertation focuses on the efficient interior-point algorithms for solving conic programming problems, including linear programming(LP), semidefinite program-ming(SDP) and symmetric conic programming(SCP).
We first propose two new Mehrotra-type predictor-corrector interior-point algo-rithm for LP using two wide neighborhoods of the central path. Both neighborhoods are related to the minus infinity neighborhood. At each iteration, the algorithms com-pute a corrector direction in addition to the classical direction, in an attempt to improve performance. We prove O(√nL) iteration complexity of the algorithms, where n is the number of variables and L is the input data length. This is the first Mehrotra-type predictor-corrector algorithm enjoyed the low iteration bound of O(√nL), the same as the best known complexity results for IPMs. The numerical experiences show that the algorithms have a superior practical performance. Subsequently, we extend one of the Mehrotra-type predictor-corrector algorithms from LP to SDP. The polynomial com-plexity is established for the algorithm using the Nesterov-Todd (NT) direction, which is analogous to the case of LP.
Then, we research into the safeguard based Mehrotra-type predictor-corrector algo-rithms for LP. This algorithm incorporates a safeguard in Mehrotra's original predictor-corrector algorithm, which keeps the iterates in the prescribed neighborhood and allows us to get a reasonably large step size. We point out a mistake in the proof of the key lemma in Koulaei and Terlaky, which extend the safeguard based algorithm to SDP. We modify the maximum step size slightly in the predictor step and propose a new Mehrotra-type predictor-corrector algorithm for SDP. However, in the case of LP, the new predictor step size is still identical with that used by Koulaei and Terlaky. Based on the NT direction, we prove O(nL) iteration complexity of the new algorithm. Fur-thermore, using the machinery of Euclidean Jordan algebras, we further extend the modified algorithm to symmetric cones, which include the nonnegative orthant, the positive semidefinite cone and second-order cone as special cases. It is proved for the NT direction that the algorithm stops after at most O(r logε-1) iteration, where r is the rank of the Jordan algebras and ε is the precision parameter. We also present a new variant of Mehrotra-type algorithm using a new adaptive updating scheme of centering parameter, and show that this algorithm enjoys the same order of complexity bound as the safeguard algorithm. Our numerical results also provide us an encouraging evidence that our new algorithms may also perform well in practice. Moreover, we present an extension of the second-order Mehrotra-type predictor-corrector algorithm proposed by Salahi and Mahdavi-Amiri for LP to SCP. In our algorithm the safeguard strategy is not necessarily used when the affine scaling step performs poorly, which is different from the algorithm of Salahi and Mahdavi-Amiri. We extend the new algorithm to symmetric cones and show that, based on the NT direction, the complexity bounds of the algorithm coincide with the case of LP. We also present a new variant of infeasible second-order Mehrotra-type algorithm for SCP. Based on the NT direction, the complexity bounds of the algorithm is O(r2logε-1). If the staring point is feasible, the complexity bound is reduced to O(r logε-1).
Finally, we establish polynomial convergence of a new primal-dual infeasible-interior-point algorithm for SCP using wide neighborhood of the central path. The convergence is shown for the "commutative class" of search directions. In particular, the complexity bound is O(r1.5logε-1) for the NT direction, and O(r2logε-1) for the xs and sx directions. If the staring point is feasible, the complexity bound is O(√rlogε-1) for the NT direction, and O(r logε-1) for the xs and sx directions. When the NT search direction is used, we get the first wide neighborhood interior-point algorithm with the same complexity as small neighborhood IPMs over symmetric cones.
引文
[1]Vandenberghe L, Boyd S. Semidefinite programming. SIAM Rev,1996.38:49-95.
[2]Vandenberghe L, Boyd S. Applications of semidefinite programming. Appl Numer Math, 1999,29:283-299.
[3]Lobo M S, Vandenberghe L, Boyd S, Lebret H. Applications of second-order cone program-ming. Linear Algebra Appl,1998,284:193-228.
[4]Boyd S, Ghaoui L El, Feron E, Balakrishnan V. Linear Matrix Inequalities in System and Control Theory. Philadelphia:SIAM,1994.
[5]Alizadeh F. Interior point methods in semidefinite programming with applications to com-binatorial optimization. SIAM J Optim,1995,5:13-51.
[6]Alizadeh F, Goldfarb D. Second-order cone programming. Math Program,2003,95:3-51.
[7]de Klerk E. Aspects of Semidefinite Programming:Interior Point Algorithms and Selected Applications. Dordrecht:Kluwer Academic Publishers,2002.
[8]Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorica, 1984,4:373-395.
[9]Nesterov Yu, Nemirovski A. Polynomial barrier methods in convex programming. Ekonomika i Matem Metody,1988,24:1084-1091.
[10]Nesterov Yu, Nemirovski A. A general approach to polynomial-time algorithms design for convex programming. Moscow:USSR Academy of Sciences, Central Economic & Mathe-matic Institute,1988.
[11]Nesterov Yu, Nemirovski A. Self-concordant functions and polynomial time methods in con-vex programming. Moscow:USSR Academy of Sciences, Central Economic & Mathematic Institute,1989.
[12]Nesterov Yu, Nemirovski A. Optimization over positive semidefinite matrices:Mathematical background and user's manual. Moscow:USSR Academy of Sciences, Central Economic & Mathematic Institute,1990.
[13]Nesterov Yu, Nemirovski A. Conic formulation of a convex programming problem and dual-ity. Moscow:USSR Academy of Sciences, Central Economic & Mathematic Institute,1991.
[14]Nesterov Yu, Nemirovskii A. Interior-Point Polynomial Algorithms in Convex Programming. Philadelphia:SIAM:1994.
[15]Alizadeh F. Combinatorial Optimization with Interior-Point Methods and Semi-Definite Matrices. Ph. D. Thesis, Minneapolis:University of Minnesota,1991.
[16]Alizadeh F. Optimization over positive semi-definite cone:Interior-point methods and com-binatorial applications. In:Pardalos P M, ed. Advances in Optimization and Parallel Com-puting. Amsterdam:North-Holland,1992:1-25.
[17]Goldfarb D, Liu S, Wang S. A logarithmic barrier function algorithm for quadratically con-strained convex quadratic programming. SIAM J Optim,1991,1:252-267
[18]Jarre F. On the convergence of the method of analytic centers when applied to convex quadratic programs. Math Program,1991,49:341-358.
[19]Mehrotra S, Sun J. A method of analytic centers for quadratically constrained convex quadratic programs SIAM J Numer Anal,1991,28:529-544.
[20]Jarre F. An interior-point method for minimizing the maximum eigenvalue of a linear com-bination of matrices. SIAM J Control Optim,1993,31:1360-1377.
[21]Alizadeh F, Haeberly J A, Overton M L. Primal-dual interior-point methods for semidefinite programming:Convergence rates, stability and numerical results. SIAM J Optim,1998,8: 746-768.
[22]Adler I, Alizadeh F. Primal-dual interior point algorithms for convex quadratically con-strained and semidefinite optimization problems. Technical Report RRR 46-95, RUTCOR, Rutgers University, December 1995.
[23]Alizadeh F, Schmieta S H. Optimization with semidefinite, quadratic and linear constraints. Technical Report RRR 23-97, RUTCOR, Rutgers University, November 1997.
[24]Nemirovski A, Scheinberg K. Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems. Math Program,1996,72:273-289.
[25]Tsuchiya T. A polynomial primal-dual path-following algorithm for second-order cone pro-gramming. Technical Report 649, The Institute of Statistical Mathematics, Tokyo,1997.
[26]Nemirovski A. What can be expressed via conic quadratic and semidefinite programming? Talk presented at RUTCOR weekly seminar, Rutgers University, August 1999.
[27]Goemans M X, Williamson D P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM,1995,42:1115-1145.
[28]Kojima M, Shindoh S, Hara S. Interior poit methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J Optim,1997,7:86-125.
[29]Monteiro R D C. Primal-dual path-following algorithms for semidefinite programming. SIAM J Optim,1997,7:663-678.
[30]Monteiro R D C. Zhang Y. A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming. Math Program.1998,81: 281-299.
[31]Helmberg C. Rendl F. Vanderbei R J. Wolkowicz H. An interior-point method for semidefinite programming. SIAM J Optim,1996,6:342-361.
[32]Pardalos P M. Wolkowicz H, eds. Topics in Semidefinite and Interior-Point Methods. Amer-ican Math Society,1998.
[33]Wolkowicz H. Saigal R, Vandenberghe L, eds. Handbook of Semidefinite Programming:The-ory, Algorithms, and Applications. Dordrecht:Kluwer Academic Publishers,2000.
[34]Alizadeh F, Schmieta S. Symmetric cones, potential reduction methods and word-by-word extensions. In:Wolkowicz H, Saigal R, Vandenberghe L, eds. Handbook of Semidefinite Pro-gramming:Theory, Algorithms, and Applications. Dordrecht:Kluwer Academic Publishers, 2000:195-233.
[35]Nesterov Yu, Todd M J. Self-scaled barriers and interior-point methods for convex program-ming. Math Oper Res,1997,22:1-42.
[36]Nesterov Yu, Todd M J. Primal-dual interior-point methods for self-scaled cones. SIAM J Optim,1998,8:324-364.
[37]Giiler O. Barrier functions in interior-point methods. Math Oper Res,1996,21:860-885.
[38]Faraut J, Koranyi A. Analysis on Symmetric Cones. Oxford:Oxford University Press,1994.
[39]Faybusovich L. Linear systems in Jordan algebras and primal-dual interior-point algorithms. J Comput Appl Math,1997,86:149-175.
[40]Faybusovich L. Euclidean Jordan algebras and interior-point algorithms. Positivity,1997,1: 331-357.
[41]Faybusovich L. A Jordan-algebraic approach to potential-reduction algorithms. Math Z, 2002,239:117-129.
[42]Faybusovich L. Several Jordan-algebraic aspects of optimization. Optimization,2008,57(3): 379-393.
[43]Faybusovich L, Arana R. A long-step primal-dual algorithm for symmetric programming problem. Systems Control Lett,2001,43:3-7.
[44]Schmieta S H, Alizadeh F. Associative and Jordan algebras, and polynomial time interior point algorithms for symmetric cones. Math Oper Res,2001,26:543-564.
[45]Schmieta S H, Alizadeh F. Extension of primal-dual interior-point algorithm to symmetric cones. Math Program,2003,96:409-438.
[46]Muramatsu M. On a commutative class of search directions for linear programming over symmetric cones. J Optim Theory Appl,2002,112:595-625.
[47]Andersen E D, Roos C, Terlaky T. On implementing a primal-dual interior-point method for conic quadratic optimization. Math Program,2003,95:249-277.
[48]Lu Y, Yuan Y X. An interior-point trust, region algorithm for general cone prognnming. SIAM J Optim.2007,18:65-8G.
[49]Rangarajan B. Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J Optim,2006,16:1211-1229.
[50]Alizadeh F, Xia Y. The Q method for symmetric cone programming. J Optim Theory Appl, 2011,149:102-137.
[51]Gu G, Zangiabadi M, Roos C. Full Nesterov-Todd step infeasible interior-point method for symmetric optimization. Eur J Oper Res,2011,214:473-484.
[52]Nesterov Yu, Tuncel L. Local quadratic convergence of polynomial-time interior-point meth-ods for conic optimization problems. Technical Report, Center for Operations Research and Econometrics, Belgium, November 2009.
[53]Chua C B. Relating homogeneous cones and positive definite cones via T-algebras. SIAM J Optim,2003,14:500-506.
[54]Chua C B. A T-algebraic approach to primal-dual interior-point algorithms. SIAM J Optim, 2009,20:503-523.
[55]Giiler O, Tungel L. Characterization of the barrier parameter of homogeneous convex cones. Math Program,1998,81:55-76.
[56]Tuncel L, Xu S. On the homogeneous cones, the Caratheodory number, and the duality mapping. Math Oper Res,2001,26:234-247.
[57]Truong V A, Tuncel L. Geometry of homogeneous convex cones, duality mapping, and op-timal self-concordant barriers. Math Program,2004,100:295-316.
[58]Shevchenko O. Recursive Construction of Optimal Self-Concordant Barriers for Homoge-neous Cones. Journal of Optimization Theory and Applications,2009,140:339-354.
[59]Kong L C, Tuncel L, Xiu X H. Existence and uniqueness of solutions for homogeneous cone complementarity problems. J Optim Theory Appl,2012, DOI:10.1007/s10957-011-9971-7.
[60]卢楠.对称锥和齐次锥上非单调互补问题的理论和算法.博十学位论文,天津：天津大学,2010.
[61]Monteiro R D C, Adler I. Polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension. Technical Report ESRC 88-8, Industrial Engineering and Operations Research Department, University of California-Berkeley, March 1988.
[62]Kojima M, Mizuno S, Yoshise A. A primal-dual interior point algorithm for linear pro-gramming. In:Megiddo N, ed. Progress in Mathematical Programming:Interior Point and Related Methods. New York:Springer,1989:29-47.
[63]Monteiro R D C, Adler I. Interior path following primal-dual algorithms, Part Ⅰ:Linear programming. Math Program,1989,44:27-41.
[64]Monteiro R D C, Adler I. Interior path-following primal-dual algorithms, Part Ⅱ:Convex quadratic programming. Math Program.1989,44:43-66.
[65]Kojima M, Mizuno S, Yoshise A. A polynomial-time algorithm for a class of linear comple-mentarity problems. Math Program,1989,44:1-26.
[66]Andersen E D, Gondzio J. Meszaros C, Xu X. Implementation of interior point methods for large scale linear programming. In:Terlaky T, ed. Interior Point Methods in Mathematical Programming. Dordrecht:Kluwer Academic Publisher,1996:189-252.
[67]Gondzio J, Terlaky T. A computational view of interior point methods for linear program-ming. In:Beasley J, ed. Advances in Linear and Integer Programming. Oxford:Oxford University Press,1996:103-144.
[68]Mizuno S, Todd M J, Ye Y. On adaptive step primal-dual interior-point algorithms for linear programming. Math Oper Res,1993,18:964-981.
[69]Peng J M, Roos C, Terlaky T. Self-regular functions and new search directions for linear and semidefinite optimization. Math Program, Ser A,2002,93:129-171.
[70]Bai Y Q, Roos C. A primal-dual interior-point method based on a new kernel function with linear growth rate. In:Proceedings of Industrial Optimization Symposium and Optimization Day. Australia,2002.
[71]Bai Y Q, Roos C, El ghami M. A new efficient large-update primal-dual interior-point method based on a finite barrier. SIAM J Optim,2003.13:766-782.
[72]Bai Y Q, El ghami M, Roos C. A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J Optim,2004,15:101-128.
[73]白延琴.锥优化的基于核函数的内点算法.北京：科学出版社,2010.
[74]Bai Y Q, Wang G Q. Primal-dual interior-point algorithms for second-order cone optimiza-tion based on a new parametric kernel function. Acta Math Sin,2007,23:2027-2042.
[75]Bai Y Q, Wang G Q, Roos C. Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions. Nonlinear Anal-Theor,2009,70:3584-3602.
[76]王国强.基于一个有限罚函数的二阶锥优化的原始对偶内点算法.运筹学报,2007,11：18-31.
[77]Wang G Q, Bai Y Q. A primal-dual interior-point algorithm for second-order cone optimiza-tion with full Nesterov-Todd step. Appl Math Comput,2009,215:1047-1061.
[78]Wang G Q, Bai Y Q. A class of polynomial interior point algorithms for the cartesian p-matrix linear complementarity problem over symmetric cones. J Optim Theory Appl,2012, DOI:10.1007/s10957-011-9938-8.
[79]Hung P. Ye Y. An asymptotical O(√nL)-iteration path-following linear programming algo-rithm that use wide neighborhoods. SIAM J Optim,1996,6:570-586.
[80]Peng J M, Terlaky T, Zhao Y B. A predictor-corrector algorithm for linear optimization based on a specific self-regular proximity function. SIAM J Optim.2005.15:1105-1127.
[81]Potra F A. A superlinearly convergent predictor-corrector method for degenerate LCP in a wide neighborhood of the central path with O(√nL)-iteration complexity. Math Program, 2004,100:317-337.
[82]Ai W. Neighborhood-following algorithms for linear programming. Sci China Math,2004, 47:812-820.
[83]Ai W, Zhang S. An O(√nL) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP. SIAM J Optim,2005,16:400-417.
[84]Feng Z, Fang L. A wide neighbourhood interior-point method with O(√nL) iteration-complexity bound for semidefinite programming. Optimization,2010,59:1235-1246.
[85]Li Y, Terlaky T. A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with O(√nlog Tr(X°s°/ε)iteration complexity. SIAM J Optim, 2010,20:2853-2875.
[86]Mehrotra S. On the implementation of a primal-dual interior point method. SIAM J Optim, 1992,2:575-601.
[87]Gondzio J. Multiple centrality corrections in a primal-dual method for linear programming. Comput Optim Appl,1996,6:137-156.
[88]Vanderbei R J. LOQO user's manual-version 3.10. Optim Method Softw,1999,12:485-514.
[89]Andersen E D. The Mosek interior point optimizer for linear programming:an implemen-tation of the homogeneous algorithm. In:Frenk H, Roos K, Terlaky T, Zhang S, eds. High performance optimization. Dordrecht:Kluwer Academic Publisher,1999:197-232.
[90]Zhang Y. Solving large-scale linear programmes by interior point methods under the Matlab environment. Optim Method Softw,1999,10:1-31.
[91]Czyzyk J, Mehrtotra S, Wagner M, Wright S J. PCx:an interior-point code for linear programming. Optim Method Softw,1999,11/12:397-430.
[92]Gondzio J. HOPDM (version 2.12)-a fast LP solver based on a primal-dual interior point method. Eur J Oper Res,1995,85(1):221-225.
[93]Sturm J F. Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optim Method Softw,1999,11:625-653.
[94]Toh K C, Todd M J, Tutuncu R H. SDPT3-a Matlab software package for semidefinite programming. Optim Methods Softw,1999,11:545-581.
[95]Fujisawa K, Kojima M. Xakata K, Yamashita M. SDPA (SemiDefmite Programming Al-gorithn) User's-version 6.2.0. Research Report B-308, Department of Mathematical and Computing Sciences. Tokyo Institute of Technology, December 1995, Revised September 2004.
[96]NETLIB:A Repository of Linear Programming Test Problems.http://www.netlib.org/.
[97]Nocedal J, Wright S J. Numerical Optimization. New York:Springer,1999.
[98]Zhang Y, Zhang D. On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms. Math Program,1995,68:303-318.
[99]Zhang D, Zhang Y. A Mehrotra-type predictor-corrector algorithm with polynomiality and Q-subquadratic convergence. Ann Oper Res,1996,62:131-150.
[100]Zhang J, Zhang K C. Polynomial complexity of an interior point algorithm with a second order corrector step for symmetric cone programming. Math Meth Oper Res,2011,73: 75-90.
[101]Salahi M, Peng J M, Terlaky T. On Mehrotra-type predictor-corrector algorithms. SIAM J Optim,2007,18:1377-1397.
[102]Salahi M, Mahdavi-Amiri N. Polynomial time second order Mehrotra-type predictor-corrector algorithms. Appl Math Comput,2006,183:646-658.
[103]Koulaei M H, Terlaky T. On the complexity analysis of a Mehrotra-type primal-dual feasible algorithm for semidefinite optimization. Optim Method Softw,2010,25:467-485.
[104]Liu C, Liu H, Liu X. Polynomial convergence of second-order Mehrotra-type predictor-corrector algorithms over symmetric cones. J Optim Theory Appl,2012, DOI: 10.1007/s10957-012-0018-5.
[105]Lustig I J. Feasibility issues in a primal-dual interior-method for linear programming. Math Program,1991,49:145-162.
[106]Tanabe K. Centered Newton method for linear programming:Interior and 'exterior' point method. In:Tone K, ed. New Methods for Linear Programming 3. The Institute of Statistical Mathematics, Tokyo, Japan.1990:98-100 (In Japanese).
[107]Kojima M, Megiddo N, Mizuno S. A primal-dual infeasible-interior-point algorithm for linear programming. Math Program,1993,61:263-280.
[108]Zhang Y. On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem. SIAM J Optim,1994,4:208-227.
[109]Kojima M, Shida M, Shindoh S. Global and local convergence of predictor-corrector infeasible-interior-point algorithms for semidefinite programs. Research Report 305, Depart-ment of Mathematical and Computing Sciences, Tokyo Institute of Technology, October 1995.
[110]Kojima M, Shida M, Shindoh S. Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs. Math Program,1998,80:129-160.
[111]Zhang Y. On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J Optim.1998.8:365-386.
[112]Potra F A, Sheng R. A superlinearly convergent primal-dual infeasible-interior-point algo-rithm for semidefinite programming. SIAM J Optim,1998.8:1007-1028.
[113]Potra F A, Sheng R. Superlinear convergence of interior-point algorithms for semidefinite programming. J Optim Theory Appl,1998,99:103-119.
[114]迟晓妮,刘三阳.二次锥规划的一种原-对偶不可行内点算法.西安电子科技大学学报,2007,34：307-311.
[115]Chi X, Liu S. An infeasible-interior-point predictor-corrector algorithm for the second-order cone program. Acta Math Sci,2008,28:551-559.
[116]Rangarajan B, Todd M T. Convergence of infeasible-interior-point methods for self-scaled conic programming. Technical Report 1388, Operations Research and Industrial Engineering, Cornell University, October 2003.
[117]Roos C. A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM J Optim,2006,16:1110-1136.
[118]Mansouri H, Roos C. A new full-Newton step O(n) infeasible interior-point algorithm for semidefinite optimization. Numer Algor,2009,52:225-255.
[119]Mansouri H, Zangiabadi M, Pirhaji M. A full-Newton step O(n) infeasible-interior-point algorithm for linear complementarity problems. Nonlinear Anal-Real,2011,12:545-561.
[120]Liu Z, Sun W. A full-NT-step infeasible interior-point algorithm for SDP based on kernel functions. Appl Math Comput,2011,217:4990-4999.
[121]Facchinei F, Pang J S. Finite-dimensional Variational Inequalities and Complementarity Problems, Vol Ⅰ. New York:Springer-Verlag,2003.
[122]Facchinei F, Pang J S. Finite-dimensional Variational Inequalities and Complementarity Problems, Vol Ⅱ. New York:Springer-Verlag,2003.
[123]韩继业,修乃华,戚厚铎.非线性互补理论与算法.上海：上海科学技术出版社,2006.
[124]Engelke S. Smoothing-type Methods for Linear Programs. Ph. D. Thesis, Hamburg:Univer-sity of Hamburg,2001.
[125]Kanzow C, Nagel C. Semidefinite programs:new search directions, smoothing-type methods, and numerical results. SIAM J Optim,2002,13:1-23.
[126]修乃华,韩继业.对称锥互补问题.数学进展,2007,36：1-12.
[127]孔令臣.对称锥互补问题的互补函数和价值函数研究.博士学位论文,北京：北京交通大学,2007.
[128]Kong L C, Xiu N H, Han J Y. The solution set structure of monotone linear complementarity problems over second-order cone. Oper Res Lett,2008,36:71-76.
[129]罗自炎.Lyapunov-type对称锥规划.博士学位论文,北京：北京交通大学,2010.
[130]Huang Z H. Han J Y. Non-interior continuation method for solving the monotone semidefinite complementarity problem. Appl Math Optim.2003,47:195-211.
[131]Huang Z H, Hu S L, Han J Y. Convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search. Sci China Math,2009,52:833-848.
[132]Huang Z H, Ni T. Smoothing algorithms for complementarity problems over symmetric cones. Comput Optim Appl,2010,45:557-579.
[133]刘晓红.KK重构函数及其在求解对称锥优化问题中的应用.博士学位论文,天津：天津大学,2010.
[134]Pan S H, Chen J S. A one-parametric class of merit functions for the symmetric cone com-plementarity problem. J Math Anal Appl,2009,355:195-215.
[135]Pan S H, Chen J S. Growth behavior of two classes of merit functions for the symmetric cone complementarity problems. J Optim Theory Appl,2009,141:167-191.
[136]Pan S H, Chen J S. A least-square semismooth Newton method for the second-order cone complementarity problem. Optim Method Softw,2009,26:1-22.
[137]Pan S H, Chen J S. A semismooth Newton method for SOCCPs based on a one-parametric class of SOC complementarity functions. Comput Optim App,2010,45:59-88.
[138]王韵.对称锥优化问题的扰动分析.博士学位论文,大连：大连理工大学,2008.
[139]张立卫.锥约束优化-最优性理论与增(?)"Lagrange方法.北京：科学出版,2010.
[140]刘勇进.对称锥优化的某些光滑函数及其应用.博士学位论文,大连：大连理工大学,2004.
[141]Liu Y J, Zhang L W. Convergence analysis of the augmented Lagrangian method for nonlin-ear second-order cone optimization problems. Nonlinear Anal-Theor,2007,67:1359-1373.
[142]Liu Y J, Zhang L W. On the approximate augmented Lagrangian for nonlinear symmetric cone programming. Nonlinear Anal-Theor,2008,68:1210-1225.
[143]Liu Y J, Zhang L W. Convergence of the augmented Lagrangian method for nonlinear opti-mization problems over second-order cones. J Optim Theory Appl,2008,139:557-575.
[144]顾剑.非凸二阶锥规划问题的非线性重新尺度化方法.博士学位论文,大连：大连理工大学,2009.
[145]李阳.求解非凸半定规划的一类非线性Lagrange方法.博士学位论文,大连：大连理工大学,2009.
[146]刘红卫.半定规划及其应用.博士学位论文,西安：西安电子科技大学,2002.
[147]迟晓妮.二次锥规划的算法研究.博士学位论文,西安：西安电子科技大学,2008.
[148]唐嘉.互补问题的算法研究.博士学位论文,西安：西安电子科技大学,2010.
[149]张襄松.几类优化问题的算法及应用研究.博士学位论文,西安：西安电子科技大学,2011.
[150]刘丽霞.几类对称锥互补问题的算法研究.博士学位论文,西安：西安电子科技大学,2011.
[151]朱见广.互补问题与非线性系统的算法研究.博士学位论文,西安：西安电子科技大学,2011.
[152]李向利.几类带界约束方程组的算法研究.博士学位论文,西安：西安电子科技大学,2011.
[153]郑秀云.变分不等式与无约束优化问题的算法研究.博士学位论文,西安：西安电子科技大学,2011.
[154]房亮.二阶锥规划和二阶锥互补问题的算法研究.博士学位论文,上海：上海交通大学,2010.
[155]Dantzig G B. Linear Programming and Extensions Princeton:Princeton University Press, 1963.
[156]Khachiyan L G. A polynomial algorithm for linear programming (in russian). Dokl Akad Nauk SSSR,1979,244:1093-1096. English translation:Soviet Mathematics Doklady,20: 191-194.
[157]Bland R G, Goldfarb D, Todd M J. The ellipsoid method:a survey. Oper Res,1981,29(6): 1039-1091.
[158]Renegar J. A polynomial-time algorithm, based on Newton's method, for linear program-ming. Math Program (Ser A),1988,40:59-93.
[159]Sonnevend G. An "analytical centre" for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In:Proceedings of the 12th IFIP Conference on System Modelling and Optimization, Budapest 1985. Lecture Notes in Control and Infor-mation Sciences. Berlin:Springer,1986,84:866-876.
[160]Megiddo N. Pathways to the optimal set in linear programming. In:Megiddo N, ed. Progress in Mathematical Programming:Interior Point and Related Methods. New York:Springer, 1989:131-158.
[161]Wright S J. Primal-Dual Interior-Point Methods. Philadelphia:SIAM,1997.
[162]Ye Y. Interior Point Algorithms:Theory and Analysis. New York:John Wiley & Sons,1997.
[163]Roos C, Terlaky T, Vial J-Ph. Interior Point Methods for Linear Optimization, second ed. Boston:Springer,2006.
[164]Potra F A, Wright S J. Interior-point methods. J Comput Appl Math,2000,124:281-302.
[165]Rockafellar R T. Lagrange multipliers and optimality. SIAM Rev,1993,35(2):183-238.
[166]Nemirovski A, Todd M J. Interior-point methods for optimization. Acta Numer,2008,17: 191-234.
[167]Hauser R, Lim Y. Self-scaled barriers for irreducible symmetric cones. SIAM J Optim,2002, 12:715-723.
[168]Goldman A J, Tucker A W. Theory of linear programming. In:Kuhn H W, Tucker A W, eds. Linear Inequalities and Related Systems. Princeton:Princeton University Press.1956: 53-97.
[169]Ye Y, Todd M J, Mizuno S. An O(√nL)-iteration homogeneous and self-dual linear pro-gramming algorithm. Math Oper Res,1994,19:53-67.
[170]Xu X. Hung P F, Ye Y. A simplified homogeneous self-dual linear programming algorithm and its implementation. Annals of Oper Res,1996,62:151-171.
[171]Andersen E D, Ye Y. On a homogeneous algorithm for monotone complementarity system. Math Program,1999,84:375-399.
[172]de Klerk E, Roos C, Terlaky T. Initialization in semidefinite programming via a self-dual skew-symmetric embedding. Oper Res Lett,1997,20:213-221.
[173]Potra F A, Sheng R. On homogeneous interior-point algorithms for semidefinite program-ming. Optim Method Softw,1998,9:161-184.
[174]Luo Z-Q, Sturm J F, Zhang S. Coinic convex programming and self-dual embedding. Optim Method Softw,2000,14:169-218.
[175]Mizuno S. Polynomiality of infeasible-interior-point algorithms for linear programming. Math Program,1994,67:109-119.
[176]Potra F A. An infeasible interior-point predictor-corrector algorithm for linear programming. SIAM J Optim,1996,6:19-32.
[177]Wright S J. An infeasible-interior-point algorithm for linear complementarity problems. Math Program,1994,67:29-51.
[178]Potra F A. A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points. Math Program,1994,67:383-406.
[179]Vanderbei R J. Linear programming:Foundations and extensions, third ed. New York: Springer,2008.
[180]Freund R M. A potential-function reduction algorithm for solving a linear program directly from an infeasible "warm start" Math Program,1991,52:441-466.
[181]Kojima M, Noma T S, Yoshise A. Global convergence in infeasible-interior-point algorithms. Math Program,1994,65:43-72.
[182]Mizuno S, Todd M J, Ye Y. A surface of analytic centers and primal-dual infeasible-interior-point algorithms for linear programming. Math Oper Res,1995,20:135-162.
[183]Billups S C, Ferris M C. Convergence of an infeasible interior-point algorithm from arbitrary positive starting points. SIAM J Optim,1996,6(2):316-325.
[184]Bonnans J F, Potra F A. On the convergence of the iteration sequence of infeasible path following algorithms for linear complementarity problems. Math Oper Res,1997,22(2): 378-407.
[185]Sheng R, Potra F A. A quadratically convergent infeasible-interior-point algorithm for LCP with polynomial complexity. SIAM J Optim,1997,7(2):304-317.
[186]Nesterov Yu, Tuncel L. Local quadratic convergence of polynomial-time interior-point meth-ods for conic optimization problems. Center for Operations Research and Econometrics, November 2009.
[187]Todd M J, Ye Y. Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming. Math Program,1998.81:1-21.
[188]Gowda M S, Sznajder R, Tao J. Some P-properties for linear transformations on Euclidean Jordan algebras. Linear Algebra Appl,2004,393:203-232.
[189]Liu C, Liu H, Cong W. An O(√nL) iteration primal-dual second-order corrector algorithm for linear programming. Optim Lett,2011,5:729-743.
[190]刘长河,刘红卫,朱见广.具有O((?)L)复杂性的Mehrotra型预估-矫正算法.吉林大学学报(理学版),2011,49(4)：633-637.
[191]Klee V, Minty G J. How good is the simplex algorithm? In:Shisha O, ed. Inequalities, Vol Ⅲ. New York:Academic Press,1972:159-175.
[192]Floudas C A, Pardalos P M. Encyclopedia of optimization,2nd ed. New York:Springer, 2009.
[193]Freund R M, Mizuno S. Interior point methods:Current status and future directions. In: Frenk H, Roos C, Terlaky T, Zhang S, eds. High Performance Optimization. Dordrecht: Kluwer Academic,1999:441-466.
[194]Gonzaga C C. Path-following methods for linear programming. SIAM Rev,1992,34:167-224.
[195]Colombo M, Gondzio J. Further development of multiple centrality correctors for interior point methods. Comput Optim Appl,2008,41:277-305.
[196]Cartis C. Some disadvantages of a Mehrotra-tpye primal-dual corrector interior point algo-rithm for linear programming. Appl Numer Math,2009,59:1110-1119.
[197]Cartis C. On the convergence of a primal-dual second-order corrector interior point al-gorithm for linear programming. Technical Report, Numerical Analysis Group, Comput-ing Laboratory, Oxford University, April 2005. Available at http://www.optimization-online.org/DBJITML/2005/03/1097.html.
[198]Ye Y. A class of projective transformations for linear programming. SIAM J Comput,1990, 19:457-466.
[199]Todd M J. Toh K C, Tutuncu R H. On the Nesterov-Todd direction in semidefinite program-ming. SIAM J Optim,1998,8:769-796.
[200]Monteiro R D C. Polynomial convergence of primal-dual algorithms for semidefinite program-ming based on Monteiro and Zhang family of directions. SIAM J Optim,1998,8:797-812.
[201]Monteiro R D C, Terlaky T. Polynomial convergence of a new family of primal-dual algo-rithms for semidefinite programming. SIAM J Optim.1999,9:551-577.
[202]Monteiro R D C. First-and second-order methods for semidefinite programming. Math Pro-gram, Ser B,2003,97:209-244.
[203]Horn R A, Johnson C R. Topics in Matrix Analysis. New York:Cambridge University Press, 1991.
[204]Horn R A, Johnson C R. Matrix Analysis. New York:Cambridge University Press,1990.
[205]Yoshise A. Interior point trajectories and a homogeneous model for nonlinear complemen-tarity problems over symmetric cones. SIAM J Optim,2006,17:1129-1153.
[206]Tsuchiya T. A convergence analysis of the scaling-invariant primal-dual path-following al-gorithms for second-order cone programming. Optim Method Softw,1999,11:141-182.
[207]Monteiro R D C, Terlaky T. Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions. Math Program,2000, 88:61-83.
[208]Vinberg E B. The theory of convex homogeneous cones. Trans Moscow Math Soc,1963,12: 340-403.
[209]Vinberg E B. The structure of the group of automorphisms of a homogeneous convex cone. Trans Moscow Math Soc,1965,13:63-93.
[210]Brenner J L. Matrices of quaternions. Pacific J Math,1951,1:329-335.
[211]Farenick D F, Pidkoich B A F. The spectral theorem in quaternions. Linear Algebra Appl, 2003,371:75-102.
[212]Zhang F. Quaternions and matrices of quaternions. Linear Algebra Appa,1997,251:21-57.
[213]Gowda M S, Tao J. The Cauchy interlacing theorem in simple Euclidean Jordan algebras and some consequences. Linear Multilinear A,2011,59:65-86.
[2]Vandenberghe L, Boyd S. Applications of semidefinite programming. Appl Numer Math, 1999,29:283-299.
[3]Lobo M S, Vandenberghe L, Boyd S, Lebret H. Applications of second-order cone program-ming. Linear Algebra Appl,1998,284:193-228.
[4]Boyd S, Ghaoui L El, Feron E, Balakrishnan V. Linear Matrix Inequalities in System and Control Theory. Philadelphia:SIAM,1994.
[5]Alizadeh F. Interior point methods in semidefinite programming with applications to com-binatorial optimization. SIAM J Optim,1995,5:13-51.
[6]Alizadeh F, Goldfarb D. Second-order cone programming. Math Program,2003,95:3-51.
[7]de Klerk E. Aspects of Semidefinite Programming:Interior Point Algorithms and Selected Applications. Dordrecht:Kluwer Academic Publishers,2002.
[8]Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorica, 1984,4:373-395.
[9]Nesterov Yu, Nemirovski A. Polynomial barrier methods in convex programming. Ekonomika i Matem Metody,1988,24:1084-1091.
[10]Nesterov Yu, Nemirovski A. A general approach to polynomial-time algorithms design for convex programming. Moscow:USSR Academy of Sciences, Central Economic & Mathe-matic Institute,1988.
[11]Nesterov Yu, Nemirovski A. Self-concordant functions and polynomial time methods in con-vex programming. Moscow:USSR Academy of Sciences, Central Economic & Mathematic Institute,1989.
[12]Nesterov Yu, Nemirovski A. Optimization over positive semidefinite matrices:Mathematical background and user's manual. Moscow:USSR Academy of Sciences, Central Economic & Mathematic Institute,1990.
[13]Nesterov Yu, Nemirovski A. Conic formulation of a convex programming problem and dual-ity. Moscow:USSR Academy of Sciences, Central Economic & Mathematic Institute,1991.
[14]Nesterov Yu, Nemirovskii A. Interior-Point Polynomial Algorithms in Convex Programming. Philadelphia:SIAM:1994.
[15]Alizadeh F. Combinatorial Optimization with Interior-Point Methods and Semi-Definite Matrices. Ph. D. Thesis, Minneapolis:University of Minnesota,1991.
[16]Alizadeh F. Optimization over positive semi-definite cone:Interior-point methods and com-binatorial applications. In:Pardalos P M, ed. Advances in Optimization and Parallel Com-puting. Amsterdam:North-Holland,1992:1-25.
[17]Goldfarb D, Liu S, Wang S. A logarithmic barrier function algorithm for quadratically con-strained convex quadratic programming. SIAM J Optim,1991,1:252-267
[18]Jarre F. On the convergence of the method of analytic centers when applied to convex quadratic programs. Math Program,1991,49:341-358.
[19]Mehrotra S, Sun J. A method of analytic centers for quadratically constrained convex quadratic programs SIAM J Numer Anal,1991,28:529-544.
[20]Jarre F. An interior-point method for minimizing the maximum eigenvalue of a linear com-bination of matrices. SIAM J Control Optim,1993,31:1360-1377.
[21]Alizadeh F, Haeberly J A, Overton M L. Primal-dual interior-point methods for semidefinite programming:Convergence rates, stability and numerical results. SIAM J Optim,1998,8: 746-768.
[22]Adler I, Alizadeh F. Primal-dual interior point algorithms for convex quadratically con-strained and semidefinite optimization problems. Technical Report RRR 46-95, RUTCOR, Rutgers University, December 1995.
[23]Alizadeh F, Schmieta S H. Optimization with semidefinite, quadratic and linear constraints. Technical Report RRR 23-97, RUTCOR, Rutgers University, November 1997.
[24]Nemirovski A, Scheinberg K. Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems. Math Program,1996,72:273-289.
[25]Tsuchiya T. A polynomial primal-dual path-following algorithm for second-order cone pro-gramming. Technical Report 649, The Institute of Statistical Mathematics, Tokyo,1997.
[26]Nemirovski A. What can be expressed via conic quadratic and semidefinite programming? Talk presented at RUTCOR weekly seminar, Rutgers University, August 1999.
[27]Goemans M X, Williamson D P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM,1995,42:1115-1145.
[28]Kojima M, Shindoh S, Hara S. Interior poit methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J Optim,1997,7:86-125.
[29]Monteiro R D C. Primal-dual path-following algorithms for semidefinite programming. SIAM J Optim,1997,7:663-678.
[30]Monteiro R D C. Zhang Y. A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming. Math Program.1998,81: 281-299.
[31]Helmberg C. Rendl F. Vanderbei R J. Wolkowicz H. An interior-point method for semidefinite programming. SIAM J Optim,1996,6:342-361.
[32]Pardalos P M. Wolkowicz H, eds. Topics in Semidefinite and Interior-Point Methods. Amer-ican Math Society,1998.
[33]Wolkowicz H. Saigal R, Vandenberghe L, eds. Handbook of Semidefinite Programming:The-ory, Algorithms, and Applications. Dordrecht:Kluwer Academic Publishers,2000.
[34]Alizadeh F, Schmieta S. Symmetric cones, potential reduction methods and word-by-word extensions. In:Wolkowicz H, Saigal R, Vandenberghe L, eds. Handbook of Semidefinite Pro-gramming:Theory, Algorithms, and Applications. Dordrecht:Kluwer Academic Publishers, 2000:195-233.
[35]Nesterov Yu, Todd M J. Self-scaled barriers and interior-point methods for convex program-ming. Math Oper Res,1997,22:1-42.
[36]Nesterov Yu, Todd M J. Primal-dual interior-point methods for self-scaled cones. SIAM J Optim,1998,8:324-364.
[37]Giiler O. Barrier functions in interior-point methods. Math Oper Res,1996,21:860-885.
[38]Faraut J, Koranyi A. Analysis on Symmetric Cones. Oxford:Oxford University Press,1994.
[39]Faybusovich L. Linear systems in Jordan algebras and primal-dual interior-point algorithms. J Comput Appl Math,1997,86:149-175.
[40]Faybusovich L. Euclidean Jordan algebras and interior-point algorithms. Positivity,1997,1: 331-357.
[41]Faybusovich L. A Jordan-algebraic approach to potential-reduction algorithms. Math Z, 2002,239:117-129.
[42]Faybusovich L. Several Jordan-algebraic aspects of optimization. Optimization,2008,57(3): 379-393.
[43]Faybusovich L, Arana R. A long-step primal-dual algorithm for symmetric programming problem. Systems Control Lett,2001,43:3-7.
[44]Schmieta S H, Alizadeh F. Associative and Jordan algebras, and polynomial time interior point algorithms for symmetric cones. Math Oper Res,2001,26:543-564.
[45]Schmieta S H, Alizadeh F. Extension of primal-dual interior-point algorithm to symmetric cones. Math Program,2003,96:409-438.
[46]Muramatsu M. On a commutative class of search directions for linear programming over symmetric cones. J Optim Theory Appl,2002,112:595-625.
[47]Andersen E D, Roos C, Terlaky T. On implementing a primal-dual interior-point method for conic quadratic optimization. Math Program,2003,95:249-277.
[48]Lu Y, Yuan Y X. An interior-point trust, region algorithm for general cone prognnming. SIAM J Optim.2007,18:65-8G.
[49]Rangarajan B. Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J Optim,2006,16:1211-1229.
[50]Alizadeh F, Xia Y. The Q method for symmetric cone programming. J Optim Theory Appl, 2011,149:102-137.
[51]Gu G, Zangiabadi M, Roos C. Full Nesterov-Todd step infeasible interior-point method for symmetric optimization. Eur J Oper Res,2011,214:473-484.
[52]Nesterov Yu, Tuncel L. Local quadratic convergence of polynomial-time interior-point meth-ods for conic optimization problems. Technical Report, Center for Operations Research and Econometrics, Belgium, November 2009.
[53]Chua C B. Relating homogeneous cones and positive definite cones via T-algebras. SIAM J Optim,2003,14:500-506.
[54]Chua C B. A T-algebraic approach to primal-dual interior-point algorithms. SIAM J Optim, 2009,20:503-523.
[55]Giiler O, Tungel L. Characterization of the barrier parameter of homogeneous convex cones. Math Program,1998,81:55-76.
[56]Tuncel L, Xu S. On the homogeneous cones, the Caratheodory number, and the duality mapping. Math Oper Res,2001,26:234-247.
[57]Truong V A, Tuncel L. Geometry of homogeneous convex cones, duality mapping, and op-timal self-concordant barriers. Math Program,2004,100:295-316.
[58]Shevchenko O. Recursive Construction of Optimal Self-Concordant Barriers for Homoge-neous Cones. Journal of Optimization Theory and Applications,2009,140:339-354.
[59]Kong L C, Tuncel L, Xiu X H. Existence and uniqueness of solutions for homogeneous cone complementarity problems. J Optim Theory Appl,2012, DOI:10.1007/s10957-011-9971-7.
[60]卢楠.对称锥和齐次锥上非单调互补问题的理论和算法.博十学位论文,天津：天津大学,2010.
[61]Monteiro R D C, Adler I. Polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension. Technical Report ESRC 88-8, Industrial Engineering and Operations Research Department, University of California-Berkeley, March 1988.
[62]Kojima M, Mizuno S, Yoshise A. A primal-dual interior point algorithm for linear pro-gramming. In:Megiddo N, ed. Progress in Mathematical Programming:Interior Point and Related Methods. New York:Springer,1989:29-47.
[63]Monteiro R D C, Adler I. Interior path following primal-dual algorithms, Part Ⅰ:Linear programming. Math Program,1989,44:27-41.
[64]Monteiro R D C, Adler I. Interior path-following primal-dual algorithms, Part Ⅱ:Convex quadratic programming. Math Program.1989,44:43-66.
[65]Kojima M, Mizuno S, Yoshise A. A polynomial-time algorithm for a class of linear comple-mentarity problems. Math Program,1989,44:1-26.
[66]Andersen E D, Gondzio J. Meszaros C, Xu X. Implementation of interior point methods for large scale linear programming. In:Terlaky T, ed. Interior Point Methods in Mathematical Programming. Dordrecht:Kluwer Academic Publisher,1996:189-252.
[67]Gondzio J, Terlaky T. A computational view of interior point methods for linear program-ming. In:Beasley J, ed. Advances in Linear and Integer Programming. Oxford:Oxford University Press,1996:103-144.
[68]Mizuno S, Todd M J, Ye Y. On adaptive step primal-dual interior-point algorithms for linear programming. Math Oper Res,1993,18:964-981.
[69]Peng J M, Roos C, Terlaky T. Self-regular functions and new search directions for linear and semidefinite optimization. Math Program, Ser A,2002,93:129-171.
[70]Bai Y Q, Roos C. A primal-dual interior-point method based on a new kernel function with linear growth rate. In:Proceedings of Industrial Optimization Symposium and Optimization Day. Australia,2002.
[71]Bai Y Q, Roos C, El ghami M. A new efficient large-update primal-dual interior-point method based on a finite barrier. SIAM J Optim,2003.13:766-782.
[72]Bai Y Q, El ghami M, Roos C. A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J Optim,2004,15:101-128.
[73]白延琴.锥优化的基于核函数的内点算法.北京：科学出版社,2010.
[74]Bai Y Q, Wang G Q. Primal-dual interior-point algorithms for second-order cone optimiza-tion based on a new parametric kernel function. Acta Math Sin,2007,23:2027-2042.
[75]Bai Y Q, Wang G Q, Roos C. Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions. Nonlinear Anal-Theor,2009,70:3584-3602.
[76]王国强.基于一个有限罚函数的二阶锥优化的原始对偶内点算法.运筹学报,2007,11：18-31.
[77]Wang G Q, Bai Y Q. A primal-dual interior-point algorithm for second-order cone optimiza-tion with full Nesterov-Todd step. Appl Math Comput,2009,215:1047-1061.
[78]Wang G Q, Bai Y Q. A class of polynomial interior point algorithms for the cartesian p-matrix linear complementarity problem over symmetric cones. J Optim Theory Appl,2012, DOI:10.1007/s10957-011-9938-8.
[79]Hung P. Ye Y. An asymptotical O(√nL)-iteration path-following linear programming algo-rithm that use wide neighborhoods. SIAM J Optim,1996,6:570-586.
[80]Peng J M, Terlaky T, Zhao Y B. A predictor-corrector algorithm for linear optimization based on a specific self-regular proximity function. SIAM J Optim.2005.15:1105-1127.
[81]Potra F A. A superlinearly convergent predictor-corrector method for degenerate LCP in a wide neighborhood of the central path with O(√nL)-iteration complexity. Math Program, 2004,100:317-337.
[82]Ai W. Neighborhood-following algorithms for linear programming. Sci China Math,2004, 47:812-820.
[83]Ai W, Zhang S. An O(√nL) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP. SIAM J Optim,2005,16:400-417.
[84]Feng Z, Fang L. A wide neighbourhood interior-point method with O(√nL) iteration-complexity bound for semidefinite programming. Optimization,2010,59:1235-1246.
[85]Li Y, Terlaky T. A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with O(√nlog Tr(X°s°/ε)iteration complexity. SIAM J Optim, 2010,20:2853-2875.
[86]Mehrotra S. On the implementation of a primal-dual interior point method. SIAM J Optim, 1992,2:575-601.
[87]Gondzio J. Multiple centrality corrections in a primal-dual method for linear programming. Comput Optim Appl,1996,6:137-156.
[88]Vanderbei R J. LOQO user's manual-version 3.10. Optim Method Softw,1999,12:485-514.
[89]Andersen E D. The Mosek interior point optimizer for linear programming:an implemen-tation of the homogeneous algorithm. In:Frenk H, Roos K, Terlaky T, Zhang S, eds. High performance optimization. Dordrecht:Kluwer Academic Publisher,1999:197-232.
[90]Zhang Y. Solving large-scale linear programmes by interior point methods under the Matlab environment. Optim Method Softw,1999,10:1-31.
[91]Czyzyk J, Mehrtotra S, Wagner M, Wright S J. PCx:an interior-point code for linear programming. Optim Method Softw,1999,11/12:397-430.
[92]Gondzio J. HOPDM (version 2.12)-a fast LP solver based on a primal-dual interior point method. Eur J Oper Res,1995,85(1):221-225.
[93]Sturm J F. Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optim Method Softw,1999,11:625-653.
[94]Toh K C, Todd M J, Tutuncu R H. SDPT3-a Matlab software package for semidefinite programming. Optim Methods Softw,1999,11:545-581.
[95]Fujisawa K, Kojima M. Xakata K, Yamashita M. SDPA (SemiDefmite Programming Al-gorithn) User's-version 6.2.0. Research Report B-308, Department of Mathematical and Computing Sciences. Tokyo Institute of Technology, December 1995, Revised September 2004.
[96]NETLIB:A Repository of Linear Programming Test Problems.http://www.netlib.org/.
[97]Nocedal J, Wright S J. Numerical Optimization. New York:Springer,1999.
[98]Zhang Y, Zhang D. On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms. Math Program,1995,68:303-318.
[99]Zhang D, Zhang Y. A Mehrotra-type predictor-corrector algorithm with polynomiality and Q-subquadratic convergence. Ann Oper Res,1996,62:131-150.
[100]Zhang J, Zhang K C. Polynomial complexity of an interior point algorithm with a second order corrector step for symmetric cone programming. Math Meth Oper Res,2011,73: 75-90.
[101]Salahi M, Peng J M, Terlaky T. On Mehrotra-type predictor-corrector algorithms. SIAM J Optim,2007,18:1377-1397.
[102]Salahi M, Mahdavi-Amiri N. Polynomial time second order Mehrotra-type predictor-corrector algorithms. Appl Math Comput,2006,183:646-658.
[103]Koulaei M H, Terlaky T. On the complexity analysis of a Mehrotra-type primal-dual feasible algorithm for semidefinite optimization. Optim Method Softw,2010,25:467-485.
[104]Liu C, Liu H, Liu X. Polynomial convergence of second-order Mehrotra-type predictor-corrector algorithms over symmetric cones. J Optim Theory Appl,2012, DOI: 10.1007/s10957-012-0018-5.
[105]Lustig I J. Feasibility issues in a primal-dual interior-method for linear programming. Math Program,1991,49:145-162.
[106]Tanabe K. Centered Newton method for linear programming:Interior and 'exterior' point method. In:Tone K, ed. New Methods for Linear Programming 3. The Institute of Statistical Mathematics, Tokyo, Japan.1990:98-100 (In Japanese).
[107]Kojima M, Megiddo N, Mizuno S. A primal-dual infeasible-interior-point algorithm for linear programming. Math Program,1993,61:263-280.
[108]Zhang Y. On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem. SIAM J Optim,1994,4:208-227.
[109]Kojima M, Shida M, Shindoh S. Global and local convergence of predictor-corrector infeasible-interior-point algorithms for semidefinite programs. Research Report 305, Depart-ment of Mathematical and Computing Sciences, Tokyo Institute of Technology, October 1995.
[110]Kojima M, Shida M, Shindoh S. Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs. Math Program,1998,80:129-160.
[111]Zhang Y. On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J Optim.1998.8:365-386.
[112]Potra F A, Sheng R. A superlinearly convergent primal-dual infeasible-interior-point algo-rithm for semidefinite programming. SIAM J Optim,1998.8:1007-1028.
[113]Potra F A, Sheng R. Superlinear convergence of interior-point algorithms for semidefinite programming. J Optim Theory Appl,1998,99:103-119.
[114]迟晓妮,刘三阳.二次锥规划的一种原-对偶不可行内点算法.西安电子科技大学学报,2007,34：307-311.
[115]Chi X, Liu S. An infeasible-interior-point predictor-corrector algorithm for the second-order cone program. Acta Math Sci,2008,28:551-559.
[116]Rangarajan B, Todd M T. Convergence of infeasible-interior-point methods for self-scaled conic programming. Technical Report 1388, Operations Research and Industrial Engineering, Cornell University, October 2003.
[117]Roos C. A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM J Optim,2006,16:1110-1136.
[118]Mansouri H, Roos C. A new full-Newton step O(n) infeasible interior-point algorithm for semidefinite optimization. Numer Algor,2009,52:225-255.
[119]Mansouri H, Zangiabadi M, Pirhaji M. A full-Newton step O(n) infeasible-interior-point algorithm for linear complementarity problems. Nonlinear Anal-Real,2011,12:545-561.
[120]Liu Z, Sun W. A full-NT-step infeasible interior-point algorithm for SDP based on kernel functions. Appl Math Comput,2011,217:4990-4999.
[121]Facchinei F, Pang J S. Finite-dimensional Variational Inequalities and Complementarity Problems, Vol Ⅰ. New York:Springer-Verlag,2003.
[122]Facchinei F, Pang J S. Finite-dimensional Variational Inequalities and Complementarity Problems, Vol Ⅱ. New York:Springer-Verlag,2003.
[123]韩继业,修乃华,戚厚铎.非线性互补理论与算法.上海：上海科学技术出版社,2006.
[124]Engelke S. Smoothing-type Methods for Linear Programs. Ph. D. Thesis, Hamburg:Univer-sity of Hamburg,2001.
[125]Kanzow C, Nagel C. Semidefinite programs:new search directions, smoothing-type methods, and numerical results. SIAM J Optim,2002,13:1-23.
[126]修乃华,韩继业.对称锥互补问题.数学进展,2007,36：1-12.
[127]孔令臣.对称锥互补问题的互补函数和价值函数研究.博士学位论文,北京：北京交通大学,2007.
[128]Kong L C, Xiu N H, Han J Y. The solution set structure of monotone linear complementarity problems over second-order cone. Oper Res Lett,2008,36:71-76.
[129]罗自炎.Lyapunov-type对称锥规划.博士学位论文,北京：北京交通大学,2010.
[130]Huang Z H. Han J Y. Non-interior continuation method for solving the monotone semidefinite complementarity problem. Appl Math Optim.2003,47:195-211.
[131]Huang Z H, Hu S L, Han J Y. Convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search. Sci China Math,2009,52:833-848.
[132]Huang Z H, Ni T. Smoothing algorithms for complementarity problems over symmetric cones. Comput Optim Appl,2010,45:557-579.
[133]刘晓红.KK重构函数及其在求解对称锥优化问题中的应用.博士学位论文,天津：天津大学,2010.
[134]Pan S H, Chen J S. A one-parametric class of merit functions for the symmetric cone com-plementarity problem. J Math Anal Appl,2009,355:195-215.
[135]Pan S H, Chen J S. Growth behavior of two classes of merit functions for the symmetric cone complementarity problems. J Optim Theory Appl,2009,141:167-191.
[136]Pan S H, Chen J S. A least-square semismooth Newton method for the second-order cone complementarity problem. Optim Method Softw,2009,26:1-22.
[137]Pan S H, Chen J S. A semismooth Newton method for SOCCPs based on a one-parametric class of SOC complementarity functions. Comput Optim App,2010,45:59-88.
[138]王韵.对称锥优化问题的扰动分析.博士学位论文,大连：大连理工大学,2008.
[139]张立卫.锥约束优化-最优性理论与增(?)"Lagrange方法.北京：科学出版,2010.
[140]刘勇进.对称锥优化的某些光滑函数及其应用.博士学位论文,大连：大连理工大学,2004.
[141]Liu Y J, Zhang L W. Convergence analysis of the augmented Lagrangian method for nonlin-ear second-order cone optimization problems. Nonlinear Anal-Theor,2007,67:1359-1373.
[142]Liu Y J, Zhang L W. On the approximate augmented Lagrangian for nonlinear symmetric cone programming. Nonlinear Anal-Theor,2008,68:1210-1225.
[143]Liu Y J, Zhang L W. Convergence of the augmented Lagrangian method for nonlinear opti-mization problems over second-order cones. J Optim Theory Appl,2008,139:557-575.
[144]顾剑.非凸二阶锥规划问题的非线性重新尺度化方法.博士学位论文,大连：大连理工大学,2009.
[145]李阳.求解非凸半定规划的一类非线性Lagrange方法.博士学位论文,大连：大连理工大学,2009.
[146]刘红卫.半定规划及其应用.博士学位论文,西安：西安电子科技大学,2002.
[147]迟晓妮.二次锥规划的算法研究.博士学位论文,西安：西安电子科技大学,2008.
[148]唐嘉.互补问题的算法研究.博士学位论文,西安：西安电子科技大学,2010.
[149]张襄松.几类优化问题的算法及应用研究.博士学位论文,西安：西安电子科技大学,2011.
[150]刘丽霞.几类对称锥互补问题的算法研究.博士学位论文,西安：西安电子科技大学,2011.
[151]朱见广.互补问题与非线性系统的算法研究.博士学位论文,西安：西安电子科技大学,2011.
[152]李向利.几类带界约束方程组的算法研究.博士学位论文,西安：西安电子科技大学,2011.
[153]郑秀云.变分不等式与无约束优化问题的算法研究.博士学位论文,西安：西安电子科技大学,2011.
[154]房亮.二阶锥规划和二阶锥互补问题的算法研究.博士学位论文,上海：上海交通大学,2010.
[155]Dantzig G B. Linear Programming and Extensions Princeton:Princeton University Press, 1963.
[156]Khachiyan L G. A polynomial algorithm for linear programming (in russian). Dokl Akad Nauk SSSR,1979,244:1093-1096. English translation:Soviet Mathematics Doklady,20: 191-194.
[157]Bland R G, Goldfarb D, Todd M J. The ellipsoid method:a survey. Oper Res,1981,29(6): 1039-1091.
[158]Renegar J. A polynomial-time algorithm, based on Newton's method, for linear program-ming. Math Program (Ser A),1988,40:59-93.
[159]Sonnevend G. An "analytical centre" for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In:Proceedings of the 12th IFIP Conference on System Modelling and Optimization, Budapest 1985. Lecture Notes in Control and Infor-mation Sciences. Berlin:Springer,1986,84:866-876.
[160]Megiddo N. Pathways to the optimal set in linear programming. In:Megiddo N, ed. Progress in Mathematical Programming:Interior Point and Related Methods. New York:Springer, 1989:131-158.
[161]Wright S J. Primal-Dual Interior-Point Methods. Philadelphia:SIAM,1997.
[162]Ye Y. Interior Point Algorithms:Theory and Analysis. New York:John Wiley & Sons,1997.
[163]Roos C, Terlaky T, Vial J-Ph. Interior Point Methods for Linear Optimization, second ed. Boston:Springer,2006.
[164]Potra F A, Wright S J. Interior-point methods. J Comput Appl Math,2000,124:281-302.
[165]Rockafellar R T. Lagrange multipliers and optimality. SIAM Rev,1993,35(2):183-238.
[166]Nemirovski A, Todd M J. Interior-point methods for optimization. Acta Numer,2008,17: 191-234.
[167]Hauser R, Lim Y. Self-scaled barriers for irreducible symmetric cones. SIAM J Optim,2002, 12:715-723.
[168]Goldman A J, Tucker A W. Theory of linear programming. In:Kuhn H W, Tucker A W, eds. Linear Inequalities and Related Systems. Princeton:Princeton University Press.1956: 53-97.
[169]Ye Y, Todd M J, Mizuno S. An O(√nL)-iteration homogeneous and self-dual linear pro-gramming algorithm. Math Oper Res,1994,19:53-67.
[170]Xu X. Hung P F, Ye Y. A simplified homogeneous self-dual linear programming algorithm and its implementation. Annals of Oper Res,1996,62:151-171.
[171]Andersen E D, Ye Y. On a homogeneous algorithm for monotone complementarity system. Math Program,1999,84:375-399.
[172]de Klerk E, Roos C, Terlaky T. Initialization in semidefinite programming via a self-dual skew-symmetric embedding. Oper Res Lett,1997,20:213-221.
[173]Potra F A, Sheng R. On homogeneous interior-point algorithms for semidefinite program-ming. Optim Method Softw,1998,9:161-184.
[174]Luo Z-Q, Sturm J F, Zhang S. Coinic convex programming and self-dual embedding. Optim Method Softw,2000,14:169-218.
[175]Mizuno S. Polynomiality of infeasible-interior-point algorithms for linear programming. Math Program,1994,67:109-119.
[176]Potra F A. An infeasible interior-point predictor-corrector algorithm for linear programming. SIAM J Optim,1996,6:19-32.
[177]Wright S J. An infeasible-interior-point algorithm for linear complementarity problems. Math Program,1994,67:29-51.
[178]Potra F A. A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points. Math Program,1994,67:383-406.
[179]Vanderbei R J. Linear programming:Foundations and extensions, third ed. New York: Springer,2008.
[180]Freund R M. A potential-function reduction algorithm for solving a linear program directly from an infeasible "warm start" Math Program,1991,52:441-466.
[181]Kojima M, Noma T S, Yoshise A. Global convergence in infeasible-interior-point algorithms. Math Program,1994,65:43-72.
[182]Mizuno S, Todd M J, Ye Y. A surface of analytic centers and primal-dual infeasible-interior-point algorithms for linear programming. Math Oper Res,1995,20:135-162.
[183]Billups S C, Ferris M C. Convergence of an infeasible interior-point algorithm from arbitrary positive starting points. SIAM J Optim,1996,6(2):316-325.
[184]Bonnans J F, Potra F A. On the convergence of the iteration sequence of infeasible path following algorithms for linear complementarity problems. Math Oper Res,1997,22(2): 378-407.
[185]Sheng R, Potra F A. A quadratically convergent infeasible-interior-point algorithm for LCP with polynomial complexity. SIAM J Optim,1997,7(2):304-317.
[186]Nesterov Yu, Tuncel L. Local quadratic convergence of polynomial-time interior-point meth-ods for conic optimization problems. Center for Operations Research and Econometrics, November 2009.
[187]Todd M J, Ye Y. Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming. Math Program,1998.81:1-21.
[188]Gowda M S, Sznajder R, Tao J. Some P-properties for linear transformations on Euclidean Jordan algebras. Linear Algebra Appl,2004,393:203-232.
[189]Liu C, Liu H, Cong W. An O(√nL) iteration primal-dual second-order corrector algorithm for linear programming. Optim Lett,2011,5:729-743.
[190]刘长河,刘红卫,朱见广.具有O((?)L)复杂性的Mehrotra型预估-矫正算法.吉林大学学报(理学版),2011,49(4)：633-637.
[191]Klee V, Minty G J. How good is the simplex algorithm? In:Shisha O, ed. Inequalities, Vol Ⅲ. New York:Academic Press,1972:159-175.
[192]Floudas C A, Pardalos P M. Encyclopedia of optimization,2nd ed. New York:Springer, 2009.
[193]Freund R M, Mizuno S. Interior point methods:Current status and future directions. In: Frenk H, Roos C, Terlaky T, Zhang S, eds. High Performance Optimization. Dordrecht: Kluwer Academic,1999:441-466.
[194]Gonzaga C C. Path-following methods for linear programming. SIAM Rev,1992,34:167-224.
[195]Colombo M, Gondzio J. Further development of multiple centrality correctors for interior point methods. Comput Optim Appl,2008,41:277-305.
[196]Cartis C. Some disadvantages of a Mehrotra-tpye primal-dual corrector interior point algo-rithm for linear programming. Appl Numer Math,2009,59:1110-1119.
[197]Cartis C. On the convergence of a primal-dual second-order corrector interior point al-gorithm for linear programming. Technical Report, Numerical Analysis Group, Comput-ing Laboratory, Oxford University, April 2005. Available at http://www.optimization-online.org/DBJITML/2005/03/1097.html.
[198]Ye Y. A class of projective transformations for linear programming. SIAM J Comput,1990, 19:457-466.
[199]Todd M J. Toh K C, Tutuncu R H. On the Nesterov-Todd direction in semidefinite program-ming. SIAM J Optim,1998,8:769-796.
[200]Monteiro R D C. Polynomial convergence of primal-dual algorithms for semidefinite program-ming based on Monteiro and Zhang family of directions. SIAM J Optim,1998,8:797-812.
[201]Monteiro R D C, Terlaky T. Polynomial convergence of a new family of primal-dual algo-rithms for semidefinite programming. SIAM J Optim.1999,9:551-577.
[202]Monteiro R D C. First-and second-order methods for semidefinite programming. Math Pro-gram, Ser B,2003,97:209-244.
[203]Horn R A, Johnson C R. Topics in Matrix Analysis. New York:Cambridge University Press, 1991.
[204]Horn R A, Johnson C R. Matrix Analysis. New York:Cambridge University Press,1990.
[205]Yoshise A. Interior point trajectories and a homogeneous model for nonlinear complemen-tarity problems over symmetric cones. SIAM J Optim,2006,17:1129-1153.
[206]Tsuchiya T. A convergence analysis of the scaling-invariant primal-dual path-following al-gorithms for second-order cone programming. Optim Method Softw,1999,11:141-182.
[207]Monteiro R D C, Terlaky T. Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions. Math Program,2000, 88:61-83.
[208]Vinberg E B. The theory of convex homogeneous cones. Trans Moscow Math Soc,1963,12: 340-403.
[209]Vinberg E B. The structure of the group of automorphisms of a homogeneous convex cone. Trans Moscow Math Soc,1965,13:63-93.
[210]Brenner J L. Matrices of quaternions. Pacific J Math,1951,1:329-335.
[211]Farenick D F, Pidkoich B A F. The spectral theorem in quaternions. Linear Algebra Appl, 2003,371:75-102.
[212]Zhang F. Quaternions and matrices of quaternions. Linear Algebra Appa,1997,251:21-57.
[213]Gowda M S, Tao J. The Cauchy interlacing theorem in simple Euclidean Jordan algebras and some consequences. Linear Multilinear A,2011,59:65-86.