We construct norming meshes for polynomial optimization by the classical Markov inequality on general convex bodies in R^d, and by a tangential Markov inequality via an estimate of Dubiner distance on smooth convex bodies. These allow to compute a (1−eps)-approximation to the minimum of any polynomial of degree not exceeding n by O((n/sqrt(eps))^(ad)) samples, with … Read more
We construct web-shaped norming meshes on starlike polygons, by radial and boundary Chebyshev points. Via the approximation theoretic notion of Dubiner distance, we get a (1-eps)-approximation to the minimum of an arbitrary polynomial of degree n by O(n^2/eps) sampling points. Citation Preprint, July 2018 Article Download View Polynomial Optimization on Chebyshev-Dubiner Webs of Starlike Polygons
Two-trust-region subproblem (TTRS), which is the minimization of a general quadratic function over the intersection of two full-dimensional ellipsoids, has been the subject of several recent research. In this paper, to solve TTRS, a hybrid of efficient algorithms for finding global and local-nonglobal minimizers of trust-region subproblem and the alternating direction method of multipliers (ADMM) … Read more
In this paper, we consider the nonconvex quadratically constrained quadratic programming (QCQP) with one quadratic constraint. By employing the conjugate gradient method, an efficient algorithm is proposed to solve QCQP that exploits the sparsity of the involved matrices and solves the problem via solving a sequence of positive definite system of linear equations after identifying … Read more
Over the years, several classes of scalarization techniques in optimization have been introduced and employed in deriving separation theorems, optimality conditions and algorithms. In this paper, we study the relationships between some of those classes in the sense of inclusion. We focus on three types of scalarizing functionals (by Hiriart-Urruty, Drummond and Svaiter, Gerstewitz) and … Read more
We consider global optimization of nonconvex problems whose factorable reformulations contain a collection of multilinear equations. Important special cases include multilinear and polynomial optimization problems. The multilinear polytope is the convex hull of a set of binary points satisfying a number of multilinear equations. Running intersection inequalities are a family of facet-defining inequalities for the … Read more
It has recently been shown that the problem of testing global convexity of polynomials of degree four is {strongly} NP-hard, answering an open question of N.Z. Shor. This result is minimal in the degree of the polynomial when global convexity is of concern. In a number of applications however, one is interested in testing convexity … Read more
In this article, we provide an overview of some of our recent results on the facial structure of the multilinear polytope with a special focus on its decomposability properties. Namely, we demonstrate that, in the context of mixed-integer nonlinear optimization, the decomposability of the multilinear polytope plays a key role from both theoretical and algorithmic … Read more
The multilinear polytope MP_G of a hypergraph G is the convex hull of a set of binary points satisfying a collection of multilinear equations. We introduce the running-intersection inequalities, a new class of facet-defining inequalities for the multilinear polytope. Accordingly, we define a new polyhedral relaxation of MP_G referred to as the running-intersection relaxation and … Read more
It is folklore knowledge that nonconvex mixed-integer nonlinear optimization problems can be notoriously hard to solve in practice. In this paper we go one step further and drop analytical properties that are usually taken for granted in mixed-integer nonlinear optimization. First, we only assume Lipschitz continuity of the nonlinear functions and additionally consider multivariate implicit … Read more