Penetration depth between two convex polyhedra: An efficient global optimization approach

During the detailed design phase of an aerospace program, one of the most important consistency checks is to ensure that no two distinct objects occupy the same physical space. Since exact geometrical modeling is usually intractable, geometry models are discretized, which often introduces small interferences not present in the fully detailed model. In this paper, … Read more

Beyond local optimality conditions: the case of maximizing a convex function

In this paper, we design an algorithm for maximizing a convex function over a convex feasible set. The algorithm consists of two phases: in phase 1 a feasible solution is obtained that is used as an initial starting point in phase 2. In the latter, a biconvex problem equivalent to the original problem is solved … Read more

Stochastic Dual Dynamic Programming And Its Variants

We provide a tutorial-type review on stochastic dual dynamic programming (SDDP), as one of the state-of-the-art solution methods for multistage stochastic programs. Since introduced about 30 years ago for solving large-scale multistage stochastic linear programming problems in a hydrothermal context, SDDP has been applied to practical problems from several fields and is enriched by various … Read more

An Exact Projection-Based Algorithm for Bilevel Mixed-Integer Problems with Nonlinearities

We propose an exact global solution method for bilevel mixed-integer optimization problems with lower-level integer variables and including nonlinear terms such as, \eg, products of upper-level and lower-level variables. Problems of this type are extremely challenging as a single-level reformulation suitable for off-the-shelf solvers is not available in general. In order to solve these problems … Read more

A Reformulation-Linearization Technique for Optimization over Simplices

We study non-convex optimization problems over simplices. We show that for a large class of objective functions, the convex approximation obtained from the Reformulation-Linearization Technique (RLT) admits optimal solutions that exhibit a sparsity pattern. This characteristic of the optimal solutions allows us to conclude that (i) a linear matrix inequality constraint, which is often added … Read more

Spectral relaxations and branching strategies for global optimization of mixed-integer quadratic programs

We consider the global optimization of nonconvex quadratic programs and mixed-integer quadratic programs. We present a family of convex quadratic relaxations which are derived by convexifying nonconvex quadratic functions through perturbations of the quadratic matrix. We investigate the theoretical properties of these quadratic relaxations and show that they are equivalent to some particular semidefinite programs. … Read more

Tight bounds on the maximal perimeter and the maximal width of convex small polygons

A small polygon is a polygon of unit diameter. The maximal perimeter and the maximal width of a convex small polygon with $n=2^s$ vertices are not known when $s \ge 4$. In this paper, we construct a family of convex small $n$-gons, $n=2^s$ and $s\ge 3$, and show that the perimeters and the widths obtained … Read more

Constrained global optimization of functions with low effective dimensionality using multiple random embeddings

We consider the bound-constrained global optimization of functions with low effective dimensionality, that are constant along an (unknown) linear subspace and only vary over the effective (complement) subspace. We aim to implicitly explore the intrinsic low dimensionality of the constrained landscape using feasible random embeddings, in order to understand and improve the scalability of algorithms … Read more

Global Dynamic Optimization with Hammerstein-Wiener Models Embedded

Hammerstein-Wiener models constitute a significant class of block-structured dynamic models, as they approximate process nonlinearities on the basis of input-output data without requiring identification of a full nonlinear process model. Optimization problems with Hammerstein-Wiener models embedded are nonconvex, and thus local optimization methods may obtain suboptimal solutions. In this work, we develop a deterministic global … Read more

VRDFON — line search in noisy unconstrained derivative-free optimization

In this paper, a new randomized solver (called VRDFON) for noisy unconstrained derivative-free optimization problems is discussed. Complexity bounds in the presence of noise for nonconvex, convex, and strongly convex functions are studied. Two effective ingredients of VRDFON are an improved derivative-free line search algorithm with many heuristic enhancements and quadratic models in adaptively determined … Read more