complexity

Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization

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

    High-order optimality conditions for convexly-constrained nonlinear optimization problems are analyzed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order $\epsilon$-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that, if derivatives of the objective function up to order $q \geq 1$ … Read more

    On the Existence of Ideal Solutions in Multi-objective 0-1 Integer Programs

  • Natashia Boland
  • Hadi Charkhgard
  • Martin Savelsbergh
    • Categories 0-1 Programming, Multi-Criteria Optimization Tags , , ,

    We study conditions under which the objective functions of a multi-objective 0-1 integer linear program guarantee the existence of an ideal point, meaning the existence of a feasible solution that simultaneously minimizes all objectives. In addition, we study the complexity of recognizing whether a set of objective functions satisfies these conditions: we show that it … Read more

    Complexity bounds for primal-dual methods minimizing the model of objective function

  • Yurii Nesterov
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    We provide Frank-Wolfe ($\equiv$ Conditional Gradients) method with a convergence analysis allowing to approach a primal-dual solution of convex optimization problem with composite objective function. Additional properties of complementary part of the objective (strong convexity) significantly accelerate the scheme. We also justify a new variant of this method, which can be seen as a trust-region … Read more

    Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization

  • Donald Goldfarb
  • Wei Liu
  • Shiqian Ma
  • Xiao Wang
    • Categories Nonlinear Optimization Tags , , , , ,

    In this paper we study stochastic quasi-Newton methods for nonconvex stochastic optimization, where we assume that noisy information about the gradients of the objective function is available via a stochastic first-order oracle ($\SFO$). We propose a general framework for such methods, for which we prove almost sure convergence to stationary points and analyze its worst-case … Read more

    A Subgradient Method for Free Material Design

  • Michal Kočvara
  • Yurii Nesterov
  • Yu Xia
    • Categories Applications - Science and Engineering, Mechanical Engineering Tags , , , , , , , , ,

    A small improvement in the structure of the material could save the manufactory a lot of money. The free material design can be formulated as an optimization problem. However, due to its large scale, second-order methods cannot solve the free material design problem in reasonable size. We formulate the free material optimization (FMO) problem into … Read more

    Complexity of Routing Problems with Release Dates and Deadlines

  • Alan L. Erera
  • Damian Reyes
  • Martin Savelsbergh
    • Categories Combinatorial Optimization, Transportation Tags , ,

    The desire of companies to offer same-day delivery leads to interesting new routing problems. We study the complexity of a setting in which a delivery to a customer is guaranteed to take place within a pre-specified time after the customer places the order. Thus, an order has a release date (when the order is placed) … Read more

    Algorithms for stochastic optimization with expectation constraints

  • Guanghui Lan
  • Zhiqiang Zhou
    • Categories Bound-constrained Optimization, Convex and Nonsmooth Optimization, Stochastic Programming Tags , , , ,

    This paper considers the problem of minimizing an expectation function over a closed convex set, coupled with an expectation constraint on either decision variables or problem parameters. We first present a new stochastic approximation (SA) type algorithm, namely the cooperative SA (CSA), to handle problems with the expectation constraint on devision variables. We show that … Read more

    Worst-Case Hardness of Approximation for Sparse Optimization with L0 Norm

  • Yichen Chen
  • Mengdi Wang
    • Categories Combinatorial Optimization, Nonlinear Optimization Tags , , , ,

    In this paper, we consider sparse optimization problems with L0 norm penalty or constraint. We prove that it is strongly NP-hard to find an approximate optimal solution within certain error bound, unless P = NP. This provides a lower bound for the approximation error of any deterministic polynomial-time algorithm. Applying the complexity result to sparse … Read more

    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