complexity

On the use of third-order models with fourth-order regularization for unconstrained optimization

  • Ernesto G. Birgin
  • José Mario Martínez
  • Sandra Augusta Santos
  • John L. Gardenghi
    • Categories Unconstrained Optimization Tags , , ,

    In a recent paper, it was shown that, for the smooth unconstrained optimization problem, worst-case evaluation complexity $O(\epsilon^{-(p+1)/p})$ may be obtained by means of algorithms that employ sequential approximate minimizations of p-th order Taylor models plus (p + 1)-th order regularization terms. The aforementioned result, which assumes Lipschitz continuity of the p-th partial derivatives, generalizes … Read more

    A Level-set Method For Convex Optimization with a Feasible Solution Path

  • Qihang Lin
  • Selvaprabu Nadarajah
  • Negar Soheili
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    Large-scale constrained convex optimization problems arise in several application domains. First-order methods are good candidates to tackle such problems due to their low iteration complexity and memory requirement. The level-set framework extends the applicability of first-order methods to tackle problems with complicated convex objectives and constraint sets. Current methods based on this framework either rely … Read more

    Computation of exact bootstrap confidence intervals: complexity and deterministic algorithms

  • Dimitris Bertsimas
  • Bradley Sturt
    • Categories Applications - OR and Management Sciences, Approximation Algorithms, Statistics Tags , , , ,

    The bootstrap is a nonparametric approach for calculating quantities, such as confidence intervals, directly from data. Since calculating exact bootstrap quantities is believed to be intractable, randomized resampling algorithms are traditionally used. Motivated by the fact that the variability from randomization can lead to inaccurate outputs, we propose a deterministic approach. First, we establish several … Read more

    Robust Combinatorial Optimization under Convex and Discrete Cost Uncertainty

  • Christoph Buchheim
  • Jannis Kurtz
    • Categories Combinatorial Optimization, Integer Programming, Robust Optimization Tags , , , , ,

    In this survey, we discuss the state-of-the-art of robust combinatorial optimization under uncertain cost functions. We summarize complexity results presented in the literature for various underlying problems, with the aim of pointing out the connections between the different results and approaches, and with a special emphasis on the role of the chosen uncertainty sets. Moreover, … Read more

    Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Nonlinear Optimization Tags ,

    The unconstrained minimization of a sufficiently smooth objective function $f(x)$ is considered, for which derivatives up to order $p$, $p\geq 2$, are assumed to be available. An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order $p$ and that is guaranteed to find a first- and second-order critical point in … Read more

    Robust Combinatorial Optimization under Budgeted-Ellipsoidal Uncertainty

  • Jannis Kurtz
    • Categories 0-1 Programming, Combinatorial Optimization, Robust Optimization Tags , , , ,

    In the field of robust optimization uncertain data is modeled by uncertainty sets, i.e. sets which contain all relevant outcomes of the uncertain parameters. The complexity of the related robust problem depends strongly on the shape of the uncertainty set. Two popular classes of uncertainty are budgeted uncertainty and ellipsoidal uncertainty. In this paper we … Read more

    Randomized Similar Triangles Method: A Unifying Framework for Accelerated Randomized Optimization Methods (Coordinate Descent, Directional Search, Derivative-Free Method)

  • Pavel Dvurechensky
  • Alexander Gasnikov
  • Alexander Tiurin
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , , , , , ,

    In this paper, we consider smooth convex optimization problems with simple constraints and inexactness in the oracle information such as value, partial or directional derivatives of the objective function. We introduce a unifying framework, which allows to construct different types of accelerated randomized methods for such problems and to prove convergence rate theorems for them. … Read more

    Coordination of a two-level supply chain with contracts under complete or asymmetric information

  • Safia Kedad-Sidhoum
  • Fanny Pascual
  • Siao-Leu Phouratsamay
    • Categories Dynamic Programming, Supply Chain Management Tags , , , , ,

    We consider the coordination of planning decisions of a single product in a supply chain composed of one supplier and one retailer by using contracts. We assume that the retailer has the market power to impose his optimal replenishment plan to the supplier. Our concern is on the minimization of the supplier’s cost. In order … Read more

    Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization

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

    Necessary conditions for high-order optimality in smooth nonlinear constrained optimization are explored and their inherent intricacy discussed. A two-phase minimization algorithm is proposed which can achieve approximate first-, second- and third-order criticality and its evaluation complexity is analyzed as a function of the choice (among existing methods) of an inner algorithm for solving subproblems in … Read more

    Lower Bound On the Computational Complexity of Discounted Markov Decision Problems

  • Yichen Chen
  • Mengdi Wang
    • Categories Dynamic Programming, Linear Programming Tags ,

    We study the computational complexity of the infinite-horizon discounted-reward Markov Decision Problem (MDP) with a finite state space $\cS$ and a finite action space $\cA$. We show that any randomized algorithm needs a running time at least $\Omega(\carS^2\carA)$ to compute an $\epsilon$-optimal policy with high probability. We consider two variants of the MDP where the … Read more