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

Apex Method: A New Scalable Iterative Method for Linear Programming

Author

Listed:
  • Leonid B. Sokolinsky

    (School of Electronic Engineering and Computer Science, South Ural State University (National Research University), 76, Lenin Prospekt, 454080 Chelyabinsk, Russia
    These authors contributed equally to this work.)

  • Irina M. Sokolinskaya

    (School of Electronic Engineering and Computer Science, South Ural State University (National Research University), 76, Lenin Prospekt, 454080 Chelyabinsk, Russia
    These authors contributed equally to this work.)

Abstract

The article presents a new scalable iterative method for linear programming called the “apex method”. The key feature of this method is constructing a path close to optimal on the surface of the feasible region from a certain starting point to the exact solution of a linear programming problem. The optimal path refers to a path of the minimum length according to the Euclidean metric. The apex method is based on the predictor—corrector framework and proceeds in two stages: quest (predictor) and target (corrector). The quest stage calculates a rough initial approximation of the linear programming problem. The target stage refines the initial approximation with a given precision. The main operation used in the apex method is an operation that calculates the pseudoprojection, which is a generalization of the metric projection to a convex closed set. This operation is used both in the quest stage and in the target stage. A parallel algorithm using a Fejér mapping to compute the pseudoprojection is presented. An analytical estimation of the parallelism degree of this algorithm is obtained. AlsoAdditionally, an algorithm implementing the target stage is given. The convergence of this algorithm is proven. An experimental study of the scalability of the apex method on a cluster computing system is described. The results of applying the apex method to solve problems from the Netlib-LP repository are presented.

Suggested Citation

  • Leonid B. Sokolinsky & Irina M. Sokolinskaya, 2023. "Apex Method: A New Scalable Iterative Method for Linear Programming," Mathematics, MDPI, vol. 11(7), pages 1-28, March.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:7:p:1654-:d:1111012
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/7/1654/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/7/1654/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Rujira Visuthirattanamanee & Krung Sinapiromsaran & Aua-aree Boonperm, 2020. "Self-Regulating Artificial-Free Linear Programming Solver Using a Jump and Simplex Method," Mathematics, MDPI, vol. 8(3), pages 1-15, March.
    2. Jonathan Brogaard & Terrence Hendershott & Ryan Riordan, 2014. "High-Frequency Trading and Price Discovery," The Review of Financial Studies, Society for Financial Studies, vol. 27(8), pages 2267-2306.
    3. Liu, Xiaolan & Zhou, Mi, 2016. "A one-layer recurrent neural network for non-smooth convex optimization subject to linear inequality constraints," Chaos, Solitons & Fractals, Elsevier, vol. 87(C), pages 39-46.
    4. ManMohan S. Sodhi, 2005. "LP Modeling for Asset-Liability Management: A Survey of Choices and Simplifications," Operations Research, INFORMS, vol. 53(2), pages 181-196, April.
    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. Baoqiang Zhan & Shu Zhang & Helen S. Du & Xiaoguang Yang, 2022. "Exploring Statistical Arbitrage Opportunities Using Machine Learning Strategy," Computational Economics, Springer;Society for Computational Economics, vol. 60(3), pages 861-882, October.
    2. Sun, Yuxin & Ibikunle, Gbenga, 2017. "Informed trading and the price impact of block trades: A high frequency trading analysis," International Review of Financial Analysis, Elsevier, vol. 54(C), pages 114-129.
    3. Bruno Biais & Fany Declerck & Sophie Moinas, 2016. "Who supplies liquidity, how and when?," BIS Working Papers 563, Bank for International Settlements.
    4. Goergen, Marc & Renneboog, Luc & Zhao, Yang, 2019. "Insider trading and networked directors," Journal of Corporate Finance, Elsevier, vol. 56(C), pages 152-175.
    5. NIdhi Aggarwal & Venkatesh Panchapagesan & Susan Thomas, 2022. "When is the Order to Trade Ratio fee effective?," Working Papers 8, xKDR.
    6. Kang, Jongho & Kang, Jangkoo & Kwon, Kyung Yoon, 2022. "Market versus limit orders of speculative high-frequency traders and price discovery," Research in International Business and Finance, Elsevier, vol. 63(C).
    7. Robert J. Kauffman & Yuzhou Hu & Dan Ma, 2015. "Will high-frequency trading practices transform the financial markets in the Asia Pacific Region?," Financial Innovation, Springer;Southwestern University of Finance and Economics, vol. 1(1), pages 1-27, December.
    8. Marcello Rambaldi & Emmanuel Bacry & Jean-Franc{c}ois Muzy, 2018. "Disentangling and quantifying market participant volatility contributions," Papers 1807.07036, arXiv.org.
    9. Uctum, Remzi & Renou-Maissant, Patricia & Prat, Georges & Lecarpentier-Moyal, Sylvie, 2017. "Persistence of announcement effects on the intraday volatility of stock returns: Evidence from individual data," Review of Financial Economics, Elsevier, vol. 35(C), pages 43-56.
    10. George Jiang & Ingrid Lo & Giorgio Valente, 2014. "High-Frequency Trading around Macroeconomic News Announcements: Evidence from the U.S. Treasury Market," Staff Working Papers 14-56, Bank of Canada.
    11. Aggarwal, Nidhi & Panchapagesan, Venkatesh & Thomas, Susan, 2023. "When is the order-to-trade ratio fee effective?," Journal of Financial Markets, Elsevier, vol. 62(C).
    12. Bank, Matthias & Baumann, Ralf H., 2016. "Price formation, market quality and the effects of reduced latency in the very short run," Research in International Business and Finance, Elsevier, vol. 37(C), pages 629-645.
    13. Seddon, Jonathan J.J.M. & Currie, Wendy L., 2017. "A model for unpacking big data analytics in high-frequency trading," Journal of Business Research, Elsevier, vol. 70(C), pages 300-307.
    14. Linnenluecke, Martina K. & Chen, Xiaoyan & Ling, Xin & Smith, Tom & Zhu, Yushu, 2017. "Research in finance: A review of influential publications and a research agenda," Pacific-Basin Finance Journal, Elsevier, vol. 43(C), pages 188-199.
    15. Benjamin Myers & Austin Gerig, 2013. "Simulating the Synchronizing Behavior of High-Frequency Trading in Multiple Markets," Papers 1311.4160, arXiv.org.
    16. Dionne, Georges & Pacurar, Maria & Zhou, Xiaozhou, 2015. "Liquidity-adjusted Intraday Value at Risk modeling and risk management: An application to data from Deutsche Börse," Journal of Banking & Finance, Elsevier, vol. 59(C), pages 202-219.
    17. Erdinc Akyildirim & Shaen Corbet & Guzhan Gulay & Duc Khuong Nguyen & Ahmet Sensoy, 2019. "Order Flow Persistence in Equity Spot and Futures Markets: Evidence from a Dynamic Emerging Market," Working Papers 2019-011, Department of Research, Ipag Business School.
    18. Jakub Kučera, 2013. "Definition, Benefits and Risks of High-Frequency Trading [Vymezení, přínosy a rizika vysokofrekvenčního obchodování]," Acta Oeconomica Pragensia, Prague University of Economics and Business, vol. 2013(5), pages 3-30.
    19. Chiarella, Carl & Ladley, Daniel, 2016. "Chasing trends at the micro-level: The effect of technical trading on order book dynamics," Journal of Banking & Finance, Elsevier, vol. 72(S), pages 119-131.
    20. Brice Corgnet & Mark DeSantis & Christoph Siemroth, 2023. "Algorithmic Trading, Price Efficiency and Welfare: An Experimental Approach," Working Papers 2313, Groupe d'Analyse et de Théorie Economique Lyon St-Étienne (GATE Lyon St-Étienne), Université de Lyon.

    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:11:y:2023:i:7:p:1654-:d:1111012. 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.