2022 Optimization Days

HEC Montréal, Québec, Canada, 16 — 18 May 2022

Schedule Authors My Schedule

WB1 - Global Optimization

May 18, 2022 01:30 PM – 03:10 PM

Location: Walter Capital (blue) Previously BDC

Chaired by Raphaël Chenouard

4 Presentations

  • 01:30 PM - 01:55 PM

    Maximal perimeter of a convex small polygon

    • Christian Bingane, presenter, Polytechnique Montréal

    A small polygon is a polygon of unit diameter. Finding the maximal perimeter of a convex small polygon with a given number of sides is an open problem when the number of sides is a power of two. This presentation discusses recent advances in this problem.

  • 01:55 PM - 02:20 PM

    Nested branch-and-bound algorithm for min-max problems

    • Daniel Ioan, presenter, Lab-STICC, ENSTA Bretagne
    • Jordan Ninin, ENSTA-Bretagne, Lab-STICC, France
    • Benoit Clément, ENSTA-Bretagne

    We address the global min-max optimization problems, where the goal is to minimize over x the maximum over y of f(x,y). This kind of problem has a broad field of applications: from structured robust control up to motion planning and collision detection. The proposed approach employs a set-valued technique, relying on two nested branch-and-bound algorithms using interval analysis. To address the resulting non-smooth objective function and improve the convergence, we exploit a discrete restriction of the feasible set of y to focus on some key points without losing the global optimum. Moreover, a warm start procedure for the secondary branch-and-bound algorithm is used. The benefits of this approach are highlighted and exploited through proof of concepts illustrations as well as simulation results.

  • 02:20 PM - 02:45 PM

    Solving under-constrained numerical constraint satisfaction problems with IBEXsolve

    • Christophe Jermann, presenter, Nantes Université
    • Alexandre Goldsztejn, CNRS
    • Gilles Chabert, IRT Jules Verne

    A numerical constraint satisfaction problem (NCSP) is defined by a set of equality and inequality constraints on real variables taking their values in a box domain. Computing formally its solution set is in general impossible. Hence, numerical constraint solvers usually produce a covering approximation consisting of a set of “certified” boxes, i.e., boxes proved to contain solutions, and a set of “unknown” boxes, which may or may not contain solutions.
    For NSCPs with no equality constraints, a certified box contains only solutions and is often called "inner" in the literature; this can be checked by interval evaluations of the inequalities. For square systems of equations, a certified box usually contains a single, isolated, real solution, and is often called a “uniqueness” box; this is typically proved by the strict contraction of an interval Newton operator.
    For all intermediate cases, with fewer equations than variables, we define a certificate that ensures the continuity of the solution set with respect to wisely chosen parameters among the variables; this can be proved using a “parametric” interval Newton operator. This definition generalizes those for the extreme cases. It is implemented in the IBEXsolve tool which can thus seamlessly handle under- to well-constrained NCSPs.

  • 02:45 PM - 03:10 PM

    Comparison of various optimization methods for parameter estimation problems using the least squares modeling for physical systems: application to some energy systems

    • Raphaël Chenouard, presenter, LS2N, Centrale Nantes, Université de Nantes

    Modeling physical systems from data measurements allow using generic physical models, that have to be calibrated to fit some available data (in which we some confidence). The least squares modeling technique is often used. It aims at minimizing the average error of the values computed by the model when compared to measurement data. Classical numerical algorithms works well for simple models. However, when dealing with highly nonlinear models, for instance dealing with complex physical phenomena, their convergence can be an issue. In this work, we compare various methods (with or without derivatives, local or global) often used in the literature. Based on some generic models of energy systems, several measurement datasets are used to compare the optimization algorithms.