An optimally fast objective-function-free minimization algorithm using random subspaces
ArticleDownload View PDF
Stochastic Programming
Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms
We present Zeroth-order Riemannian Averaging Stochastic Approximation (\texttt{Zo-RASA}) algorithms for stochastic optimization on Riemannian manifolds. We show that \texttt{Zo-RASA} achieves optimal sample complexities for generating $\epsilon$-approximation first-order stationary solutions using only one-sample or constant-order batches in each iteration. Our approach employs Riemannian moving-average stochastic gradient estimators, and a novel Riemannian-Lyapunov analysis technique for convergence analysis. … Read more
A Bilevel Optimization Approach for a Class of Combinatorial Problems with Disruptions and Probing
We consider linear combinatorial optimization problems under uncertain disruptions that increase the cost coefficients of the objective function. A decision-maker, or planner, can invest resources to probe the components (i.e., the coefficients) in order to learn their disruption status. In the proposed probing optimization problem, the planner, knowing just the disruptions’ probabilities, selects which components … Read more
Inexact Newton methods with matrix approximation by sampling for nonlinear least-squares and systems
We develop and analyze stochastic inexact Gauss-Newton methods for nonlinear least-squares problems and inexact Newton methods for nonlinear systems of equations. Random models are formed using suitable sampling strategies for the matrices involved in the deterministic models. The analysis of the expected number of iterations needed in the worst case to achieve a desired level … Read more
The Terminator: An Integration of Inner and Outer Approximations for Solving Regular and Distributionally Robust Chance Constrained Programs via Variable Fixing
We present a novel approach aimed at enhancing the efficacy of solving both regular and distributionally robust chance constrained programs using an empirical reference distribution. In general, these programs can be reformulated as mixed-integer programs (MIPs) by introducing binary variables for each scenario, indicating whether a scenario should be satisfied. While existing methods have predominantly … Read more
Gradient-based rho Parameter for Progressive Hedging
Watson and Woodruff (2011) developed a heuristic for computing variable-dependent values of the penalty parameter $\rho$ from the model itself. We combine this heuristic with a gradient-based method, in order to obtain a new method for calculating $\rho$ values. We then introduce a method for iteratively computing variable-dependent $\rho$ values. This method is based on … Read more
Distributions and Bootstrap for Data-based Stochastic Programming
In the context of optimization under uncertainty, we consider various combinations of distribution estimation and resampling (bootstrap and bagging) for obtaining samples used to acquire a solution and for computing a confidence interval for an optimality gap. This paper makes three experimental contributions to on-going research in data driven stochastic programming: a) most of the … Read more
Almost-sure convergence of iterates and multipliers in stochastic sequential quadratic optimization
Stochastic sequential quadratic optimization (SQP) methods for solving continuous optimization problems with nonlinear equality constraints have attracted attention recently, such as for solving large-scale data-fitting problems subject to nonconvex constraints. However, for a recently proposed subclass of such methods that is built on the popular stochastic-gradient methodology from the unconstrained setting, convergence guarantees have been … Read more
Enhancing explainability of stochastic programming solutions via scenario and recourse reduction
Stochastic programming (SP) is a well-studied framework for modeling optimization problems under uncertainty. However, despite the significant advancements in solving large SP models, they are not widely used in industrial practice, often because SP solutions are difficult to understand and hence not trusted by the user. Unlike deterministic optimization models, SP models generally involve recourse … Read more
Stability of Markovian Stochastic Programming
Multi-stage stochastic programming is notoriously hard, since solution methods suffer from the curse of dimensionality. Recently, stochastic dual dynamic programming has shown promising results for Markovian problems with many stages and a moderately large state space. In order to numerically solve these problems simple discrete representations of Markov processes are required but a convincing theoretical … Read more