  


Inexact Successive Quadratic Approximation for Regularized Optimization
Chingpei Lee (chingpeics.wisc.edu) Abstract: Successive quadratic approximations, or secondorder proximal methods, are useful for minimizing functions that are a sum of a smooth part and a convex, possibly nonsmooth part that promotes regularization. Most analyses of iteration complexity focus on the special case of proximal gradient method, or accelerated variants thereof. There have been only a few studies of methods that use a secondorder approximation to the smooth part, due in part to the difficulty of obtaining closedform solutions to the subproblems at each iteration. In fact, iterative algorithms may need to be used to find inexact solutions to these subproblems. In this work, we present global analysis of the iteration complexity of inexact successive quadratic approximation methods, showing that an inexact solution of the subproblem that is within a fixed multiplicative precision of optimality suffices to guarantee the same order of convergence rate as the exact version, with complexity related in an intuitive way to the measure of inexactness. Our result allows flexible choices of the secondorder term, including Newton and quasiNewton choices, and does not necessarily require increasing precision of the subproblem solution on later iterations. For problems exhibiting a property related to strong convexity, the algorithms converge at global linear rates. For general convex problems, the convergence rate is linear in early stages, while the overall rate is $O(1/k)$. For nonconvex problems, a firstorder optimality criterion converges to zero at a rate of $O(1/\sqrt{k})$. Keywords: Convex optimization, Nonconvex optimization, Regularized optimization, Variable metric, Proximal method, Secondorder approximation, Inexact method Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization ) Category 2: Nonlinear Optimization Citation: Computational Optimization and Applications, 2019. Download: [PDF] Entry Submitted: 03/03/2018 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  