Nonsmooth Optimization

Accelerating block-decomposition first-order methods for solving composite saddle-point and two-player Nash equilibrium problems

  • Yunlong He
  • Renato D.C. Monteiro
    • Categories Convex Optimization, Generalized Convexity/Monoticity, Nonsmooth Optimization Tags , , , , , ,

    This article considers the two-player composite Nash equilibrium (CNE) problem with a separable non-smooth part, which is known to include the composite saddle-point (CSP) problem as a special case. Due to its two-block structure, this problem can be solved by any algorithm belonging to the block-decomposition hybrid proximal-extragradient (BD-HPE) framework. The framework consists of a … Read more

    About [q]-regularity properties of collections of sets

  • Alexander Y. Kruger
  • Nguyen H. Thao
    • Categories Nonsmooth Optimization

    We examine three primal space local Hoelder type regularity properties of finite collections of sets, namely, [q]-semiregularity, [q]-subregularity, and uniform [q]-regularity as well as their quantitative characterizations. Equivalent metric characterizations of the three mentioned regularity properties as well as a sufficient condition of [q]-subregularity in terms of Frechet normals are established. The relationships between [q]-regularity … Read more

    Quantitative Characterizations of Regularity Properties of Collections of Sets

  • Alexander Y. Kruger
  • Nguyen H. Thao
    • Categories Nonsmooth Optimization

    Several primal and dual characterizations of regularity properties of collections of sets in normed linear spaces are discussed. Relationships between regularity properties of collections of sets and those of set-valued mappings are provided. CitationJOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS (2015) 164:41–67ArticleDownload View PDF

    Quadratic growth and critical point stability of semi-algebraic functions

  • Dmitriy Drusvyatskiy
  • Alexander D. Ioffe
    • Categories Nonsmooth Optimization Tags , , ,

    We show that quadratic growth of a semi-algebraic function is equivalent to strong metric subregularity of the subdifferential — a kind of stability of generalized critical points. In contrast, this equivalence can easily fail outside of the semi-algebraic setting. Citation13 pages, September, 2013ArticleDownload View PDF

    Separable Approximations and Decomposition Methods for the Augmented Lagrangian

  • Burak Buke
  • Peter Richtarik
  • Rachael Tappenden
    • Categories Convex Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , , , , , , ,

    In this paper we study decomposition methods based on separable approximations for minimizing the augmented Lagrangian. In particular, we study and compare the Diagonal Quadratic Approximation Method (DQAM) of Mulvey and Ruszczy\'{n}ski and the Parallel Coordinate Descent Method (PCDM) of Richt\'{a}rik and Tak\'{a}\v{c}. We show that the two methods are equivalent for feasibility problems up … Read more

    Inexact Coordinate Descent: Complexity and Preconditioning

  • Jacek Gondzio
  • Peter Richtarik
  • Rachael Tappenden
    • Categories Convex Optimization, Nonlinear Systems and Least-Squares, Nonsmooth Optimization Tags , , , , ,

    In this paper we consider the problem of minimizing a convex function using a randomized block coordinate descent method. One of the key steps at each iteration of the algorithm is determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is solved exactly. … Read more

    A direct splitting method for nonsmooth variational inequalities

  • Yunier Bello-Cruz
  • R. Diaz Millan
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Nonsmooth Optimization

    We propose a direct splitting method for solving nonsmooth variational inequality problems in Hilbert spaces. The weak convergence is established, when the operator is the sum of two point-to-set and monotone operators. The proposed method is a natural extension of the incremental subgradient method for nondifferentiable optimization, which explores strongly the structure of the operator … 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

    On smoothness properties of optimal value functions at the boundary of their domain under complete convexity

  • Oliver Stein
  • Nathan Sudermann-Merx
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    This article studies continuity and directional differentiability properties of optimal value functions, in particular at boundary points of their domain. We extend and complement standard continuity results from W.W. Hogan, Point-to-set maps in mathematical programming, SIAM Review, Vol. 15 (1973), 591-603, for abstract feasible set mappings under complete convexity as well as standard differentiability results … Read more