A path-following algorithm for stochastic quadratically constrained convex quadratic programming in a Hilbert space

Document Type : Original paper

Authors

The University of Jordan

Abstract

We propose logarithmic-barrier decomposition-based interior-point algorithms for solving two-stage stochastic quadratically constrained convex quadratic programming problems in a Hilbert space. We prove the polynomial complexity of the proposed algorithms, and show that this complexity is independent on the choice of the Hilbert space, and hence it coincides with the best-known complexity estimates in the finite-dimensional case. We also apply our results on a concrete example from the stochastic control theory.

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), no. 1, 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, Logarithmic-barrier decomposition interior-point methods for stochastic linear optimization in a Hilbert space, Numer. Funct. Anal. Optim. 41 (2020), no. 8, 901–928.
https://doi.org/10.1080/01630563.2019.1709499
[5] B. Alzalg and K.A. Ariyawansa, Logarithmic barrier decomposition-based interior point methods for stochastic symmetric programming, J. Math. Anal. Appl. 409 (2014), 973–995.
https://doi.org/10.1016/j.jmaa.2013.07.075
[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.
https://doi.org/10.1007/s10957-018-1445-8
[7] 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
[8] B. Alzalg and M. Pirhaji, Primal-dual path-following algorithms for circular programming, Commun. Comb. Optim. 2 (2017), no. 2, 65–85.
https://doi.org/10.22049/cco.2017.25865.1051
[9] 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.
https://doi.org/10.1090/s0025-5718-2010-02449-4
[10] G.M. Cho, Log-barrier method for two-stage quadratic stochastic programming, Appl. Math. Comput. 164 (2005), no. 1, 45–69.
https://doi.org/10.1016/j.amc.2004.04.095
[11] L. Faybusovich and J.B. Moore, Infinite-dimensional quadratic optimization: interior-point methods and control applications, Appl. Math. Optim. 36 (1997), no. 1, 43–66.
https://doi.org/10.1007/BF02683337
[12] L. Faybusovich and J.B. Moore, Long-step path-following algorithm for convex quadratic programming prob-
lems in a Hilbert space, J. Optim. Theory Appl. 95 (1997), no. 3, 615–635.
https://doi.org/10.1023/A:1022626006554
[13] S. Mehrotra and M. Gokhan Ozevin, Decomposition based interior point methods for two-stage stochastic convex quadratic programs with recourse, Oper. Res. 57 (2009), no. 4, 964–974.
https://doi.org/10.1287/opre.1080.0659
[14] 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
[15] S. Mehrotra and M.G. Ozevin, Decomposition based interior point methods for two-stage stochastic convex quadratic programs with recourse, Oper. Res. 57 (2009), no. 4, 964–974.
http://doi.org/10.1287/opre.1080.0659
[16] Y. Nesterov and A. Nemirovskii, Interior-point polynomial algorithms in convex programming, SIAM, 1994.
[17] J. Renegar, Linear programming, complexity theory and elementary functional analysis, Math. Program. 70 (1995), no. 1, 279–351.
https://doi.org/10.1007/BF01585941
[18] J. Renegar, A mathematical view of interior-point methods in convex optimization, SIAM, 2001.
[19] C. Roos and J.P. Vial, A polynomial method of approximate centers for linear programming, Math. Program. 54 (1992), no. 1, 295–305.
https://doi.org/10.1007/BF01586056
[20] G. Zhao, A log-barrier method with Benders decomposition for solving two-stage stochastic linear programs, Math. Program. 90 (2001), no. 3, 507–536.
https://doi.org/10.1007/PL00011433
 
Communications in Combinatorics and Optimization
Volume 9, Issue 2
June 2024
Pages 353-387

Files

Share

How to cite

Statistics