| Peer-Reviewed

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

Received: 11 February 2019     Accepted: 22 March 2019     Published: 22 April 2019
Views:       Downloads:
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.

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
  • 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
  • Department of Mathematics, Faculty of Science, Federal University, Dutse, Nigeria

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

  • Sections