Efficient methods for structured nonconvex optimization and optimization under inexact oracles
(2025)
Files
thesis.pdf
Open Access - Adobe PDF
- 6.48 MB
Details
- Authors
- Supervisors
- Glineur, François
- Abstract
- This thesis revolves around three main optimization frameworks, each ac- counting for one thesis part. In each of them, contributions are spread among theoretical results and fully implementable algorithms. Notably, a particular emphasis has been put throughout this work to either pro- pose parameter-free methods or to specify how to fix the values of an algo- rithms’ parameters. The first part about Tunable Oracle Methods addresses the problem of op- timally coping with inexact updates/information within traditional meth- ods when inexactness is controllable and its (worst-case) impact predictable. Based on an assumed relationship linking the computational cost invested at a given iteration and the level of inexactness incurred, we derive optimal inexactness schedules for a given total computational budget. In the second part about Difference-of-Convex Methods, we highlight various substructures of generic Difference-of-Convex (DC) objectives (e.g. Sum of Minimum-of-Convex) to which individual chapters are dedicated. (DC) objectives represent a broad class of nonconvex and generally nonsmooth functions that enhance and extend the modelling power of convex ones. Their optimization is thereby practically very attractive but unfortunately computationally really difficult. Within each of the aforementioned chap- ters, we endow the substructure with a specific minimization oracle. Com- puting these oracles always amount to solving some convex optimization problem. Then, we analyze what can be achieved with the oracle at hand and how it can be best exploited to harvest the best objective values in rea- sonable computational times. In the last part about Chance-Constrained Programs (CCP), we present pre- solve techniques for optimization problems that exhibit a single proba- bilistic constraint. We focus on the finite-support case, i.e. the random parameter involved in the formulation can take any value among several possible scenarios. Such (CCP) are usually reformulated as mixed-integer convex programs involving binary variables. Under the assumption of quasi-convexity of the probabilistic constraint with respect to the random parameter, we use some geometric arguments in the parameter-space lead- ing to sufficient conditions to reduce the number of binary variables used. These conditions dramatically speed-up the solving of the aforementioned mixed-integer convex programs
- Affiliations
UCLouvain SST/ICTM/INMA - Pôle en ingénierie mathématique
Citations
Van Dessel, G. (2025). Efficient methods for structured nonconvex optimization and optimization under inexact oracles. https://hdl.handle.net/2078.5/275036