Algebraic-based primal interior-point algorithms for stochastic infinity norm optimization

Document Type : Original paper

Authors

1 Department of Mathematics, The University of Jordan, Amman, Jordan 11942

2 Department of Mathematics, M’Hamed Bougara University of Boumerdés, Algeria 22038

Abstract

We study the two-stage stochastic infinity norm optimization problem with recourse based on a commutative algebra. First, we explore and develop the algebraic structure of the infinity norm cone, and utilize it to compute the derivatives of the barrier recourse functions. Then, we prove that the barrier recourse functions and the composite barrier functions for this optimization problem are self-concordant families with reference to barrier parameters. These findings are used to develop interior-point algorithms based on primal decomposition for this class of stochastic programming problems. Our complexity results for the short- and long-step algorithms show that the dominant complexity terms are linear in the rank of the underlying cone. Despite the asymmetry of the infinity norm cone, we also show that the obtained complexity results match (in terms of rank) the best known results in the literature for other well-studied stochastic symmetric cone programs. Finally, we demonstrate the efficiency of the proposed algorithm by presenting some numerical experiments on both stochastic uniform facility location problems and randomly-generated problems. 

Keywords

Main Subjects

References

[1] B. Alzalg, Decomposition-based interior point methods for stochastic quadratic second-order cone programming, Appl. Math. Comput. 249 (2014), 1–18.  https://doi.org/10.1016/j.amc.2014.10.015
[2] B. Alzalg, Homogeneous self-dual algorithms for stochastic second-order cone programming, J. Optim. Theory Appl. 163 (2014), 148–164.  https://doi.org/10.1007/s10957-013-0428-z
[3] B. Alzalg, Volumetric barrier decomposition algorithms for stochastic quadratic second-order cone programming, Appl. Math. Comput. 265 (2015), 494–508.  https://doi.org/10.1016/j.amc.2015.05.014
[4] B. Alzalg, The Jordan algebraic structure of the circular cone, Oper Matrices 11 (2017), no. 1, 1–21. http://dx.doi.org/10.7153/oam-11-01
[5] B. Alzalg, Primal interior-point decomposition algorithms for two-stage stochastic extended second-order cone programming, Optimization 67 (2018), no. 12, 2291–2323.  https://doi.org/10.1080/02331934.2018.1533553
[6] B. Alzalg, Logarithmic-barrier decomposition interior-point methods for stochastic linear optimization in a hilbert space, Numer. Func. Anal. Optim. 41 (2020), no. 8, 901–928.  https://doi.org/10.1080/01630563.2019.1709499
[7] B. Alzalg, Combinatorial and Algorithmic Mathematics: From Foundation to Optimization, Kindle Direct Publishing, Seatle WA, 2022.
[8] B. Alzalg and K.A. Ariyawansa, Logarithmic barrier decomposition-based interior point methods for stochastic symmetric programming, J. Math. Anal. Appl. 409 (2014), no. 2, 973–995.  https://doi.org/10.1016/j.jmaa.2013.07.075
[9] B. Alzalg, K. Badarneh, and A. Ababneh, An infeasible interior-point algorithm for stochastic second-order cone optimization, J. Optim. Theory Appl. 181 (2019), 324–346.  https://doi.org/10.1007/s10957-018-1445-8
[10] B. Alzalg, A. Gafour, and L. Alzaleq, Volumetric barrier cutting plane algorithms for stochastic linear semi-infinite optimization, IEEE Access 8 (2019), 4995–5008.  https://doi.org/10.1109/ACCESS.2019.2962840
[11] B. Alzalg and M. Pirhaji, Elliptic cone optimization and primal–dual path-following algorithms, Optimization 66 (2017), no. 12, 2245–2274.  https://doi.org/10.1080/02331934.2017.1360888
[12] R. Andreani, E.H. Fukuda, G. Haeser, D.O. Santos, and L.D. Secchin, On the use of Jordan Algebras for improving global convergence of an Augmented Lagrangian method in nonlinear semidefinite programming, Comput. Optim. Appl. 79 (2021), no. 3, 633–648.  https://doi.org/10.1007/s10589-021-00281-8
[13] K. Ariyawansa and Y. Zhu, A class of polynomial volumetric barrier decomposition algorithms for stochastic semidefinite programming, Math. Comput. 80 (2011), no. 275, 1639–1661.  http://doi.org/10.1090/S0025-5718-2010-02449-4
[14] P. Benner and T. Mitchell, Faster and more accurate computation of the H∞ norm via optimization., SIAM J Sci Comput. 40 (2018), A3609–A3635.
[15] T. Cai and W.X. Zhou, A max-norm constrained minimization approach to 1-bit matrix completion., J. Mach. Learn. Res. 14 (2013), no. 1, 3619–3647.
[16] M. Chen and S. Mehrotra, Self-concordance and decomposition-based interior point methods for the two-stage stochastic convex optimization problem, SIAM J. Optim. 21 (2011), no. 4, 1667–1687.  https://doi.org/10.1137/080742026
[17] I. Gravagne and I.D. Walker, Properties of minimum infinity-norm optimization applied to kinematically redundant robots, Proc. IEEE/RSJ Int. Conf. Intel. Robots Syst., IEEE, 1998, pp. 152–160.  https://doi.org/10.1109/IROS.1998.724612
[18] S. Kakihara, A. Ohara, and T. Tsuchiya, Curvature integrals and iteration complexities in SDP and symmetric cone programs, Comput. Optim. Appl. 57 (2014), no. 3, 623–665.  https://doi.org/10.1007/s10589-013-9608-x
[19] T. Liu, M.T. Hoang, Y. Yang, and M. Pesavento, A parallel optimization approach on the infinity norm minimization problem, 27th Proc Eur Signal Process Conf., IEEE, 2019, pp. 1–5.  https://doi.org/10.23919/EUSIPCO.2019.8902548
[20] S. Mehrotra and M.G. Özevin, Decomposition-based interior point methods for two-stage stochastic semidefinite programming, SIAM J. Optim. 18 (2007), no. 1, 206–222.  https://doi.org/10.1137/050622067
[21] Y. Nesterov and A. Nemirovskii, Interior-point polynomial algorithms in convex programming, SIAM, 1994.
[22] M.S. Sayadi Shahraki, H. Mansouri, and M. Zangiabadi, Two wide neighborhood interior-point methods for symmetric cone optimization, Comput Optim Appl. 68 (2017), 29–55.  https://doi.org/10.1007/s10589-017-9905-x
[23] G. Yu, Min-max optimization of several classical discrete optimization problems, J. Optim. Theory Appl. 98 (1998), 221–242.  https://doi.org/10.1023/A:1022601301102
[24] G. Zhao, A log-barrier method with benders decomposition for solving two-stage stochastic linear programs, Math. Program. 90 (2001), 507–536.  https://doi.org/10.1007/PL00011433
[25] G. Zhao, A lagrangian dual method with self-concordant barriers for multi-stage stochastic convex programming, Math. Program. 102 (2005), 1–24.  https://doi.org/10.1007/s10107-003-0471-x
Communications in Combinatorics and Optimization
Volume 9, Issue 4
December 2024
Pages 655-692

Files

Share

How to cite

Statistics