A derivative-free 𝒱𝒰-algorithm for convex finite-max problems. (3rd May 2020)

• Record Type: Journal Article
• Authors: Hare, Warren; Planiden, Chayne; Sagastizábal, Claudia
• Is Part Of: Optimization methods and software. Volume 35:Number 3(2020)
• Page Start: 521
• Page End: 559
• Publication Date: 2020-05-03
• Subjects: Convex minimization -- derivative-free optimization -- finite-max function -- proximal-point mapping -- U-gradient -- U-Hessian -- VU-algorithm -- VU-decomposition; Primary 49M30 -- 90C56 -- Secondary 65K10 -- 90C20; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2019.1668944
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: The V U -algorithm is a superlinearly convergent method for minimizing nonsmooth, convex functions. At each iteration, the algorithm works with a certain V -space and its orthogonal U -space, such that the nonsmoothness of the objective function is concentrated on its projection onto the V -space, and on the U -space the projection is smooth. This structure allows for an alternation between a Newton-like step where the function is smooth, and a proximal-point step that is used to find iterates with promising V U -decompositions. We establish a derivative-free variant of the V U -algorithm for convex finite-max objective functions. We show global convergence and provide numerical results from a proof-of-concept implementation, which demonstrates the feasibility and practical value of the approach. We also carry out some tests using nonconvex functions and discuss the results.