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

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

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.

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.

[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. AlizadehJ.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. KojimaS. 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. KojimaM. 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. LiuC. 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. MizunoM. 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. ToddK. 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. YangY. 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. YangH. 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. AlizadehJ.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. KojimaS. 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. KojimaM. 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. LiuC. 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. MizunoM. 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. ToddK. 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. YangY. 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. YangH. 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}$
$\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
$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]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193

[17]

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

[18]

Afaf Bouharguane, Pascal Azerad, Frédéric Bouchette, Fabien Marche, Bijan Mohammadi. Low complexity shape optimization & a posteriori high fidelity validation. Discrete & Continuous Dynamical Systems - B, 2010, 13 (4) : 759-772. doi: 10.3934/dcdsb.2010.13.759

[19]

David Yang Gao, Changzhi Wu. On the triality theory for a quartic polynomial optimization problem. Journal of Industrial & Management Optimization, 2012, 8 (1) : 229-242. doi: 10.3934/jimo.2012.8.229

[20]

Fang Zeng, Pablo Suarez, Jiguang Sun. A decomposition method for an interior inverse scattering problem. Inverse Problems & Imaging, 2013, 7 (1) : 291-303. doi: 10.3934/ipi.2013.7.291

 Impact Factor: 

Metrics

  • PDF downloads (14)
  • HTML views (38)
  • Cited by (0)

Other articles
by authors

[Back to Top]