complexity

Iteration-complexity of a Rockafellar’s proximal method of multipliers for convex programming based on second-order approximations

  • M. Marques Alves
  • Renato D.C. Monteiro
  • Benar Fux Svaiter
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Global Optimization Tags , , , ,

    This paper studies the iteration-complexity of a new primal-dual algorithm based on Rockafellar’s proximal method of multipliers (PMM) for solving smooth convex programming problems with inequality constraints. In each step, either a step of Rockafellar’s PMM for a second-order model of the problem is computed or a relaxed extragradient step is performed. The resulting algorithm … Read more

    Blessing of Massive Scale: Spatial Graphical Model Estimation with a Total Cardinality Constraint

  • Ethan Fang
  • Mengdi Wang
  • Han Liu
    • Categories Combinatorial Optimization, Statistics Tags , , , ,

    We consider the problem of estimating high dimensional spatial graphical models with a total cardinality constraint (i.e., the l0-constraint). Though this problem is highly nonconvex, we show that its primal-dual gap diminishes linearly with the dimensionality and provide a convex geometry justification of this ‘blessing of massive scale’ phenomenon. Motivated by this result, we propose … Read more

    An Abstract Model for Branching and its Application to Mixed Integer Programming

  • Pierre Le Bodic
  • George L. Nemhauser
    • Categories (Mixed) Integer Linear Programming, Optimization Software Design Principles Tags , , , ,

    The selection of branching variables is a key component of branch-and-bound algorithms for solving Mixed-Integer Programming (MIP) problems since the quality of the selection procedure is likely to have a significant effect on the size of the enumeration tree. State-of-the-art procedures base the selection of variables on their “LP gains”, which is the dual bound … Read more

    Revisiting some results on the sample complexity of multistage stochastic programs and some extensions

  • Marcus de Mendes C. R. Reaiche
    • Categories Stochastic Programming Tags , , ,

    In this work we present explicit definitions for the sample complexity associated with the Sample Average Approximation (SAA) Method for instances and classes of multistage stochastic optimization problems. For such, we follow the same notion firstly considered in Kleywegt et al. (2001). We define the complexity for an arbitrary class of problems by considering its … Read more

    The Budgeted Minimum Cost Flow Problem with Unit Upgrading Cost

  • Christina Büsing
  • Arie M.C.A. Koster
  • Sarah Kirchner
  • Annika Thome
    • Categories Combinatorial Optimization, Dynamic Programming, Network Optimization Tags , , ,

    The budgeted minimum cost flow problem (BMCF(K)) with unit upgrading costs extends the classical minimum cost flow problem by allowing to reduce the cost of at most K arcs. In this paper, we consider complexity and algorithms for the special case of an uncapacitated network with just one source. By a reduction from 3-SAT we … Read more

    From error bounds to the complexity of first-order descent methods for convex functions

  • Jérôme Bolte
  • Trong Phong Nguyen
  • Juan Peypouquet
  • Bruce Suter
    • Categories Convex and Nonsmooth Optimization Tags , , , , , ,

    This paper shows that error bounds can be used as effective tools for deriving complexity results for first-order descent methods in convex minimization. In a first stage, this objective led us to revisit the interplay between error bounds and the Kurdyka-\L ojasiewicz (KL) inequality. One can show the equivalence between the two concepts for convex … Read more

    On the computational complexity of minimum-concave-cost flow in a two-dimensional grid

  • Shabbir Ahmed
  • Qie He
  • George L. Nemhauser
  • Shi Li
    • Categories Combinatorial Optimization, Network Optimization, Production and Logistics Tags , , ,

    We study the minimum-concave-cost flow problem on a two-dimensional grid. We characterize the computational complexity of this problem based on the number of rows and columns of the grid, the number of different capacities over all arcs, and the location of sources and sinks. The concave cost over each arc is assumed to be evaluated … Read more

    Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of $O(\epsilon^{-3/2})$ proved by Cartis, Gould and Toint (IMAJNA 32(4) 2012, pp.1662-1695) for computing an $\epsilon$-approximate first-order critical point can be obtained under significantly weaker assumptions. Moreover, the result is generalized to the case where high-order derivatives are … Read more

    An accelerated non-Euclidean hybrid proximal extragradient-type Algorithm for convex-concave saddle-point Problems

  • Oliver Kolossoski
  • Renato D.C. Monteiro
    • Categories Convex Optimization Tags , , , , , , , ,

    This paper describes an accelerated HPE-type method based on general Bregman distances for solving monotone saddle-point (SP) problems. The algorithm is a special instance of a non-Euclidean hybrid proximal extragradient framework introduced by Svaiter and Solodov [28] where the prox sub-inclusions are solved using an accelerated gradient method. It generalizes the accelerated HPE algorithm presented … Read more

    New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure

  • Robert M. Freund
  • Haihao Lu
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    Motivated by recent work of Renegar, we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods. Our problem of interest is the general convex optimization problem f^* = \min_{x \in Q} f(x), where we presume knowledge of a strict lower bound f_slb < f^*. [Indeed, f_slb is naturally ... Read more