December 2021 – Page 3 – Optimization Online

Distributionally risk-receptive and risk-averse network interdiction problems with general ambiguity set

Published: 2021/12/16, Updated: 2022/06/11

Nonlinear Optimization, Stochastic Programming decomposition algorithm, distributionally risk-receptive, distributionally robust optimization, general ambiguity set, stochastic network interdiction

We introduce generalizations of stochastic network interdiction problem with distributional ambiguity. Specifically, we consider a distributionally risk-averse (or robust) network interdiction problem (DRA-NIP) and a distributionally risk-receptive network interdiction problem (DRR-NIP) where a leader maximizes a follower’s minimal expected objective value for either the worst-case or the best-case, respectively, probability distribution belonging to ambiguity set … Read more

The SCIP Optimization Suite 8.0

Published: 2021/12/16, Updated: 2022/01/31

Jasper van Doornmalen

Branch and Cut Algorithms, Integer Programming, Optimization Software and Modeling Systems branch-and-cut, branch-and-price, column generation, constraint integer programming, linear programming, mixed-integer linear programming, mixed-integer nonlinear programming, mixed-integer semidefinite programming, optimization solver, parallelization

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type … Read more

A unified analysis of descent sequences in weakly convex optimization, including convergence rates for bundle methods

Published: 2021/12/15, Updated: 2022/06/23

Complementarity and Variational Inequalities, Nonlinear Optimization bundle methods, descent methods, error bound, linear convergence, model-based methods, proximal descent, proximal gradient method, weak convexity

We present a framework for analyzing convergence and local rates of convergence of a class of descent algorithms, assuming the objective function is weakly convex. The framework is general, in the sense that it combines the possibility of explicit iterations (based on the gradient or a subgradient at the current iterate), implicit iterations (using a … Read more

Bayesian Distributionally Robust Optimization

Published: 2021/12/15, Updated: 2023/02/08

Alexander Shapiro

Enlu Zhou

Yifan Lin

Robust Optimization, Stochastic Programming

We introduce a new framework, Bayesian Distributionally Robust Optimization (Bayesian-DRO), for data-driven stochastic optimization where the underlying distribution is unknown. Bayesian-DRO contrasts with most of the existing DRO approaches in the use of Bayesian estimation of the unknown distribution. To make computation of Bayesian updating tractable, Bayesian-DRO first assumes the underlying distribution takes a parametric … Read more

A nested primal–dual FISTA-like scheme for composite convex optimization problems

Published: 2021/12/14, Updated: 2022/08/05

Silvia Bonettini

Marco Prato

Simone Rebegoldi

Convex Optimization, Nonsmooth Optimization convex optimization, forward--backward algorithms, image deblurring, inertial techniques, primal-dual algorithms

We propose a nested primal–dual algorithm with extrapolation on the primal variable suited for minimizing the sum of two convex functions, one of which is continuously differentiable. The proposed algorithm can be interpreted as an inexact inertial forward–backward algorithm equipped with a prefixed number of inner primal–dual iterations for the proximal evaluation and a “warm–start” … Read more

A covering decomposition algorithm for power grid cyber-network segmentation

Published: 2021/12/13

Applications - OR and Management Sciences defender-attacker-defender, interdiction, mixed-integer programming, power networks, security, trilevel optimization

We present a trilevel interdiction model for optimally segmenting the Supervisory Control and Data Acquisition (SCADA) network controlling an electric power grid. In this formulation, we decide how to partition nodes of the SCADA network in order to minimize the shedding of load from a worst-case cyberattack, assuming that the grid operator has the opportunity … Read more

An adaptive regularization algorithm for unconstrained optimization with inexact function and derivatives values

Published: 2021/12/12

Nicholas I. M. Gould

Philippe L. Toint

Nonlinear Systems and Least-Squares, Unconstrained Optimization adaptive regularization, evaluation complexity, inexact functions and derivative values, nonconvex optimization

An adaptive regularization algorithm for unconstrained nonconvex optimization is proposed that is capable of handling inexact objective-function and derivative values, and also of providing approximate minimizer of arbitrary order. In comparison with a similar algorithm proposed in Cartis, Gould, Toint (2022), its distinguishing feature is that it is based on controlling the relative error between … Read more

Trust-region algorithms: probabilistic complexity and intrinsic noise with applications to subsampling techniques

Published: 2021/12/12

Nonlinear Systems and Least-Squares, Unconstrained Optimization evaluation complexity, finite-sum optimization, inexact functions and derivatives, probabilistic analysis, subsampling methods, trust-region methods

A trust-region algorithm is presented for finding approximate minimizers of smooth unconstrained functions whose values and derivatives are subject to random noise. It is shown that, under suitable probabilistic assumptions, the new method finds (in expectation) an epsilon-approximate minimizer of arbitrary order q > 0 in at most O(epsilon^{-(q+1)}) inexact evaluations of the function and … Read more

Risk-averse Regret Minimization in Multi-stage Stochastic Programs

Published: 2021/12/11

Mehran Poursoltani

Erick Delage

Angelos Georghiou

Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming multi-stage stochastic programming, regret minimization, risk measures, robust optimization

Within the context of optimization under uncertainty, a well-known alternative to minimizing expected value or the worst-case scenario consists in minimizing regret. In a multi-stage stochastic programming setting with a discrete probability distribution, we explore the idea of risk-averse regret minimization, where the benchmark policy can only benefit from foreseeing Delta steps into the future. … Read more

Multiple-Periods Locally-Facet-Based MIP Formulations for the Unit Commitment Problem

Published: 2021/12/11, Updated: 2022/10/26

Linfeng Yang

Shifei Chen

Zhaoyang Dong

(Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Polyhedra compact, convex hull, facet, High-dimensional, locally ideal, polytope, tight, unit commitment

The thermal unit commitment (UC) problem has historically been formulated as a mixed integer quadratic programming (MIQP), which is difficult to solve efficiently, especially for large-scale systems. The tighter characteristic reduces the search space, therefore, as a natural consequence, significantly reduces the computational burden. In literatures, many tightened formulations for a single unit with parts … Read more