complexity

Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality, and Saddle-Points

  • Krishnakumar Balasubramanian
  • Saeed Ghadimi
    • Categories Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    In this paper, we propose and analyze zeroth-order stochastic approximation algorithms for nonconvex and convex optimization, with a focus on addressing constrained optimization, high-dimensional setting, and saddle-point avoiding. To handle constrained optimization, we first propose generalizations of the conditional gradient algorithm achieving rates similar to the standard stochastic gradient algorithm using only zeroth-order information. To … Read more

    On High-order Model Regularization for Multiobjective Optimization

  • L. Calderón
  • Maria A. Diniz-Ehrhardt
  • José Mario Martínez
    • Categories Constrained Nonlinear Optimization Tags , ,

    A p-order regularization method for finding weak stationary points of multiobjective optimization problems with constraints is introduced. Under Holder conditions on the derivatives of the objective functions, complexity results are obtained that generalize properties recently proved for scalar optimization. Article Download View On High-order Model Regularization for Multiobjective Optimization

    Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results

  • Martine Labbé
  • Martin Schmidt
  • Fränk Plein
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Network Optimization Tags , , , , ,

    As a consequence of the liberalisation of the European gas market in the last decades, gas trading and transport have been decoupled. At the core of this decoupling are so-called bookings and nominations. Bookings are special capacity right contracts that guarantee that a specified amount of gas can be supplied or withdrawn at certain entry … Read more

    On the complexity of solving feasibility problems

  • Luís Felipe Bueno
  • José Mario Martínez
    • Categories Nonlinear Systems and Least-Squares Tags , , ,

    We consider feasibility problems defined by a set of constraints that exhibit gradient H\”older continuity plus additional constraints defined by the affordability of obtaining approximate minimizers of quadratic models onto the associated feasible set. Each iteration of the method introduced in this paper involves the approximate minimization of a two-norm regularized quadratic subject to the … Read more

    On the complexity of an Inexact Restoration method for constrained optimization

  • Luís Felipe Bueno
  • José Mario Martínez
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    Recent papers indicate that some algorithms for constrained optimization may exhibit worst-case complexity bounds that are very similar to those of unconstrained optimization algorithms. A natural question is whether well established practical algorithms, perhaps with small variations, may enjoy analogous complexity results. In the present paper we show that the answer is positive with respect … Read more

    Efficient global unconstrained black box optimization

  • Morteza Kimiaei
  • Arnold Neumaier
    • Categories Stochastic Approaches, Unconstrained Optimization Tags , , , ,

    For the unconstrained optimization of black box functions, this paper introduces a new randomized algorithm called VRBBO. In practice, VRBBO matches the quality of other state-of-the-art algorithms for finding, in small and large dimensions, a local minimizer with reasonable accuracy. Although our theory guarantees only local minimizers our heuristic techniques turn VRBBO into an efficient … Read more

    Generalized Stochastic Frank-Wolfe Algorithm with Stochastic “Substitute” Gradient for Structured Convex Optimization

  • Robert M. Freund
  • Haihao Lu
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , , ,

    The stochastic Frank-Wolfe method has recently attracted much general interest in the context of optimization for statistical and machine learning due to its ability to work with a more general feasible region. However, there has been a complexity gap in the guaranteed convergence rate for stochastic Frank-Wolfe compared to its deterministic counterpart. In this work, … Read more

    Coordination of a two-level supply chain with contracts

  • Safia Kedad-Sidhoum
  • Fanny Pascual
  • Siao-Leu Phouratsamay
    • Categories Dynamic Programming, Production and Logistics, 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: he can impose his optimal replenishment plan to the supplier. Our aim is to minimize the supplier’s cost without increasing the … Read more

    On the Complexity of Detecting Convexity over a Box

  • Amir Ali Ahmadi
  • Georgina Hall
    • Categories Convex Optimization, Global Optimization, Nonlinear Optimization Tags , , ,

    It has recently been shown that the problem of testing global convexity of polynomials of degree four is {strongly} NP-hard, answering an open question of N.Z. Shor. This result is minimal in the degree of the polynomial when global convexity is of concern. In a number of applications however, one is interested in testing convexity … Read more

    Stable interior point method for convex quadratic programming with strict error bounds

  • Stefania Bellavia
  • Martin Neuenhofen
    • Categories Quadratic Programming Tags , , ,

    We present a short step interior point method for solving a class of nonlinear programming problems with quadratic objective function. Convex quadratic programming problems can be reformulated as problems in this class. The method is shown to have weak polynomial time complexity. A complete proof of the numerical stability of the method is provided. No … Read more