Convex and Nonsmooth Optimization

Efficient QUIC-Based Damped Inexact Iterative Reweighting for Sparse Inverse Covariance Estimation with Nonconvex Partly Smooth Regularization

  • Xiangyu Yang
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    In this paper, we study sparse inverse covariance matrix estimation incorporating partly smooth nonconvex regularizers. To solve the resulting regularized log-determinant problem, we develop DIIR-QUIC—a novel Damped Inexact Iteratively Reweighted algorithm based on QUadratic approximate Inverse Covariance (QUIC) method. Our approach generalizes the classic iteratively reweighted \(\ell_1\) scheme through damped fixed-point updates. A key novelty … Read more

    Dual certificates of primal cone membership

  • Joonyeob Lee
  • Dávid Papp
  • Anita Varga
    • Categories Cone Programming, Convex Optimization, Semi-definite Programming Tags , , , , ,

    We discuss easily verifiable cone membership certificates, that is, certificates proving relations of the form \( b\in K \) for convex cones \(K\) that consist of vectors in the dual cone \(K^*\). Vectors in the dual cone are usually associated with separating hyperplanes, and so they are interpreted as certificates of non-membership in the standard … Read more

    Asymptotically Fair and Truthful Allocation of Public Goods

  • Arnesh Sujanani
    • Categories Convex and Nonsmooth Optimization, Game Theory, Nonlinear Optimization Tags , , ,

    We study the fair and truthful allocation of m divisible public items among n agents, each with distinct preferences for the items. To aggregate agents’ preferences fairly, we focus on finding a core solution. For divisible items, a core solution always exists and can be calculated by maximizing the Nash welfare objective. However, such a … Read more

    Lipschitz-Free Mirror Descent Methods for Non-Smooth Optimization Problems

  • Bowen Yuan
    • Categories Convex Optimization, Nonsmooth Optimization Tags , ,

    The part of the analysis of the convergence rate of the mirror descent method that is connected with the adaptive time-varying step size rules due to Alkousa et al. (MOTOR 2024, pp. 3-18) is corrected. Moreover, a Lipschitz-free mirror descent method that achieves weak ergodic convergence is presented, generalizing the convergence results of the mirror … Read more

    Gradient Methods with Online Scaling Part I. Theoretical Foundations

  • Wenzhi Gao
    • Categories Convex Optimization, Nonlinear Optimization, Unconstrained Optimization Tags , ,

    This paper establishes the theoretical foundations of the online scaled gradient methods (OSGM), a framework that utilizes online learning to adapt stepsizes and provably accelerate first-order methods. OSGM quantifies the effectiveness of a stepsize by a feedback function motivated from a convergence measure and uses the feedback to adjust the stepsize through an online learning … Read more

    A symmetric extrapolated proximal alternating predictor-corrector method for saddle-point problems

  • Feng Ma
    • Categories Convex Optimization Tags , , , ,

    The proximal alternating predictor-corrector (PAPC) method is a widely used first-order algorithm for solving convex-concave saddle-point problems involving both smooth and nonsmooth components. Unlike the primal-dual hybrid gradient (PDHG) method, which incorporates an extrapolation step with parameter $\theta \in (0,1]$ to improve convergence, the existing convergence analysis of PAPC has been limited to the case … Read more

    Multi-cut stochastic approximation methods for solving stochastic convex composite optimization

  • Jiaming Liang
  • Honghao Zhang
  • Renato D.C. Monteiro
    • Categories Convex Optimization, Stochastic Programming Tags , , ,

    The development of a multi-cut stochastic approximation (SA) method for solving stochastic convex composite optimization (SCCO) problems has remained an open challenge. The difficulty arises from the fact that the stochastic multi-cut model, constructed as the pointwise maximum of individual stochastic linearizations, provides a biased estimate of the objective function, with the error being uncontrollable. … Read more

    Inverse Optimization via Learning Feasible Regions

  • Ke Ren
  • Peyman Mohajerin Esfahani
  • Angelos Georghiou
    • Categories (Mixed) Integer Linear Programming, Nonsmooth Optimization, Robust Optimization Tags , , ,

    We study inverse optimization (IO), where the goal is to use a parametric optimization program as the hypothesis class to infer relationships between input-decision pairs. Most of the literature focuses on learning only the objective function, as learning the constraint function (i.e., feasible regions) leads to nonconvex training programs. Motivated by this, we focus on … Read more

    cuHALLaR: A GPU accelerated low-rank augmented Lagrangian method for large-scale semidefinite programming

  • Jacob Aguirre
  • Diego Cifuentes
  • Vincent Guigues
  • Renato D.C. Monteiro
  • Victor Hugo Nascimento
  • Arnesh Sujanani
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , , ,

    This paper introduces cuHALLaR, a GPU-accelerated implementation of the HALLaR method proposed in Monteiro et al. 2024 for solving large-scale semidefinite programming (SDP) problems. We demonstrate how our Julia-based implementation efficiently uses GPU parallelism through optimization of simple, but key, operations, including linear maps, adjoints, and gradient evaluations. Extensive numerical experiments across three problem classes—maximum … Read more

    Subgradient Regularization: A Descent-Oriented Subgradient Method for Nonsmooth Optimization

  • Hanyang Li
  • Ying Cui
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    In nonsmooth optimization, a negative subgradient is not necessarily a descent direction, making the design of convergent descent methods based on zeroth-order and first-order information a challenging task. The well-studied bundle methods and gradient sampling algorithms construct descent directions by aggregating subgradients at nearby points in seemingly different ways, and are often complicated or lack … Read more