  


HagerZhang Active Set Algorithm for LargeScale Continuous Knapsack Problems
Ruhollah Tavakoli(rohtavgmail.com) Abstract: The structure of many realworld optimization problems includes minimization of a nonlinear (or quadratic) functional subject to bound and singly linear constraints (in the form of either equality or bilateral inequality) which are commonly called as continuous knapsack problems. Since there are efficient methods to solve largescale bound constrained nonlinear programs, it is desirable to adapt these methods to solve knapsack problems, while preserving their efficiency and convergence theories. The goal of this paper is to introduce a general framework to extend a boxconstrained optimization solver to solve knapsack problems. This framework includes two main ingredients which are O(n) methods; in terms of the computational cost and required memory; for the projection onto the knapsack constrains and the nullspace manipulation of the related linear constraint. The main focus of this work is on the extension of HagerZhang active set algorithm (SIAM J. Optim. 2006, pp. 526557). The main reasons for this choice was its promising efficiency in practice as well as its excellent convergence theories (e.g., superlinear local convergence rate without strict complementarity assumption). Moreover, this method does not use any explicit form of second order information and/or solution of linear systems during iteration which makes it an ideal for largescale problems. The efficient implementation of the method is discussed in details. Keywords: degenerate constraints, gradient projection, linearly constrained optimization, null space method, singly linear bound constrained optimization, superlinear convergence, support vector machines Category 1: Nonlinear Optimization Category 2: Applications  OR and Management Sciences Category 3: Applications  Science and Engineering Citation: R. Tavakoli, HagerZhang Active Set Algorithm for LargeScale Continuous Knapsack Problems, preprint, 2009. Download: [PDF] Entry Submitted: 09/17/2009 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  