Nonsmooth Optimization

Preconditioned Proximal Gradient Methods with Conjugate Momentum: A Subspace Perspective

  • Jian Chen
  • Xinmin Yang
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

    In this paper, we propose a descent method for composite optimization problems with linear operators. Specifically, we first design a structure-exploiting preconditioner tailored to the linear operator so that the resulting preconditioned proximal subproblem admits a closed-form solution through its dual formulation. However, such a structure-driven preconditioner may be poorly aligned with the local curvature … Read more

    On the Complexity of Subgradient Methods for Trilevel Hierarchical Generalized Variational Inequalities

  • Lorenzo Lampariello
  • Simone Sagratella
  • Valerio Giuseppe Sasso
    • Categories Convex Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    We study generalized variational inequalities with a three-level hierarchical structure. This setting extends nested GVI models beyond the bilevel case, for which $\mathcal{O}(\delta^{-4})$ complexity bounds are known for any prescribed positive tolerance $\delta$, to a fully three-level hierarchical structure. We analyze a projected averaged subgradient method combined with a Tikhonov-like regularization scheme. Under compactness, maximal … Read more

    Revisiting Superlinear Convergence of Proximal Newton-Like Methods to Degenerate Solutions

  • Ching-pei Lee
  • Stephen Wright
    • Categories Nonsmooth Optimization Tags , , , , ,

    We describe inexact proximal Newton-like methods for solving degenerate regularized optimization problems and for the broader problem of finding a zero of a generalized equation that is the sum of a continuous map and a maximal monotone operator. Superlinear convergence for both the distance to the solution set and a certain measure of first-order optimality … Read more

    Tilt Stability on Riemannian Manifolds with Application to Convergence Analysis of Generalized Riemannian Newton Method

  • Zijian Shi
  • Miantao Chao
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    We generalize tilt stability, a fundamental concept in perturbation analysis of optimization problems in Euclidean spaces, to the setting of Riemannian manifolds. We prove the equivalence of the following conditions: Riemannian tilt stability, Riemannian variational strong convexity, Riemannian uniform quadratic growth, local strong monotonicity of Riemannian subdifferential, strong metric regularity of Riemannian subdifferential, and positive … Read more

    An efficient penalty decomposition algorithm for minimization over sparse symmetric sets

  • Ahmad Mousavi
  • Morteza Kimiaei
  • Saman Babaie-Kafaki
  • Vyacheslav Kungurtsev
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    This paper proposes an improved quasi-Newton penalty decomposition algorithm for the minimization of continuously differentiable functions, possibly nonconvex, over sparse symmetric sets. The method solves a sequence of penalty subproblems approximately via a two-block decomposition scheme: the first subproblem admits a closed-form solution without sparsity constraints, while the second subproblem is handled through an efficient … Read more

    The Maximum Clique Problem under Adversarial Uncertainty: a min-max approach

  • Giovanni Spisso
  • Immanuel M. Bomze
  • Francesco Rinaldi
  • Chiara Faccio
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Other Topics Tags , , ,

    We analyze the problem of identifying large cliques in graphs that are affected by adversarial uncertainty. More specifically, we consider a new formulation, namely the adversarial maximum clique problem, which extends the classical maximum-clique problem to graphs with edges strategically perturbed by an adversary. The proposed mathematical model is thus formulated as a two-player zero-sum … Read more

    An Inexact Modified Quasi-Newton Method for Nonsmooth Regularized Optimization

  • Nathan Allaire
  • Sébastien Le Digabel
  • Dominique Orban
    • Categories Data Science Algorithms, Nonlinear Optimization, Nonsmooth Optimization Tags , , , , , , , ,

    We introduce method iR2N, a modified proximal quasi-Newton method for minimizing the sum of a \(C^1\) function \(f\) and a lower semi-continuous prox-bounded \(h\) that permits inexact evaluations of \(f\), \(\nabla f\) and of the relevant proximal operators. Both \(f\) and \(h\) may be nonconvex. In applications where the proximal operator of \(h\) is not … Read more

    A Proximal-Gradient Method for Solving Regularized Optimization Problems with General Constraints

  • Daniel P. Robinson
  • Frank E. Curtis
  • Xiaoyi Qu
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , , , , ,

    We propose, analyze, and test a proximal-gradient method for solving regularized optimization problems with general constraints. The method employs a decomposition strategy to compute trial steps and uses a merit function to determine step acceptance or rejection. Under various assumptions, we establish a worst-case iteration complexity result, prove that limit points are first-order KKT points, … Read more

    An Elementary Proof of the Near Optimality of LogSumExp Smoothing

  • Thabo Samakhoana
  • Benjamin Grimmer
    • Categories Convex Optimization, Data Science Algorithms, Nonsmooth Optimization Tags , , , ,

    We consider the design of smoothings of the (coordinate-wise) max function in $\mathbb{R}^d$ in the infinity norm. The LogSumExp function $f(x)=\ln(\sum^d_i\exp(x_i))$ provides a classical smoothing, differing from the max function in value by at most $\ln(d)$. We provide an elementary construction of a lower bound, establishing that every overestimating smoothing of the max function must … Read more

    Robust optimality for nonsmooth mathematical programs with equilibrium constraints under data uncertainty

  • Vivek Laha
    • Categories Applications - OR and Management Sciences, Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization, Convex Optimization, Nonlinear Optimization, Nonsmooth Optimization, Robust Optimization Tags

    We develop a unified framework for robust nonsmooth optimization problems with equilibrium constraints (UNMPEC). As a foundation, we study a robust nonsmooth nonlinear program with uncertainty in both the objective function and the inequality constraints (UNP). Using Clarke subdifferentials, we establish Karush–Kuhn–Tucker (KKT)–type necessary optimality conditions under an extended no–nonzero–abnormal–multiplier constraint qualification (ENNAMCQ). When the … Read more