Error bounds for non-polyhedral convex optimization and applications to linear convergence of FDM and PGM

Yulan Liu and Shujun Bi

Applied Mathematics and Computation, 2019, vol. 358, issue C, 418-435

Abstract: This paper is concerned with the composite convex minimization problem where the cost function consists of a smooth convex function with Lipschitz gradient and a closed proper convex function with non-polyhedral epigraph. For this class of non-polyhedral convex optimization problems, we establish the locally Lipschitzian type error bounds for estimating the distance to the solution set from any feasible point near the solution set, and the globally Lipschitzian type error bounds for the smooth function with a special structure, with the help of the local weak sharpness of minima or the calmness of appropriate multifunctions, and also provide verifiable regularity conditions to guarantee them to hold. Although the derived local error bounds are weaker than the one used in Luo and Tseng (1992,1993) and Wei and Jen (2014), when applying them to an inexact feasible descent method (FDM) and proximal gradient method (PGM), respectively, we still achieve the asymptotic Q-linear convergence and R-linear convergence of the objective value sequence and the iterate sequence, respectively. As an illustration of these results, we obtain the linear convergence of the PGM for the trace norm regularized least squares problem under a regularity condition of the linear operator.

Keywords: Local error bounds; Non-polyhedral convex optimization; Convergence rate; Inexact feasible descent method; Inexact proximal gradient method (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300319303364
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:358:y:2019:i:c:p:418-435

DOI: 10.1016/j.amc.2019.04.048

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().