Optimization methods based on interpolation conditions

Details

Supervisors

Glineur, François ; Hendrickx, Julien

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en mathématiques appliquées, à finalité spécialisée

Abstract

This thesis investigates smooth convex optimization in the regime where the problem dimension is small relative to the number of oracle evaluations. This setting is largely overlooked by classical complexity theory, whose lower bounds are designed for the opposite regime (when the number of first order oracle evaluations is less than the problem dimension), leaving open the possibility of doing better in any fixed finite-dimensional space. The central question is whether retaining and exploiting the full history of past first order oracle evaluations, rather than discarding it as standard first-order methods do, can yield more effective algorithms when oracle calls are costly. When each evaluation is expensive, the cost of solving a harder subproblem, such as a quadratic program to determine the next query point becomes negligible by comparison, making it worthwhile to build and exploit richer models of the objective. The investigation is deliberately exploratory: rather than optimizing a single method, it maps the design space by revisiting cutting-plane and bundle methods under smoothness assumptions, and by developing new algorithms grounded in the use of smooth convex interpolation conditions. The proposed approaches are evaluated experimentally on a range of smooth convex problems to assess their relative strengths and limitations. Those preliminary results are encouraging: the proposed methods consistently outperform standard first-order methods in the targeted regime and often exhibit linear convergence, suggesting that aggressive memory exploitation is a productive direction for this class of problems.