2025 CMS Summer Meeting

Quebec City, June 6 - 9, 2025

Submission Form Plenary, Prize and Public Lectures By session By speaker Posters

Derivative-free optimization and simulation-based optimization
Org: Kwassi Joseph Dzahini (Argonne National Laboratory) and Gabriel Jarry-Bolduc (Mount Royal University)
[PDF]

PIERRE-YVES BOUCHET, Polytechnique Montréal Convergence towards a local minimum by algorithms with a covering step [PDF]: This talk introduces a new algorithmic step that may fit into virtually any optimization algorithm to strengthen its convergence analysis. By design, this so-called covering step ensures that all accumulation points generated by the algorithm are local solutions to the optimization problem. This new result holds true even for a discontinuous objective function, under a mild assumption that is discussed in details. A practical construction scheme for the covering step that works at low additional cost per iteration is also provided.
The content of this talk has been recently published on Optimization Letters 19, 211--231, 2025 (https://doi.org/10.1007/s11590-024-02165-2).
YIWEN CHEN, University of British Columbia Random subspace trust-region algorithm for high-dimensional convex-constrained derivative-free optimization [PDF]: Model-based derivative-free optimization (DFO) methods are one major class of DFO methods widely used in practice. However, these methods are known to struggle in high dimensions. Recent research tackles this issue by searching for decreases in low-dimensional subspaces sampled randomly in each iteration. This talk proposes a random subspace trust-region algorithm for general convex-constrained DFO problems. We provide a new subspace sampling technique that guarantees that the subspace preserves the first-order criticality measure by a certain percentage with a fixed probability. We define a new class of models that can be constructed using only feasible points in the subspace. Based on these new theoretical results, an almost-sure global convergence and a worst-case complexity analysis of our algorithm are presented. Numerical experiments demonstrate the strong performance of our algorithm in high dimensions.
EDWARD HALLÉ-HANNAN, Polytechnique Montréal
GABRIEL JARRY-BOLDUC, Mount Royal University The cosine measure of a function [PDF]: The cosine measure of a set of vectors is a valuable tool in derivative-free optimization (DFO) to judge the quality of the set. It provides information on how uniformly the set of vectors is covering the space $\mathbb{R}^n$. It is used in the convergence theory of certain DFO algorithms. A set of vectors is a positive spanning set of $\mathbb{R}^n$ if and only if its cosine measure is greater than zero. An important property of positive spanning sets is that when the gradient of a function at a point is well-defined and not equal to the zero vector, then there is at least one descent direction (ascent direction) of the function at the point contained in this set. This is not necessarily true if the gradient is equal to the zero vector or if the gradient does not exist. To characterize the previous two cases, the novel concept of cosine measure of a function is introduced in this paper. It provides an infimum on the value of the cosine measure of a set of vectors guaranteed to contain a descent direction of the function at the point of interest. Pseudo-codes are developed that makes it possible to compute the cosine measure of infinite sets of vectors and it is shown how to compute the cosine measure of a function for two popular classes of nonsmooth functions: indicator functions and max functions.
TANMAYA KARMARKAR, University of British Columbia Computing the convex envelope of bivariate piecewise linear-quadratic (PLQ) functions [PDF]: We introduce a linear-time algorithm for computing the convex envelope of bivariate piecewise linear-quadratic (PLQ) functions and establish that the biconjugate is piecewise rational defined over a polyhedral subdivision. Our approach consists of the following steps: (1) compute the convex envelope of each quadratic piece obtaining piecewise rational functions (quadratic divided by linear function) defined over a polyhedral subdivision;(2) compute the conjugate of each resulting piece to obtain piecewise quadratic functions defined over a parabolic subdivision; (3) compute the maximum of all those functions to obtain the conjugate of the original PLQ function as a piecewise quadratic function defined on a parabolic subdivision; (4) compute the conjugate of each resulting piece; and finally (5) compute the maximum over all those functions to obtain the biconjugate as rational functions (quadratic divided by linear function) defined over a polyhedral subdivision.

top of page