Rigorous convex underestimators for general twice-differentiable problems

In order to generate valid convex lower bounding problems for nonconvex twice-differentiable optimization problems, a method that is based on second-order information of general twice-differentiable functions is presented. Using interval Hessian matrices, valid lower bounds on the eigenvalues of such functions are obtained and used in constructing convex underestimators. By solving several nonlinear example problems, it is shown that the lower bounds are sufficiently tight to ensure satisfactory convergence of the BB, a branch and bound algorithm which relies on this underestimation procedure [3].     

On the functional form of convex underestimators for twice continuously differentiable functions

The optimal functional form of convex underestimators for general twice continuously differentiable functions is of major importance in deterministic global optimization. In this paper, we provide new theoretical results that address the classes of optimal functional forms for the convex underestimators. These are derived based on the properties of shift-invariance and sign- invariance.     

An effective branch-and-bound algorithm for convex quadratic integer programming

We present a branch-and-bound algorithm for minimizing a convex quadratic objective function over integer variables subject to convex constraints. In a given node of the enumeration tree, corresponding to the fixing of a subset of the variables, a lower bound is given by the continuous minimum of the restricted objective function. We improve this bound by exploiting the integrality of the variables using suitably-defined lattice-free ellipsoids. Experiments show that our approach is very fast on both unconstrained problems and problems with box constraints. The main reason is that all expensive calculations can be done in a preprocessing phase, while a single node in the enumeration tree can be processed in linear time in the problem dimension.     

Integrating nonlinear branch-and-bound and outer approximation for convex Mixed Integer Nonlinear Programming

In this paper, we present a new hybrid algorithm for convex Mixed Integer Nonlinear Programming (MINLP). The proposed hybrid algorithm is an improved version of the classical nonlinear branch-and-bound (BB) procedure, where the enhancements are obtained with the application of the outer approximation algorithm on some nodes of the enumeration tree. The two methods are combined in such a way that each one collaborates to the convergence of the other. Computational experiments with benchmark instances of the MINLP problem show the good performance of the proposed algorithm, which is compared to the outer approximation algorithm, the nonlinear BB algorithm and the hybrid algorithm implemented in the solver Bonmin.     

Convex underestimators of polynomials

Convex underestimators of a polynomial on a box. Given a non convex polynomial ${f\in \mathbb{R}[{\rm x}]}$ and a box ${{\rm B}\subset \mathbb{R}^n}$ , we construct a sequence of convex polynomials ${(f_{dk})\subset \mathbb{R}[{\rm x}]}$ , which converges in a strong sense to the “best” (convex and degree-d) polynomial underestimator ${f^{*}_{d}}$ of f. Indeed, ${f^{*}_{d}}$ minimizes the L ₁-norm ${\Vert f-g\Vert_1}$ on B, over all convex degree-d polynomial underestimators g of f. On a sample of problems with non convex f, we then compare the lower bounds obtained by minimizing the convex underestimator of f computed as above and computed via the popular α BB method and some of its other refinements. In most of all examples we obtain significantly better results even with the smallest value of k.     

Tight convex underestimators for {{\mathcal C}^2}-continuous problems: I. univariate functions

A novel method for the convex underestimation of univariate functions is presented in this paper. The method is based on a piecewise application of the well-known αBB underestimator, which produces an overall underestimator that is piecewise convex. Subsequently, two algorithms are used to identify the linear segments needed for the construction of its -continuous convex envelope, which is itself a valid convex underestimator of the original function. The resulting convex underestimators are very tight, and their tightness benefits from finer partitioning of the initial domain. It is theoretically proven that there is always some finite level of partitioning for which the method yields the convex envelope of the function of interest. The method was applied on a set of univariate test functions previously presented in the literature, and the results indicate that the method produces convex underestimators of high quality in terms of both lower bound and tightness over the whole domain under consideration.     

An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints

In this paper, we propose a branch-and-bound algorithm for finding a global optimal solution for a nonconvex quadratic program with convex quadratic constraints (NQPCQC). We first reformulate NQPCQC by adding some nonconvex quadratic constraints induced by eigenvectors of negative eigenvalues associated with the nonconvex quadratic objective function to Shor’s semidefinite relaxation. Under the assumption of having a bounded feasible domain, these nonconvex quadratic constraints can be further relaxed into linear ones to form a special semidefinite programming relaxation. Then an efficient branch-and-bound algorithm branching along the eigendirections of negative eigenvalues is designed. The theoretic convergence property and the worst-case complexity of the proposed algorithm are proved. Numerical experiments are conducted on several types of quadratic programs to show the efficiency of the proposed method.     

Tight convex underestimators for $${\mathcal{C}^2}$$ -continuous problems: II. multivariate functions

In Part I (Gounaris, C.E., Floudas, C.A.: Tight convex understimators for -continuous functions: I: Univariate functions. J. Global Optim. (2008). doi: ), we introduced a novel approach for the underestimation of univariate functions which was based on a piecewise application of the well-known αBB underestimator. The resulting underestimators were shown to be very tight and, in fact, can be driven to coincide with the convex envelopes themselves. An approximation by valid linear supports, resulting in piecewise linear underestimators was also presented. In this paper, we demonstrate how one can make use of the high quality results of the approach in the univariate case so as to extend its applicability to functions with a higher number of variables. This is achieved by proper projections of the multivariate αBB underestimators into select two-dimensional planes. Furthermore, since our method utilizes projections into lower-dimensional spaces, we explore ways to recover some of the information lost in this process. In particular, we apply our method after having transformed the original problem in an orthonormal fashion. This leads to the construction of even tighter underestimators, through the accumulation of additional valid linear cuts in the relaxation.     

An algorithmic framework for convex mixed integer nonlinear programs

This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch-and-bound and polyhedral outer approximation are the two extreme cases, are proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported. Both the library of mixed integer nonlinear problems that exhibit convex continuous relaxations, on which the experiments are carried out, and a version of the software used are publicly available.     

Surrogate duality in a branch-and-bound procedure for integer programming

The existence of efficient techniques such as subgradient search for solving Lagrangean duals has led to some very successful applications of Lagrangean duality in solving specially structured discrete problems. While surrogate duals have been theoretically shown to provide stronger bounds, the complexity of surrogate dual multiplier search has discouraged their employment in solving integer programs. We have recently suggested a new strategy for computing surrogate dual values that allows us to directly use established Lagrangean search methods for exploring surrogate dual multipliers. This paper considers the problem of incorporating surrogate duality within a branch-and-bound procedure for solving integer programming problems. Computational experience with randomly generated multiconstraint knapsack problems is also reported.     

A convex optimisation framework for the unequal-areas facility layout problem

The unequal-areas facility layout problem is concerned with finding the optimal arrangement of a given number of non-overlapping indivisible departments with unequal area requirements within a facility. We present a convex-optimisation-based framework for efficiently finding competitive solutions for this problem. The framework is based on the combination of two mathematical programming models. The first model is a convex relaxation of the layout problem that establishes the relative position of the departments within the facility, and the second model uses semidefinite optimisation to determine the final layout. Aspect ratio constraints, frequently used in facility layout methods to restrict the occurrence of overly long and narrow departments in the computed layouts, are taken into account by both models. We present computational results showing that the proposed framework consistently produces competitive, and often improved, layouts for well-known large instances when compared with other approaches in the literature.     

Performance of first-order methods for smooth convex minimization: a novel approach

We introduce a novel approach for analyzing the worst-case performance of first-order black-box optimization methods. We focus on smooth unconstrained convex minimization over the Euclidean space. Our approach relies on the observation that by definition, the worst-case behavior of a black-box optimization method is by itself an optimization problem, which we call the performance estimation problem (PEP). We formulate and analyze the PEP for two classes of first-order algorithms. We first apply this approach on the classical gradient method and derive a new and tight analytical bound on its performance. We then consider a broader class of first-order black-box methods, which among others, include the so-called heavy-ball method and the fast gradient schemes. We show that for this broader class, it is possible to derive new bounds on the performance of these methods by solving an adequately relaxed convex semidefinite PEP. Finally, we show an efficient procedure for finding optimal step sizes which results in a first-order black-box method that achieves best worst-case performance.     

Convergence on closed convex sets in a locally convex space

The purpose of this paper is to compare several kinds of convergences on the space C(X) of nonempty closed convex subsets of a locally convex space X. First we verify that the AW-convergence on C(X) is weaker than the metric Attouch-Wets convergence on C(X) of a metrizable locally convex space X. Moreover, we show that X is normable if and only if the two convergences on C(X × R) are equivalent. Secondly we define two convergences on C(X) analogous to the corresponding ones in a normed linear space, and investigate some basic properties of these convergences and compare them.     

Improved penalty calculations for a mixed integer branch-and-bound algorithm

This paper presents an extension of Tomlin's penalties for the branch-and-bound linear mixed integer programming algorithm of Beale and Small. Penalties which are uniformly stronger are obtained by jointly conditioning on a basic variable and the non-basic variable yielding the Tomlin penalty. It is shown that this penalty can be computed with a little additional arithmetic and some extra bookkeeping. The improvement is easy to incorporate for the normal case as well as when the variables are grouped into ordered sets with generalized upper bounds. Computational experience bears out the usefulness of the extra effort for predominantly integer problems.     

Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering

Minimum sum-of-squares clustering consists in partitioning a given set of n points into c clusters in order to minimize the sum of squared distances from the points to the centroid of their cluster. Recently, Sherali and Desai (JOGO, 2005) proposed a reformulation-linearization based branch-and-bound algorithm for this problem, claiming to solve instances with up to 1,000 points. In this paper, their algorithm is investigated in further detail, reproducing some of their computational experiments. However, our computational times turn out to be drastically larger. Indeed, for two data sets from the literature only instances with up to 20 points could be solved in less than 10 h of computer time. Possible reasons for this discrepancy are discussed. The effect of a symmetry breaking rule due to Plastria (EJOR, 2002) and of the introduction of valid inequalities of the convex hull of points in two dimensions which may belong to each cluster is also explored.     

Packing a convex domain with similar convex domains

Given a convex domain C and a positive integer k, inscribe k nonoverlapping convex domains into C, all of them similar to C. Denote by f(k) the maximal sum of their circumferences. In this paper it is shown, that for C square, parallelogram or triangle (1) the first increase of f(k) after k = l² occurs not later than at k = l² + 2, (2) constructions can be given, where the following lower bounds are attained for f(k) = f(l² + j):

$\text{(}\text{1}\text{c}\text{) ? l +}\text{(j ? 1)}\text{2l}\text{j}\text{odd}\text{, l? 2}$

$\text{? l +}\text{j}\text{2}\text{(l + 1) j}\text{even}\text{, l?2}$

where c denotes the circumference of C.     

An axiomatic duality framework for the theta body and related convex corners

Lovász theta function and the related theta body of graphs have been in the center of the intersection of four research areas: combinatorial optimization, graph theory, information theory, and semidefinite optimization. In this paper, utilizing a modern convex optimization viewpoint, we provide a set of minimal conditions (axioms) under which certain key, desired properties are generalized, including the main equivalent characterizations of the theta function, the theta body of graphs, and the corresponding antiblocking duality relations. Our framework describes several semidefinite and polyhedral relaxations of the stable set polytope of a graph as generalized theta bodies. As a by-product of our approach, we introduce the notion of “Schur Lifting” of cones which is dual to PSD Lifting (more commonly used in SDP relaxations of combinatorial optimization problems) in our axiomatic generalization. We also generalize the notion of complements of graphs to diagonally scaling-invariant polyhedral cones. Finally, we provide a weighted generalization of the copositive formulation of the fractional chromatic number by Dukanovic and Rendl from 2010.