Search Directions in Infeasible Newton’s Method for Computing Weighted Analytic Center for Linear Matrix Inequalities

Shafiu Jibrin; Ibrahim Abdullahi

doi:doi:10.11648/j.acm.20190801.14

| Peer-Reviewed

Search Directions in Infeasible Newton’s Method for Computing Weighted Analytic Center for Linear Matrix Inequalities

Shafiu Jibrin, Ibrahim Abdullahi

Published in Applied and Computational Mathematics (Volume 8, Issue 1)

Received: 11 February 2019 Accepted: 22 March 2019 Published: 22 April 2019

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

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⁻¹ 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⁻¹ method.

Published in	Applied and Computational Mathematics (Volume 8, Issue 1)
DOI	10.11648/j.acm.20190801.14
Page(s)	21-28
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2019. Published by Science Publishing Group

Keywords

Linear Matrix Inequalities, Weighted Analytic Center, Newton’s Method, Semidefinite Programming

References

[1]	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.
[2]	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.
[3]	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.
[4]	S. Jibrin, “Computing Weighted Analytic Center for Linear Matrix Inequalities Using Infeasible Newton’s Method”, Journal of Mathematics, vol. 2015, Article ID 456392, 2015.
[5]	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.
[6]	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.
[7]	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.
[8]	J. Renegar, “A polynomial-time algorithm, based on Newton’s method, for linear programming,” Math. Programming, Vol. 40, 1988, pp. 59–93.
[9]	L. Vandenberghe and S. Boyd, “Semidefinite Programming”, SIAM Review, Vol. 38, 1996, pp. 49-95.
[10]	L. Vandenberghe and S. Boyd, “Convex Optimization”, Cambridge University Press, New York 2004.
[11]	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.
[12]	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.

Cite This Article

Plain Text BibTeX RIS

APA Style

Shafiu Jibrin, Ibrahim Abdullahi. (2019). Search Directions in Infeasible Newton’s Method for Computing Weighted Analytic Center for Linear Matrix Inequalities. Applied and Computational Mathematics, 8(1), 21-28. https://doi.org/10.11648/j.acm.20190801.14

Copy | Download

ACS Style

Shafiu Jibrin; Ibrahim Abdullahi. Search Directions in Infeasible Newton’s Method for Computing Weighted Analytic Center for Linear Matrix Inequalities. Appl. Comput. Math. 2019, 8(1), 21-28. doi: 10.11648/j.acm.20190801.14

Copy | Download

AMA Style

Shafiu Jibrin, Ibrahim Abdullahi. Search Directions in Infeasible Newton’s Method for Computing Weighted Analytic Center for Linear Matrix Inequalities. Appl Comput Math. 2019;8(1):21-28. doi: 10.11648/j.acm.20190801.14

Copy | Download

@article{10.11648/j.acm.20190801.14,
  author = {Shafiu Jibrin and Ibrahim Abdullahi},
  title = {Search Directions in Infeasible Newton’s Method for Computing Weighted Analytic Center for Linear Matrix Inequalities},
  journal = {Applied and Computational Mathematics},
  volume = {8},
  number = {1},
  pages = {21-28},
  doi = {10.11648/j.acm.20190801.14},
  url = {https://doi.org/10.11648/j.acm.20190801.14},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20190801.14},
  abstract = {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.},
 year = {2019}
}

Copy | Download

TY - JOUR
T1 - Search Directions in Infeasible Newton’s Method for Computing Weighted Analytic Center for Linear Matrix Inequalities
AU - Shafiu Jibrin
AU - Ibrahim Abdullahi
Y1 - 2019/04/22
PY - 2019
N1 - https://doi.org/10.11648/j.acm.20190801.14
DO - 10.11648/j.acm.20190801.14
T2 - Applied and Computational Mathematics
JF - Applied and Computational Mathematics
JO - Applied and Computational Mathematics
SP - 21
EP - 28
PB - Science Publishing Group
SN - 2328-5613
UR - https://doi.org/10.11648/j.acm.20190801.14
AB - 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.
VL - 8
IS - 1
ER -

Copy | Download

Author Information

Shafiu Jibrin

Department of Mathematics, Faculty of Science, Federal University, Dutse, Nigeria
Ibrahim Abdullahi

Department of Mathematics, Faculty of Science, Federal University, Dutse, Nigeria

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Shafiu Jibrin, Ibrahim Abdullahi. (2019). Search Directions in Infeasible Newton’s Method for Computing Weighted Analytic Center for Linear Matrix Inequalities. Applied and Computational Mathematics, 8(1), 21-28. https://doi.org/10.11648/j.acm.20190801.14

Copy | Download

ACS Style

Shafiu Jibrin; Ibrahim Abdullahi. Search Directions in Infeasible Newton’s Method for Computing Weighted Analytic Center for Linear Matrix Inequalities. Appl. Comput. Math. 2019, 8(1), 21-28. doi: 10.11648/j.acm.20190801.14

Copy | Download

AMA Style

Shafiu Jibrin, Ibrahim Abdullahi. Search Directions in Infeasible Newton’s Method for Computing Weighted Analytic Center for Linear Matrix Inequalities. Appl Comput Math. 2019;8(1):21-28. doi: 10.11648/j.acm.20190801.14

Copy | Download

@article{10.11648/j.acm.20190801.14,
  author = {Shafiu Jibrin and Ibrahim Abdullahi},
  title = {Search Directions in Infeasible Newton’s Method for Computing Weighted Analytic Center for Linear Matrix Inequalities},
  journal = {Applied and Computational Mathematics},
  volume = {8},
  number = {1},
  pages = {21-28},
  doi = {10.11648/j.acm.20190801.14},
  url = {https://doi.org/10.11648/j.acm.20190801.14},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20190801.14},
  abstract = {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.},
 year = {2019}
}

Copy | Download