Title: Eigenvector-based acceleration strategies for gradient-type methods

Abstract:

Several strategies are described and analyzed to speed-up gradient-type methods when applied to the minimization of strictly convex quadratics and strictly convex functions. The proposed techniques focus on relaxing the traditional optimal step length associated with gradient methods, including the steepest descent (SD) and the minimal residual (MR) methods. Such a relaxation avoids the well-known negative zigzag effect and allows the iterates to move in the entire space which in turn implies that every so often the search direction approaches some eigenvector of the underlying Hessian matrix. The proposed speedups then rely on taking advantage of the properties of the Lanczos method once a search direction that approaches an eigenvector has been identified in order to accelerate the convergence towards the global minimizer. After analyzing the proposed strategies, we illustrate them on the global minimization of strictly convex functions.

Abstract:

In this work, we study two-stage distributionally robust mixed-integer programs with uncertain parameters having finite discrete support. This setting is particularly attractive from a computational perspective because the DRO problem remains tractable and can be reformulated as a (possibly much larger) mixed-integer program, allowing the use of standard optimization technology. We propose an ambiguity set defined through a generalized optimal transportation problem. This formulation extends the classical Kantorovich ambiguity set, enabling the modeling of a wider range of practical situations while preserving useful structural properties. We analyze the main characteristics of this ambiguity set and discuss how they affect the structure of the resulting optimization problem.

Three solution frameworks are investigated. The first is the Benders-like method proposed by Bansal, Huang, and Mehrotra (2018). The second derives a single-stage formulation obtained by dualizing the transportation problem defining the ambiguity set. The third uses an epigraph formulation with dynamically generated optimality cuts in a row-and-column generation scheme. The approaches are evaluated on a distributionally robust location–transportation problem with uncertain demand. Computational results show that the relative performance of the approaches depends strongly on the characteristics of the ambiguity set: the dualization approach is simple and effective in the easiest instances, the row-and-column generation performs well when the ambiguity set approximates robust optimization, and the Benders-type method is preferable in the remaining settings.