Month: June 2017

First Order Methods Beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems

  • Jérôme Bolte
  • Shoham Sabach
  • Marc Teboulle
  • Yakov Vaisbourd
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , , , ,

    We focus on nonconvex and nonsmooth minimization problems with a composite objective, where the differentiable part of the objective is freed from the usual and restrictive global Lipschitz gradient continuity assumption. This longstanding smoothness restriction is pervasive in first order methods (FOM), and was recently circumvent for convex composite optimization by Bauschke, Bolte and Teboulle, … Read more

    Proximal ADMM with larger step size for two-block separable convex programs

  • Sun Hongchun
  • Min Sun
    • Categories Convex and Nonsmooth Optimization

    The alternating direction method of multipliers (ADMM) is a benchmark for solving two-block separable convex programs, and it finds more and more applications in many areas. However, as other first-order methods, ADMM also suffers from low convergence. In this paper, to accelerate the convergence of ADMM, we relax the restriction region of the Fortin and … Read more

    Optimizing power generation in the presence of micro-grids

  • Boris Detienne
  • Michael Poss
  • De Boeck Jérome
  • Pan Stefania
  • Wim van Ackooij
    • Categories 0-1 Programming, Applications - Science and Engineering, Stochastic Programming Tags , , ,

    In this paper we consider energy management optimization problems in a future wherein an interaction with micro-grids has to be accounted for. We will model this interaction through a set of contracts between the generation companies owning centralized assets and the micro-grids. We will formulate a general stylized model that can, in principle, account for … Read more

    Improved Conic Reformulations for K-means Clustering

  • Grani A. Hanasusanto
  • Madhushini Narayana Prasad
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    In this paper, we show that the popular K-means clustering problem can equivalently be reformulated as a conic program of polynomial size. The arising convex optimization problem is NP-hard, but amenable to a tractable semidefinite programming (SDP) relaxation that is tighter than the current SDP relaxation schemes in the literature. In contrast to the existing … Read more

    New algorithms for discrete vector optimization based on the Graef-Younes method and cone-monotone sorting functions

  • Christian Günther
  • Nicolae Popovici
    • Categories Constrained Nonlinear Optimization, Multi-Criteria Optimization

    The well-known Jahn-Graef-Younes algorithm, proposed by Jahn in 2006, generates all minimal elements of a finite set with respect to an ordering cone. It consists of two Graef-Younes procedures, namely the forward iteration, which eliminates a part of the non-minimal elements, followed by the backward iteration, which is applied to the reduced set generated by … Read more

    Satisfiability Modulo Theories for Process Systems Engineering

  • Andrea Callia D'Iddio
  • Michael Huth
  • Ruth Misener
  • Miten Mistry
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    Process systems engineers have long recognized the importance of both logic and optimization for automated decision-making. But modern challenges in process systems engineering could strongly benefit from methodological contributions in computer science. In particular, we propose satisfiability modulo theories (SMT) for process systems engineering applications. We motivate SMT using a series of test beds and … Read more

    Computing the channel capacity of a communication system affected by uncertain transition probabilities

  • Aharon Ben-Tal
  • Krzysztof Postek
    • Categories Robust Optimization, Telecommunications Tags , ,

    We study the problem of computing the capacity of a discrete memoryless channel under uncertainty affecting the channel law matrix, and possibly with a constraint on the average cost of the input distribution. The problem has been formulated in the literature as a max-min problem. We use the robust optimization methodology to convert the max-min … Read more

    On Glowinski’s Open Question of Alternating Direction Method of Multipliers

  • Tao Min
  • Xiao-Ming Yuan
    • Categories Applications - OR and Management Sciences, Convex Optimization Tags , , , ,

    The alternating direction method of multipliers (ADMM) was proposed by Glowinski and Marrocco in 1975; and it has been widely used in a broad spectrum of areas, especially in some sparsity-driven application domains. In 1982, Fortin and Glowinski suggested to enlarge the range of the step size for updating the dual variable in ADMM from … Read more

    A Line-Search Algorithm Inspired by the Adaptive Cubic Regularization Framework and Complexity Analysis

  • Elhoucine Bergou
  • Youssef Diouane
  • Serge Gratton
    • Categories Unconstrained Optimization Tags , , , , ,

    Adaptive regularized framework using cubics has emerged as an alternative to line-search and trust-region algorithms for smooth nonconvex optimization, with an optimal complexity amongst second-order methods. In this paper, we propose and analyze the use of an iteration dependent scaled norm in the adaptive regularized framework using cubics. Within such scaled norm, the obtained method … Read more

    Mixed-integer convex representability

  • Miles Lubin
  • Juan Pablo Vielma
  • Ilias Zadik
    • Categories (Mixed) Integer Nonlinear Programming

    Motivated by recent advances in solution methods for mixed-integer convex optimization (MICP), we study the fundamental and open question of which sets can be represented exactly as feasible regions of MICP problems. We establish several results in this direction, including the first complete characterization for the mixed-binary case and a simple necessary condition for the … Read more