Including an Industrial Optimization Day

HEC Montréal, May 7 - 9, 2012


HEC Montréal, May 7 — 9, 2012

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

TD8 Méthodes de régularisation en optimisation convexe / Regularization Methods in Convex Optimization

May 8, 2012 03:30 PM – 05:10 PM

Location: Transat

Chaired by Dominique Orban

4 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    03:30 PM - 03:55 PM

    An Interior-Point Method for Constrained Linear Least-Squares

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

    We specialize the primal-dual regularization of Friedlander and Orban (2012)to the case of constrained linear least-squares. The structure of the problem allows to recover a symmetric quasi-definite linear system at each iteration and to provide an interpretation in terms of regularized unconstrained linear least-squares. Although our method is factorization based, this opens the door to efficient matrix-free implementations. We report on preliminary numerical
    experience and suggest how the method generalizes to constrained nonlinear least-squares.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    03:55 PM - 04:20 PM

    A Regularized Interior-Point Method for Semidefinite Programming

    • Ahad Dehghani, presenter, GERAD - McGill University
    • Jean-Louis Goffin, GERAD - McGill University
    • Dominique Orban, GERAD - Polytechnique Montréal

    Interior-point methods in semi-definite programming (SDP) require the solution of a sequence of linear systems which are used to derive the search directions. Safeguards are typically required in order to handle rank-deficient Jacobians and free variables. We propose a primal-dual regularization to the original SDP and show that it is possible to recover an optimal solution of
    the original SDP via inaccurate solves of a sequence of regularized SDPs for both the NT and dual HKM directions. This work is a generalization of recent work by Friedlander and Orban for quadratic programming.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    04:20 PM - 04:45 PM

    Addressing Rank Degeneracy in Constraint-Reduced Interior-Point Methods for Linear Optimization

    • Luke Winternitz, NASA Goddard
    • Andre Tits, presenter, University of Maryland
    • Pierre-Antoine Absil, Université Catholique de Louvain

    Constraint-reduction is a technique by which the cost-per-iteration of an interior-point method is significantly reduced, for problems with many inequality constraints, by selecting, at each iteration, a small subset of the constraints for the computation of the search direction. Here, we show how situations where the gradients for the "small subset" do not span the entire space, so that the standard interior-point direction is not well defined, can be dealt with.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    04:45 PM - 05:10 PM

    Algorithme de points intérieurs de type projectif pour la programmation semi-définie linéaire

    • Djamel Benterki, presenter, Université Ferhat Abbas

    Dans ce travail, on présente un algorithme de points intérieurs primal réalisable de type projectif pour la programmation semi-définie linéaire. L'algorithme démarre avec une solution strictement réalisable produite par l'algorithme en question appliqué sur un problème associé. Nous présentons aussi deux techniques pour calculer le pas de déplacement d’une manière moins coûteuse que les recherches linéaires.