Global Optimization

New and Improved Conditions for Uniqueness of Sparsest Solutions of Underdetermined Linear Systems

  • Yun-Bin Zhao
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization, Global Optimization Tags , , , , ,

    The uniqueness of sparsest solutions of underdetermined linear systems plays a fundamental role in the newly developed compressed sensing theory. Several new algebraic concepts, including the sub-mutual coherence, scaled mutual coherence, coherence rank, and sub-coherence rank, are introduced in this paper in order to develop new and improved sufficient conditions for the uniqueness of sparsest … Read more

    A proximal technique for computing the Karcher mean of symmetric positive definite matrices

  • Ronaldo Malheiros Gregório
  • Paulo Roberto Oliveira
    • Categories Generalized Convexity/Monoticity, Global Optimization Tags , , , ,

    This paper presents a proximal point approach for computing the Riemannian or intrinsic Karcher mean of symmetric positive definite matrices. Our method derives from proximal point algorithm with Schur decomposition developed to compute minimum points of convex functions on symmetric positive definite matrices set when it is seen as a Hadamard manifold. The main idea … Read more

    On a generalization of Pólya’s and Putinar-Vasilescu’s Positivstellensätze

  • Peter J.C. Dickinson
  • Janez Povh
    • Categories Convex and Nonsmooth Optimization, Global Optimization, Linear, Cone and Semidefinite Programming

    In this paper we provide a generalization of two well-known positivstellensätze, namely the positivstellensatz from Pólya [Georg Pólya. Über positive darstellung von polynomen vierteljschr. In Naturforsch. Ges. Zürich, 73: 141-145, 1928] and the positivestellensatz from Putinar and Vasilescu [Mihai Putinar and Florian-Horia Vasilescu. Positive polynomials on semialgebraic sets. Comptes Rendus de l’Académie des Sciences – … Read more

    Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization

  • Ion Necoara
  • Andrei Patrascu
    • Categories Global Optimization, Global Optimization Theory, Nonlinear Optimization

    In this paper we analyze several new methods for solving nonconvex optimization problems with the objective function formed as a sum of two terms: one is nonconvex and smooth, and another is convex but simple and its structure is known. Further, we consider both cases: unconstrained and linearly constrained nonconvex problems. For optimization problems of … Read more

    Analysis of MILP Techniques for the Pooling Problem

  • Santanu S. Dey
  • Akshay Gupte
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Global Optimization Tags , , , , ,

    The $pq$-relaxation for the pooling problem can be constructed by applying McCormick envelopes for each of the bilinear terms appearing in the so-called $pq$-formulation of the pooling problem. This relaxation can be strengthened by using piecewise-linear functions that over- and under-estimate each bilinear term. The resulting relaxation can be written as a mixed integer linear … Read more

    A note on Legendre-Fenchel conjugate of the product of two positive-definite quadratic forms

  • Hsia Yong
    • Categories Global Optimization Theory, Unconstrained Optimization Tags ,

    The Legendre-Fenchel conjugate of the product of two positive-definite quadratic forms was posted as an open question in the field of nonlinear analysis and optimization by Hiriart-Urruty [`Question 11′ in {\it SIAM Review} 49, 255-273, (2007)]. Under a convex assumption on the function, it was answered by Zhao [SIAM J. Matrix Analysis $\&$ Applications, 31(4), … Read more

    Globally convergent DC trust-region methods

  • Le Thi Hoai An
  • Huynh Van Ngai
  • A. Ismael F. Vaz
  • Luis Nunes Vicente
  • Tao Pham Dinh
    • Categories Global Optimization, Nonlinear Optimization Tags , , ,

    In this paper, we investigate the use of DC (Difference of Convex functions) models and algorithms in the solution of nonlinear optimization problems by trust-region methods. We consider DC local models for the quadratic model of the objective function used to compute the trust-region step, and apply a primal-dual subgradient method to the solution of … Read more

    Faster, but Weaker, Relaxations for Quadratically Constrained Quadratic Programs

  • Samuel Burer
  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Convex Optimization, Global Optimization, Quadratic Programming Tags , , ,

    We introduce a new relaxation framework for nonconvex quadratically constrained quadratic programs (QCQPs). In contrast to existing relaxations based on semidefinite programming (SDP), our relaxations incorporate features of both SDP and second order cone programming (SOCP) and, as a result, solve more quickly than SDP. A downside is that the calculated bounds are weaker than … Read more

    An inexact proximal bundle method with applications to convex conic programming

  • Chek Beng Chua
  • Huiling Lin
    • Categories Convex and Nonsmooth Optimization, Global Optimization Tags , , , ,

    We present an inexact bundle method for minimizing an unconstrained convex sup-function with an open domain. Under some mild assumptions, we reformulate a convex conic programming problem as such problem in terms of the support function. This method is a first-order method, hence it requires much less computational cost in each iteration than second-order approaches … Read more

    An Enhanced Spatial Branch-and-Bound Method in Global Optimization with Nonconvex Constraints

  • Peter Kirst
  • Oliver Stein
  • Paul Steuermann
    • Categories Global Optimization Tags , , ,

    We discuss some difficulties in determining valid upper bounds in spatial branch-and-bound methods for global minimization in the presence of nonconvex constraints. In fact, two examples illustrate that standard techniques for the construction of upper bounds may fail in this setting. Instead, we propose to perturb infeasible iterates along Mangasarian-Fromovitz directions to feasible points whose … Read more