15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 July 2017

15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 July 2017

Schedule Authors My Schedule

Factorization-Free Methods for Large-Scale Optimization

Jul 13, 2017 01:30 PM – 03:10 PM

Location: TD Assurance Meloche Monnex

Chaired by Dominique Orban

4 Presentations

  • 01:30 PM - 01:55 PM

    Efficient computed tomography reconstruction algorithms in cylindrical coordinates

    • Yves Goussard, presenter, École Polytechnique de Montréal

    Three dimensional X-ray computed tomography (CT) is of great importance for medical diagnosis, nondestructive testing, etc. CT reconstruction can be viewed as a very large optimization problem, possibly with box constraints, in which the computation time is critical. Here, we present an approach in which the medium under study is represented in cylindrical coordinates so as to take advantage of invariances occurring in the data collection process and derive a highly parallel structure. In this communication, we discuss the issues of numerical efficiency, conditioning of the problem, development of specific preconditioners and ability to account for box constraints.

  • 01:55 PM - 02:20 PM

    Factorization-free methods for computed tomography

    • Maxime McLaughlin, presenter, Polytechnique Montréal
    • Dominique Orban, GERAD - Polytechnique Montréal
    • Yves Goussard, École Polytechnique de Montréal

    We study a tomographic reconstruction problem in cylindrical coordinates. A change of variables involving a Fourier matrix attempts to improve the conditioning of the Hessian but introduces linear inequality constraints. The scale and density of the problem call for factorization-free methods. We argue that projections into the feasible set can be computed efficiently by solving a bound-constrained least-squares problem with a fast linear operator. In this talk, we focus on a Barzilai-Borwein projected gradient method and a trust-region projected Newton method. We compare two solvers for the projection subproblem: a two-metric projection algorithm and a trust-region projected Newton method. The performance of several combinations of these techniques is assessed using realistic synthetic data.

  • 02:20 PM - 02:45 PM

    A Factorization-Free Interior-Point Method for Constrained Least-Squares Problems with Exact Regularization

    • Mohsen Dehghani, École Polytechnique de Montréal
    • Andrew Lambe, presenter, École Polytechnique de Montréal
    • Dominique Orban, GERAD - Polytechnique Montréal

    We present an interior-point method for linear least-squares problems with linear constraints. The method employs the exact primal-dual regularization procedure of Friedlander and Orban (2012) to treat degenerate constraints. The method is factorization-free in the sense that neither the constraint Jacobian nor the least-squares operator need be available as explicit matrices; only matrix-operator products are required. Numerical results demonstrate the effectiveness and robustness of the method.

  • 02:45 PM - 03:10 PM

    A Factorization-Free Regularized Sequential Quadratic Optimization Method

    • Dominique Orban, presenter, GERAD - Polytechnique Montréal
    • Sylvain Arreckx, GERAD - Polytechnique Montréal

    When formulated appropriately, augmented Lagrangian methods require the solution of a symmetric quasi-definite linear system at each iteration. The latter are indefinite but their strong relationships with definite systems enable specialized linear algebra and make them prime candidates for matrix-free implementations. We illustrate how the adequately-formulated augmented Lagrangian method for equality-constrained problems provides the motivation for regularized sequential quadratic optimization. We present an efficient factorization-free implementation for large-scale problems, describe global and fast local convergence results, and report on numerical experiments. We conclude with comments on extensions to inequality constraints.