  


Complexity Analysis of Interior Point Algorithms for NonLipschitz and Nonconvex Minimization
Wei Bian(bianweilvse520163.com) Abstract: We propose a first order interior point algorithm for a class of nonLipschitz 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 algorithm is easy to implement and the objective function value is reduced monotonically along the iteration points. We show that the worstcase complexity for finding an $\epsilon$ scaled first order stationary point is $O(\epsilon^{2})$. Moreover, we develop a second order interior point algorithm using the Hessian matrix, and solve a quadratic program with 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 worstcase complexity for finding an $\epsilon$ scaled second order stationary point is reduced to $O(\epsilon^{3/2})$. An $\epsilon$ scaled second order stationary point is an $\epsilon$ scaled first order stationary point. Keywords: constrained nonLipschitz optimization; complexity analysis; interior point method; first order algorithm; second order algorithm Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization ) Category 2: Applications  Science and Engineering Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization ) Citation: Department of Applied Mathematics, The Hong Kong Polytechnic University, July, 2012 Download: [PDF] Entry Submitted: 08/01/2012 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  