Convex and Nonsmooth Optimization

Local Linear Convergence of the Alternating Direction Method of Multipliers for Semidefinite Programming under Strict Complementarity

  • Shucheng Kang
    • Categories Convex Optimization, Semi-definite Programming

    We investigate the local linear convergence properties of the Alternating Direction Method of Multipliers (ADMM) when applied to Semidefinite Programming (SDP). A longstanding belief suggests that ADMM is only capable of solving SDPs to moderate accuracy, primarily due to its sublinear worst-case complexity and empirical observations of slow convergence. We challenge this notion by introducing … Read more

    The Least Singular Value Function in Variational Analysis

  • Mario Jelitte
  • Boris S. Mordukhovich
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Nonsmooth Optimization Tags , , , ,

    Metric regularity is among the central concepts of nonlinear and variational analysis, constrained optimization, and their numerous applications. However, met- ric regularity can be elusive for some important ill-posed classes of problems includ- ing polynomial equations, parametric variational systems, smooth reformulations of complementarity systems with degenerate solutions, etc. The study of stability issues for such … Read more

    New Sufficient and Necessary Conditions for Constrained and Unconstrained Lipschitzian Error Bounds

  • Andreas Fischer
  • Alexey F. Izmailov
  • Mario Jelitte
    • Categories Complementarity and Variational Inequalities, Global Optimization Theory, Nonsmooth Optimization Tags , , , , , , ,

    Local error bounds play a fundamental role in mathematical programming and variational analysis. They are used e.g. as constraint qualifications in optimization, in developing calculus rules for generalized derivatives in nonsmooth and set-valued analysis, and they serve as a key ingredient in the design and convergence analysis of Newton-type methods for solving systems of possibly … Read more

    A Rank-One-Update Method for the Training of Support Vector Machines

  • Florian Jarre
    • Categories Bound-constrained Optimization, Convex Optimization, Data Science Algorithms Tags , ,

    This paper considers convex quadratic programs associated with the training of support vector machines (SVM). Exploiting the special structure of the SVM problem a new type of active set method with long cycles and stable rank-one-updates is proposed and tested (CMU: cycling method with updates). The structure of the problem allows for a repeated simple … Read more

    A Universally Optimal Primal-Dual Method for Minimizing Heterogeneous Compositions

  • Aaron Zoll
  • Benjamin Grimmer
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , ,

    This paper proposes a universal, optimal algorithm for convex minimization problems of the composite form $g_0(x)+h(g_1(x),\dots, g_m(x)) + u(x)$. We allow each $g_j$ to independently range from being nonsmooth Lipschitz to smooth, from convex to strongly convex, described by notions of H\”older continuous gradients and uniform convexity. Note that, although the objective is built from … Read more

    On Sum-Rules for Second-Order Contingent Derivatives

  • Mario Jelitte
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Nonsmooth Optimization Tags , , ,

    We are concerned with contingent derivatives and their second-order counterparts (introduced by Ngai et al.) of set-valued mappings. Special attention is given to the development of new sum-rules for second-order contingent derivatives. To be precise, we want to find conditions under which the second-order contingent derivative of the sum of a smooth and a set-valued … Read more

    A new problem qualification based on approximate KKT conditions for Lipschitzian optimization with application to bilevel programming

  • Isabella Käming
  • Andreas Fischer
  • Alain Zemkoho
    • Categories Bilevel Optimization, Complementarity and Variational Inequalities, Nonsmooth Optimization

    When dealing with general Lipschitzian optimization problems, there are many problem classes where even weak constraint qualications fail at local minimizers. In contrast to a constraint qualification, a problem qualification does not only rely on the constraints but also on the objective function to guarantee that a local minimizer is a Karush-Kuhn-Tucker (KKT) point. For … Read more

    Relaxation methods for pessimistic bilevel optimization

  • Alain Zemkoho
    • Categories Bilevel Optimization, Complementarity and Variational Inequalities, Nonsmooth Optimization Tags , , , ,

    We consider a smooth pessimistic bilevel optimization problem, where the lower-level problem is convex and satisfies the Slater constraint qualification. These assumptions ensure that the Karush-Kuhn-Tucker (KKT) reformulation of our problem is well-defined. We then introduce and study the (i) Scholtes, (ii) Lin and Fukushima, (iii) Kadrani, Dussault and Benchakroun, (iv) Steffensen and Ulbrich, and … Read more

    Interior-point algorithms with full Newton steps for nonsymmetric convex conic optimization

  • Dávid Papp
  • Anita Varga
    • Categories Cone Programming, Convex Optimization Tags , , ,

    We design and analyze primal-dual, feasible interior-point algorithms (IPAs) employing full Newton steps to solve convex optimization problems in standard conic form. Unlike most nonsymmetric cone programming methods, the algorithms presented in this paper require only a logarithmically homogeneous self-concordant barrier (LHSCB) of the primal cone, but compute feasible and \(\varepsilon\)-optimal solutions to both the … Read more

    Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent

  • Wenzhi Gao
    • Categories Convex Optimization, Nonlinear Optimization Tags

    This paper investigates the convergence properties of the hypergradient descent method (HDM), a 25-year-old heuristic originally proposed for adaptive stepsize selection in stochastic first-order methods. We provide the first rigorous convergence analysis of HDM using the online learning framework of [Gao24] and apply this analysis to develop new state-of-the-art adaptive gradient methods with empirical and … Read more