Global Optimization

RSP-Based Analysis for Sparsest and Least $\ell_1hBcNorm Solutions to Underdetermined Linear Systems

  • Yun-Bin Zhao
    • Categories Global Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Recently, the worse-case analysis, probabilistic analysis and empirical justification have been employed to address the fundamental question: When does $\ell_1$-minimization find the sparsest solution to an underdetermined linear system? In this paper, a deterministic analysis, rooted in the classic linear programming theory, is carried out to further address this question. We first identify a necessary … Read more

    An Inexact Proximal Method for Quasiconvex Minimization

  • Lennin Mallma Ramirez
  • Paulo Roberto Oliveira
  • Erik Alex Papa Quiroz
    • Categories Global Optimization, Nonlinear Optimization Tags , , , ,

    In this paper we propose an inexact proximal point method to solve constrained minimization problems with locally Lipschitz quasiconvex objective functions. Assuming that the function is also bounded from below, lower semicontinuous and using proximal distances, we show that the sequence generated for the method converges to a stationary point of the problem. CitationJuly 2013ArticleDownload … Read more

    A Penalized Quadratic Convex Reformulation Method for Random Quadratic Unconstrained Binary Optimization

  • Karthik Natarajan
  • Kim-Chuan Toh
  • Dongjian Shi
    • Categories 0-1 Programming, Stochastic Approaches Tags , ,

    The Quadratic Convex Reformulation (QCR) method is used to solve quadratic unconstrained binary optimization problems. In this method, the semidefinite relaxation is used to reformulate it to a convex binary quadratic program which is solved using mixed integer quadratic programming solvers. We extend this method to random quadratic unconstrained binary optimization problems. We develop a … Read more

    Branching and Bounding Improvements for Global Optimization Algorithms with Lipschitz Continuity Properties

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Jaroslav M. Fowkes
    • Categories Global Optimization, Nonlinear Optimization Tags ,

    We present improvements to branch and bound techniques for globally optimizing functions with Lipschitz continuity properties by developing novel bounding procedures and parallelisation strategies. The bounding procedures involve nonconvex quadratic or cubic lower bounds on the objective and use estimates of the spectrum of the Hessian or derivative tensor, respectively. As the nonconvex lower bounds … Read more

    Nonmonotone line search methods with variable sample size

  • Nataša Krejić
  • Nataša Krklec Jerinkić
    • Categories Global Optimization Tags , , ,

    Nonmonotone line search methods for unconstrained minimization with the objective functions in the form of mathematical expectation are considered. The objective function is approximated by the sample average approximation (SAA) with a large sample of fixed size. The nonmonotone line search framework is embedded with a variable sample size strategy such that different sample size … Read more

    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