4 Presentations

• 
  03:30 PM - 03:55 PM

  Optimisation globale multi-objectif pour des problèmes de moindres carrés à faible cardinalité

  • Ramzi Ben Mhenni, presenter, LS2N, École centrale de Nantes, France
  • Sébastien Bourguignon, LS2N, École centrale de Nantes, France
  • Jordan Ninin, ENSTA-Bretagne, Lab-STICC, France
  • Marcel Mongeau, ENAC, Université de Toulouse, France
  • Hervé Carfantan, IRAP, Université de Toulouse, France

  Nous proposons un algorithme branch-and-bound pour l'optimisation de critères de moindres carrés à faible cardinalité, abordée comme un problème bi-objectif. Le couplage d'une stratégie d'exploration et d'un algorithme de relaxation spécifiques permet de résoudre globalement et conjointement des problèmes de cardinalité variable.
• 
  03:55 PM - 04:20 PM

  Sparse cutting planes for nonconvex quadratically constrained quadratic programs

  • Santanu Dey, Georgia Tech
  • Aleksandr M. Kazachkov, presenter, Polytechnique Montréal
  • Andrea Lodi, Polytechnique Montreal
  • Gonzalo Muñoz, Polytechnique Montréal

  Nonconvex quadratically-constrained quadratic programs (QCQPs) arise in a wide variety of real-life applications. However, interior point solvers struggle with the semidefinite programming relaxations for large instances, whereas using linear relaxations, particularly sparse ones, provides a scalable path forward. However, how to properly use such relaxations remains poorly understood. We investigate how to systematically incorporate sparse cutting planes in the solution process for nonconvex QCQPs. We analyze how to appropriately select sparse linear relaxations depending on the instance and present results of preliminary experiments illustrating the precise tradeoffs between sparsity and strength, as well as how to predict strength of cuts given a sparsity pattern.
• 
  04:20 PM - 04:45 PM

  Generalized surrogate duality for mixed-integer nonlinear programs

  • Maxime Gasse, Polytechnique Montréal
  • Andrea Lodi, Polytechnique Montreal
  • Benjamin Müller, Zuse Institute Berlin
  • Gonzalo Muñoz, presenter, Polytechnique Montréal

  An important ingredient for solving optimization problems is a tight and tractable relaxation, usually required to be convex. Nonetheless, current solvers can often handle moderate presence of non-convexities. In this talk, we study non-convex surrogate relaxations (obtained via constraint aggregation) and show benefits and challenges of such relaxations.

  Non-convex optimization, surrogate duality, non-convex relaxations
• 
  04:45 PM - 05:10 PM

  Non-monotone adaptive trust-region method

  • Dimitri Papadimitriou, presenter, University of Antwerp

  For solving nonconvex (unconstrained) minimization problems, we present an adaptive trust region algorithm that guarantees convergence to approximate second-order stationary points together and analyze its worst-case complexity. The method extends the generic nonlinear stepsize control framework by conditioning the (curvature-aware) update strategy for the trust-region radius to the actual model decrease. We then relax the monotonicity assumption of the objective function to propose a nonmonotonic variant of this algorithm.

  Keywords: second-order iterative methods, adaptive trust region, nonconvex