Convex Optimization

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

    Mean and variance estimation complexity in arbitrary distributions via Wasserstein minimization

  • Valentio Iverson
  • Stephen A. Vavasis
    • Categories Convex Optimization, Statistics Tags , , , ,

    Parameter estimation is a fundamental challenge in machine learning, crucial for tasks such as neural network weight fitting and Bayesian inference. This paper focuses on the complexity of estimating translation μ∈R^l and shrinkage σ∈R++ parameters for a distribution of the form (1/sigma^l) f_0((x−μ)/σ), where f_0 is a known density in R^l given n samples. We … Read more

    A necessary condition for the guarantee of the superiorization method

  • Kay Barshad
  • Yair Censor
  • Walaa M. Moursi
  • Tyler Weames
  • Henry Wolkowicz
    • Categories Biomedical Applications, Constrained Nonlinear Optimization, Convex Optimization Tags , , , , ,

    We study a method that involves principally convex feasibility-seeking and makes secondary efforts of objective function value reduction. This is the well-known superiorization method (SM), where the iterates of an asymptotically convergent iterative feasibility-seeking algorithm are perturbed by objective function nonascent steps. We investigate the question under what conditions a sequence generated by an SM … Read more

    Stable Set Polytopes with Rank |V(G)|/3 for the Lovász-Schrijver SDP Operator

  • Yu Hin (Gary) Au
    • Categories Combinatorial Optimization, Convex Optimization, Semi-definite Programming Tags , , , ,

    We study the lift-and-project rank of the stable set polytope of graphs with respect to the Lovász–Schrijver SDP operator \( \text{LS}_+ \) applied to the fractional stable set polytope. In particular, we show that for every positive integer \( \ell \), the smallest possible graph with \( \text{LS}_+ \)-rank \( \ell \) contains \( 3\ell … Read more

    Unifying restart accelerated gradient and proximal bundle methods

  • Jiaming Liang
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    This paper presents a novel restarted version of Nesterov’s accelerated gradient method and establishes its optimal iteration-complexity for solving convex smooth composite optimization problems. The proposed restart accelerated gradient method is shown to be a specific instance of the accelerated inexact proximal point framework introduced in “An accelerated hybrid proximal extragradient method for convex optimization … Read more

    Primal-dual proximal bundle and conditional gradient methods for convex problems

  • Jiaming Liang
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , , ,

    This paper studies the primal-dual convergence and iteration-complexity of proximal bundle methods for solving nonsmooth problems with convex structures. More specifically, we develop a family of primal-dual proximal bundle methods for solving convex nonsmooth composite optimization problems and establish the iteration-complexity in terms of a primal-dual gap. We also propose a class of proximal bundle … Read more

    A subgradient splitting algorithm for optimization on nonpositively curved metric spaces

  • Ariel Goodwin
  • Adrian Lewis
    • Categories Convex Optimization, Generalized Convexity/Monoticity, Nonsmooth Optimization

    Many of the primal ingredients of convex optimization extend naturally from Euclidean to Hadamard spaces — nonpositively curved metric spaces like Euclidean, Hilbert, and hyperbolic spaces, metric trees, and more general CAT(0) cubical complexes. Linear structure, however, and the duality theory it supports are absent. Nonetheless, we introduce a new type of subgradient for convex … Read more

    Inexact FISTA-like Methods with Adaptive Backtracking

  • Gabriel Grillo
  • Sandra A. Santos
  • Elias Salomão Helou
    • Categories Biomedical Applications, Convex and Nonsmooth Optimization, Convex Optimization Tags , ,

    Accelerated proximal gradient methods have become a useful tool in large-scale convex optimization, specially for variational regularization with non-smooth priors. Prevailing convergence analysis considers that users can perform the proximal and the gradient steps exactly. Still, in some practical applications, the proximal or the gradient steps must be computed inexactly, which can harm convergence speed … Read more

    Addressing Estimation Errors through Robust Portfolio Optimization

  • Gérard Cornuéjols
  • Ozgun Elci
  • Vrishabh Patil
    • Categories Convex Optimization, Quadratic Programming, Robust Optimization Tags , ,

    It is well known that the performance of the classical Markowitz model for portfolio optimization is extremely sensitive to estimation errors on the expected asset returns. Robust optimization mitigates this issue. We focus on ellipsoidal uncertainty sets around a point estimate of the expected asset returns. An important issue is the choice of the parameters … Read more