String-averaging incremental subgradient methods for constrained convex optimization problems

Author(s)

Rafael Massambone de Oliveira

• Document type: Doctoral Thesis
• Press: São Carlos.
• Institution: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Defense date: 2017-07-12

Examining board members

Maristela Oliveira dos Santos; Roberto Andreani; Marina Andretta; Paulo José da Silva e Silva

• Advisor: Elias Salomão Helou Neto

Abstract

In this doctoral thesis, we propose new iterative methods for solving a class of convex optimization problems. In general, we consider problems in which the objective function is composed of a finite sum of convex functions and the set of constraints is, at least, convex and closed. The iterative methods we propose are basically designed through the combination of incremental subgradient methods and string-averaging algorithms. Furthermore, in order to obtain methods able to solve optimization problems with many constraints (and possibly in high dimensions), generally given by convex functions, our analysis includes an operator that calculates approximate projections onto the feasible set, instead of the Euclidean projection. This feature is employed in the two methods we propose; one deterministic and the other stochastic. A convergence analysis is proposed for both methods and numerical experiments are performed in order to verify their applicability, especially in large scale problems. (AU)

• FAPESP's process: 15/10171-2 - Incremental methods and String-Averaging for non-differentiable convex optimization with inaccurate Subgradients
• Grantee: Rafael Massambone de Oliveira
• Support Opportunities: Scholarships in Brazil - Doctorate