Decomposition Algorithm Model for Singly Linearly-Constrained Problems Subject to Lower and Upper Bounds

C. J. Lin, S. Lucidi, Laura Palagi, A. Risi and M. Sciandrone ()
Additional contact information
C. J. Lin: National Taiwan University
S. Lucidi: University of Rome “La Sapienza”
A. Risi: Istituto di Analisi dei Sistemi ed Informatica “A. Ruberti”, CNR
M. Sciandrone: University of Florence

Journal of Optimization Theory and Applications, 2009, vol. 141, issue 1, No 7, 107-126

Abstract: Abstract Many real applications can be formulated as nonlinear minimization problems with a single linear equality constraint and box constraints. We are interested in solving problems where the number of variables is so huge that basic operations, such as the evaluation of the objective function or the updating of its gradient, are very time consuming. Thus, for the considered class of problems (including dense quadratic programs), traditional optimization methods cannot be applied directly. In this paper, we define a decomposition algorithm model which employs, at each iteration, a descent search direction selected among a suitable set of sparse feasible directions. The algorithm is characterized by an acceptance rule of the updated point which on the one hand permits to choose the variables to be modified with a certain degree of freedom and on the other hand does not require the exact solution of any subproblem. The global convergence of the algorithm model is proved by assuming that the objective function is continuously differentiable and that the points of the level set have at least one component strictly between the lower and upper bounds. Numerical results on large-scale quadratic problems arising in the training of support vector machines show the effectiveness of an implemented decomposition scheme derived from the general algorithm model.

Keywords: Large scale optimization; Decomposition methods; Support vector machines (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-008-9489-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:141:y:2009:i:1:d:10.1007_s10957-008-9489-9

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-008-9489-9

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().