IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i23p4536-d989701.html
   My bibliography  Save this article

A Non-Archimedean Interior Point Method and Its Application to the Lexicographic Multi-Objective Quadratic Programming

Author

Listed:
  • Lorenzo Fiaschi

    (Department of Information Engineering, University of Pisa, 56122 Pisa, Italy)

  • Marco Cococcioni

    (Department of Information Engineering, University of Pisa, 56122 Pisa, Italy)

Abstract

This work presents a generalized implementation of the infeasible primal-dual interior point method (IPM) achieved by the use of non-Archimedean values, i.e., infinite and infinitesimal numbers. The extended version, called here the non-Archimedean IPM (NA-IPM), is proved to converge in polynomial time to a global optimum and to be able to manage infeasibility and unboundedness transparently, i.e., without considering them as corner cases: by means of a mild embedding (addition of two variables and one constraint), the NA-IPM implicitly and transparently manages their possible presence. Moreover, the new algorithm is able to solve a wider variety of linear and quadratic optimization problems than its standard counterpart. Among them, the lexicographic multi-objective one deserves particular attention, since the NA-IPM overcomes the issues that standard techniques (such as scalarization or preemptive approach) have. To support the theoretical properties of the NA-IPM, the manuscript also shows four linear and quadratic non-Archimedean programming test cases where the effectiveness of the algorithm is verified. This also stresses that the NA-IPM is not just a mere symbolic or theoretical algorithm but actually a concrete numerical tool, paving the way for its use in real-world problems in the near future.

Suggested Citation

  • Lorenzo Fiaschi & Marco Cococcioni, 2022. "A Non-Archimedean Interior Point Method and Its Application to the Lexicographic Multi-Objective Quadratic Programming," Mathematics, MDPI, vol. 10(23), pages 1-34, November.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:23:p:4536-:d:989701
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/23/4536/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/23/4536/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Cococcioni, Marco & Pappalardo, Massimo & Sergeyev, Yaroslav D., 2018. "Lexicographic multi-objective linear programming using grossone methodology: Theory and algorithm," Applied Mathematics and Computation, Elsevier, vol. 318(C), pages 298-311.
    2. Masakazu Kojima & Nimrod Megiddo & Shinji Mizuno, 1993. "A General Framework of Continuation Methods for Complementarity Problems," Mathematics of Operations Research, INFORMS, vol. 18(4), pages 945-963, November.
    3. Letsios, Dimitrios & Mistry, Miten & Misener, Ruth, 2021. "Exact lexicographic scheduling and approximate rescheduling," European Journal of Operational Research, Elsevier, vol. 290(2), pages 469-478.
    4. Pourkarimi, L. & Zarepisheh, M., 2007. "A dual-based algorithm for solving lexicographic multiple objective programs," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1348-1356, February.
    5. Khorram, E. & Zarepisheh, M. & Ghaznavi-ghosoni, B.A., 2010. "Sensitivity analysis on the priority of the objective functions in lexicographic multiple objective linear programs," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1162-1168, December.
    6. Kevin A. McShane & Clyde L. Monma & David Shanno, 1989. "An Implementation of a Primal-Dual Interior Point Method for Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 1(2), pages 70-83, May.
    7. Sherali, Hanif D., 1982. "Equivalent weights for lexicographic multi-objective programs: Characterizations and computations," European Journal of Operational Research, Elsevier, vol. 11(4), pages 367-379, December.
    8. Gondzio, Jacek, 2012. "Interior point methods 25 years later," European Journal of Operational Research, Elsevier, vol. 218(3), pages 587-601.
    Full references (including those not matched with items on IDEAS)

    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. Coralia Cartis & Yiming Yan, 2016. "Active-set prediction for interior point methods using controlled perturbations," Computational Optimization and Applications, Springer, vol. 63(3), pages 639-684, April.
    2. Zhang Jiangao & Shitao Yang, 2016. "On the Lexicographic Centre of Multiple Objective Optimization," Journal of Optimization Theory and Applications, Springer, vol. 168(2), pages 600-614, February.
    3. Coralia Cartis & Yiming Yan, 2016. "Active-set prediction for interior point methods using controlled perturbations," Computational Optimization and Applications, Springer, vol. 63(3), pages 639-684, April.
    4. Dimitrios Letsios & Jeremy T. Bradley & Suraj G & Ruth Misener & Natasha Page, 2021. "Approximate and robust bounded job start scheduling for Royal Mail delivery offices," Journal of Scheduling, Springer, vol. 24(2), pages 237-258, April.
    5. M. Zarepisheh & E. Khorram, 2011. "On the transformation of lexicographic nonlinear multiobjective programs to single objective programs," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 74(2), pages 217-231, October.
    6. Luciana Casacio & Aurelio R. L. Oliveira & Christiano Lyra, 2018. "Using groups in the splitting preconditioner computation for interior point methods," 4OR, Springer, vol. 16(4), pages 401-410, December.
    7. Bittencourt, Tiberio & Ferreira, Orizon Pereira, 2015. "Local convergence analysis of Inexact Newton method with relative residual error tolerance under majorant condition in Riemannian manifolds," Applied Mathematics and Computation, Elsevier, vol. 261(C), pages 28-38.
    8. Stefania Bellavia & Valentina De Simone & Daniela di Serafino & Benedetta Morini, 2016. "On the update of constraint preconditioners for regularized KKT systems," Computational Optimization and Applications, Springer, vol. 65(2), pages 339-360, November.
    9. de Groot, Oliver & Mazelis, Falk & Motto, Roberto & Ristiniemi, Annukka, 2021. "A toolkit for computing Constrained Optimal Policy Projections (COPPs)," Working Paper Series 2555, European Central Bank.
    10. Fanrong Xie & Anuj Sharma & Zuoan Li, 2022. "An alternate approach to solve two-level priority based assignment problem," Computational Optimization and Applications, Springer, vol. 81(2), pages 613-656, March.
    11. Laura Laguna-Salvadó & Matthieu Lauras & Uche Okongwu & Tina Comes, 2019. "A multicriteria Master Planning DSS for a sustainable humanitarian supply chain," Annals of Operations Research, Springer, vol. 283(1), pages 1303-1343, December.
    12. Amir Akbari & Paul I. Barton, 2018. "An Improved Multi-parametric Programming Algorithm for Flux Balance Analysis of Metabolic Networks," Journal of Optimization Theory and Applications, Springer, vol. 178(2), pages 502-537, August.
    13. Martijn H. H. Schoot Uiterkamp & Marco E. T. Gerards & Johann L. Hurink, 2022. "On a Reduction for a Class of Resource Allocation Problems," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1387-1402, May.
    14. Fereshteh Akbari & Mehrdad Ghaznavi & Esmaile Khorram, 2018. "A Revised Pascoletti–Serafini Scalarization Method for Multiobjective Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 178(2), pages 560-590, August.
    15. Michaël Allouche & Emmanuel Gobet & Clara Lage & Edwin Mangin, 2024. "Structured dictionary learning of rating migration matrices for credit risk modeling," Computational Statistics, Springer, vol. 39(6), pages 3431-3456, September.
    16. R. Almeida & A. Teixeira, 2015. "On the convergence of a predictor-corrector variant algorithm," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(2), pages 401-418, July.
    17. Sherali, Hanif D. & Van Goubergen, Dirk & Van Landeghem, Hendrik, 2008. "A quantitative approach for scheduling activities to reduce set-up in multiple machine lines," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1224-1237, June.
    18. Sharma, Anuj & Verma, Vanita & Kaur, Prabhjot & Dahiya, Kalpana, 2015. "An iterative algorithm for two level hierarchical time minimization transportation problem," European Journal of Operational Research, Elsevier, vol. 246(3), pages 700-707.
    19. repec:hal:wpaper:hal-03715954 is not listed on IDEAS
    20. Immanuel Bomze & Werner Schachinger & Gabriele Uchida, 2012. "Think co(mpletely)positive ! Matrix properties, examples and a clustered bibliography on copositive optimization," Journal of Global Optimization, Springer, vol. 52(3), pages 423-445, March.
    21. Enrico Bettiol & Lucas Létocart & Francesco Rinaldi & Emiliano Traversi, 2020. "A conjugate direction based simplicial decomposition framework for solving a specific class of dense convex quadratic programs," Computational Optimization and Applications, Springer, vol. 75(2), pages 321-360, March.

    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:gam:jmathe:v:10:y:2022:i:23:p:4536-:d:989701. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.