2022 Optimization Days
HEC Montréal, Québec, Canada, 16 — 18 May 2022
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
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 branchandbound algorithm for minmax problems
We address the global minmax 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 setvalued technique, relying on two nested branchandbound algorithms using interval analysis. To address the resulting nonsmooth 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 branchandbound 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 underconstrained 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 wellconstrained 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
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.