complexity

Accelerated Stochastic Peaceman-Rachford Method for Empirical Risk Minimization

  • Jianchao Bai
  • Fengmiao Bian
  • Xiaokai Chang
  • Lin Du
    • Categories Convex Optimization, Stochastic Programming Tags , , , ,

    This work is devoted to studying an Accelerated Stochastic Peaceman-Rachford Splitting Method (AS-PRSM) for solving a family of structural empirical risk minimization problems. The objective function to be optimized is the sum of a possibly nonsmooth convex function and a finite-sum of smooth convex component functions. The smooth subproblem in AS-PRSM is solved by a stochastic gradient method using variance reduction … Read more

    Analysis of the Frank-Wolfe Method for Convex Composite Optimization involving a Logarithmically-Homogeneous Barrier

  • Robert M. Freund
  • Renbo Zhao
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , , ,

    We present and analyze a new generalized Frank-Wolfe method for the composite optimization problem (P): F*:= min_x f(Ax) + h(x), where f is a \theta-logarithmically-homogeneous self-concordant barrier and the function h has bounded domain but is possibly non-smooth. We show that our generalized Frank-Wolfe method requires O((Gap_0 + \theta + Var_h)\ln(\delta_0) + (\theta + Var_h)^2/\epsilon) … Read more

    Efficient Algorithms for Multi-Threaded Interval Scheduling with Machine Availabilities

  • Mariia Anapolska
  • Christina Büsing
  • Tabea Krabs
  • Tobias Mömke
    • Categories Scheduling Tags ,

    In the known Interval Scheduling Problem with Machine Availabilities (ISMA), each machine has a contiguous availability interval and each job has a specific 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

    Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution

  • Bahar Tașkesen
  • Soroosh Shafieezadeh-Abadeh
  • Daniel Kuhn
    • Categories Convex and Nonsmooth Optimization, Robust Optimization, Stochastic Programming Tags , , , , , ,

    Semi-discrete optimal transport problems, which evaluate the Wasserstein distance between a discrete and a generic (possibly non-discrete) probability measure, are believed to be computationally hard. Even though such problems are ubiquitous in statistics, machine learning and computer vision, however, this perception has not yet received a theoretical justification. To fill this gap, we prove that … Read more

    Matching Algorithms and Complexity Results for Constrained Mixed-Integer Optimal Control with Switching Costs

  • Felix Bestehorn
  • Christian Kirches
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms Tags , , , ,

    We extend recent work on the performance of the combinatorial integral approximation decomposition approach for Mixed-Integer Optimal Control Problems (MIOCPs) in the presence of combinatorial constraints or switching costs on an equidistant grid. For the time discretized problem, we reformulate the emerging rounding problem in the decomposition approach as a matching problem on a bipartite … Read more

    The Non-Stop Disjoint Trajectories Problem

  • Benno Hoch
  • Frauke Liers
  • Sarah Neumann
  • Francisco Javier Zaragoza Martínez
    • Categories Combinatorial Optimization, Network Optimization Tags , , , , ,

    Consider an undirected network with traversal times on its edges and a set of commodities with connection requests from sources to destinations and release dates. The non-stop disjoint trajectories problem is to find trajectories that fulfill all requests, such that the commodities never meet. In this extension to the \NP-complete disjoint paths problem, trajectories must … Read more

    Complexity Aspects of Fundamental Questions in Polynomial Optimization

  • Jeffrey Zhang
    • Categories Game Theory, Global Optimization Theory, Nonlinear Optimization Tags , , , ,

    In this thesis, we settle the computational complexity of some fundamental questions in polynomial optimization. These include the questions of (i) finding a local minimum, (ii) testing local minimality of a candidate point, and (iii) deciding attainment of the optimal value. Our results characterize the complexity of these three questions for all degrees of the … Read more

    On the Complexity of Finding a Local Minimizer of a Quadratic Function over a Polytope

  • Amir Ali Ahmadi
  • Jeffrey Zhang
    • Categories Quadratic Programming Tags , , ,

    We show that unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance $c^n$ (for any constant $c \ge 0$) of a local minimizer of an $n$-variate quadratic function over a polytope. This result (even with $c=0$) answers a question of Pardalos and Vavasis that appeared in 1992 on a … Read more

    Complexity Aspects of Local Minima and Related Notions

  • Amir Ali Ahmadi
  • Jeffrey Zhang
    • Categories Global Optimization Theory, Nonlinear Optimization, Semi-definite Programming Tags , , , , ,

    We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariate polynomials. For each type of point, and as a function of the degree of the polynomial, we study the complexity of deciding (1) if a given point is of that type, and (2) if … Read more

    Selective Maximum Coverage and Set Packing

  • Björn Tauer
  • Felix J. L. Willamowski
    • Categories Approximation Algorithms Tags , , , ,

    In this paper we introduce the selective maximum coverage and the selective maximum set packing problem and variants of them. Both problems are strongly related to well studied problems such as maximum coverage, set packing, and (bipartite) hypergraph matching. The two problems are given by a collection of subsets of a ground set and index … Read more