  


Analysis of the Gradient Method with an ArmijoWolfe Line Search on a Class of Nonsmooth Convex Functions
Azam Asl (aa2821nyu.edu) Abstract: It has long been known that the gradient (steepest descent) method may fail on nonsmooth problems, but the examples that have appeared in the literature are either devised specifically to defeat a gradient or subgradient method with an exact line search or are unstable with respect to perturbation of the initial point. We give an analysis of the gradient method with steplengths satisfying the Armijo and Wolfe inexact line search conditions on the nonsmooth convex function $f(x) = ax^{(1)} + \sum_{i=2}^{n} x^{(i)}$. We show that if $a$ is sufficiently large, satisfying a condition that depends only on the Armijo parameter, then, when the method is initiated at any point $x_0 \in \R^n$ with $x^{(1)}_0\not = 0$, the iterates converge to a point $\bar x$ with $\bar x^{(1)}=0$, although $f$ is unbounded below. We also give conditions under which the iterates $f(x_k)\to\infty$, using a specific ArmijoWolfe bracketing line search. Our experimental results demonstrate that our analysis is reasonably tight. Keywords: Steepest descent method, Convex Optimization, Nonsmooth Optimization Category 1: Convex and Nonsmooth Optimization Citation: https://arxiv.org/abs/1711.08517 Download: [PDF] Entry Submitted: 11/27/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  