4 Presentations

• 
  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.

• 
  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.

• 
  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.

• 
  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.