IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v141y2009i1d10.1007_s10957-008-9489-9.html
   My bibliography  Save this article

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

Author

Listed:
  • C. J. Lin

    (National Taiwan University)

  • S. Lucidi

    (University of Rome “La Sapienza”)

  • L. Palagi

    (University of Rome “La Sapienza”)

  • A. Risi

    (Istituto di Analisi dei Sistemi ed Informatica “A. Ruberti”, CNR)

  • M. Sciandrone

    (University of Florence)

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.

Suggested Citation

  • C. J. Lin & S. Lucidi & L. Palagi & A. Risi & M. Sciandrone, 2009. "Decomposition Algorithm Model for Singly Linearly-Constrained Problems Subject to Lower and Upper Bounds," Journal of Optimization Theory and Applications, Springer, vol. 141(1), pages 107-126, April.
    • Handle: RePEc:spr:joptap:v:141:y:2009:i:1:d:10.1007_s10957-008-9489-9
    DOI: 10.1007/s10957-008-9489-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-008-9489-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-008-9489-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. O. L. Mangasarian & M. E. Thompson, 2006. "Massive Data Classification via Unconstrained Support Vector Machines," Journal of Optimization Theory and Applications, Springer, vol. 131(3), pages 315-325, December.
    2. José R. Correa & Andreas S. Schulz & Nicolás E. Stier-Moses, 2004. "Selfish Routing in Capacitated Networks," Mathematics of Operations Research, INFORMS, vol. 29(4), pages 961-976, November.
    3. Chihwa Kao & Lung-fei Lee & Mark M. Pitt, 2001. "Simulated Maximum Likelihood Estimation of the Linear Expenditure System with Binding Non-Negativity Constraints," Annals of Economics and Finance, Society for AEF, vol. 2(1), pages 215-235, May.
    4. Joachims, Thorsten, 1998. "Making large-scale SVM learning practical," Technical Reports 1998,28, Technische Universität Dortmund, Sonderforschungsbereich 475: Komplexitätsreduktion in multivariaten Datenstrukturen.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Dellepiane, Umberto & Palagi, Laura, 2015. "Using SVM to combine global heuristics for the Standard Quadratic Problem," European Journal of Operational Research, Elsevier, vol. 241(3), pages 596-605.
    2. Paul Tseng & Sangwoon Yun, 2010. "A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training," Computational Optimization and Applications, Springer, vol. 47(2), pages 179-206, October.
    3. Ion Necoara & Andrei Patrascu, 2014. "A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints," Computational Optimization and Applications, Springer, vol. 57(2), pages 307-337, March.
    4. Amir Beck, 2014. "The 2-Coordinate Descent Method for Solving Double-Sided Simplex Constrained Minimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 162(3), pages 892-919, September.
    5. Andrea Cristofari, 2019. "An almost cyclic 2-coordinate descent method for singly linearly constrained problems," Computational Optimization and Applications, Springer, vol. 73(2), pages 411-452, June.
    6. Cassioli, A. & Di Lorenzo, D. & Sciandrone, M., 2013. "On the convergence of inexact block coordinate descent methods for constrained optimization," European Journal of Operational Research, Elsevier, vol. 231(2), pages 274-281.
    7. Giampaolo Liuzzi & Laura Palagi & Mauro Piacentini, 2010. "On the convergence of a Jacobi-type algorithm for Singly Linearly-Constrained Problems Subject to simple Bounds," DIS Technical Reports 2010-01, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    8. I. V. Konnov, 2016. "Selective bi-coordinate variations for resource allocation type problems," Computational Optimization and Applications, Springer, vol. 64(3), pages 821-842, July.
    9. Leonardo Galli & Alessandro Galligari & Marco Sciandrone, 2020. "A unified convergence framework for nonmonotone inexact decomposition methods," Computational Optimization and Applications, Springer, vol. 75(1), pages 113-144, January.
    10. Tommaso Colombo & Simone Sagratella, 2020. "Distributed algorithms for convex problems with linear coupling constraints," Journal of Global Optimization, Springer, vol. 77(1), pages 53-73, May.
    11. Andrea Manno & Laura Palagi & Simone Sagratella, 2018. "Parallel decomposition methods for linearly constrained problems subject to simple bound with application to the SVMs training," Computational Optimization and Applications, Springer, vol. 71(1), pages 115-145, September.
    12. G. Liuzzi & S. Lucidi & F. Rinaldi, 2012. "Derivative-free methods for bound constrained mixed-integer optimization," Computational Optimization and Applications, Springer, vol. 53(2), pages 505-526, October.
    13. David Di Lorenzo & Alessandro Galligari & Marco Sciandrone, 2015. "A convergent and efficient decomposition method for the traffic assignment problem," Computational Optimization and Applications, Springer, vol. 60(1), pages 151-170, January.
    14. Andrei Patrascu & Ion Necoara, 2015. "Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization," Journal of Global Optimization, Springer, vol. 61(1), pages 19-46, January.
    15. Giampaolo Liuzzi & Stefano Lucidi & Francesco Rinaldi, 2015. "Derivative-Free Methods for Mixed-Integer Constrained Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 164(3), pages 933-965, March.
    16. Veronica Piccialli & Marco Sciandrone, 2022. "Nonlinear optimization and support vector machines," Annals of Operations Research, Springer, vol. 314(1), pages 15-47, July.
    17. G. Cocchi & G. Liuzzi & A. Papini & M. Sciandrone, 2018. "An implicit filtering algorithm for derivative-free multiobjective optimization with box constraints," Computational Optimization and Applications, Springer, vol. 69(2), pages 267-296, March.
    18. P. Tseng & S. Yun, 2009. "Block-Coordinate Gradient Descent Method for Linearly Constrained Nonsmooth Separable Optimization," Journal of Optimization Theory and Applications, Springer, vol. 140(3), pages 513-535, March.
    19. Veronica Piccialli & Marco Sciandrone, 2018. "Nonlinear optimization and support vector machines," 4OR, Springer, vol. 16(2), pages 111-149, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Andrea Manno & Laura Palagi & Simone Sagratella, 2018. "Parallel decomposition methods for linearly constrained problems subject to simple bound with application to the SVMs training," Computational Optimization and Applications, Springer, vol. 71(1), pages 115-145, September.
    2. Hoang, Nam H. & Vu, Hai L. & Lo, Hong K., 2018. "An informed user equilibrium dynamic traffic assignment problem in a multiple origin-destination stochastic network," Transportation Research Part B: Methodological, Elsevier, vol. 115(C), pages 207-230.
    3. Daron Acemoglu & Asuman Ozdaglar, 2005. "Competition and Efficiency in Congested Markets," NBER Working Papers 11201, National Bureau of Economic Research, Inc.
    4. Luca Zanni, 2006. "An Improved Gradient Projection-based Decomposition Technique for Support Vector Machines," Computational Management Science, Springer, vol. 3(2), pages 131-145, April.
    5. Millimet, Daniel L. & Tchernis, Rusty, 2008. "Estimating high-dimensional demand systems in the presence of many binding non-negativity constraints," Journal of Econometrics, Elsevier, vol. 147(2), pages 384-395, December.
    6. E. Nikolova & N. E. Stier-Moses, 2014. "A Mean-Risk Model for the Traffic Assignment Problem with Stochastic Travel Times," Operations Research, INFORMS, vol. 62(2), pages 366-382, April.
    7. Peng Han & Xinyue Yang & Yifei Zhao & Xiangmin Guan & Shengjie Wang, 2022. "Quantitative Ground Risk Assessment for Urban Logistical Unmanned Aerial Vehicle (UAV) Based on Bayesian Network," Sustainability, MDPI, vol. 14(9), pages 1-13, May.
    8. Parilina, Elena & Sedakov, Artem & Zaccour, Georges, 2017. "Price of anarchy in a linear-state stochastic dynamic game," European Journal of Operational Research, Elsevier, vol. 258(2), pages 790-800.
    9. Vincenzo Bonifaci & Tobias Harks & Guido Schäfer, 2010. "Stackelberg Routing in Arbitrary Networks," Mathematics of Operations Research, INFORMS, vol. 35(2), pages 330-346, May.
    10. Andrej Čopar & Blaž Zupan & Marinka Zitnik, 2019. "Fast optimization of non-negative matrix tri-factorization," PLOS ONE, Public Library of Science, vol. 14(6), pages 1-15, June.
    11. José R. Correa & Nicolás Figueroa & Nicolás E. Stier-Moses, 2008. "Pricing with markups in industries with increasing marginal costs," Documentos de Trabajo 256, Centro de Economía Aplicada, Universidad de Chile.
    12. Koutchad, P. & Carpentier, A. & Femenia, F., 2018. "Dealing with corner solutions in multi-crop micro-econometric models: an endogenous regime approach with regime fixed costs," 2018 Conference, July 28-August 2, 2018, Vancouver, British Columbia 277530, International Association of Agricultural Economists.
    13. Gaëtan Fournier & Marco Scarsini, 2014. "Hotelling Games on Networks: Efficiency of Equilibria," Documents de travail du Centre d'Economie de la Sorbonne 14033, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    14. Pieter Kleer, 2023. "Price of anarchy for parallel link networks with generalized mean objective," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 45(1), pages 27-55, March.
    15. Li, Song-Song, 2018. "Efficiency analysis with respect to the unit cost objectives in scheduling games," Mathematical Social Sciences, Elsevier, vol. 94(C), pages 13-18.
    16. Tianrui Yin & Wei Chen & Bo Liu & Changzhen Li & Luyao Du, 2023. "Light “You Only Look Once”: An Improved Lightweight Vehicle-Detection Model for Intelligent Vehicles under Dark Conditions," Mathematics, MDPI, vol. 12(1), pages 1-19, December.
    17. Roberto Cominetti & José R. Correa & Nicolás E. Stier-Moses, 2009. "The Impact of Oligopolistic Competition in Networks," Operations Research, INFORMS, vol. 57(6), pages 1421-1437, December.
    18. Marco Scarsini & Tristan Tomala, 2012. "Repeated congestion games with bounded rationality," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(3), pages 651-669, August.
    19. Thanasis Lianeas & Evdokia Nikolova & Nicolas E. Stier-Moses, 2019. "Risk-Averse Selfish Routing," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 38-57, February.
    20. Qian, Hang, 2009. "Estimating SUR Tobit Model while errors are gaussian scale mixtures: with an application to high frequency financial data," MPRA Paper 31509, University Library of Munich, Germany.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:141:y:2009:i:1:d:10.1007_s10957-008-9489-9. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.