Convex and Nonsmooth Optimization

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

    Accelerated fast iterative shrinkage thresholding algorithms for sparsity-regularized cone-beam CT image reconstruction

  • Mark Anastasio
  • Jun Tan
  • Alex Sawatzky
  • Qiaofeng Xu
  • Deshan Yang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Optimization Software and Modeling Systems

    Purpose: The development of iterative image reconstruction algorithms for cone-beam computed tomography (CBCT) remains an active and important research area. Even with hardware acceleration, the overwhelming majority of the available 3D iterative algorithms that implement nonsmooth regularizers remain computationally burdensome and have not been translated for routine use in time-sensitive applications such as image-guided radiation … Read more

    Semi-Smooth Second-order Type Methods for Composite Convex Programs

  • Yongfeng Li
  • Zaiwen Wen
  • Xiantao Xiao
  • Liwei Zhang
    • Categories Convex Optimization Tags , , , , ,

    The goal of this paper is to study approaches to bridge the gap between first-order and second-order type methods for composite convex programs. Our key observations are: i) Many well-known operator splitting methods, such as forward-backward splitting (FBS) and Douglas-Rachford splitting (DRS), actually define a possibly semi-smooth and monotone fixed-point mapping; ii) The optimal solutions … Read more

    Tight global linear convergence rate bounds for operator splitting methods

  • Goran Banjac
  • Paul J. Goulart
    • Categories Convex Optimization, Linear Programming Tags , , , , , , ,

    In this paper we establish necessary and sufficient conditions for linear convergence of operator splitting methods for a general class of convex optimization problems where the associated fixed-point operator is averaged. We also provide a tight bound on the achievable convergence rate. Most existing results establishing linear convergence in such methods require restrictive assumptions regarding … 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

    Coordinate Friendly Structures, Algorithms and Applications

  • Zhimin Peng
  • Yangyang Xu
  • Ming Yan
  • Wotao Yin
  • Tianyu Wu
    • Categories Convex Optimization, Nonlinear Optimization, Parallel Algorithms Tags , , , ,

    This paper focuses on coordinate update methods, which are useful for solving problems involving large or high-dimensional datasets. They decompose a problem into simple subproblems, where each updates one, or a small block of, variables while fixing others. These methods can deal with linear and nonlinear mappings, smooth and nonsmooth functions, as well as convex … Read more

    An Inexact Proximal Method with Proximal Distances for Quasimonotone Equilibrium Problems

  • Lennin Mallma Ramirez
  • Paulo Roberto Oliveira
  • Erik Alex Papa Quiroz
    • Categories Generalized Convexity/Monoticity

    In this paper we propose an inexact proximal point method to solve equilibrium problem using proximal distances and the diagonal subdi erential. Under some natural assumptions on the problem and the quasimonotonicity condition on the bifunction, we prove that the sequence generated for the method converges to a solution point of the problem. Citation Report01-2016-PESC-COPPE-UFRJ Article … Read more

    Two-sided linear chance constraints and extensions

  • Daniel Bienstock
  • Miles Lubin
  • Juan Pablo Vielma
    • Categories Convex Optimization, Second-Order Cone Programming, Stochastic Programming

    We examine the convexity and tractability of the two-sided linear chance constraint model under Gaussian uncertainty. We show that these constraints can be applied directly to model a larger class of nonlinear chance constraints as well as provide a reasonable approximation for a challenging class of quadratic chance constraints of direct interest for applications in … Read more

    Approximations and Generalized Newton Methods

  • Diethard Klatte
  • Bernd Kummer
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , , , ,

    We study local convergence of generalized Newton methods for both equations and inclusions by using known and new approximations and regularity properties at the solution. Including Kantorovich-type settings, our goal are statements about all (not only some) Newton sequences with appropriate initial points. Our basic tools are results of Klatte-Kummer (2002) and Kummer (1988, 1995), … Read more

    The Euclidean distance degree of orthogonally invariant matrix varieties

  • Dmitriy Drusvyatskiy
  • Hon-Leung Lee
  • Giorgio Ottaviani
  • Rekha R. Thomas
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    The Euclidean distance degree of a real variety is an important invariant arising in distance minimization problems. We show that the Euclidean distance degree of an orthogonally invariant matrix variety equals the Euclidean distance degree of its restriction to diagonal matrices. We illustrate how this result can greatly simplify calculations in concrete circumstances. Article Download … Read more