Search Directions in Infeasible Newton’s Method for Computing Weighted Analytic Center for Linear Matrix Inequalities
Applied and Computational Mathematics
Volume 8, Issue 1, February 2019, Pages: 21-28
Received: Feb. 11, 2019;
Accepted: Mar. 22, 2019;
Published: Apr. 22, 2019
Views 156 Downloads 30
Shafiu Jibrin, Department of Mathematics, Faculty of Science, Federal University, Dutse, Nigeria
Ibrahim Abdullahi, Department of Mathematics, Faculty of Science, Federal University, Dutse, Nigeria
Four different search directions for Infeasible Newton’s method for computing the weighted analytic center defined by a system of linear matrix inequality constraints are studied. Newton’s method is applied to find the weighted analytic center and the starting point can be infeasible, that is, outside the feasible region determined by the linear matrix inequality constraints. More precisely, Newton’s method is used to solve system of equations given by the KKT optimality conditions for the weighted analytic center. The search directions for the Newton’s method considered are the ZY, ZY+YZ, Z−1 and NT methods that have been used in semidefinite programming. Backtracking line search is used for the Newton’s method. Numerical experiments are used to compare these search direction methods on randomly generated test problems by looking at the iterations and time taken to compute the weighted analytic center. The starting points are picked randomly outside the feasible region. Our numerical results indicate that ZY+YZ and ZY are the best methods. The ZY+YZ method took the least number of iterations on average while ZY took the least time on average and they handle weights better than the other methods when some of the weights are very large relative to the other weights. These are followed by NT method and then Z−1 method.
Search Directions in Infeasible Newton’s Method for Computing Weighted Analytic Center for Linear Matrix Inequalities, Applied and Computational Mathematics.
Vol. 8, No. 1,
2019, pp. 21-28.
Copyright © 2019 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/
) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
F. Alizadeh, “Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization”, SIAM Journal on Optimization, Vol. 5, No. 1, 1995, pp. 13-51.
F. Alizadeh, J. A. Haeberly and M. Overton, “Primal-Dual Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results”, SIAM Journal on Optimization, Vol. 8, 1998, no. 3, pp. 746-768.
D. S. Atkinson and P. M. Vaidya, “A scaling technique for finding the weighted analytic center of a polytope,” Math. Prog., 57, 1992, pp. 163–192.
S. Jibrin, “Computing Weighted Analytic Center for Linear Matrix Inequalities Using Infeasible Newton’s Method”, Journal of Mathematics, vol. 2015, Article ID 456392, 2015.
S. Jibrin and J. W. Swift, “The Boundary of the Weighted Analytic Center for Linear Matrix inequalities.” Journal of Inequalities in Pure and Applied Mathematics, Vol. 5, Issue 1, Article 14, 2004.
J. Machacek and S. Jibrin, “An Interior Point Method for Solving Semidefinite Programs Using Cutting Planes and Weighted Analytic Centers”, Journal of Applied Mathematics, Vol. 2012, Article ID 946893, 2012.
I. S. Pressman and S. Jibrin, “A Weighted Analytic Center for Linear Matrix Inequalities”, Journal of Inequalities in Pure and Applied Mathematics, Vol. 2, Issue 3, Article 29, 2002.
J. Renegar, “A polynomial-time algorithm, based on Newton’s method, for linear programming,” Math. Programming, Vol. 40, 1988, pp. 59–93.
L. Vandenberghe and S. Boyd, “Semidefinite Programming”, SIAM Review, Vol. 38, 1996, pp. 49-95.
L. Vandenberghe and S. Boyd, “Convex Optimization”, Cambridge University Press, New York 2004.
L. Vandenberghe, S.-P. Boyd and S. Wu, “Determinant Maximization with Linear Matrix Inequality Constraints”, SIAM Journal on Matrix Analysis, Vol. 19, no. 2, 1998, pp. 499-533.
M. J. Todd, K. C. Toh and R. H. Tuntuncu, “On the Nesterov-Todd direction in semidefinite programming,” SIAM J. Optim., vol. 8, 1998, pp. 769-796.