The small hexagon and heptagon with maximum sum of distances between vertices

The hexagon and heptagon with unit diameter and maximum sum of Euclidean distances between vertices are determined by enumerating diameter configurations, and by using a branch and cut algorithm for nonconvex quadratic programming. Lower bounds on the value on this sum are presented for polygon with a larger number of vertices.     

A variance-based method to rank input variables of the Mesh Adaptive Direct Search algorithm

The Mesh Adaptive Direct Search algorithm (Mads) algorithm is designed for nonsmooth blackbox optimization problems in which the evaluation of the functions defining the problems are expensive to compute. The Mads algorithm is not designed for problems with a large number of variables. The present paper uses a statistical tool based on variance decomposition to rank the relative importance of the variables. This statistical method is then coupled with the Mads algorithm so that the optimization is performed either in the entire space of variables or in subspaces associated with statistically important variables. The resulting algorithm is called Stats-Mads and is tested on bound constrained test problems having up to 500 variables. The numerical results show a significant improvement in the objective function value after a fixed budget of function evaluations.     

Disjunctive cuts for continuous linear bilevel programming

This work shows how disjunctive cuts can be generated for a bilevel linear programming problem (BLP) with continuous variables. First, a brief summary on disjunctive programming and bilevel programming is presented. Then duality theory is used to reformulate BLP as a disjunctive program and, from there, disjunctive programming results are applied to derive valid cuts. These cuts tighten the domain of the linear relaxation of BLP. An example is given to illustrate this idea, and a discussion follows on how these cuts may be incorporated in an algorithm for solving BLP.     

The small octagon with longest perimeter

The convex octagon with unit diameter and maximum perimeter is determined. This answers an open question dating from 1922. The proof uses geometric reasoning and an interval arithmetic based global optimization algorithm to solve a series of non-linear and non-convex programs involving trigonometric functions.     

New Branch-and-Cut Algorithm for Bilevel Linear Programming

Linear mixed 0–1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP) problems. We exploit these equivalences to transpose the concept of mixed 0–1 Gomory cuts to BLP. The first phase of our new algorithm generates Gomory-like cuts. The second phase consists of a branch-and-bound procedure to ensure finite termination with a global optimal solution. Different features of the algorithm, in particular, the cut selection and branching criteria are studied in details. We propose also a set of algorithmic tests and procedures to improve the method. Finally, we illustrate the performance through numerical experiments. Our algorithm outperforms pure branch-and-bound when tested on a series of randomly generated problems. Work of the authors was partially supported by FCAR, MITACS and NSERC grants.     

Quantifying uncertainty with ensembles of surrogates for blackbox optimization

Blackbox optimization tackles problems where the functions are expensive to evaluate and where no analytical information is available. In this context, a tried and tested technique is to build surrogates of the objective and the constraints in order to conduct the optimization at a cheaper computational cost. This work introduces an extension to a specific type of surrogates: ensembles of surrogates, enabling them to quantify the uncertainty on the predictions they produce. The resulting extended ensembles of surrogates behave as stochastic models and allow the use of efficient Bayesian optimization tools. The method is incorporated in the search step of the mesh adaptive direct search (MADS) algorithm to improve the exploration of the search space. Computational experiments are conducted on seven analytical problems, two multi-disciplinary optimization problems and two simulation problems. The results show that the proposed approach solves expensive simulation-based problems at a greater precision and with a lower computational effort than stochastic models.

     

Algorithmic Construction of the Subdifferential from Directional Derivatives

The subdifferential of a function is a generalization for nonsmooth functions of the concept of gradient. It is frequently used in variational analysis, particularly in the context of nonsmooth optimization. The present work proposes algorithms to reconstruct a polyhedral subdifferential of a function from the computation of finitely many directional derivatives. We provide upper bounds on the required number of directional derivatives when the space is ?¹ and ?², as well as in ? ⁿ where subdifferential is known to possess at most three vertices.     

Mesh adaptive direct search algorithms for mixed variable optimization

This paper introduces a new derivative-free class of mesh adaptive direct search (MADS) algorithms for solving constrained mixed variable optimization problems, in which the variables may be continuous or categorical. This new class of algorithms, called mixed variable MADS (MV-MADS), generalizes both mixed variable pattern search (MVPS) algorithms for linearly constrained mixed variable problems and MADS algorithms for general constrained problems with only continuous variables. The convergence analysis, which makes use of the Clarke nonsmooth calculus, similarly generalizes the existing theory for both MVPS and MADS algorithms, and reasonable conditions are established for ensuring convergence of a subsequence of iterates to a suitably defined stationary point in the nonsmooth and mixed variable sense.