More Like this

1. Biased Kernel Density Estimators for Chance Constrained Optimal Control Problems

   https://doi.org/10.23919/ACC45564.2020.9148040  

   Keil, Rachel E.; Miller, Alexander; Kumar, Mrinal; Rao, Anil V. (July 2020, 2020 American Control Conference)

   null (Ed.)

   A method is developed for transforming chance constrained optimization problems to a form numerically solvable. The transformation is accomplished by reformulating the chance constraints as nonlinear constraints using a method that combines the previously developed Split-Bernstein approximation and kernel density estimator (KDE) methods. The Split-Bernstein approximation in a particular form is a biased kernel density estimator. The bias of this kernel leads to a nonlinear approximation that does not violate the bounds of the original chance constraint. The method of applying biased KDEs to reformulate chance constraints as nonlinear constraints transforms the chance constrained optimization problem to a deterministic optimization problems that retains key properties of the chance constrained optimization problem and can be solved numerically. This method can be applied to chance constrained optimal control problems. As a result, the Split-Bernstein and Gaussian kernels are applied to a chance constrained optimal control problem and the results are compared. 

   more » « less
2. Newton-CG Methods for Nonconvex Unconstrained Optimization with Hölder Continuous Hessian

   https://doi.org/10.1287/moor.2023.0356  

   He, Chuan; Huang, Heng; Lu, Zhaosong (May 2025, Mathematics of Operations Research)

   In this paper, we consider a nonconvex unconstrained optimization problem minimizing a twice differentiable objective function with Hölder continuous Hessian. Specifically, we first propose a Newton-conjugate gradient (Newton-CG) method for finding an approximate first- and second-order stationary point of this problem, assuming the associated Hölder parameters are explicitly known. Then, we develop a parameter-free Newton-CG method without requiring any prior knowledge of these parameters. To the best of our knowledge, this method is the first parameter-free second-order method achieving the best-known iteration and operation complexity for finding an approximate first- and second-order stationary point of this problem. Finally, we present preliminary numerical results to demonstrate the superior practical performance of our parameter-free Newton-CG method over a well-known regularized Newton method. Funding: C. He was partially financially supported by the Wallenberg AI, Autonomous Systems and Software Program funded by the Knut and Alice Wallenberg Foundation. H. Huang was partially financially supported by the National Science Foundation [Award IIS-2347592]. Z. Lu was partially financially supported by the National Science Foundation [Award IIS-2211491], the Office of Naval Research [Award N00014-24-1-2702], and the Air Force Office of Scientific Research [Award FA9550-24-1-0343]. 

   more » « less
3. ALSO-X and ALSO-X+: Better Convex Approximations for Chance Constrained Programs

   https://doi.org/10.1287/opre.2021.2225  

   Jiang, Nan; Xie, Weijun (February 2022, Operations Research)

   In a chance constrained program (CCP), decision makers seek the best decision whose probability of violating the uncertainty constraints is within the prespecified risk level. As a CCP is often nonconvex and is difficult to solve to optimality, much effort has been devoted to developing convex inner approximations for a CCP, among which the conditional value-at-risk (CVaR) has been known to be the best for more than a decade. This paper studies and generalizes the ALSO-X, originally proposed by Ahmed, Luedtke, SOng, and Xie in 2017 , for solving a CCP. We first show that the ALSO-X resembles a bilevel optimization, where the upper-level problem is to find the best objective function value and enforce the feasibility of a CCP for a given decision from the lower-level problem, and the lower-level problem is to minimize the expectation of constraint violations subject to the upper bound of the objective function value provided by the upper-level problem. This interpretation motivates us to prove that when uncertain constraints are convex in the decision variables, ALSO-X always outperforms the CVaR approximation. We further show (i) sufficient conditions under which ALSO-X can recover an optimal solution to a CCP; (ii) an equivalent bilinear programming formulation of a CCP, inspiring us to enhance ALSO-X with a convergent alternating minimization method (ALSO-X+); and (iii) an extension of ALSO-X and ALSO-X+ to distributionally robust chance constrained programs (DRCCPs) under the ∞−Wasserstein ambiguity set. Our numerical study demonstrates the effectiveness of the proposed methods. 

   more » « less
4. A Convex Optimization Approach to Chance-Constrained Linear Stochastic Drift Counteraction Optimal Control

   https://doi.org/10.1109/CDC45484.2021.9683303  

   Tang, Sunbochen; Li, Nan; Kolmanovsky, Ilya; Zidek, Robert (December 2021, Proceedings of 2021 60th IEEE Conference on Decision and Control (CDC))

   In this paper, we propose a convex optimization approach to chance-constrained drift counteraction optimal control (DCOC) problems for linear systems with additive stochastic disturbances. Chance-constrained DCOC aims to compute an optimal control law to maximize the time duration before the probability of violating a prescribed set of constraints can no longer be maintained to be below a specified risk level. While conventional approaches to this problem involve solving a mixed-integer programming problem, we show that an optimal solution to the problem can also be found by solving a convex second-order cone programming problem without integer variables. We illustrate the application of chance-constrained DCOC to an automotive adaptive cruise control example. 

   more » « less
5. A Stochastic Primal-Dual Method for Optimization with Conditional Value at Risk Constraints

   https://doi.org/10.1007/s10957-021-01888-x  

   Madavan, Avinash N.; Bose, Subhonmesh (June 2021, Journal of optimization theory and applications)

   We study a first-order primal-dual subgradient method to optimize risk-constrained risk-penalized optimization problems, where risk is modeled via the popular conditional value at risk (CVaR) measure. The algorithm processes independent and identically distributed samples from the underlying uncertainty in an online fashion and produces an η/√K-approximately feasible and η/√K-approximately optimal point within K iterations with constant step-size, where η increases with tunable risk-parameters of CVaR. We find optimized step sizes using our bounds and precisely characterize the computational cost of risk aversion as revealed by the growth in η. Our proposed algorithm makes a simple modification to a typical primal-dual stochastic subgradient algorithm. With this mild change, our analysis surprisingly obviates the need to impose a priori bounds or complex adaptive bounding schemes for dual variables to execute the algorithm as assumed in many prior works. We also draw interesting parallels in sample complexity with that for chance-constrained programs derived in the literature with a very different solution architecture. 

   more » « less