IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2006034.html
   My bibliography  Save this paper

Nonsymmetric potential-reduction methods for general cones

Author

Listed:
  • NESTEROV, Yu.

Abstract

In this paper we propose two new nonsymmetric primal-dual potential-reduction methods for conic problems. The methods are based on the primal-dual lifting [5]. This procedure allows to construct a strictly feasible primal-dual pair related by an exact scaling relation even if the cones are not symmetric. It is important that all necessary elements of our methods can be obtained from the standard solvers for primal Newton system. The first of the proposed schemes is based on the usual affine-scaling direction. For the second one, we apply a new first-order affine-scaling direction, which incorporates in a symmetric way the gradients of primal and dual barriers. For both methods we prove the standard O( ln 1 ) complexity estimate, where is the parameter of the barrier and is the required accuracy.

Suggested Citation

  • NESTEROV, Yu., 2006. "Nonsymmetric potential-reduction methods for general cones," LIDAM Discussion Papers CORE 2006034, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2006034
    as

    Download full text from publisher

    File URL: https://sites.uclouvain.be/core/publications/coredp/coredp2006.html
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. NESTEROV, Yu., 2006. "Constructing self-concordant barriers for convex cones," LIDAM Discussion Papers CORE 2006030, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. NESTEROV , Yurii & TODD , Michael, 1995. "Primal-Dual Interior-Point Methods for Self-Scaled Cones," LIDAM Discussion Papers CORE 1995044, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. NESTEROV, Yu., 2006. "Towards nonsymmetric conic optimization," LIDAM Discussion Papers CORE 2006028, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    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. Robert Chares & François Glineur, 2008. "An interior-point method for the single-facility location problem with mixed norms using a conic formulation," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 68(3), pages 383-405, December.
    2. Luo, Z-Q. & Sturm, J.F. & Zhang, S., 1998. "Conic convex programming and self-dual embedding," Econometric Institute Research Papers EI 9815, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    3. Arjan B. Berkelaar & Jos F. Sturm & Shuzhong Zhang, 1997. "Polynomial Primal-Dual Cone Affine Scaling for Semidefinite Programming," Tinbergen Institute Discussion Papers 97-025/4, Tinbergen Institute.
    4. Krokhmal, Pavlo A. & Soberanis, Policarpio, 2010. "Risk optimization with p-order conic constraints: A linear programming approach," European Journal of Operational Research, Elsevier, vol. 201(3), pages 653-671, March.
    5. Mehdi Karimi & Levent Tunçel, 2020. "Primal–Dual Interior-Point Methods for Domain-Driven Formulations," Mathematics of Operations Research, INFORMS, vol. 45(2), pages 591-621, May.
    6. F. A. Potra & R. Sheng, 1998. "Superlinear Convergence of Interior-Point Algorithms for Semidefinite Programming," Journal of Optimization Theory and Applications, Springer, vol. 99(1), pages 103-119, October.
    7. A. D'Aspremont, 2003. "Interest rate model calibration using semidefinite Programming," Applied Mathematical Finance, Taylor & Francis Journals, vol. 10(3), pages 183-213.
    8. Da Tian, 2014. "An entire space polynomial-time algorithm for linear programming," Journal of Global Optimization, Springer, vol. 58(1), pages 109-135, January.
    9. Chris Coey & Lea Kapelevich & Juan Pablo Vielma, 2022. "Solving Natural Conic Formulations with Hypatia.jl," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2686-2699, September.
    10. Quoc Tran-Dinh & Anastasios Kyrillidis & Volkan Cevher, 2018. "A Single-Phase, Proximal Path-Following Framework," Mathematics of Operations Research, INFORMS, vol. 43(4), pages 1326-1347, November.
    11. Sturm, J.F., 2001. "Avoiding Numerical Cancellation in the Interior Point Method for Solving Semidefinite Programs," Discussion Paper 2001-27, Tilburg University, Center for Economic Research.
    12. NESTEROV, Yu., 2006. "Towards nonsymmetric conic optimization," LIDAM Discussion Papers CORE 2006028, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    13. Li Yang & Bo Yu, 2013. "A homotopy method for nonlinear semidefinite programming," Computational Optimization and Applications, Springer, vol. 56(1), pages 81-96, September.
    14. Alemseged Weldeyesus & Mathias Stolpe, 2015. "A primal-dual interior point method for large-scale free material optimization," Computational Optimization and Applications, Springer, vol. 61(2), pages 409-435, June.
    15. Brendan O’Donoghue & Eric Chu & Neal Parikh & Stephen Boyd, 2016. "Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding," Journal of Optimization Theory and Applications, Springer, vol. 169(3), pages 1042-1068, June.
    16. NESTEROV, Yu., 2006. "Constructing self-concordant barriers for convex cones," LIDAM Discussion Papers CORE 2006030, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    17. Ali Mohammad-Nezhad & Tamás Terlaky, 2017. "A polynomial primal-dual affine scaling algorithm for symmetric conic optimization," Computational Optimization and Applications, Springer, vol. 66(3), pages 577-600, April.
    18. Luo, Z-Q. & Sturm, J.F. & Zhang, S., 1997. "Duality Results for Conic Convex Programming," Econometric Institute Research Papers EI 9719/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    19. Gu, G. & Zangiabadi, M. & Roos, C., 2011. "Full Nesterov-Todd step infeasible interior-point method for symmetric optimization," European Journal of Operational Research, Elsevier, vol. 214(3), pages 473-484, November.
    20. Luo, Z-Q. & Sturm, J.F. & Zhang, S., 1996. "Superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming," Econometric Institute Research Papers 9607/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.

    More about this item

    Statistics

    Access and download statistics

    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:cor:louvco:2006034. 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: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.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.