A Wide Neighborhood Interior-Point Algorithm for Convex Quadratic Semidefinite Optimization

doi:10.1007/s40305-018-0219-1

Journal of the Operations Research Society of China ›› 2020, Vol. 8 ›› Issue (1): 145-164.doi: 10.1007/s40305-018-0219-1

Previous Articles Next Articles

A Wide Neighborhood Interior-Point Algorithm for Convex Quadratic Semidefinite Optimization

Mohammad Pirhaji¹, Maryam Zangiabadi², Hossien Mansouri², Ali Nakhaei¹, Ali Shojaeifard¹

1 Department of Mathematics and Statistics, Imam Hossein Comprehensive University, Tehran, Iran;
2 Department of Applied Mathematics, Shahrekord University, Shahrekord, Iran

Received:2017-08-17 Revised:2018-08-18 Online:2020-03-30 Published:2020-02-18
Contact: Mohammad Pirhaji, Maryam Zangiabadi, Hossien Mansouri, Ali Nakhaei, Ali Shojaeifard E-mail:Mojtabapirhaji@yahoo.com;Zangiabadi-m@sci.sku.ac.ir;mansouri@sci.sku.ac.ir;kpnakhaei@ihu.ac.ir;shojaeifarrd@ihu.ac.ir

Abstract

Abstract: In this paper, we propose an interior-point algorithm based on a wide neighborhood for convex quadratic semidefinite optimization problems. Using the Nesterov-Todd direction as the search direction, we prove the convergence analysis and obtain the polynomial complexity bound of the proposed algorithm. Although the algorithm belongs to the class of large-step interior-point algorithms, its complexity coincides with the best iteration bound for short-step interior-point algorithms. The algorithm is also implemented to demonstrate that it is efficient.

Key words: Convex quadratic semidefinite optimization, Feasible interior-point method, Wide neighborhood, Polynomial complexity

CLC Number:

Mohammad Pirhaji, Maryam Zangiabadi, Hossien Mansouri, Ali Nakhaei, Ali Shojaeifard. A Wide Neighborhood Interior-Point Algorithm for Convex Quadratic Semidefinite Optimization[J]. Journal of the Operations Research Society of China, 2020, 8(1): 145-164.

TrendMD

References

[1] Karmarkar, N.:New polynomial-time algorithm for linear programming. Combinattorica 4, 373-395(1984)
[2] Nie, J., Yuan, Y.:A predictor-corrector algorithm for QSDP combining Dikin-type and Newton centering steps. Ann. Oper. Res. 103, 115-133(2001)
[3] Toh, K.:An inexact primal-dual path following algorithm for convex quadratic SDP. Math. Program. 112, 221-254(2008)
[4] Xiao, X., Zhang, L., Zhang, J.:A smoothing Newton method for a type of inverse semidefinite quadratic programming problem. J. Comput. Appl. Math. 223, 485-498(2009)
[5] Achache, M., Guerra, L.:A full Nesterov-Todd-step feasible primal-dual interior point algorithm for convex quadratic semi-definite optimizationJ. Appl. Math. Comput. 231, 581-590(2014)
[6] Ai, W., Zhang, S.:An O(√nL) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP. SIAM J. Optim. 16, 400-417(2005)
[7] Ai, W.:Neighborhood-following algorithms for linear programming. Sci. China Ser. A 47, 812-820(2004)
[8] Li, Y., Terlaky, T.:A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with O(√n log(Tr(X⁰S⁰)/ε)) iteration complexity. SIAM J. Optim. 20, 2853-2875(2010)
[9] Liu, H., Yang, X., Liu, C.:A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming. J. Optim. Theory Appl. 158, 796-815(2013)
[10] Liu, H., Yang, X., Liu, C.:A Mehrotra-type predictor-corrector infeasible-interior point method with a new one-norm neighborhood for symmetric optimization. J. Comput. Appl. Math. 283, 106-121(2015)
[11] Liu, C., Wu, D., Shang, Y.:A new infeasible interior-point algorithm based on wide neighborhood for symmetric cone programming. J. Oper. Res. Soc. China 4, 147-165(2016)
[12] Yang, X., Liu, H., Zhang, Y.:A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighbourhood for semi-definite programming. J. Comput. Math. 91, 1082-1096(2013)
[13] Horn, R., Johnson, C.:Topics in Matrix Analysis. Cambridge University Press, New York (1991)
[14] Zhang, Y.:On extending some primal-dual algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8, 365-386(1998)
[15] Kojima, M., Shindoh, S., Hara, S.:Interior-point methods for the monotone semidefinite linear complementarity problems. SIAM J. Optim. 7, 86-125(1997)
[16] Alizadeh, F., Haeberly, J., Overton, M.:Primal-dual interior-point methods for semidefinite programming:convergence rates, stability and numerical results. SIAM J. Optim. 8, 746-768(1998)
[17] Monteiro, R.D.C.:Polynomial convergence of primal-dual algorithm for semidefinite programming based on Monteiro and Zhang family of direction. SIAM J. Optim. 8, 797-812(1998)
[18] Nesterov, Y., Todd, M.:Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8, 324-364(1998)
[19] Klerk, E.:Interior Point Methods for Semidefinite Programming. Dissertation, University of Pretoria (1970)
[20] Schmieta, S., Alizadeh, F.:Extension of primal-dual interior point algorithms to symmetric cones. Math. Program. Ser. A 96, 409-438(2003)
[21] Wang, G.Q., Yu, C.J., Teo, K.L.:A new full Nesterov-Todd step feasible interior-point method for convex quadratic symmetric cone optimization. Appl. Math. Comput. 221, 329-343(2013)
[22] Chun-liang, F., Yan-qin, B., Jing, Z., Wei, X.:New primal-dual interior-point algorithm for solving semidefinite optimization. Commun. Appl. Math. Comput. (2014). https://doi.org/10.3969/j.issn.1006-6330.2013.03.009
[23] Liu, C., Liu, H.:A new second-order corrector interior-point algorithm for semidefinite programming. Math. Methods Oper. Res. 75, 165-183(2012)

A Wide Neighborhood Interior-Point Algorithm for Convex Quadratic Semidefinite Optimization

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 8

Recommended Articles

Metrics

Comments

[1]	Mohammad Pirhaji,Hossein Mansouri,Maryam Zangiabadi. A Wide-Neighborhood Predictor-Corrector Interior-Point Algorithm for Linear Complementarity Problems [J]. Journal of the Operations Research Society of China, 2018, 6(4): 529-544.
[2]	Behrouz Kheirfam. A Modified and Simplified Full Nesterov–Todd Step O(N) Infeasible Interior-Point Method for Second-Order Cone Optimization [J]. Journal of the Operations Research Society of China, 2018, 6(2): 301-315.
[3]	Chang-He Liu,Dan Wu,You-Lin Shang. A New Infeasible-Interior-Point Algorithm Based on Wide Neighborhoods for Symmetric Cone Programming [J]. Journal of the Operations Research Society of China, 2016, 4(2): 147-.
[4]	Soodabeh Asadi· Hossein Mansouri ·Maryam Zangiabadi. A Path-Following Full Newton-Step Infeasible Interior-Point Algorithm for P∗(κ)-HLCPs Based on a Kernel Function [J]. Journal of the Operations Research Society of China, 2016, 4(1): 77-.
[5]	Marzieh Sayadi Shahraki · Hossein Mansouri·Maryam Zangiabadi. A Wide Neighborhood Interior-Point Method for Cartesian P∗(κ)-LCP over Symmetric Cones [J]. Journal of the Operations Research Society of China, 2015, 3(3): 331-.
[6]	Soodabeh Asadi · Hossein Mansouri ·Maryam Zangiabadi. A Class of Path-Following Interior-Point Methods for P∗(κ)-Horizontal Linear Complementarity Problems [J]. Journal of the Operations Research Society of China, 2015, 3(1): 17-.
[7]	Behrouz Kheirfam. A Full Nesterov-Todd Step FeasibleWeighted Primal-Dual Interior-Point Algorithm for Symmetric Optimization [J]. Journal of the Operations Research Society of China, 2013, 1(4): 467-482.
[8]	B. Kheirfam · F. Hasani. A Large-Update Feasible Interior-Point Algorithm for Convex Quadratic Semi-definite Optimization Based on a New Kernel Function [J]. Journal of the Operations Research Society of China, 2013, 1(3): 359-376.