complexity

Efficient parameter-free restarted accelerated gradient methods for convex and strongly convex optimization

  • Arnesh Sujanani
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonlinear Optimization Tags , , , , ,

    This paper develops a new parameter-free restarted method, namely RPF-SFISTA, and a new parameter-free aggressive regularization method, namely A-REG, for solving strongly convex and convex composite optimization problems, respectively. RPF-SFISTA has the major advantage that it requires no knowledge of both the strong convexity parameter of the entire composite objective and the Lipschitz constant of … Read more

    Examples of slow convergence for adaptive regularization optimization methods are not isolated

  • Philippe L. Toint
    • Categories Nonlinear Optimization Tags , ,

    The adaptive regularization algorithm for unconstrained nonconvex optimization was shown in Nesterov and Polyak (2006) and Cartis, Gould and Toint (2011) to  require, under standard assumptions, at most O(\epsilon^{3/(3-q)}) evaluations of the objective function and its derivatives of degrees one and two to produce an \epsilon-approximate critical point of order q in {1,2}. This bound … Read more

    Horoballs and the subgradient method

  • Adrian Lewis
    • Categories Convex and Nonsmooth Optimization, Other Topics Tags , , , , ,

    To explore convex optimization on Hadamard spaces, we consider an iteration in the style of a subgradient algorithm. Traditionally, such methods assume that the underlying spaces are manifolds and that the objectives are geodesically convex: the methods are described using tangent spaces and exponential maps. By contrast, our iteration applies in a general Hadamard space, … Read more

    The Balanced Facility Location Problem: Complexity and Heuristics

  • Malena Schmidt
  • Bismark Singh
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization Tags , , , ,

    In a recent work, Schmitt and Singh propose a new quadratic facility location model to address ecological challenges faced by policymakers in Bavaria, Germany. Building on this previous work, we significantly extend our understanding of this new problem. We develop connections to traditional combinatorial optimization models and show the problem is NP-hard. We then develop … Read more

    Mind the \(\tilde{O}\): asymptotically better, but still impractical, quantum distributed algorithms

  • David E. Bernal Neira
    • Categories Combinatorial Optimization, Graphs and Matroids Tags , , , ,

    \(\) The CONGEST and CONGEST-CLIQUE models have been carefully studied to represent situations where the communication bandwidth between processors in a network is severely limited. Messages of only \( O(log(n)) \) bits of information each may be sent between processors in each round. The quantum versions of these models allow the processors instead to communicate … Read more

    On the Number of Pivots of Dantzig’s Simplex Methods for Linear and Convex Quadratic Programs

  • Shaoning Han
    • Categories Complementarity and Variational Inequalities, Linear Programming, Quadratic Programming Tags , , , , ,

    Refining and extending works by Ye and Kitahara-Mizuno, this paper presents new results on the number of pivots of simplex-type methods for solving linear programs of the Leontief kind, certain linear complementarity problems of the P kind, and nonnegative constrained convex quadratic programs. Our results contribute to the further understanding of the complexity and efficiency … Read more

    The complexity of first-order optimization methods from a metric perspective

  • Adrian Lewis
  • Tonghua Tian
    • Categories Nonsmooth Optimization, Other Topics Tags , , , , ,

    A central tool for understanding first-order optimization algorithms is the Kurdyka-Lojasiewicz inequality. Standard approaches to such methods rely crucially on this inequality to leverage sufficient decrease conditions involving gradients or subgradients. However, the KL property fundamentally concerns not subgradients but rather “slope”, a purely metric notion. By highlighting this view, and avoiding any use of … Read more

    A New Inexact Proximal Linear Algorithm with Adaptive Stopping Criteria for Robust Phase Retrieval

  • Zhong Zheng
  • Shiqian Ma
  • Lingzhou Xue
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    This paper considers the robust phase retrieval problem, which can be cast as a nonsmooth and nonconvex optimization problem. We propose a new inexact proximal linear algorithm with the subproblem being solved inexactly. Our contributions are two adaptive stopping criteria for the subproblem. The convergence behavior of the proposed methods is analyzed. Through experiments on … Read more

    On the B-differential of the componentwise minimum of two affine vector functions

  • Jean-Pierre Dussault
  • Jean Charles Gilbert
  • Baptiste Plaquevent-Jourdain
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Nonsmooth Optimization Tags , , , , , , , , , , , , , , ,

    This paper focuses on the description and computation of the B-differential of the componentwise minimum of two affine vector functions. This issue arises in the reformulation of the linear complementarity problem with the Min C-function. The question has many equivalent formulations and we identify some of them in linear algebra, convex analysis and discrete geometry. … Read more

    Multithread Interval Scheduling with Flexible Machine Availabilities: Complexity and Efficient Algorithms

  • Mariia Anapolska
  • Christina Büsing
  • Tabea Brandt
  • Tobias Mömke
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization Tags , ,

    In the known Interval Scheduling problem with Machine Availabilities (ISMA), each machine has a contiguous availability interval and each job has a specic time interval which has to be scheduled. The objective is to schedule all jobs such that the machines’ availability intervals are respected or to decide that there exists no such schedule. We … Read more