Nonsmooth Optimization

The Sound of APALM Clapping: Faster Nonsmooth Nonconvex Optimization with Stochastic Asynchronous PALM

  • Damek Davis
  • Brent Edmunds
  • Madeleine Udell
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    We introduce the Stochastic Asynchronous Proximal Alternating Linearized Minimization (SAPALM) method, a block coordinate stochastic proximal-gradient method for solving nonconvex, nonsmooth optimization problems. SAPALM is the first asynchronous parallel optimization method that provably converges on a large class of nonconvex, nonsmooth problems. We prove that SAPALM matches the best known rates of convergence — among … Read more

    Pessimistic bilevel linear optimization

  • Stephan Dempe
  • Susanne Franke
  • Guimei Luo
    • Categories Nonsmooth Optimization Tags , , , ,

    In this paper, we investigate the pessimistic bilevel linear optimization problem (PBLOP). Based on the lower level optimal value function and duality, the PBLOP can be transformed to a single-level while nonconvex and nonsmooth optimization problem. By use of linear optimization duality, we obtain a tractable and equivalent transformation and propose algorithms for computing global … Read more

    Computation of Graphical Derivative for a Class of Normal Cone Mappings under a Very Weak Condition

  • Huy Chieu Nguyen
  • Le Van Hien
    • Categories Nonsmooth Optimization Tags , , , ,

    Let $\Gamma:=\{x\in \R^n\, |\, q(x)\in\Theta\},$ where $q: \R^n\rightarrow\R^m$ is a twice continuously differentiable mapping, and $\Theta$ is a nonempty polyhedral convex set in $\R^m.$ In this paper, we first establish a formula for exactly computing the graphical derivative of the normal cone mapping $N_\Gamma:\R^n\rightrightarrows\R^n,$ $x\mapsto N_\Gamma(x),$ under the condition that $M_q(x):=q(x)-\Theta$ is metrically subregular at … Read more

    The Asynchronous PALM Algorithm for Nonsmooth Nonconvex Problems

  • Damek Davis
    • Categories Nonsmooth Optimization Tags , , , , ,

    We introduce the Asynchronous PALM algorithm, a new extension of the Proximal Alternating Linearized Minimization (PALM) algorithm for solving nonconvex nonsmooth optimization problems. Like the PALM algorithm, each step of the Asynchronous PALM algorithm updates a single block of coordinates; but unlike the PALM algorithm, the Asynchronous PALM algorithm eliminates the need for sequential updates … Read more

    Error bounds, quadratic growth, and linear convergence of proximal methods

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
    • Categories Nonsmooth Optimization Tags , , , ,

    We show that the the error bound property, postulating that the step lengths of the proximal gradient method linearly bound the distance to the solution set, is equivalent to a standard quadratic growth condition. We exploit this equivalence in an analysis of asymptotic linear convergence of the proximal gradient algorithm for structured problems, which lack … Read more

    Gap functions for quasi-equilibria

  • Giancarlo Bigi
  • Mauro Passacantando
    • Categories Complementarity and Variational Inequalities, Game Theory, Nonsmooth Optimization Tags , , , ,

    An approach for solving quasi-equilibrium problems (QEPs) is proposed relying on gap functions, which allow reformulating QEPs as global optimization problems. The (generalized) smoothness properties of a gap function are analysed and an upper estimates of its Clarke directional derivative is given. Monotonicity assumptions on both the equilibrium and constraining bifunctions are a key tool … Read more

    Nash Equilibrium in a Pay-as-bid Electricity Market: Part 1 – Existence and Characterisation

  • Didier Aussel
  • Pascale Bendotti
  • Miroslav Pistek
    • Categories Finance and Economics, Nonsmooth Optimization

    We consider a model of a pay-as-bid electricity market based on a multi-leader-common-follower approach where the producers as leaders are at the upper level and the regulator as a common follower is at the lower level. We fully characterise Nash equilibria for this model by describing necessary and sufficient conditions for their existence as well … Read more

    Nash Equilibrium in a Pay-as-bid Electricity Market: Part 2 – Best Response of a Producer

  • Didier Aussel
  • Pascale Bendotti
  • Miroslav Pistek
    • Categories Finance and Economics, Nonsmooth Optimization

    We consider a multi-leader-common-follower model of a pay-as-bid electricity market in which the producers provide the regulator with either linear or quadratic bids. We prove that for a given producer only linear bids can maximise his profit. Such linear bids are referred as the “best response” of the given producer. They are obtained assuming the … Read more

    Variational Analysis of the Crouzeix Ratio

  • Anne Greenbaum
  • Adrian Lewis
  • Michael L. Overton
    • Categories Nonsmooth Optimization Tags , , ,

    Let $W(A)$ denote the field of values (numerical range) of a matrix $A$. For any polynomial $p$ and matrix $A$, define the Crouzeix ratio to have numerator $\max\left\{|p(\zeta)|:\zeta\in W(A)\right\}$ and denominator $\|p(A)\|_2$. M.~Crouzeix’s 2004 conjecture postulates that the globally minimal value of the Crouzeix ratio is $1/2$, over all polynomials $p$ of any degree and … Read more

    Approximate Versions of the Alternating Direction Method of Multipliers

  • Jonathan Eckstein
  • Wang Yao
    • Categories Convex Optimization, Data-Mining, Nonsmooth Optimization Tags , ,

    We present three new approximate versions of alternating direction method of multipliers (ADMM), all of which require only knowledge of subgradients of the subproblem objectives, rather than bounds on the distance to the exact subproblem solution. One version, which applies only to certain common special cases, is based on combining the operator-splitting analysis of the … Read more