This paper introduces a weighted analytic center for a system of second order cone constraints. The associated barrier function is shown to be convex and conjugate gradient (CG) methods are used to compute the weighted analytic center. In contrast with Newton’s-like methods, CG methods use only the gradient and not the Hessian to minimize a function. The methods considered are the HPRP and ZA with exact and inexact line searches. The exact line search uses Newton’s method and quadratic interpolation is used for the inexact line search. The performance of each method on random test problems was evaluated by observing the number of iterations and time required to find the weighted analytic center. Our numerical methods indicate that ZA is better than HPRP with any of the two line searches, in terms of the number of iterations and time to find the weighted analytic center. Quadratic interpolation inexact line search gives the best success rate and fewest number of iterations for the CG methods considered. On the other hand, the fastest time for the CG methods is found with the Newton’s exact line search. In addition, these results indicate that for each of the methods, our Quadratic interpolation inexact line search has a higher cost per iteration than that of the Newton’s exact line search.
| Published in | Applied and Computational Mathematics (Volume 10, Issue 6) |
| DOI | 10.11648/j.acm.20211006.13 |
| Page(s) | 146-155 |
| 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), 2021. Published by Science Publishing Group |
Second-Order Cone Constraints, Weighted Analytic Center, Conjugate Gradient Methods, Interior-point Methods
| [1] | I. Abdullahi and R. Ahmad, “Convergence analysis of a new conjugate gradient method for unconstrained optimization”. Applied Mathematical Sciences, vol. 9, no. 140, 2015, pp 6969-6984. |
| [2] | A. Alhawarat, M. Mamat, M. Rivaie and Z. Salleh, “An efficient hybrid conjugate gradient method with the strong Wolfe-Powell line search, Mathematical Problems in Engineering, vol. 2015, Article ID 103517, 2015. |
| [3] | D. S. Atkinson and P. M. Vaidya, “A scaling technique for finding the weighted analytic center of a polytope,” Math. Prog., vol. 57, 1992, pp. 163–192. |
| [4] | C. Barta, M. Kolar and J. Sustek, “On Hessians of Composite Functions”, Applied Mathematical Sciences, vol. 8, no. 172, 2014, pp. 8601 – 8609. |
| [5] | R. Burden and D. Faires, “Numerical Analysis”, 9th Ed., Addison Wesley, 2011. |
| [6] | V. L. Basescu and J. E. Mitchell, “An Analytic Center Cutting Plane Approach for Conic Programming”, Mathematics of Operations Research, vol. 33, no. 3, 2008, pp. 529-551. |
| [7] | S. Boyd and L. El Ghaoui, “Method of Centers for Minimizing Generalized Eigenvalues”, Linear Algebra and its Applications, vol. 188, 1993, pp. 63-111. |
| [8] | J. L. Goffin and J. P. Vial, “On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm”, Mathematical Programming, vol. 60, 1993, pp. 81-92. |
| [9] | N. Goldberg and S. Leyffer, “An active-set method for second-order conic-constrained quadratic programming”, SIAM Journal on Optimization, vol. 25, no. 3, 2015, pp. 1455-1477. |
| [10] | W. W. Hager and H. Zhang, “A survey of nonlinear conjugate gradient method”, Pacific Journal of Optimization, vol. 2, no. 1, 2006, pp. 35-58. |
| [11] | M. R. Hestenes and E. Stiefel, “Methods of Conjugate Gradients for Solving Linear Systems”, J. Res. Natl. Bur. Stand., vol. 49, no. 6, 1952, pp. 409-436 |
| [12] | W. Jia, T. Ding and M. Shahidehpour, “Second-Order Cone Programming for Data-Driven Fluid and Gas Energy Flow With a Tight Reformulation, “IEEE Transactions on Power Systems, vol. 36, Issue 2, 2021, pp. 1652 - 1655. |
| [13] | S. Jibrin, “Computing Weighted Analytic Center for Linear Matrix Inequalities Using Infeasible Newton’s Method”, Journal of Mathematics, vol. 2015, Article ID 456392, 2015, 9 pages. |
| [14] | S. Jibrin, I. Abdullahi, “Conjugate Gradient Methods for Computing Weighted Analytic Center for Linear Matrix Inequalities Under Exact and Quadratic Interpolation Line Searches”, American Journal of Applied Mathematics, vol. 8, Issue 1, 2020, pp. 1-10. |
| [15] | S. Jibrin and I. Pressman, “Monte Carlo Algorithms for the Detection of Nonredundant Linear Matrix Inequality Constraints,” International Journal of Nonlinear Sciences and Numerical Simulation, vol. 2, 2001, pp. 139–153. |
| [16] | 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. |
| [17] | X. Liu, Z. Shen and P. Lu, “Entry Trajectory Optimization by Second-Order Cone Programming”, Journal of Guidance, Control, and Dynamics, vol. 39, no. 2, 2016, pp. 227-241. |
| [18] | 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, 21 pages. |
| [19] | R. D. C. Monteiro and T. Tsuchiya, “Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions, Math. Programming, vol. 88, 2000, pp. 61-83. |
| [20] | E. Polak and G. Ribiere, “Note sur la convergence de methodes de directions conjuguees”, ESAIM: Mathematical Modelling and Numerical Analysis - Modlisation Mathmatique et Analyse Numrique, vol. 3, Issue R1, 1969, pp. 35-43. |
| [21] | M. J. D. Powell, “Restart procedures of the conjugate gradient method”, Math. Prog., vol. 2, 1977, pp. 241-254. |
| [22] | 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. |
| [23] | M. Rivaie, A. Abashar, M. Mamat and M. Ismail, The convergence properties of a new type of conjugate gradient methods, Applied Mathematical Sciences, vol. 9, no. 54, 2015, pp. 2671-2682. |
| [24] | Z. Salleh and A. Alhawarat, “An efficient modification of the Hestenes-Stiefel nonlinear conjugate gradient method with restart property”, Journal of Inequalities and Applications, vol. 2016, no. 1, Article 110, 2016, 14 pages. |
| [25] | G. Sonnevend, “New algorithms in convex programming based on a notion of ‘centre’ (for systems of analytic inequalities) and on rational extrapolation”, International Series of Numerical Mathematics, vol. 84, 1988, pp. 311-326. |
| [26] | R. J. Vanderbei and H. Yurttan, “Using LOQO to Solve Second-Order Cone Programming Problems”, Technical Report SOR-98-09, Statistics and Operations Research, Princeton University, 1998. |
| [27] | L. Vandenberghe and S. Boyd, “Convex Optimization”, Cambridge University Press, New York 2004. |
| [28] | L. Vandenberghe and S. Boyd, “Semidefinite Programming”, SIAM Review, vol. 38, 1996, pp. 49-95. |
| [29] | L. Vandenberghe, S. Boyd, H. Lebret and M. S. Lobo, “Applications of second-order cone programming”, Linear Algebra and Its Applications, vol. 284, 1998, pp. 193-228. |
| [30] | A. Weigandt, K. Tuthill and S. Jibrin, “Constraint Consensus Methods for Finding Interior Feasible Points in Second-Order Cone Constraints”, Journal of Applied Mathematics, vol. 2010, Article ID 307209, 2010, 19 pages. |
| [31] | M. Yamashita, T. J. Mullin and S. Safarina, “An efficient second-order cone programming approach for optimal selection in tree breeding”, Optimization Letters, https://doi.org/10.1007/s11590-018-1229-y, 2018. |
| [32] | Y. Zhang, H. Zheng, C. Zhang, Global convergence of a modified PRP conjugate gradient method, Procedia Engineering, vol. 31, 2012, pp. 986-995. |
| [33] | Q. Zhao, W. Fu and Z. Chen, “A Sensitivity Result for Quadratic Second-Order Cone Programming and its Application”, Applications of Mathematics, vol. 66, 2021, pp. 413-436. |
APA Style
Bamanga Dawuda, Shafiu Jibrin, Ibrahim Abdullahi. (2021). A Weighted Analytic Center for Second-Order Cone Constraints. Applied and Computational Mathematics, 10(6), 146-155. https://doi.org/10.11648/j.acm.20211006.13
ACS Style
Bamanga Dawuda; Shafiu Jibrin; Ibrahim Abdullahi. A Weighted Analytic Center for Second-Order Cone Constraints. Appl. Comput. Math. 2021, 10(6), 146-155. doi: 10.11648/j.acm.20211006.13
AMA Style
Bamanga Dawuda, Shafiu Jibrin, Ibrahim Abdullahi. A Weighted Analytic Center for Second-Order Cone Constraints. Appl Comput Math. 2021;10(6):146-155. doi: 10.11648/j.acm.20211006.13
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.acm.20211006.13,
author = {Bamanga Dawuda and Shafiu Jibrin and Ibrahim Abdullahi},
title = {A Weighted Analytic Center for Second-Order Cone Constraints},
journal = {Applied and Computational Mathematics},
volume = {10},
number = {6},
pages = {146-155},
doi = {10.11648/j.acm.20211006.13},
url = {https://doi.org/10.11648/j.acm.20211006.13},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20211006.13},
abstract = {This paper introduces a weighted analytic center for a system of second order cone constraints. The associated barrier function is shown to be convex and conjugate gradient (CG) methods are used to compute the weighted analytic center. In contrast with Newton’s-like methods, CG methods use only the gradient and not the Hessian to minimize a function. The methods considered are the HPRP and ZA with exact and inexact line searches. The exact line search uses Newton’s method and quadratic interpolation is used for the inexact line search. The performance of each method on random test problems was evaluated by observing the number of iterations and time required to find the weighted analytic center. Our numerical methods indicate that ZA is better than HPRP with any of the two line searches, in terms of the number of iterations and time to find the weighted analytic center. Quadratic interpolation inexact line search gives the best success rate and fewest number of iterations for the CG methods considered. On the other hand, the fastest time for the CG methods is found with the Newton’s exact line search. In addition, these results indicate that for each of the methods, our Quadratic interpolation inexact line search has a higher cost per iteration than that of the Newton’s exact line search.},
year = {2021}
}
TY - JOUR T1 - A Weighted Analytic Center for Second-Order Cone Constraints AU - Bamanga Dawuda AU - Shafiu Jibrin AU - Ibrahim Abdullahi Y1 - 2021/11/27 PY - 2021 N1 - https://doi.org/10.11648/j.acm.20211006.13 DO - 10.11648/j.acm.20211006.13 T2 - Applied and Computational Mathematics JF - Applied and Computational Mathematics JO - Applied and Computational Mathematics SP - 146 EP - 155 PB - Science Publishing Group SN - 2328-5613 UR - https://doi.org/10.11648/j.acm.20211006.13 AB - This paper introduces a weighted analytic center for a system of second order cone constraints. The associated barrier function is shown to be convex and conjugate gradient (CG) methods are used to compute the weighted analytic center. In contrast with Newton’s-like methods, CG methods use only the gradient and not the Hessian to minimize a function. The methods considered are the HPRP and ZA with exact and inexact line searches. The exact line search uses Newton’s method and quadratic interpolation is used for the inexact line search. The performance of each method on random test problems was evaluated by observing the number of iterations and time required to find the weighted analytic center. Our numerical methods indicate that ZA is better than HPRP with any of the two line searches, in terms of the number of iterations and time to find the weighted analytic center. Quadratic interpolation inexact line search gives the best success rate and fewest number of iterations for the CG methods considered. On the other hand, the fastest time for the CG methods is found with the Newton’s exact line search. In addition, these results indicate that for each of the methods, our Quadratic interpolation inexact line search has a higher cost per iteration than that of the Newton’s exact line search. VL - 10 IS - 6 ER -
Email: