Journées de l'optimisation 2022
HEC Montréal, Québec, Canada, 16 — 18 mai 2022
WB1 - Global Optimization
18 mai 2022 13h30 – 15h10
Salle: Walter Capital (bleu) Anciennement BDC
Présidée par Raphaël Chenouard
13h30 - 13h55
Maximal perimeter of a convex small polygon
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.
13h55 - 14h20
Nested branch-and-bound algorithm for min-max problems
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.
14h20 - 14h45
Solving under-constrained numerical constraint satisfaction problems with IBEXsolve
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.
14h45 - 15h10
Comparison of various optimization methods for parameter estimation problems using the least squares modeling for physical systems: application to some energy systems
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.