Search

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 subgradient at the next iteration, like in the proximal schemes), as well as iterations when the associated subgradient is specially constructed and does not correspond either to the current or the next point (this is the case of descent steps in bundle methods). Under the subdifferential-based error bound on the distance to critical points, linear rates of convergence are established. Our analysis applies, among other techniques, to prox-descent for decomposable functions, the proximal-gradient method for a sum of functions, redistributed bundle methods, and a class of algorithms that can be cast in the feasible descent framework for constrained optimization. [ABSTRACT FROM AUTHOR]

We develop new variants of Benders decomposition methods for variational inequality problems. The construction is done by applying the general class of Dantzig–Wolfe decomposition of Luna et al. (Math Program 143(1–2):177–209, 2014) to an appropriately defined dual of the given variational inequality, and then passing back to the primal space. As compared to previous decomposition techniques of the Benders kind for variational inequalities, the following improvements are obtained. Instead of rather specific single-valued monotone mappings, the framework includes a rather broad class of multi-valued maximally monotone ones, and single-valued nonmonotone. Subproblems' solvability is guaranteed instead of assumed, and approximations of the subproblems' mapping are allowed (which may lead, in particular, to further decomposition of subproblems, which may otherwise be not possible). In addition, with a certain suitably chosen approximation, variational inequality subproblems become simple bound-constrained optimization problems, thus easier to solve. [ABSTRACT FROM AUTHOR]

Joint chance constrained problems give rise to many algorithmic challenges. Even in the convex case, i.e., when an appropriate transformation of the probabilistic constraint is a convex function, its cutting-plane linearization is just an approximation, produced by an oracle providing subgradient and function values that can only be evaluated inexactly. As a result, the cutting-plane model may lie above the true constraint. For dealing with such upper inexact oracles, and still solving the problem up to certain precision, a special numerical algorithm must be put in place. We introduce a family of constrained bundle methods, based on the so-called improvement functions, that is shown to be convergent and encompasses many previous approaches as well as new algorithms. Depending on the oracle accuracy, we analyze to what extent the considered methods solve the joint chance constrained program. The approach is assessed on real-life energy problems, arising when dealing with stochastic hydroreservoir management. [ABSTRACT FROM AUTHOR]