# Hessian barrier algorithms for linearly constrained optimization problems

2 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : In this paper, we propose an interior-point method for linearly constrained-and possibly nonconvex-optimization problems. The method-which we call the Hessian barrier algorithm (HBA)-combines a forward Euler discretization of Hessian-Riemannian gradient flows with an Armijo backtracking step-size policy. In this way, HBA can be seen as an alternative to mirror descent, and contains as special cases the affine scaling algorithm, regularized Newton processes, and several other iterative solution methods. Our main result is that, modulo a nondegeneracy condition, the algorithm converges to the problem's critical set; hence, in the convex case, the algorithm converges globally to the problem's minimum set. In the case of linearly constrained quadratic programs (not necessarily convex), we also show that the method's convergence rate is $O(1/k^\rho)$ for some $\rho \in (0, 1]$ that depends only on the choice of kernel function (i.e., not on the problem's primi-tives). These theoretical results are validated by numerical experiments in standard nonconvex test functions and large-scale traffic assignment problems.
Keywords :
Document type :
Journal articles

Cited literature [53 references]

https://hal.inria.fr/hal-02403531
Contributor : Panayotis Mertikopoulos Connect in order to contact the contributor
Submitted on : Wednesday, December 11, 2019 - 6:54:40 PM
Last modification on : Friday, July 8, 2022 - 10:09:07 AM
Long-term archiving on: : Thursday, March 12, 2020 - 1:01:08 PM

### File

MainHBALinear.pdf
Files produced by the author(s)

### Citation

Immanuel M Bomze, Panayotis Mertikopoulos, Werner Schachinger, Mathias Staudigl. Hessian barrier algorithms for linearly constrained optimization problems. SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2019, 29, pp.2100 - 2127. ⟨10.1137/18M1215682⟩. ⟨hal-02403531⟩

Record views