Convex and Nonsmooth Optimization

New Fractional Error Bounds for Nonconvex Polynomial Systems with Applications to Holderian Stability in Optimization and Spectral Theory of Tensors

  • Guoyin Li
  • Boris S. Mordukhovich
  • Tiên-So'n Pham
    • Categories Convex and Nonsmooth Optimization Tags , , , , , ,

    In this paper we derive new fractional error bounds for nonconvex polynomial systems with exponents explicitly determined by the dimension of the underlying space and the number/degree of the involved polynomials. The results obtained do not require any regularity assumptions and resolve, in particular, some open questions posed in the literature. The developed techniques are … Read more

    Second-Order Variational Analysis in Conic Programming with Applications to Optimality and Stability

  • Boris S. Mordukhovich
  • Jiri V. Outrata
  • Héctor Ramírez
    • Categories Convex and Nonsmooth Optimization Tags , , , , , ,

    This paper is devoted to the study of a broad class of problems in conic programming modeled via parameter-dependent generalized equations. In this framework we develop a second-order generalized di erential approach of variational analysis to calculate appropriate derivatives and coderivatives of the corresponding solution maps. These developments allow us to resolve some important issues related … Read more

    Partial Second-Order Subdifferentials in Variational Analysis and Optimization

  • Boris S. Mordukhovich
  • Nguyen Mau Nam
  • Nguyen Thi Yen Nhi
    • Categories Nonsmooth Optimization Tags , , , , , ,

    This paper presents a systematic study of partial second-order subdifferentials for extended-real-valued functions, which have already been applied to important issues of variational analysis and constrained optimization in finite-dimensional spaces. The main results concern developing extended calculus rules for these second-order constructions in both finite-dimensional and infinite-dimensional frameworks. We also provide new applications of partial … Read more

    Trajectories of Descent

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
  • Alexander D. Ioffe
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    Steepest descent drives both theory and practice of nonsmooth optimization. We study slight relaxations of two influential notions of steepest descent curves — curves of maximal slope and solutions to evolution equations. In particular, we provide a simple proof showing that lower-semicontinuous functions that are locally Lipschitz continuous on their domains — functions playing a … Read more

    Constrained Bundle Methods for Upper Inexact Oracles with Application to Joint Chance Constrained Energy Problems

  • Claudia Sagastizábal
  • Wim van Ackooij
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming Tags , ,

    Joint chance constrained problems give rise to many algorithmic challenges. Even in the convex case, i.e., when an appropriate transformation of the probabilistic constraint is a convex function, its cutting-plane linearization is just an approximation, produced by an oracle providing subgradient and function values that can only be evaluated inexactly. As a result, the cutting-plane … Read more

    Augmented Lagrangian and Alternating Direction Methods for Convex Optimization: A Tutorial and Some Illustrative Computational Results

  • Jonathan Eckstein
    • Categories Convex Optimization Tags , ,

    The alternating direction of multipliers (ADMM) is a form of augmented Lagrangian algorithm that has experienced a renaissance in recent years due to its applicability to optimization problems arising from “big data” and image processing applications, and the relative ease with which it may be implemented in parallel and distributed computational environments. This paper aims … Read more

    A Douglas-Rachford type primal-dual method for solving inclusions with mixtures of composite and parallel-sum type monotone operators

  • Radu Ioan Bot
  • Christopher Hendrich
    • Categories Convex Optimization Tags , , ,

    In this paper we propose two different primal-dual splitting algorithms for solving inclusions involving mixtures of composite and parallel-sum type monotone operators which rely on an inexact Douglas-Rachford splitting method, however applied in different underlying Hilbert spaces. Most importantly, the algorithms allow to process the bounded linear operators and the set-valued operators occurring in the … Read more

    Convergence analysis of the Peaceman-Rachford splitting method for nonsmooth convex optimization

  • Deren Han
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , ,

    In this paper, we focus on the convergence analysis for the application of the Peaceman-Rachford splitting method to a convex minimization model whose objective function is the sum of a smooth and nonsmooth convex functions. The sublinear convergence rate in term of the worst-case O(1/t) iteration complexity is established if the gradient of the smooth … Read more

    Parallel Coordinate Descent Methods for Big Data Optimization

  • Peter Richtarik
  • Martin Takac
    • Categories Convex Optimization, Parallel Algorithms Tags , , , , , , , ,

    In this work we show that randomized (block) coordinate descent methods can be accelerated by parallelization when applied to the problem of minimizing the sum of a partially separable smooth convex function and a simple separable convex function. The theoretical speedup, as compared to the serial method, and referring to the number of iterations needed … Read more