Interior point algorithm for second-order cone optimization based on a new kernel function

Authors

  • Roumaissa Charif
  • El Amir Djeffal

DOI:

https://doi.org/10.54021/seesv5n1-062

Keywords:

second-order cone optimization, Kernel function, interior point method, complexity bound

Abstract

Second-order cone optimization (SOCO) problems are crucial in various fields such as engineering, finance, and machine learning due to their ability to model complex convex optimization tasks efficiently. In this article, we propose an interior point algorithm tailored for SOCO, leveraging a novel kernel function to enhance optimization performance. Traditional interior point methods for SOCO often encounter challenges in scalability and efficiency, particularly with large-scale problems. These methods typically rely on barrier functions that may suffer from slow convergence rates, especially when dealing with highly ill-conditioned or degenerate cones. To address these limitations, our approach introduces a new kernel function that exploits the geometric properties of second-order cones, thereby improving convergence behavior and computational efficiency. The key innovation of our algorithm lies in the construction of the kernel function, which incorporates insights from the structure of second-order cones to efficiently capture the curvature information of the optimization problem. By exploiting this curvature information, our algorithm can effectively navigate the optimization landscape, leading to faster convergence and enhanced robustness compared to traditional methods. Furthermore, our algorithm is equipped with advanced techniques for handling various challenges encountered in SOCO, such as dealing with degenerate cones and exploiting problem structure to accelerate convergence. Additionally, we incorporate strategies for warm-starting and adaptive step-size selection to further improve efficiency, particularly in iterative optimization processes. Finally, our proposed interior point algorithm for second-order cone optimization, based on a new kernel function, derives the iteration bounds O (Nlog (N/∊)) for large update methods. Here denotes N the number of second-order cones in the problem formulation and ∊ the desired accuracy. These iteration bounds are currently the best known bounds for such methods.

References

BAI, Yan Qin; WANG, Guo Qiang. Primal-dual Interior-point Algorithms for Second-order Cone Optimization Based on a New Parametric Kernel Function, 2007.

BAI, Y. Q.; WANG, G. Q.; ROOSB, C. Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions, 2009.

DONG, Li; TANG, Jingyong. Interior-Point Method for Second-order Cone Pro- gramming. Based on a Simple Kernel Function, 2010.

WANG, G. Q.; BAI, Y. Q. A primal-dual interior-point algorithm for second- order cone optimization with full. Nesterov-Todd step, 2009.

MORSHED, Md Sarowar; VOGIATZIS, Chrysafis; NOOR-E-ALAM, Md. A primal-dual interior point method for a novel type-2 second order cone optimization problem, 2019.

BAI, Yan Qin; ZHANG, Wei Xie Jing. New parameterized kernel functions for linear optimization, 2012.

PENG, J.; ROOS, C.; TERLAKY, T. Self-Regularity. A New Paradigm for Pri- mal-Dual Interior-Point Algorithms. Princeton University Press, Prince- ton, NJ, 2002.

BAI, Y. Q.; EL GHAMI, M.; ROOS, C. A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM Journal on Optimization, (electronic), v. 15, p. 101-128, 2004.

Downloads

Published

2024-04-16

How to Cite

Charif, R., & Djeffal, E. A. (2024). Interior point algorithm for second-order cone optimization based on a new kernel function. STUDIES IN ENGINEERING AND EXACT SCIENCES, 5(1), 1187–1205. https://doi.org/10.54021/seesv5n1-062