2022 Optimization Days
HEC Montréal, Québec, Canada, 16 — 18 May 2022
WA5  Numerical optimization and linear algebra with Julia II
May 18, 2022 10:30 AM – 12:10 PM
Location: LouisLaberge (red)
Chaired by Alexis Montoison
4 Presentations

10:30 AM  10:55 AM
Evaluating cone oracles nicely in interior point algorithms
We will give a broad overview of the cone oracles required by some current conic interior point solvers. For example, the interior point solver Hypatia uses up to third order derivative information (which can be evaluated nicely for many cones). The algorithm by Dahl and Andersen (2021) uses similar information but also requires access to a derivative of the conjugate of the barrier function for the cones in the problem. In this talk we will discuss when this information is efficiently computable and how this affects the interior point algorithm.

10:55 AM  11:20 AM
A modular regularized interiorpoint algorithm for convex quadratic optimization in multiprecision
In this talk, we describe a Julia implementation of RipQP, a regularized interiorpoint method for convex quadratic optimization.
RipQP is able to solve problems in several floatingpoint formats, and can also start in a lower precision as a form of warmstart, and transition to a higher precision.
The main cost of the algorithm consists in solving a linear system.
RipQP can use sparse factorizations, such as Cholesky or indefinite LDL, but it can also be used with Krylov methods from the Julia package Krylov.jl.
We present a comparison of some of the best Krylov methods on different formulations of the linear system on linear and convex quadratic problems. 
11:20 AM  11:45 AM
Coordinate Linear Variance Reduction for Generalized Linear Programming
In this talk, we present Coordinate Linear Variance Reduction (CLVR; pronounced “clever”), an efficient, scalable firstorder algorithm designed for the convexconcave minmax problem originated from reformulating a class of generalized linear programs (GLP), which can include simple nonsmooth convex regularizer and simple convex set constraints. When the regularization terms and constraints are separable, CLVR admits an efficient lazy update strategy that makes its complexity bounds scale with the number of nonzero elements of the linear constraint matrix in (GLP) rather than the matrix dimensions. We demonstrate the applicability of CLVR on the Distributionally Robust Optimization (DRO) problems with ambiguity sets based on both fdivergence and Wasserstein metrics, reformulating them as GLPs by introducing sparsely connected auxiliary variables. We implement our algorithm in Julia and complement our theoretical guarantees with numerical experiments that verify our algorithm’s practical effectiveness.

11:45 AM  12:10 PM
QLP factorization for dense matrices
Abstract: The QLP factorization of a dense matrix A of any shape can be determined in a more efficient way than computing the QR factors of A followed by the LQ factors of R. For symmetric matrices we propose orthogonal tridiagonalization followed by QLP factorization of the resulting triadiagonal. This QLP factorization of dense symmetric matrices requires similar storage to Cholesky and LDL^T factorizations and is more stable. For unsymmetric or rectangular matrices, we propose orthogonal bidiagonalization. Both factorizations are standard for EVD and SVD computation but are also relevant for QLP factorization. Two applications are for rank estimation and determining the minimumnorm solution x that minimizes b  Ax when A in R^{m x n} and rank(A) < min(m, n).