/system/images/000/000/219/Logo_Journ_es_Optimisation__2012_Outl_default.png

Incluant une Journée industrielle de l'optimisation

HEC Montréal, 7 - 9 mai 2012

JOPT2012

HEC Montréal, 7 — 9 mai 2012

Horaire Auteurs Mon horaire

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

8 mai 2012 15h30 – 17h10

Salle: Transat

Présidée par Dominique Orban

4 présentations

  • 15h30 - 15h55

    An Interior-Point Method for Constrained Linear Least-Squares

    • Mohsen Dehghani, prés., É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.

  • 15h55 - 16h20

    A Regularized Interior-Point Method for Semidefinite Programming

    • Ahad Dehghani, prés., 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.

  • 16h20 - 16h45

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

    • Luke Winternitz, NASA Goddard
    • Andre Tits, prés., 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.

  • 16h45 - 17h10

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

    • Djamel Benterki, prés., 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.

Retour