2019
Chapter
Communications in Computer and Information Science
Springer
Evgeni Nurminski, Natalia Shamray Computational Experience and Challenges with the Conjugate Epi-Projection Algorithms for Non-smooth Optimization // Optimization and Applications. 10th International Conference, OPTIMA 2019, Petrovac, Montenegro, September 30 – October 4, 2019. Revised Selected Papers. Springer, Communications in Computer and Information Science (CCIS). Volume 1145. P.443-454.
This paper considers implementable versions of a conceptual convex optimization algorithm which provides a high-speed (super-linear, quadratic and finite) convergence for broad classes of convex optimization problems. The algorithm can be best viewed in the space of conjugate variables and as such it implicitly solves optimality conditions by sequential projection on the epigraph of conjugate function. The implementable version of this algorithm tries to solve projection problems approximately by construction of the inner approximations of the epigraph up to sufficient accuracy. This paper suggests also a version of the algorithm with additional linear cuts imposed on the epigraph which requires solution of an non-traditional auxiliary one-dimensional optimization problem. We derive an explicit form of this subproblem and provide convergence theorem for the resulting algorithm.
DOI: 10.1007/978-3-030-38603-0