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

Algebraic Solution of Tropical Polynomial Optimization Problems

Author

Listed:
  • Nikolai Krivulin

    (Faculty of Mthematics and Mechanics, St. Petersburg State University, Universitetskaya Emb. 7/9, 199034 St. Petersburg, Russia)

Abstract

We consider constrained optimization problems defined in the tropical algebra setting on a linearly ordered, algebraically complete (radicable) idempotent semifield (a semiring with idempotent addition and invertible multiplication). The problems are to minimize the objective functions given by tropical analogues of multivariate Puiseux polynomials, subject to box constraints on the variables. A technique for variable elimination is presented that converts the original optimization problem to a new one in which one variable is removed and the box constraint for this variable is modified. The novel approach may be thought of as an extension of the Fourier–Motzkin elimination method for systems of linear inequalities in ordered fields to the issue of polynomial optimization in ordered tropical semifields. We use this technique to develop a procedure to solve the problem in a finite number of iterations. The procedure includes two phases: backward elimination and forward substitution of variables. We describe the main steps of the procedure, discuss its computational complexity and present numerical examples.

Suggested Citation

  • Nikolai Krivulin, 2021. "Algebraic Solution of Tropical Polynomial Optimization Problems," Mathematics, MDPI, vol. 9(19), pages 1-18, October.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:19:p:2472-:d:649581
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/19/2472/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/19/2472/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Nikolai Krivulin, 2020. "Using Parameter Elimination to Solve Discrete Linear Chebyshev Approximation Problems," Mathematics, MDPI, vol. 8(12), pages 1-16, December.
    2. Nikolai Krivulin, 2020. "Using tropical optimization techniques in bi-criteria decision problems," Computational Management Science, Springer, vol. 17(1), pages 79-104, January.
    3. Nikolai Krivulin, 2017. "Using tropical optimization to solve constrained minimax single-facility location problems with rectilinear distance," Computational Management Science, Springer, vol. 14(4), pages 493-518, October.
    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. Toly Chen, 2021. "A diversified AHP-tree approach for multiple-criteria supplier selection," Computational Management Science, Springer, vol. 18(4), pages 431-453, October.
    2. Nikolai Krivulin, 2020. "Tropical optimization technique in bi-objective project scheduling under temporal constraints," Computational Management Science, Springer, vol. 17(3), pages 437-464, October.
    3. Nikolai Krivulin, 2023. "Algebraic Solution of Tropical Best Approximation Problems," Mathematics, MDPI, vol. 11(18), pages 1-17, September.
    4. Nikolai Krivulin & Alexey Prinkov & Igor Gladkikh, 2022. "Using Pairwise Comparisons to Determine Consumer Preferences in Hotel Selection," Mathematics, MDPI, vol. 10(5), pages 1-25, February.
    5. Nikolai Krivulin, 2021. "Algebraic Solution to Constrained Bi-Criteria Decision Problem of Rating Alternatives through Pairwise Comparisons," Mathematics, MDPI, vol. 9(4), pages 1-22, February.

    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:9:y:2021:i:19:p:2472-:d:649581. 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.