Implementable VU-decomposition methods for composite optimization

• Grant number: 17/15936-2
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: November 01, 2017
• End date: November 30, 2018
• Field of knowledge: Physical Sciences and Mathematics - Mathematics - Applied Mathematics
• Principal Investigator: José Mário Martinez Perez
• Grantee: Shuai Liu
• Host Institution: Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 13/05475-7 - Computational methods in optimization, AP.TEM

Abstract

Nonsmooth optimization arises naturally when modelling real-life problems in energy, finance, signal processing, geometric mechanics. Moreover, smooth problems sometimes lead to the use of nonsmooth optimization methods, to make the solution process manageable in terms of size or structure (for instance by means of Lagrangean or Benders decomposition). It also may happen that a problem is analytically smooth but stiff and, hence, from the numerical viewpoint it appears as being nonsmooth. These considerations show the importance of developing computational and theoretical tools that handle efficiently mathematical optimization problems that are nonsmooth. The research program considers a special class of methods for nonsmooth convex functions, based on the so-called VU-decomposition. The U-structure corresponds to a subpace where, at least locally, the function appears as being smooth, so that a Newton step can be made along the U-directions. In this manner, superlinear speed becomes possible, even for functions without first order derivatives. The theoretical approach, introduced by Lemarechal and Sagastizabal, depends on the ability of making exact proximal computations and properly identifying the (orthogonal) V and U subspaces. Using a bundle-like approach to approximate those calculations, Mifflin and Sagastizabal developed a bundle VU-algorithm that generates a (sub)sequence of iterates converging to a solution at superlinear speed. The question of how to properly identify the V and Ustructures algorithmically remained an open question that this research intends to answer, for an important subclass of convex functions, of composite type. Specifically, the considered functions are the result of composing a closed sublinear convex function with a smooth mapping. Properly identifying the V and U subspaces amounts to a process similar to what in nonlinear programming is done to find active inequality constraints. The extended concept, called smooth manifold of activity, was introduced by Lewis when studying functions said to be partly smooth. The U-subspace is tangent to the activity manifold. The research will study to characterize several concepts related to partial smoothness for composite functions. In particular, we introduce a relaxed space decomposition depending on certain V-epsilon and U-epsilon subspaces that converge continuously to the V- and U-counterparts as epsilon tends to zero. To the new epsilon-VU decomposition corresponds an epsilon-activity set that contains the manifold where function is partlysmooth (akin to finding inequalities that are active up to epsilon in nonlinear programming). This is a natural continuation of a research developed by the candidate jointly with C. Sagastizabal and M. Solodov. Thanks to the supervision of J. M. Martinez in this second stage of the project, the candidate will benefit from the vast expertise in numerical optimization from the PI, thus making it possible the implementation of efficient variants of the developed algorithms. (AU)

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

LIU, SHUAI. A simple version of bundle method with linear programming. COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, v. 72, n. 2, p. 391-412, MAR 2019. (17/15936-2)

LIU, SHUAI; SAGASTIZABAL, CLAUDIA; SOLODOV, MIKHAIL, V. PROXIMAL GRADIENT VU-METHOD WITH SUPERLINEAR CONVERGENCE FOR NONSMOOTH CONVEX OPTIMIZATION. SIAM JOURNAL ON OPTIMIZATION, v. 35, n. 3, p. 29-pg., 2025-01-01. (17/15936-2)