Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/21435
Title: Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization
Authors: Bian, W
Chen, X 
Ye, Y
Keywords: Interior point method
Complexity analysis
Constrained non-Lipschitz optimization
First order algorithm
Second order algorithm
Issue Date: 2014
Publisher: Springer Verlag
Source: Mathematical programming, 2014, v. 149, no. 1-2, p. 301-327 How to cite?
Journal: Mathematical Programming 
Abstract: We propose a first order interior point algorithm for a class of non-Lipschitz and nonconvex minimization problems with box constraints, which arise from applications in variable selection and regularized optimization. The objective functions of these problems are continuously differentiable typically at interior points of the feasible set. Our first order algorithm is easy to implement and the objective function value is reduced monotonically along the iteration points. We show that the worst-case iteration complexity for finding an ? scaled first order stationary point is (Formula Presented). Furthermore, we develop a second order interior point algorithm using the Hessian matrix, and solve a quadratic program with a ball constraint at each iteration. Although the second order interior point algorithm costs more computational time than that of the first order algorithm in each iteration, its worst-case iteration complexity for finding an ? scaled second order stationary point is reduced to (Formula Presented.). Note that an ? scaled second order stationary point must also be an ? scaled first order stationary point.
URI: http://hdl.handle.net/10397/21435
ISSN: 0025-5610
DOI: 10.1007/s10107-014-0753-5
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

11
Last Week
0
Last month
1
Citations as of May 21, 2017

WEB OF SCIENCETM
Citations

11
Last Week
1
Last month
1
Citations as of May 23, 2017

Page view(s)

31
Last Week
3
Last month
Checked on May 21, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.