stochastic optimization

Retrospective Approximation Sequential Quadratic Programming for Stochastic Optimization with General Deterministic Nonlinear Constraints

  • Shagun Gupta
  • Raghu Bollapragada
  • Albert S. Berahas
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Optimization in Data Science Tags , , , ,

    In this paper, we propose a framework based on the Retrospective Approximation (RA) paradigm to solve optimization problems with a stochastic objective function and general nonlinear deterministic constraints. This framework sequentially constructs increasingly accurate approximations of the true problems which are solved to a specified accuracy via a deterministic solver, thereby decoupling the uncertainty from … Read more

    On Multidimensonal Disjunctive Inequalities for Chance-Constrained Stochastic Problems with Finite Support

  • Diego Cattaruzza
  • Martine LabbĂ©
  • Matteo Petris
  • Marius Roland
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    We consider mixed-integer linear chance-constrained problems for which the random vector that parameterizes the feasible region has finite support. Our key objective is to improve branch-and-bound or -cut approaches by introducing new types of valid inequalities that improve the dual bounds and, by this, the overall performance of such methods. We introduce so-called primal-dual as … Read more

    Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees

  • Zhaosong Lu
  • Sanyou Mei
  • Yifeng Xiao
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    In this paper, we study a class of deterministically constrained stochastic optimization problems. Existing methods typically aim to find an \(\epsilon\)-stochastic stationary point, where the expected violations of both constraints and first-order stationarity are within a prescribed accuracy \(\epsilon\). However, in many practical applications, it is crucial that the constraints be nearly satisfied with certainty, … Read more

    A Two Stepsize SQP Method for Nonlinear Equality Constrained Stochastic Optimization

  • Michael J. O'Neill
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , ,

    We develop a Sequential Quadratic Optimization (SQP) algorithm for minimizing a stochastic objective function subject to deterministic equality constraints. The method utilizes two different stepsizes, one which exclusively scales the component of the step corrupted by the variance of the stochastic gradient estimates and a second which scales the entire step. We prove that this … Read more

    On the Trade-Off Between Distributional Belief and Ambiguity: Conservatism, Finite-Sample Guarantees, and Asymptotic Properties

  • Man Yiu Tsang
  • Karmel S. Shehadeh
    • Categories Robust Optimization, Stochastic Programming Tags , , , ,

    We propose and analyze a new data-driven trade-off (TRO) approach for modeling uncertainty that serves as a middle ground between the optimistic approach, which adopts a distributional belief, and the pessimistic distributionally robust optimization approach, which hedges against distributional ambiguity. We equip the TRO model with a TRO ambiguity set characterized by a size parameter … Read more

    Modified Line Search Sequential Quadratic Methods for Equality-Constrained Optimization with Unified Global and Local Convergence Guarantees

  • Albert S. Berahas
  • Raghu Bollapragada
  • Jiahao Shi
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Other Topics Tags , ,

    In this paper, we propose a method that has foundations in the line search sequential quadratic programming paradigm for solving general nonlinear equality constrained optimization problems. The method employs a carefully designed modified line search strategy that utilizes second-order information of both the objective and constraint functions, as required, to mitigate the Maratos effect. Contrary … Read more

    A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity

  • Serge Gratton
  • Sadok Jerad
  • Philippe L. Toint
    • Categories Data Science Algorithms, Nonlinear Optimization Tags , , , ,

    A fully stochastic second-order adaptive-regularization method for unconstrained nonconvex optimization is presented which never computes the objective-function value, but yet achieves the optimal $\mathcal{O}(\epsilon^{-3/2})$ complexity bound for finding first-order critical points. The method is noise-tolerant and the inexactness conditions required for convergence depend on the history of past steps. Applications to cases where derivative evaluation … Read more

    BattOpt: Optimal Facility Planning for Electric Vehicle Battery Recycling

  • Matthew Brun
  • Xu Andy Sun
    • Categories Energy, Global Optimization Applications, Stochastic Programming Tags , , ,

    The electric vehicle (EV) battery supply chain will face challenges in sourcing scarce, expensive minerals required for manufacturing and in disposing of hazardous retired batteries. Integrating recycling technology into the supply chain has the potential to alleviate these issues; however, players in the battery market must design investment plans for recycling facilities. In this paper, … Read more

    A Unified Approach for Maximizing Continuous $\gamma$-weakly DR-submodular Functions

  • Mohammad Pedramfar
  • Christopher Quinn
  • Vaneet Aggarwal
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , ,

    This paper presents a unified approach for maximizing continuous \(\gamma\)-weakly DR-submodular functions that encompasses a range of settings and oracle access types. Our approach includes a Frank-Wolfe type offline algorithm for both monotone and non-monotone functions, with different restrictions on the convex feasible region. We consider settings where the oracle provides access to either the … Read more

    Doubly stochastic primal dual splitting algorithm with variance reduction for saddle point problems

  • Dimitri Papadimitriou
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonlinear Optimization, Unconstrained Optimization Tags , , , , ,

    The structured saddle-point problem involving the infimal convolution in real Hilbert spaces finds applicability in many applied mathematics disciplines. For this purpose, we develop a stochastic primal-dual splitting algorithm with loopless variance-reduction for solving this generic problem. We first prove the weak almost sure convergence of the iterates. We then demonstrate that our algorithm achieves … Read more