×

zbMATH — the first resource for mathematics

Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions. (English) Zbl 1190.90275
Summary: We present primal-dual interior-point algorithms for second-order cone optimization based on a wide variety of kernel functions. This class of kernel functions has been investigated earlier for the case of linear optimization. In this paper we derive the iteration bounds \(O(\sqrt N \log N)\log \frac{N}{\varepsilon}\) for large- and \(O(\sqrt N)\log \frac{N}{\varepsilon}\) for small-update methods, respectively. Here \(N\) denotes the number of second-order cones in the problem formulation and \(\varepsilon \) the desired accuracy. These iteration bounds are currently the best known bounds for such methods. Numerical results show that the algorithms are efficient.

MSC:
90C51 Interior-point methods
90C25 Convex programming
Software:
SeDuMi
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] I. Adler, F. Alizadeh, Primal – dual interior point algorithms for convex quadratically constrained and semidefinite optimization problems, Technical Report RRR-111-95, Rutger Center for Operations Research, Brunswick, NJ, 1995
[2] Andersen, E.D.; Gondzio, J.; Mészáros, Cs.; Xu, X., Implementation of interior point methods for large scale linear programming, (), 189-252 · Zbl 0874.90127
[3] Andersen, E.D.; Roos, C.; Terlaky, T., On implementing a primal – dual interior-point method for conic quadratic optimization, Mathematical programming (series B), 95, 249-277, (2003) · Zbl 1030.90137
[4] 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, 15, 1, 101-128, (2004) · Zbl 1077.90038
[5] Y.Q. Bai, J. Guo, C. Roos, A new kernel function yielding the best known iteration bounds for primal – dual interior-point algorithms, Acta Mathematica Sinica, English Series, July 2006 (submitted for publication) · Zbl 1184.90099
[6] Bai, Y.Q.; Roos, C., A primal – dual interior-point method based on a new kernel function with linear growth rate, (), 15-28
[7] Faybusovich, L., Linear system in Jordan algebras and primal – dual interior-point algorithms, Journal of computational and applied mathematics, 86, 1, 149-175, (1997) · Zbl 0889.65066
[8] Fukushima, M.; Luo, Z.Q.; Tseng, P., A smoothing function for second-order-cone complementary problems, SIAM journal on optimization, 12, 436-460, (2001) · Zbl 0995.90094
[9] A. Haseli, An interior-point algorithm based on a new kernel function yielding the best known iteration bound, 2006, manuscript
[10] Lobo, M.S.; Vandenberghe, L.; Boyd, S.E.; Lebret, H., Applications of the second-order cone programming, Linear algebra and its applications, 284, 193-228, (1998) · Zbl 0946.90050
[11] Luo, Z.Q.; Sturm, J.F.; Zhang, S., Conic convex programming and self-dual embedding, Optimization methods and software, 14, 3, 169-218, (2000) · Zbl 1072.90559
[12] Monteiro, R.D.C.; Tsuchiya, T., Polynomial convergence of primal – dual algorithms for the second-order program based the MZ-family of directions, Mathematical programming, 88, 61-93, (2000) · Zbl 0967.65077
[13] Nesterov, Y.E.; Todd, M.J., Self-scaled barriers and interior-point methods for convex programming, Mathematics of operations research, 22, 1, 1-42, (1997) · Zbl 0871.90064
[14] Nesterov, Y.E.; Todd, M.J., Primal – dual interior-point methods for self-scaled cones, SIAM journal on optimization, 8, 2, 324-364, (1998) · Zbl 0922.90110
[15] Peng, J.; Roos, C.; Terlaky, T., New complexity analysis of the primal – dual Newton method for linear optimization, Annals of operations research, 99, 23-39, (2001), Applied mathematical programming and modeling, IV (Limassol, 1998), 2000 · Zbl 0990.90065
[16] Peng, J.; Roos, C.; Terlaky, T., A new and efficient large-update interior-point method for linear optimization, Journal of computational technologies, 6, 4, 61-80, (2001) · Zbl 0987.90089
[17] Peng, J.; Roos, C.; Terlaky, T., Self-regular functions and new search directions for linear and semidefinite optimization, Mathematical programming (series A), 93, 129-171, (2002) · Zbl 1007.90037
[18] Peng, J.; Roos, C.; Terlaky, T., Self-regularity. A new paradigm for primal-dual interior-point algorithms, (2002), Princeton University Press · Zbl 1136.90045
[19] Robinson, S.M., Some continuity properties of polyhedral multifunctions, Mathematical programming study, 14, 206-214, (1981), Mathematical Programming at Oberwolfach (Proc. Conf., Math. Forschungsinstitut, Oberwolfach, 1979) · Zbl 0449.90090
[20] Roos, C.; Terlaky, T.; Vial, J.-Ph., Theory and algorithms for linear optimization. an interior-point approach, (1997), John Wiley & Sons Chichester, UK
[21] Schmieta, S.H.; Alizadeh, F., Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones, Mathematics of operations research, 26, 3, 543-564, (2001) · Zbl 1073.90572
[22] Sturm, J.F., Implementation of interior point methods for mixed semidefinite and second order cone optimization problems, Optimization methods and software, 17, 6, 1105-1154, (2002) · Zbl 1032.90021
[23] Sturm, J.F., Using sedumi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optimization methods and software, 11, 625-653, (1999) · Zbl 0973.90526
[24] T. Tsuchiya, A polynomial primal – dual path-following algorithm for second-order cone programming. Research Memorandum No. 649, The Institute of Statistical Mathematics, Tokyo, Japan, 1997
[25] Tsuchiya, T., A convergence analysis of the scaling-invariant primal – dual path-following algorithms for second-order cone programing, Optimization methods and software, 11-12, 141-182, (1999) · Zbl 0957.90129
[26] Wang, G.Q.; Bai, Y.Q.; Roos, C., Primal – dual interior-point algorithms for semidefinite optimization based on a simple kernel function, Journal of mathematical modelling and algorithms, 4, 409-433, (2005) · Zbl 1111.90083
[27] (), Theory, algorithms, and applications
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.