Advanced Search
Article Contents
Article Contents

On the extension of an arc-search interior-point algorithm for semidefinite optimization

  • * Corresponding author: Behrouz Kheirfam

    * Corresponding author: Behrouz Kheirfam 
Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by
  • This paper concerns an extension of the arc-search strategy that was proposed by Yang [26] for linear optimization to semidefinite optimization case. Based on the Nesterov-Todd direction as Newton search direction it is shown that the complexity bound of the proposed algorithm is of the same order as that of the corresponding algorithm for linear optimization. Some preliminary numerical results indicate that our primal-dual arc-search path-following method is promising for solving the semidefinite optimization problems.

    Mathematics Subject Classification: 90C51.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  Numerical results for Example 1

    $\varepsilon$ MTYAlgor NewAlgor
    Iter. CPU DGAP Iter. CPU DGAP
    $10^{-6}$ 55 0.1882 $4.4981e^{-6}$ 11 0.0729 $2.1703e^{-6}$
    $10^{-8}$ 73 0.2476 $4.7261e^{-8}$ 13 0.0679 $9.6585e^{-9}$
     | Show Table
    DownLoad: CSV

    Table 2.  Numerical results for Example 2

    $n\times m$ MTYAlgor NewAlgor
    Iter. CPU Iter. CPU
    $10\times20$ 97.2 3.4915 28.8 1.1028
    $30\times30$ 117.3 18.7385 32.3 5.9383
    $25\times40$ 116.2 67.5448 33.7 23.2533
    $40\times20$ 115.9 70.7626 33.1 24.0481
    $50\times50$ 136.7 179.9818 35.4 87.9356
     | Show Table
    DownLoad: CSV
  •   F. Alizadeh, Combinatorial Optimization with Interior-Point Methods and Semi-definite Matrices, Ph. D. thesis, Computer Science Department, University of Minnesota, Minneapolis, MN, 1991.
      F. Alizadeh , Interior-point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim., 5 (1995) , 13-51.  doi: 10.1137/0805002.
      F. Alizadeh , J.A. Haeberly  and  M. L. Overton , Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results, SIAM J. Optim., 8 (1998) , 746-768.  doi: 10.1137/S1052623496304700.
      S. Boyd, L. Ghoui, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, SIAM, Philadelphia, PA, 1994. doi: 10.1137/1.9781611970777.
      E. De Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications, Kluwer Academic Publishers, Dordrecht, Netherlands, 2002. doi: 10.1007/b105286.
      D. Herbison-Evans, Solving quartics and cubics for graphics Technical Report, R94-487, Basser Department of Computer Science, University of Sydney, Sydney, Australia, 1994. doi: 10.1016/B978-0-12-543457-7.50009-7.
      B. Kheirfam , An arc-search interior point method in the $\mathcal{N}_{∞}^-$ neighborhood for symmetric optimization, Fundam. Inform., 146 (2016) , 255-269.  doi: 10.3233/FI-2016-1385.
      M. Kojima , S. Shindoh  and  S. Hara , Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices, SIAM J. Optim., 7 (1997) , 86-125.  doi: 10.1137/S1052623494269035.
      M. Kojima , M. Shida  and  S. Shindoh , Local convergence of predictor-corrector infeasible interior-point algorithm for SDPs and SDLCPs, Math. Program., 80 (1998) , 129-160.  doi: 10.1007/BF01581723.
      Y. Li  and  T. Terlaky , A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with $O(\sqrt{n}\log(\frac{{\rm tr}(X^0S^0)}{ε}))$ iteration complexity, SIAM J. Optim., 8 (2010) , 2853-2875.  doi: 10.1137/080729311.
      H. W. Liu , C. H. Liu  and  X. M. Yang , New complexity analysis of a Mehrotra-type predictor-corrector algorithm for semidefinite programming, Optim. Methods Softw., 28 (2013) , 1179-1194.  doi: 10.1080/10556788.2012.679270.
      S. Mizuno , M. J. Todd  and  Y. Ye , On adaptive-step primal-dual interior-point algorithms for linear programming, Math. Oper. Res., 18 (1993) , 964-981.  doi: 10.1287/moor.18.4.964.
      R. D. C. Monteiro  and  I. Adler , Interior path following primal-dual algorithm. Part Ⅰ: linear programming, Math. Program., 44 (1989) , 27-41.  doi: 10.1007/BF01587075.
      R. D. C. Monteiro , Polynomial convergence of primal-dual algorithms for semidefinite programming based on the Monteiro and Zhang family of directions, SIAM J. Optim., 8 (1998) , 797-812.  doi: 10.1137/S1052623496308618.
      R. D. C. Monteiro  and  Y. Zhang , A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming, Math. Program., 81 (1998) , 281-299.  doi: 10.1007/BF01580085.
      Y. E. Nesterov and A. S. Nemirovskii, Interior Point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics, Vol. 13 SIAM, Philadelphia, USA, 1994. doi: 10.1137/1.9781611970791.
      Y. E. Nesterov  and  M. J. Todd , Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res., 22 (1997) , 1-42.  doi: 10.1287/moor.22.1.1.
      Y. E. Nesterov  and  M. J. Todd , Primal-dual interior point methods for self-scaled cones, SIAM J. Optim., 8 (1998) , 324-364.  doi: 10.1137/S1052623495290209.
      F. A. Potra  and  R. Sheng , A superlinearly convergent primal-dual infeasible -interior-point algorithm for semidefinite programming, SIAM J. Optim., 8 (1998) , 1007-1028.  doi: 10.1137/S1052623495294955.
      M. J. Todd , K. C. Toh  and  R. H. $T\ddot u\ddot unc\ddot u$ , On the Nesterov-Todd direction in semidefinite programming, SIAM J. Optim., 8 (1998) , 769-796.  doi: 10.1137/S105262349630060X.
      S. Veeraraghavan  and  D. A. Mazziotti , Semidefinite programming formulation of linear-scaling electronic structure theories Artic, Phys. Rev. A, 92 (2015) , 215-220. 
      H. Wolkowicz, R. Saigal and L. Vandenberghe, Handbook of Semidefinite Programming, International Series in Operations Research and Management Science (27) Kluwer Academic Publishers, Boston, MA, 2000. doi: 10.1007/978-1-4615-4381-7.
      S. Wright, Primal-Dual Interior-point Methods, SIAM, Philadelphia, 1997. doi: 10.1137/1.9781611971453.
      Y. Yang, Arc-search path-following interior-point algorithm for linear programming, Optimization online, 2009.
      Y. Yang , A polynomial arc-search interior-point algorithm for convex quadratic programming, Eur. J. Oper. Res., 215 (2011) , 25-38.  doi: 10.1016/j.ejor.2011.06.020.
      Y. Yang , A polynomial arc-search interior-point algorithm for linear programming, J. Optim. Theory Appl., 158 (2013) , 859-873.  doi: 10.1007/s10957-013-0281-0.
      X. Yang , Y. Zhang  and  H. Liu , A wide neighborhood infeasible-interior-point method with arc-search for linear programming, J. Appl. Math. Comput., 51 (2016) , 209-225.  doi: 10.1007/s12190-015-0900-z.
      X. Yang , H. Liu  and  Y. Zhang , An arc-search infeasible-interior-point method for symmetric optimization in a wide neighborhood of the central path, Optim. Lett., 11 (2017) , 135-152.  doi: 10.1007/s11590-016-0997-5.
      Y. Zhang , On extending primal-dual interior-point algorithms from linear programming to semidefinite programming, SIAM J. Optim., 8 (1998) , 365-386.  doi: 10.1137/S1052623495296115.
  • 加载中



Article Metrics

HTML views(1110) PDF downloads(271) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint