Open Collections

Iteratively re-weighted lest squares and ADMM methods for solving affine inclusions

Banff International Research Station for Mathematical Innovation and Discovery

We describe two matrix-free methods for solving large-scale affine inclusion problems on the product (or intersection) of convex sets. The first approach is a novel iterative re-weighting algorithm (IRWA) that iteratively minimizes quadratic models of relaxed subproblems while automatically updating a relaxation vector. The second approach is based on alternating direction augmented Lagrangian (ADAL) technology. The main computational costs of each algorithm are the repeated minimizations of convex quadratic functions which can be performed matrix-free. Both algorithms are globally convergent under loose assumptions, and each requires at most $O(1/\varepsilon^2)$ iterations to reach $\varepsilon$-optimality of the objective function. Numerical experiments show that both algorithms efficiently find inexact solutions. However, in certain cases, these experiments indicate that IRWA can be significantly more efficient than ADAL.

Mathematics; Operations research, mathematical programming; Operator theory; Control/optimization/operation research

video/mp4

Author affiliation: University of Washington

2019-03-08

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/68544

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/