Thu, 06 May 2021
14:00
Virtual

A proximal quasi-Newton trust-region method for nonsmooth regularized optimization

Dominique Orban
(École Polytechnique Montréal)
Abstract

We develop a trust-region method for minimizing the sum of a smooth term f and a nonsmooth term h, both of which can be nonconvex. Each iteration of our method minimizes a possibly nonconvex model of f+h in a trust region. The model coincides with f+h in value and subdifferential at the center. We establish global convergence to a first-order stationary point when f satisfies a smoothness condition that holds, in particular, when it has Lipschitz-continuous gradient, and h is proper and lower semi-continuous. The model of h is required to be proper, lower-semi-continuous and prox-bounded. Under these weak assumptions, we establish a worst-case O(1/ε^2) iteration complexity bound that matches the best known complexity bound of standard trust-region methods for smooth optimization. We detail a special instance in which we use a limited-memory quasi-Newton model of f and compute a step with the proximal gradient method, resulting in a practical proximal quasi-Newton method. We describe our Julia implementations and report numerical results on inverse problems from sparse optimization and signal processing. Our trust-region algorithm exhibits promising performance and compares favorably with linesearch proximal quasi-Newton methods based on convex models.

This is joint work with Aleksandr Aravkin and Robert Baraldi.

-

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact @email.

Thu, 16 Nov 2017

14:00 - 15:00
L4

New Formulations for Generator Maintenance Scheduling in Hydropower Systems

Professor Miguel Anjos
(École Polytechnique Montréal)
Abstract

Maintenance activities help prevent costly power generator breakdowns but because generators under maintenance are typically unavailable, the impact of maintenance schedules is significant and their cost must be accounted for when planning maintenance. In this paper we address the generator maintenance scheduling problem in hydropower systems. While this problem has been widely studied, specific operating conditions of hydroelectric systems have received less attention. We present a mixed-integer linear programming model that considers the time windows of the maintenance activities, as well as the nonlinearities and disjunctions of the hydroelectric production functions. Because the resulting model is hard to solve, we also propose an extended formulation, a set reduction approach that uses logical conditions for excluding unnecessary set elements from the model, and valid inequalities. Computational experiments using a variety of instances adapted from a real hydropower system in Canada support the conclusion that the extended formulation with set reduction achieves the best results in terms of computational time and optimality gap. This is joint work with Jesus Rodriguez, Pascal Cote and Guy Desaulniers.

Thu, 18 Jun 2015

14:00 - 15:00
L5

Linear Algebra for Matrix-Free Optimization

Dominique Orban
(École Polytechnique Montréal)
Abstract

When formulated appropriately, the broad families of sequential quadratic programming, augmented Lagrangian and interior-point methods all require the solution of symmetric saddle-point linear systems. When regularization is employed, the systems become symmetric and quasi definite. The latter are
indefinite but their rich structure and strong relationships with definite systems enable specialized linear algebra, and make them prime candidates for matrix-free implementations of optimization methods. In this talk, I explore various formulations of the step equations in optimization and corresponding
iterative methods that exploit their structure.

Subscribe to École Polytechnique Montréal