Global Optimization
A more efficient reformulation of complex SDP as real SDP
This note proposes a new reformulation of complex semidefinite programs (SDPs) as real SDPs. As an application, we present an economical reformulation of complex SDP relaxations of complex polynomial optimization problems as real SDPs and derive some further reductions by exploiting inner structure of the complex SDP relaxations. Various numerical examples demonstrate that our new … Read more
Cutting planes from the simplex tableau for quadratically constrained optimization problems
We describe a method to generate cutting planes for quadratically constrained optimization problems. The method uses information from the simplex tableau of a linear relaxation of the problem in combination with McCormick estimators. The method is guaranteed to cut off a basic feasible solution of the linear relaxation that violates the quadratic constraints in the … Read more
Diagonal Partitioning Strategy Using Bisection of Rectangles and a Novel Sampling Scheme
In this paper we consider a global optimization problem, where the objective function is supposed to be Lipschitz-continuous with an unknown Lipschitz constant. Based on the recently introduced BIRECT (BIsection of RECTangles) algorithm, a new diagonal partitioning and sampling scheme is introduced. 0ur framework, called BIRECT-V (where V stands for vertices), combines bisection with sampling … Read more
A novel UCB-based batch strategy for Bayesian optimization
The optimization of expensive black-box functions appears in many situations. Bayesian optimization methods have been successfully applied to solve these prob- lems using well-known single-point acquisition functions. Nowadays, the develop- ments in technology allow us to perform evaluations of some of these expensive function in parallel. Therefore, there is a need for batch infill criteria … Read more
Reformulation-Perspectification Technique for nonconvex optimization problems
In this paper, we propose a new global optimization approach for solving nonconvex optimization problems in which the nonconvex components are sums of products of convex functions. A broad class of nonconvex problems can be formulated in this way, such as concave minimization problems, problems with difference of convex functions in the objective and constraints, … Read more
Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees
We introduce novel convergence results for asynchronous iterations that appear in the analysis of parallel and distributed optimization algorithms. The results are simple to apply and give explicit estimates for how the degree of asynchrony impacts the convergence rates of the iterates. Our results shorten, streamline and strengthen existing convergence proofs for several asynchronous optimization … Read more
A Moment-SOS Hierarchy for Robust Polynomial Matrix Inequality Optimization with SOS-Convexity
We study a class of polynomial optimization problems with a robust polynomial matrix inequality constraint for which the uncertainty set is defined also by a polynomial matrix inequality (including robust polynomial semidefinite programs as a special case). Under certain SOS-convexity assumptions, we construct a hierarchy of moment-SOS relaxations for this problem to obtain convergent upper … Read more
Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completion
Low-rank matrix completion consists of computing a matrix of minimal complexity that recovers a given set of observations as accurately as possible. Unfortunately, existing methods for matrix completion are heuristics that, while highly scalable and often identifying high-quality solutions, do not provide an instance-wise certificate of optimality. We reexamine matrix completion with an optimality-oriented eye. … Read more
Heuristic methods for noisy derivative-free bound-constrained mixed-integer optimization
This paper introduces MATRS, a novel matrix adaptation trust-region strategy designed to solve noisy derivative-free mixed-integer optimization problems with simple bounds in low dimensions. MATRS operates through a repeated cycle of five phases: mutation, selection, recombination, trust-region, and mixed-integer, executed in this sequence. But if in the mutation phase a new best point (the point … Read more