Journées de l'optimisation 2016

HEC Montréal, Québec, Canada, 2 — 4 mai 2016

Horaire Auteurs Mon horaire
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

WA7 Conic and Polynomial Optimization

4 mai 2016 10h30 – 12h10

Salle: TAL Gestion globale d'actifs inc.

Présidée par Miguel F. Anjos

3 présentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10h30 - 10h55

    Computational study of some valid inequalities to k-Way graph partitioning

    • Vilmar Jefte Rodrigues De Sousa, prés., Polytechnique Montréal
    • Miguel F. Anjos, GERAD, Polytechnique Montréal
    • Sebastien Le Digabel, Polytechnique Montréal

    We focus on identifying the strongest inequalities to tight the semidefinite programming (SDP) relaxation of the maximum k-cut problem. Therefore, we conduct an experimental study for four inequalities: Clique, General clique, Wheel and Bicycle wheel. Our tests suggest that the bicycle wheel and wheel are the strongest.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10h55 - 11h20

    Semidefinite programming based approaches for quadratic programs with linear complementarity constraints

    • Patricia Gillett, prés., Polytechnique Montréal
    • Miguel F. Anjos, GERAD, Polytechnique Montréal
    • Joaquim João Júdice, Instituto de Telecomunicações

    We present a semidefinite programming (SDP) relaxation for quadratic programs with linear complementarity constraints (QPLCC). We extract from the SDP solution a candidate point that can be used to warmstart an NLP solve of the QPLCC. We report computational results regarding the SDP bound, candidate point, and warmstarting procedures.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11h20 - 11h45

    Convergence analysis for Lasserre’s hierarchy of upper bounds for polynomial optimization

    • Zhao Sun, prés., Polytechnique Montréal

    We consider the problem of minimizing a polynomial over a compact set, and analyze a measure-based hierarchy of upper bounds proposed by Lasserre. This hierarchy is obtained by searching for an optimal probability density function which is a sum of squares of polynomials, so that the expectation is minimized. In this talk, we will show its rate of convergence. The main idea is to use the truncated Taylor series of the Gaussian distribution function.