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

Advanced Optimization using Julia

Jul 12, 2017 03:30 PM – 05:10 PM

Location: TD Assurance Meloche Monnex

Chaired by Dominique Orban

4 Presentations

  • 03:30 PM - 03:55 PM

    TRARC: a unified implementation of trust region and ARC algorithms

    • Jean-Pierre Dussault, presenter, Université de Sherbrooke

    Adaptive cubic regularization (ARC) and trust region (TR) methods use modified linear systems to compute their steps. The modified systems consists in adding some multiple of the identity matrix (or a well chosen positive definite matrix) to the hessian to obtain a sufficiently positive definite linear system, the so called shifted system. This type of system were first proposed by Levenberg and Marquardt. Some trial and error is often involved to obtain a specified value for this shift parameter. We provide an efficient unified implementation to track the shift parameter; our implementation encompasses many ARC and TR variants. The Julia language is used for the implementation.

  • 03:55 PM - 04:20 PM

    Simple Linesearch Computation satisfying Strong Wolfe conditions

    • Samuel Goyette, presenter, Université de Sherbrooke
    • Jean-Pierre Dussault, Université de Sherbrooke

    The study focuses on linesearch for differentiable optimization problems. We solve those problems using variations of conjugate gradient, Newton, steepest descent and LBFGS algorithms. We compare the efficiency of different linesearch algorithms with those descent algorithms. The one-dimensional version of the trust regions and ARC algorithms easily satisfy the strong Wolfe conditions. We benchmark them against a basic linesearch, bisection and the “zoom” algorithm presented in Numerical Optimization by Nocedal and Wright. The algorithms were implemented in Julia.

  • 04:20 PM - 04:45 PM

    Solving tomographic reconstruction problems using first order iterative methods

    • Jonathan Baillargeon, presenter,
    • Jean-Pierre Dussault, Université de Sherbrooke

    PET and CT tomographic reconstruction problems are convex (very) large scale bound constrained optimization problems, especially so for 3D instances. We consider solving them using first order methods; we introduce a new adaptation of FISTA and compare it to several algorithms including the most recent Hager and Zhang limited memory conjugate gradient method and the baseline benchmarks provided by the L-BFGS-B software and the well known MLEM algorithm. Our presentation is from the optimization point of view (convergence properties of the algorithms) but nevertheless we will comment on the reconstructed images quality.

  • 04:45 PM - 05:10 PM

    How to Compute a Stationary Point of the MPCC?

    • Tangi Migot, presenter, IRMAR-Insa Rennes
    • Jean-Pierre Dussault, Université de Sherbrooke
    • Mounir Haddou, Insa Rennes
    • Abdeslam Kadrani, INSEA

    Mathematical programs with complementarity constraints (MPCC) are non-linear optimization problems over a possibly non-convex and non-connected domain. Recent progress on optimality conditions allow to build efficient relaxation methods that converge to MPCC-kind stationary point. However, in 2015 Kanzow & Schwarz pointed out that the implementation of those methods may not guarantee anymore the strong desired convergence properties. We introduce here an algorithm that tackle this issue by computing specific approximate solutions of the regularized subproblems. We provide theoretical results on convergence and existence of the approximate solutions in a general framework that include all the relaxation methods from the literature. We also present numerical results in Julia.