American Institute of Mathematical Sciences

Advanced
June  2018, 8(2): 261-275. doi: 10.3934/naco.2018015

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

Behrouz Kheirfam 1,, and  Morteza Moslemi 1,

1. 

Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, I. R. Iran

* Corresponding author: Behrouz Kheirfam

Received  June 2017 Revised  March 2018 Published  May 2018

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.

Keywords: Interior-point method, semidefinite optimization, arc-search strategy, polynomial complexity.
Mathematics Subject Classification: 90C51.
Citation: Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control and Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015
References:
[1]

F. Alizadeh, Combinatorial Optimization with Interior-Point Methods and Semi-definite Matrices, Ph. D. thesis, Computer Science Department, University of Minnesota, Minneapolis, MN, 1991.

[2]

F. Alizadeh, Interior-point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim., 5 (1995), 13-51.  doi: 10.1137/0805002.

[3]

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.

[4]

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.

[5]

E. De Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications, Kluwer Academic Publishers, Dordrecht, Netherlands, 2002. doi: 10.1007/b105286.

[6]

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.

[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.

[8]

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.

[9]

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.

[10]

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.

[11]

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.

[12]

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.

[13]

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.

[14]

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.

[15]

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.

[16]

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.

[17]

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.

[18]

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.

[19]

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.

[20]

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.

[21]

S. Veeraraghavan and D. A. Mazziotti, Semidefinite programming formulation of linear-scaling electronic structure theories Artic, Phys. Rev. A, 92 (2015), 215-220. 

[22]

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.

[23]

S. Wright, Primal-Dual Interior-point Methods, SIAM, Philadelphia, 1997. doi: 10.1137/1.9781611971453.

[24]

Y. Yang, Arc-search path-following interior-point algorithm for linear programming, Optimization online, 2009.

[25]

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.

[26]

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.

[27]

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.

[28]

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.

[29]

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.

show all references

References:
[1]

F. Alizadeh, Combinatorial Optimization with Interior-Point Methods and Semi-definite Matrices, Ph. D. thesis, Computer Science Department, University of Minnesota, Minneapolis, MN, 1991.

[2]

F. Alizadeh, Interior-point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim., 5 (1995), 13-51.  doi: 10.1137/0805002.

[3]

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.

[4]

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.

[5]

E. De Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications, Kluwer Academic Publishers, Dordrecht, Netherlands, 2002. doi: 10.1007/b105286.

[6]

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.

[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.

[8]

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.

[9]

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.

[10]

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.

[11]

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.

[12]

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.

[13]

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.

[14]

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.

[15]

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.

[16]

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.

[17]

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.

[18]

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.

[19]

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.

[20]

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.

[21]

S. Veeraraghavan and D. A. Mazziotti, Semidefinite programming formulation of linear-scaling electronic structure theories Artic, Phys. Rev. A, 92 (2015), 215-220. 

[22]

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.

[23]

S. Wright, Primal-Dual Interior-point Methods, SIAM, Philadelphia, 1997. doi: 10.1137/1.9781611971453.

[24]

Y. Yang, Arc-search path-following interior-point algorithm for linear programming, Optimization online, 2009.

[25]

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.

[26]

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.

[27]

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.

[28]

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.

[29]

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.

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}$
Table Options

Download as excel

$\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}$
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
Table Options

Download as excel

$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
[1]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101
[2]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[3]

Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022003
[4]

Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial and Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739
[5]

Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial and Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949
[6]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211
[7]

Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control and Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601
[8]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial and Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891
[9]

Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial and Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103
[10]

Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial and Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190
[11]

Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control and Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011
[12]

Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030
[13]

Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2579-2598. doi: 10.3934/jimo.2021082
[14]

Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011
[15]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control and Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014
[16]

Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control and Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283
[17]

Victor Magron, Marcelo Forets, Didier Henrion. Semidefinite approximations of invariant measures for polynomial systems. Discrete and Continuous Dynamical Systems - B, 2019, 24 (12) : 6745-6770. doi: 10.3934/dcdsb.2019165
[18]

Lunji Song, Zhimin Zhang. Polynomial preserving recovery of an over-penalized symmetric interior penalty Galerkin method for elliptic problems. Discrete and Continuous Dynamical Systems - B, 2015, 20 (5) : 1405-1426. doi: 10.3934/dcdsb.2015.20.1405
[19]

Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial and Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469
[20]

Jie Sun. On methods for solving nonlinear semidefinite optimization problems. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 1-14. doi: 10.3934/naco.2011.1.1

 Impact Factor: 

Tools

Metrics

  • PDF downloads (241)
  • HTML views (381)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy