[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

On self-concordant barriers for generalized power cones

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

In the study of interior-point methods for nonsymmetric conic optimization and their applications, Nesterov (Optim Methods Softw 27(4–5): 893–917, 2012) introduced a 4-self-concordant barrier for the power cone, also known as Koecher’s cone. In his PhD thesis, Chares (Cones and interior-point algorithms for structured convex optimization involving powers and exponentials, PhD thesis, Universite catholique de Louvain, 2009) found an improved 3-self-concordant barrier for the power cone. In addition, he introduced the generalized power cone, and conjectured a “nearly optimal” self-concordant barrier for it. In this paper, we prove Chares’ conjecture. As a byproduct of our analysis, we derive a self-concordant barrier for a nonnegative power cone.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Badenbroek, R., Dahl, J.: An algorithm for nonsymmetric conic optimization inspired by MOSEK. Preprint. arXiv:2003.01546 (2020)

  2. Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. SIAM, MPS-SIAM Series on Optimization (2001)

  3. Chares, P.R.: Cones and interior-point algorithms for structured convex optimization involving powers and exponentials. PhD thesis, Universite catholique de Louvain (2009)

  4. Dahl, J., Andersen, E.D.: A primal–dual interior-point algorithm for nonsymmetric exponential-cone optimization. Preprint, MOSEK white paper (2019)

  5. Güler, O.: Barrier functions in interior point methods. Math. Oper. Res. 21(4), 860–885 (1996)

    Article  MathSciNet  Google Scholar 

  6. Hildebrand, R.: A lower bound on the barrier parameter of barriers for convex cones. Math. Program. 142(1), 311–329 (2013)

    Article  MathSciNet  Google Scholar 

  7. Koecher, M.: Positivitätsbereiche in \({R}^n\). Am. J. Math. 79(3), 575–596 (1957)

    Article  Google Scholar 

  8. Nesterov, Y.: Constructing self-concordant barriers for convex cones. CORE discussion paper 2006/30, Center for Operations Research and Econometrics, Catholic University of Louvain (2006)

  9. Nesterov, Y.: Primal–dual interior-point methods with asymmetric barriers. CORE discussion paper 2008/57, Center for Operations Research and Econometrics, Catholic University of Louvain (2008)

  10. Nesterov, Y.: Towards non-symmetric conic optimization. Optim. Methods Softw. 27(4–5), 893–917 (2012)

    Article  MathSciNet  Google Scholar 

  11. Nesterov, Y., Nemirovskii, A. Interior-point polynomial algorithms in convex programming, volume 13 of SIAM Studies in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1994)

  12. Serrano, S.A.: Algorithms for unsymmetric cone optimization and implementation for problems with the exponential cone. PhD thesis, Standford University (2015)

  13. Skajaa, A., Ye, Y.: A homogeneous interior-point algorithm for nonsymmetric convex conic optimization. Math. Program. 150(2), 391–422 (2015)

    Article  MathSciNet  Google Scholar 

  14. Truong, V.A., Tunçel, L.: Geometry of homogeneous convex cones, duality mapping, and optimal self-concordant barriers. Math. Program. Ser. A 100, 295–316 (2004)

    Article  MathSciNet  Google Scholar 

  15. Tunçel, L.: Generalization of primal–dual interior-point methods to convex optimization problems in conic form. Found. Comput. Math. 1, 229–254 (2001)

    Article  MathSciNet  Google Scholar 

  16. Tunçel, L., Nemirovski, A.: Self-concordant barriers for convex approximations of structured convex sets. Found. Comput. Math. 10(5), 485–525 (2010)

    Article  MathSciNet  Google Scholar 

  17. Tunçel, L., Song, X.: On homogeneous convex cones, the Carathéodory number, and the duality mapping. Math. Oper. Res. 26(2), 234–247 (2001)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Microsoft Corporation, Redmond, WA, 98052, USA

    Scott Roy

  2. Microsoft Research, Redmond, WA, 98052, USA

    Lin Xiao

Authors
  1. Scott Roy
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lin Xiao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lin Xiao.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix: Derivative calculations

Appendix: Derivative calculations

In this section, we work through the derivative calculations in the proofs of Theorems 1 and 2. All derivatives are taken at the point (x, z) and in direction \((\varDelta x, \varDelta z)\). The first two derivatives of \(\xi \) are easy to compute as \(\xi ' = e_1 \xi \) and \(\xi '' = -e_2 \xi \). Before computing \(\xi '''\), we compute \(e_1'\) and \(e_2'\), which are useful quantities in computing \(\xi '''\) as well as other derivatives later. Noting that \(\delta _i' = -\delta _i^2\) (where \(\delta _i\) is as in the proofs of Theorems 1 and 2), it is straightforward to show

$$\begin{aligned} e_1' = -s_2 = -e_1^2 - e_2 \end{aligned}$$

and

$$\begin{aligned} e_2' = s_2' - 2 s_1 s_1' = -2 s_3 + 2s_1 s_2 = -e_1 e_2 - e_3. \end{aligned}$$

We then compute \(\xi '''\) by

$$\begin{aligned} \xi ''' = (-e_2 \xi )' = -e_2' \xi -e_2 \xi ' = (e_1 e_2 + e_3) \xi - e_2 (e_1 \xi ) = e_3 \xi . \end{aligned}$$

Now we compute the derivatives of the function \(f = \xi - \frac{\Vert z\Vert _2^2}{\xi }\) in the proof of Theorem 1:

$$\begin{aligned} f'&= \xi ' + \frac{\xi }{\xi ^2} \Vert z \Vert _2^2 - \frac{1}{\xi } \left( 2z \cdot \varDelta z \right) = \xi ' + \frac{1}{\xi } ( e_1 \Vert z \Vert _2^2 - 2 z \cdot \varDelta z) ,\\ f''&= \left( \xi ' + \frac{1}{\xi } ( e_1 \Vert z \Vert _2^2 - 2 z \cdot \varDelta z) \right) ' \\&= \xi '' - \frac{\xi '}{\xi ^2} (e_1 \Vert z \Vert _2^2 - 2 z \cdot \varDelta z) + \frac{1}{\xi } \left( (-e_1^2 - e_2) \Vert z \Vert _2^2 + 2 e_1 z \cdot \varDelta z - 2 \Vert \varDelta z \Vert _2^2 \right) \\&= \xi '' - \frac{1}{\xi } \left( 2 e_1^2 \Vert z \Vert _2^2 - 4 e_1 z \cdot \varDelta z + e_2 \Vert z \Vert _2^2 + 2 \Vert \varDelta z \Vert _2^2 \right) \\&= \xi '' - \frac{e_2}{\xi } \Vert z \Vert _2^2 - \frac{2}{\xi } \Vert e_1 z - \varDelta z \Vert _2^2 ,\\ f'''&= \left( \xi '' - \frac{e_2}{\xi } \Vert z \Vert _2^2 - \frac{2}{\xi } \Vert e_1 z - \varDelta z \Vert _2^2 \right) ' \\&= \xi ''' + \frac{\xi '}{\xi ^2} e_2 \Vert z \Vert _2^2 - \frac{1}{\xi } \left( (-e_1 e_2 - e_3) \Vert z\Vert _2^2 + 2 e_2 z \cdot \varDelta z \right) + \frac{2 \xi '}{\xi ^2} \Vert e_1 z - \varDelta z \Vert _2^2 \\&- \frac{2}{\xi } \left( 2 e_1 (-e_1^2 - e_2) \Vert z\Vert _2^2 + 2 e_1^2 z \cdot \varDelta z - 2 \left( (-e_1^2 - e_2) z \cdot \varDelta z + e_1 \Vert \varDelta z \Vert _2^2 \right) \right) \\&= \xi ''' + \frac{e_3}{\xi } \Vert z \Vert _2^2 + \frac{2}{\xi } \left( 3 e_1 e_2 \Vert z\Vert _2^2 - 3 e_2 z \cdot \varDelta z + e_1 \Vert e_1 z - \varDelta z \Vert _2^2 \right. \\&\quad \left. + 2 e_1^3 \Vert z\Vert _2^2 - 4 e_1^2 z \cdot \varDelta z + 2 e_1 \Vert \varDelta z \Vert _2^2 \right) \\&= \xi ''' + \frac{e_3}{\xi } \Vert z \Vert _2^2 + \frac{2}{\xi } \left( 3 e_1 e_2 \Vert z\Vert _2^2 - 3 e_2 z \cdot \varDelta z + 3 e_1 \Vert e_1 z - \varDelta z \Vert _2^2 \right) \\&= \xi ''' + \frac{e_3}{\xi } \Vert z \Vert _2^2 + \frac{6}{\xi } \left( e_1 \Vert e_1 z - \varDelta z \Vert _2^2 + e_2 z \cdot (e_1 z - \varDelta z) \right) . \end{aligned}$$

The derivatives of \(z - \frac{z^2}{\xi }\) in the proof of Theorem 2 are computed in a very similar manner and are omitted.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Roy, S., Xiao, L. On self-concordant barriers for generalized power cones. Optim Lett 16, 681–694 (2022). https://doi.org/10.1007/s11590-021-01748-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-021-01748-7

Keywords

Search

Navigation