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

VRBBON — line search in noisy unconstrained black box optimization

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

Computational advances in polynomial optimization: RAPOSa, a freely available global solver

In this paper we introduce RAPOSa, a global optimization solver specifically designed for (continuous) polynomial programming problems with box-constrained variables. Written entirely in C++, RAPOSa is based on the Reformulation-Linearization Technique developed by Sherali and Tuncbilek (1992) and subsequently improved in Sherali et al. (2012a), Sherali et al. (2012b) and Dalkiran and Sherali (2013). We … Read more

A Comparison of two Mixed-Integer Linear Programs for Piecewise Linear Function Fitting

The problem of fitting continuous piecewise linear (PWL) functions to discrete data has applications in pattern recognition and engineering, amongst many others. To find an optimal PWL function, it is required that the positioning of the breakpoints connecting adjacent linear segments are not constrained, and are allowed to be placed freely. While the PWL fitting … Read more

Convex Hull Representations for Bounded Products of Variables

It is well known that the convex hull of {(x,y,xy)}, where (x,y) is constrained to lie in a box, is given by the Reformulation-Linearization Technique (RLT) constraints. Belotti et al. (2010) and Miller et al. (2011) showed that if there are additional upper and/or lower bounds on the product z=xy, then the convex hull can … Read more