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

    Second-order Characterizations of Tilt Stability with Applications to Nonlinear Programming

  • Boris S. Mordukhovich
  • Nghia Tran
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    The paper is devoted to the study of tilt-stable local minimizers of general optimization problems in finite-dimensional spaces and its applications to classical nonlinear programs with twice continuously differentiable data. The importance of tilt stability has been well recognized from both theoretical and numerical aspects of optimization, and this notion has been extensively studied in … Read more

    Some notes on applying computational divided differencing in optimization

  • Stephen A. Vavasis
    • Categories Optimization Software Design Principles Tags , , ,

    We consider the problem of accurate computation of the finite difference $f(\x+\s)-f(\x)$ when $\Vert\s\Vert$ is very small. Direct evaluation of this difference in floating point arithmetic succumbs to cancellation error and yields 0 when $\s$ is sufficiently small. Nonetheless, accurate computation of this finite difference is required by many optimization algorithms for a “sufficient decrease” … Read more

    Convex relaxation for finding planted influential nodes in a social network

  • Lisa Elkin
  • Ting Kei Pong
  • Stephen A. Vavasis
    • Categories Convex Optimization, Data-Mining Tags , ,

    We consider the problem of maximizing influence in a social network. We focus on the case that the social network is a directed bipartite graph whose arcs join senders to receivers. We consider both the case of deterministic networks and probabilistic graphical models, that is, the so-called “cascade” model. The problem is to find the … Read more

    Full Stability in Finite-Dimensional Optimization

  • Boris S. Mordukhovich
  • Tyrrell Rockafellar
  • Nghia Tran
    • Categories Convex and Nonsmooth Optimization

    The paper is devoted to full stability of optimal solutions in general settings of finite-dimensional optimization with applications to particular models of constrained optimization problems including those of conic and specifically semidefinite programming. Developing a new technique of variational analysis and generalized differentiation, we derive second-order characterizations of full stability, in both Lipschitzian and H\”olderian … Read more

    On the Separation of Split Inequalities for Non-Convex Quadratic Integer Programming

  • Christoph Buchheim
  • Emiliano Traversi
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Quadratic Programming

    We investigate the computational potential of split inequalities for non-convex quadratic integer programming, first introduced by Letchford and further examined by Burer and Letchford. These inequalities can be separated by solving convex quadratic integer minimization problems. For small instances with box-constraints, we show that the resulting dual bounds are very tight; they can close a … Read more

    A practicable framework for distributionally robust linear optimization

  • Dimitris Bertsimas
  • Melvyn Sim
  • Meilin Zhang
    • Categories Applications - OR and Management Sciences Tags , ,

    We developed a modular framework to obtain exact and approximate solutions to a class of linear optimization problems with recourse with the goal to minimize the worst-case expected objective over an ambiguity set of distributions. The ambiguity set is specified by linear and conic quadratic representable expectation constraints and the support set is also linear … Read more

    Full stability of locally optimal solutions in second-order cone programming

  • Boris S. Mordukhovich
  • Jiri V. Outrata
  • Ebrahim Sarabi
    • Categories Nonsmooth Optimization Tags , , , , , ,

    The paper presents complete characterizations of Lipschitzian full stability of locally optimal solutions to problems of second-order cone programming (SOCP) expressed entirely in terms of their initial data. These characterizations are obtained via appropriate versions of the quadratic growth and strong second-order sucient conditions under the corresponding constraint quali cations. We also establish close relationships between … Read more

    Polynomial solvability of variants of the trust-region subproblem

  • Daniel Bienstock
  • Alexander Michalka
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , ,

    The trust region subproblem concerns the minimization of a general quadratic over the unit ball in R^n. Extensions to this problem are of interest because of applications to, for example, combinatorial optimization. However the extension obtained by adding an arbitrary family of linear side constraints is NP-hard. In this paper we consider variants of the … Read more

    A Unified View on Relaxations for a Nonlinear Network Flow Problem

  • Armin Fügenschuh
  • Jesco Humpola
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Network Optimization

    We consider a nonlinear nonconvex network flow problem that arises, for example, in natural gas or water transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides … Read more