A homogeneous predictor-corrector algorithm for stochastic nonsymmetric convex conic optimization with discrete support

Document Type : Original paper

Authors

1 Department of Mathematics, The University of Jordan.

2 Math Dept, Balqa Applied University

Abstract

We consider a stochastic convex optimization problem over nonsymmetric cones with discrete support. This class of optimization problems has not been studied yet. By using a logarithmically homogeneous self-concordant barrier function, we present a homogeneous predictor-corrector interior-point algorithm for solving stochastic nonsymmetric conic optimization problems. We also derive an iteration bound for the proposed algorithm. Our main result is that we uniquely combine a nonsymmetric algorithm with efficient methods for computing the predictor and corrector directions. Finally, we describe a realistic application and present computational results for instances of the stochastic facility location problem formulated as a stochastic nonsymmetric convex conic optimization problem.

Keywords

Main Subjects

References

[1] F. Alizadeh and D. Goldfarb, Second-order cone programming, Math. Program. Ser. B 95 (2003), no. 1, 3–51.
[2] B. Alzalg, Decomposition-based interior point methods for stochastic quadratic second-order cone programming, Appl. Math. Comput. 249 (2014), 1–18.
[3] B. Alzalg, Homogeneous self-dual algorithms for stochastic second-order cone programming, J. Optim. Theory Appl. 163 (2014), no. 1, 148–164.
[4] B. Alzalg, Volumetric barrier decomposition algorithms for stochastic quadratic second-order cone programming, App. Math. Comput. 265 (2015), 494–508.
[5] 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.
[6] B. Alzalg, K. Badarneh, and A. Ababneh, An infeasible interior-point algorithm for stochastic second-order cone optimization, J. Optim. Theory Appl. 181 (2019), no. 1, 324–346.
[7] B. Alzalg, F. Maggioni, and S. Vitali, Homogeneous self-dual methods for symmetric cones under uncertainty, Far East J. Math. Sc. 99 (2016), no. 11, 1603–1778.
[8] 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.
[9] K.A. Ariyawansa and Y. Zhu, A class of volumetric barrier decomposition algorithms for stochastic quadratic programming, Appl. Math. Comput. 186 (2007), no. 2, 1683–1693.
[10] A. Ben-Tal and A. Nemirovski, Lectures on modern convex optimization: analysis, algorithms, and engineering applications, SIAM, Philadelphia, 2001.
[11] J.R. Birge and D.F. Holmes, Efficient solution of two-stage stochastic linear programs using interior point methods, Comp. Optim. Appl. 1 (1992), no. 3, 245–276.
[12] J.R. Birge and F. Louveaux, Introduction to Stochastic Programming, Springer Science & Business Media, 2011.
[13] I.M. Bomze, Copositive optimization–recent developments and applications, European J. Oper. Res. 216 (2012), no. 3, 509–520.
[14] P.R. Chares, Algorithms for unsymmetric cone optimization and an implementation for problems with the exponential cone, Ph.D. thesis, Uni. Catholique de Louvain, 2009.
[15] G.-M. Cho, Log-barrier method for two-stage quadratic stochastic programming, Appl. Math. Comput. 164 (2005), no. 1, 45–69.
[16] J. Dahl and E.D. Andersen, A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimization, Math. Program. 194 (2022), no. 1, 341–370.
[17] J. Faraut, Analysis on symmetric cones, Oxford University Press, Oxford, UK, 1994.
[18] F. Glineur and T. Terlaky, Conic formulation for lp-norm optimization, J. Optim. Theory Appl. 122 (2004), no. 2, 285–307.
[19] M. Hegland, M.R. Osborne, and J. Sun, Parallel interior point schemes for solving multistage convex programming, Ann. Oper. Res. 108 (2001), no. 1, 75–85.
[20] R. Hildebrand, On the algebraic structure of the copositive cone, Optim. Lett. 14 (2020), no. 8, 2007–2019.
[21] S. Jin and Y. Ariyawansa, K.A .and Zhu, Homogeneous self-dual algorithms for stochastic semidefinite programming, J. Optim. Theory Appl. 155 (2012), no. 3, 1073–1083.
[22] B. Kheirfam, A corrector-predictor path-following method for second-order cone optimization, Int. J. Comput. Math. 93 (2016), no. 12, 2064–2078.
[23] B. Kheirfam, N. Osmanpour, and M. Keyanpour, An arc-search infeasible interior-point method for semidefinite optimization with the negative infinity neighborhood, Nume. Algorithms 88 (2021), no. 1, 143–163.
[24] Y. Lu, C.-Y. Yang, J.-S. Chen, and H.-D. Qi, The decompositions with respect to two core non-symmetric cones, J. Global Optim. 76 (2020), no. 1, 155–188.
[25] I.J. Lustig, J.M. Mulvey, and T.J. Carpenter, Formulating two-stage stochastic programs for interior point methods, Oper. Res. 39 (1991), no. 5, 757–770.
[26] Y. Matsukawa and A. Yoshise, A primal barrier function phase i algorithm for non-symmetric conic optimization problems, Japan J. Indust. Appl. Math. 29 (2012), no. 3, 499–517.
[27] J.M. Mulvey and A. Ruszczyński, A new scenario decomposition method for large-scale stochastic optimization, Oper. Res. 43 (1995), no. 3, 477–490.
[28] S.Z. Németh and G. Zhang, Extended lorentz cones and mixed complementarity problems, J. Global Optim. 62 (2015), no. 3, 443–457.
[29] Y.E. Nesterov, Towards non-symmetric conic optimization, Optim. Method Softw. 27 (2012), no. 4-5, 893–917.
[30] Y.E. Nesterov and M.J. Todd, Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res. 22 (1997), no. 1, 1–42.
[31] J. Renegar, Hyperbolic programs, and their derivative relaxations, Found. Comput. Math. 6 (2005), 59–79.
[32] R.T. Rockafellar and R.J.B. Wets, Scenarios and policy aggregation in optimization under uncertainty, Math. Oper. Res. 16 (1991), no. 1, 119–147.
[33] S.H. Schmieta and F. Alizadeh, Extension of primal-dual interior point algorithms to symmetric cones, Math. Program. Ser. A 96 (2003), no. 3, 409–438.
[34] S.A. Serrano, Cones and interior-point algorithms for structured convex optimization involving powers and exponentials, Ph.D. thesis, Stanford University, 2015.
[35] A. Skajaa and Y. Ye, A homogeneous interior-point algorithm for nonsymmetric convex conic optimization, Math. Program. Ser. A 150 (2015), no. 2, 391–422.
[36] J. Sun and X. Liu, Scenario formulation of stochastic linear programs and the homogeneous self-dual interior-point method, INFORMS J. Comput. 18 (2006), no. 4, 444–454.
[37] Y. Sun, S. Pan, and S. Bi, Metric subregularity and/or calmness of the normal cone mapping to the p-order conic constraint system, Optim. Lett. 13 (2019), no. 5, 1095–1110.
[38] M.J. Todd, Semidefinite optimization, Acta Numer. 10 (2001), 515–560.
[39] L. Tuncel, Generalization of primal–dual interior-point methods to convex optimization problems in conic form, Found. Comput. Math. 1 (2001), no. 3, 229–254.
[40] Alexander V. and Pavlo A.K., Polyhedral approximations in $p$-order cone programming, Optim. Methods Softw. 29 (2014), no. 6, 1210–1237.
[41] R.M. Van Slyke and R. Wets, L-shaped linear programs with applications to optimal control and stochastic programming, SIAM J. Applied Math. 17 (1969), no. 4, 638–663.
[42] A. Vinel and P. Krokhmal, On valid inequalities for mixed integer $p$−order cone programming, J. Optim. Theory Appl. 160 (2014), no. 2, 439–456.
[43] G. Zhao, A log-barrier method with Benders decomposition for solving two-stage stochastic linear programs, Math. Program. Ser. A 90 (2001), no. 3, 507–536.
[44] G. Zhao, A Lagrangian dual method with self-concordant barriers for multi-stage stochastic convex programming, Math. Program. 102 (2005), no. 1, 1–24.
 
Communications in Combinatorics and Optimization
Volume 8, Issue 3
September 2023
Pages 531-559

Files

Share

How to cite

Statistics