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 & 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. Google Scholar

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

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

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

[5]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[21]

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

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

[23]

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

[24]

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

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

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

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

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

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

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. Google Scholar

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

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

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

[5]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[21]

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

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

[23]

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

[24]

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

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

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

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

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

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

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 & 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 & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[3]

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

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

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

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

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

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

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 & Management Optimization, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2018190
[10]

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

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

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

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

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

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

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

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018142
[18]

Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial & Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457
[19]

Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185
[20]

Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029

 Impact Factor: 

Tools

Metrics

  • PDF downloads (50)
  • HTML views (123)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences