IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v33y2021i1p120-142.html
   My bibliography  Save this article

Optimization for L 1 -Norm Error Fitting via Data Aggregation

Author

Listed:
  • Young Woong Park

    (Ivy College of Business, Iowa State University, Ames, Iowa 50011)

Abstract

We propose a data aggregation-based algorithm with monotonic convergence to a global optimum for a generalized version of the L 1 -norm error fitting model with an assumption of the fitting function. The proposed algorithm generalizes the recent algorithm in the literature, aggregate and iterative disaggregate (AID), which selectively solves three specific L 1 -norm error fitting problems. With the proposed algorithm, any L 1 -norm error fitting model can be solved optimally if it follows the form of the L 1 -norm error fitting problem and if the fitting function satisfies the assumption. The proposed algorithm can also solve multidimensional fitting problems with arbitrary constraints on the fitting coefficients matrix. The generalized problem includes popular models, such as regression and the orthogonal Procrustes problem. The results of the computational experiment show that the proposed algorithms are faster than the state-of-the-art benchmarks for L 1 -norm regression subset selection and L 1 -norm regression over a sphere. Furthermore, the relative performance of the proposed algorithm improves as data size increases.

Suggested Citation

  • Young Woong Park, 2021. "Optimization for L 1 -Norm Error Fitting via Data Aggregation," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 120-142, January.
    • Handle: RePEc:inm:orijoc:v:33:y:2021:i:1:p:120-142
    DOI: 10.1287/ijoc.2019.0908
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2019.0908
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2019.0908?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
    ---><---

    References listed on IDEAS

    as
    1. Brooks, J.P. & Dulá, J.H. & Boone, E.L., 2013. "A pure L1-norm principal component analysis," Computational Statistics & Data Analysis, Elsevier, vol. 61(C), pages 83-98.
    2. Roy Mendelssohn, 1980. "Technical Note—Improved Bounds for Aggregated Linear Programs," Operations Research, INFORMS, vol. 28(6), pages 1450-1453, December.
    3. Dimitris Bertsimas & Romy Shioda, 2009. "Algorithm for cardinality-constrained quadratic optimization," Computational Optimization and Applications, Springer, vol. 43(1), pages 1-22, May.
    4. Robert Geisberger & Peter Sanders & Dominik Schultes & Christian Vetter, 2012. "Exact Routing in Large Road Networks Using Contraction Hierarchies," Transportation Science, INFORMS, vol. 46(3), pages 388-404, August.
    5. Egon Balas, 1965. "Solution of Large-Scale Transportation Problems Through Aggregation," Operations Research, INFORMS, vol. 13(1), pages 82-93, February.
    6. Newman, Alexandra M. & Kuchta, Mark, 2007. "Using aggregation to optimize long-term production planning at an underground mine," European Journal of Operational Research, Elsevier, vol. 176(2), pages 1205-1218, January.
    7. Wim van Ackooij & Welington de Oliveira & Yongjia Song, 2018. "Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 57-70, February.
    8. Clautiaux, François & Hanafi, Saïd & Macedo, Rita & Voge, Marie-Émilie & Alves, Cláudio, 2017. "Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints," European Journal of Operational Research, Elsevier, vol. 258(2), pages 467-477.
    9. David F. Rogers & Robert D. Plante & Richard T. Wong & James R. Evans, 1991. "Aggregation and Disaggregation Techniques and Methodology in Optimization," Operations Research, INFORMS, vol. 39(4), pages 553-582, August.
    10. Vakhutinsky, I Y & Dudkin, L M & Ryvkin, A A, 1979. "Iterative Aggregation-A New Approach to the Solution of Large-Scale Problems," Econometrica, Econometric Society, vol. 47(4), pages 821-841, July.
    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. Shao-Bo Lin & Shaojie Tang & Yao Wang & Di Wang, 2022. "Toward Efficient Ensemble Learning with Structure Constraints: Convergent Algorithms and Applications," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3096-3116, November.
    2. Renaud Chicoisne, 2023. "Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes," Computational Optimization and Applications, Springer, vol. 84(3), pages 789-831, April.

    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. Michelle L. Blom & Adrian R. Pearce & Peter J. Stuckey, 2016. "A Decomposition-Based Algorithm for the Scheduling of Open-Pit Networks Over Multiple Time Periods," Management Science, INFORMS, vol. 62(10), pages 3059-3084, October.
    2. Jornsten, Kurt & Leisten, Rainer, 1995. "Decomposition and iterative aggregation in hierarchical and decentralised planning structures," European Journal of Operational Research, Elsevier, vol. 86(1), pages 120-141, October.
    3. Selvaprabu Nadarajah & Andre A. Cire, 2020. "Network-Based Approximate Linear Programming for Discrete Optimization," Operations Research, INFORMS, vol. 68(6), pages 1767-1786, November.
    4. John Turner, 2012. "The Planning of Guaranteed Targeted Display Advertising," Operations Research, INFORMS, vol. 60(1), pages 18-33, February.
    5. Richard Connors & David Watling, 2015. "Assessing the Demand Vulnerability of Equilibrium Traffic Networks via Network Aggregation," Networks and Spatial Economics, Springer, vol. 15(2), pages 367-395, June.
    6. Lili Pan & Ziyan Luo & Naihua Xiu, 2017. "Restricted Robinson Constraint Qualification and Optimality for Cardinality-Constrained Cone Programming," Journal of Optimization Theory and Applications, Springer, vol. 175(1), pages 104-118, October.
    7. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    8. Merrick, James H. & Weyant, John P., 2019. "On choosing the resolution of normative models," European Journal of Operational Research, Elsevier, vol. 279(2), pages 511-523.
    9. Jize Zhang & Tim Leung & Aleksandr Aravkin, 2018. "A Relaxed Optimization Approach for Cardinality-Constrained Portfolio Optimization," Papers 1810.10563, arXiv.org.
    10. Wilhelm, Wilbert E. & Xu, Kaihong, 2002. "Prescribing product upgrades, prices and production levels over time in a stochastic environment," European Journal of Operational Research, Elsevier, vol. 138(3), pages 601-621, May.
    11. Lara, Cristiana L. & Koenemann, Jochen & Nie, Yisu & de Souza, Cid C., 2023. "Scalable timing-aware network design via lagrangian decomposition," European Journal of Operational Research, Elsevier, vol. 309(1), pages 152-169.
    12. Vicens, E. & Alemany, M. E. & Andres, C. & Guarch, J. J., 2001. "A design and application methodology for hierarchical production planning decision support systems in an enterprise integration context," International Journal of Production Economics, Elsevier, vol. 74(1-3), pages 5-20, December.
    13. James H. Merrick & John E. T. Bistline & Geoffrey J. Blanford, 2021. "On representation of energy storage in electricity planning models," Papers 2105.03707, arXiv.org, revised May 2021.
    14. Kenneth Carling & Mengjie Han & Johan Håkansson, 2012. "Does Euclidean distance work well when the p-median model is applied in rural areas?," Annals of Operations Research, Springer, vol. 201(1), pages 83-97, December.
    15. Srinivasa, Anand V. & Wilhelm, Wilbert E., 1997. "A procedure for optimizing tactical response in oil spill clean up operations," European Journal of Operational Research, Elsevier, vol. 102(3), pages 554-574, November.
    16. Chen, Bi Yu & Chen, Xiao-Wei & Chen, Hui-Ping & Lam, William H.K., 2020. "Efficient algorithm for finding k shortest paths based on re-optimization technique," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    17. Francesco Cesarone & Andrea Scozzari & Fabio Tardella, 2015. "Linear vs. quadratic portfolio selection models with hard real-world constraints," Computational Management Science, Springer, vol. 12(3), pages 345-370, July.
    18. Rui Pedro Brito & Hélder Sebastião & Pedro Godinho, 2015. "Portfolio Management With Higher Moments: The Cardinality Impact," GEMF Working Papers 2015-15, GEMF, Faculty of Economics, University of Coimbra.
    19. Ceren Tuncer Şakar & Murat Köksalan, 2013. "A stochastic programming approach to multicriteria portfolio optimization," Journal of Global Optimization, Springer, vol. 57(2), pages 299-314, October.
    20. Ricardo M. Lima & Ignacio E. Grossmann, 2017. "On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study," Computational Optimization and Applications, Springer, vol. 66(1), pages 1-37, January.

    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:inm:orijoc:v:33:y:2021:i:1:p:120-142. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.