Table 1.
Numerical results for Example 1
-
Previous Article
Experiments with sparse Cholesky using a sequential task-flow implementation
- NACO Home
- This Issue
- Next Article
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 |
This paper concerns an extension of the arc-search strategy that was proposed by Yang [
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. |
| [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. |
| MTYAlgor | NewAlgor | |||||
| Iter. | CPU | DGAP | Iter. | CPU | DGAP | |
| 55 | 0.1882 | 11 | 0.0729 | |||
| 73 | 0.2476 | 13 | 0.0679 | |||
| MTYAlgor | NewAlgor | |||||
| Iter. | CPU | DGAP | Iter. | CPU | DGAP | |
| 55 | 0.1882 | 11 | 0.0729 | |||
| 73 | 0.2476 | 13 | 0.0679 | |||
Table 2.
Numerical results for Example 2
| MTYAlgor | NewAlgor | |||
| Iter. | CPU | Iter. | CPU | |
| |
97.2 | 3.4915 | 28.8 | 1.1028 |
| 117.3 | 18.7385 | 32.3 | 5.9383 | |
| 116.2 | 67.5448 | 33.7 | 23.2533 | |
| 115.9 | 70.7626 | 33.1 | 24.0481 | |
| 136.7 | 179.9818 | 35.4 | 87.9356 | |
| MTYAlgor | NewAlgor | |||
| Iter. | CPU | Iter. | CPU | |
| |
97.2 | 3.4915 | 28.8 | 1.1028 |
| 117.3 | 18.7385 | 32.3 | 5.9383 | |
| 116.2 | 67.5448 | 33.7 | 23.2533 | |
| 115.9 | 70.7626 | 33.1 | 24.0481 | |
| 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] |
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 |
| [16] |
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 |
| [17] |
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 |
| [18] |
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 |
| [19] |
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 |
| [20] |
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 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]