Convex and Nonsmooth Optimization

Relaxing kink qualifications and proving convergence rates in piecewise smooth optimization

  • Andreas Griewank
  • Andrea Walther
    • Categories Nonsmooth Optimization Tags , , , , , , ,

    Abstract. In the paper [9] we derived first order (KKT) and second order (SSC) optimality conditions for functions defined by evaluation programs involving smooth elementals and absolute values. In that analysis, a key assumption on the local piecewise linearization was the Linear Independence Kink Qualification (LIKQ), a generalization of the Linear Independence Constraint Qualification (LICQ) … Read more

    Adaptive Fista

  • Peter Ochs
  • Thomas Pock
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    In this paper we propose an adaptively extrapolated proximal gradient method, which is based on the accelerated proximal gradient method (also known as FISTA), however we locally optimize the extrapolation parameter by carrying out an exact (or inexact) line search. It turns out that in some situations, the proposed algorithm is equivalent to a class … Read more

    A One-Parameter Family of Middle Proximal ADMM for Constrained Separable Convex Optimization

  • Jianchao Bai
  • Hongchao Zhang
    • Categories Convex Optimization Tags , , , , , ,

    This work is devoted to studying a family of Middle Proximal Alternating Direction Method of Multipliers (MP-ADM) for solving multi-block constrained separable convex optimization. Such one-parameter family of MP-ADM combines both Jacobian and Gauss-Seidel types of alternating direction method, and proximal point techniques are only applied to the middle subproblems to promote the convergence. We … Read more

    The nonsmooth landscape of phase retrieval

  • Damek Davis
  • Dmitriy Drusvyatskiy
  • Courtney Paquette
    • Categories Nonsmooth Optimization Tags , , , , , ,

    We consider a popular nonsmooth formulation of the real phase retrieval problem. We show that under standard statistical assumptions, a simple subgradient method converges linearly when initialized within a constant relative distance of an optimal solution. Seeking to understand the distribution of the stationary points of the problem, we complete the paper by proving that … Read more

    Set-Completely-Positive Representations and Cuts for the Max-Cut Polytope and the Unit Modulus Lifting

  • Florian Jarre
  • Ya-Feng Liu
  • Felix Lieder
  • Cheng Lu
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    This paper considers a generalization of the “max-cut-polytope” $\conv\{\ xx^T\mid x\in\real^n, \ \ |x_k| = 1 \ \hbox{for} \ 1\le k\le n\}$ in the space of real symmetric $n\times n$-matrices with all-ones-diagonal to a complex “unit modulus lifting” $\conv\{xx\HH\mid x\in\complex^n, \ \ |x_k| = 1 \ \hbox{for} \ 1\le k\le n\}$ in the space of … Read more

    Characterizing and testing subdifferential regularity for piecewise smooth objective functions

  • Andreas Griewank
  • Andrea Walther
    • Categories Nonsmooth Optimization Tags , , , , , ,

    Functions defined by evaluation programs involving smooth elementals and absolute values as well as the max- and min-operator are piecewise smooth. Using piecewise linearization we derived in [7] for this class of nonsmooth functions first and second order conditions for local optimality (MIN). They are necessary and sufficient, eespectively. These generalizations of the classical KKT … Read more

    Weak Stability of $\ell_1hBcminimization Methods in Sparse Data Reconstruction

  • H. Jiang
  • Zhi-Quan Luo
  • Yun-Bin Zhao
    • Categories Convex and Nonsmooth Optimization, Data-Mining, Linear Programming Tags , , , , ,

    As one of the most plausible convex optimization methods for sparse data reconstruction, $\ell_1$-minimization plays a fundamental role in the development of sparse optimization theory. The stability of this method has been addressed in the literature under various assumptions such as restricted isometry property (RIP), null space property (NSP), and mutual coherence. In this paper, … Read more

    Pareto efficient solutions in multi-objective optimization involving forbidden regions

  • Christian Günther
    • Categories Facility Planning and Design, Generalized Convexity/Monoticity, Multi-Criteria Optimization

    In this paper, the aim is to compute Pareto efficient solutions of multi-objective optimization problems involving forbidden regions. More precisely, we assume that the vector-valued objective function is componentwise generalized-convex and acts between a real topological linear pre-image space and a finite-dimensional image space, while the feasible set is given by the whole pre-image space … Read more

    Adaptive Sampling Strategies for Stochastic Optimization

  • Raghu Bollapragada
  • Richard H. Byrd
  • Jorge Nocedal
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , ,

    In this paper, we propose a stochastic optimization method that adaptively controls the sample size used in the computation of gradient approximations. Unlike other variance reduction techniques that either require additional storage or the regular computation of full gradients, the proposed method reduces variance by increasing the sample size as needed. The decision to increase … Read more

    Convergence rates of accelerated proximal gradient algorithms under independent noise

  • Jiang Hao
  • Barrio Roberto
  • Cheng Lizhi
  • Sun Tao
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    We consider an accelerated proximal gradient algorithm for the composite optimization with “independent errors” (errors little related with historical information) for solving linear inverse problems. We present a new inexact version of FISTA algorithm considering deterministic and stochastic noises. We prove some convergence rates of the algorithm and we connect it with the current existing … Read more