- Previous Article
- NACO Home
- This Issue
-
Next Article
Experiments with sparse Cholesky using a sequential task-flow implementation
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 [
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 |
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 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
Other articles
by authors
[Back to Top]