×

zbMATH — the first resource for mathematics

A primal-dual interior-point method based on various selections of displacement step for symmetric optimization. (English) Zbl 1414.90322
Summary: In this paper, we develop a primal-dual central trajectory interior-point algorithm for symmetric programming problems and establish its complexity analysis. The main contribution of the paper is that it uniquely equips the central trajectory algorithm with various selections of the displacement step while solving symmetric programming. To show the efficiency of the proposed algorithm, these selections of calculating the displacement step are compared in numerical examples for second-order cone programming, which is a special case of symmetric programming.

MSC:
90C30 Nonlinear programming
90C46 Optimality conditions and duality in mathematical programming
90C51 Interior-point methods
17A15 Noncommutative Jordan algebras
Software:
CQP; Mosek; SDPT3
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Schmieta, SH; Alizadeh, F., Extension of primal-dual interior point methods to symmetric cones, Math. Program. Ser. A, 96, 409-438, (2003) · Zbl 1023.90083
[2] Schmieta, SH; Alizadeh, F., Associative and Jordan algebras, and polynomial time interior point algorithms for symmetric cones, Math. Oper. Res., 26, 543-564, (2001) · Zbl 1073.90572
[3] Alizadeh, F.; Goldfarb, D., Second-order cone programming, Math. Program. Ser. B, 95, 3-51, (2003) · Zbl 1153.90522
[4] Alzalg, B., Stochastic second-order cone programming: application models, Appl. Math. Model., 36, 5122-5134, (2012) · Zbl 1252.90055
[5] Todd, MJ, Semidefinite optimization, ACTA Numer., 10, 515-560, (2001) · Zbl 1105.65334
[6] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Rev., 38, 49-95, (1996) · Zbl 0845.65023
[7] Nesterov, YE; Todd, MJ, Primal-dual interior-point methods for self-scaled cones, SIAM J. Optim., 8, 324-364, (1998) · Zbl 0922.90110
[8] Alzalg, B.; Ariyawansa, KA, Logarithmic barrier decomposition-based interior point methods for stochastic symmetric programming, J. Math. Anal. Appl., 409, 973-995, (2014) · Zbl 1306.90103
[9] Alzalg, B.; Maggiono, F.; Vitali, S., Homogeneous self-dual methods for symmetric cones under uncertainty, Far East J. Math. Sci., 99, 1603-1778, (2016) · Zbl 1356.90092
[10] Benterki, D.; Leulmi, A., An improving procedure of the interior projective method for linear programming, Appl. Math. Comput., 199, 811-819, (2008) · Zbl 1143.65045
[11] Dodani, M.; Babu, A., Karmarkar’s projective method for linear programming: a computational appraisal, Comput. Ind. Eng., 16, 189-206, (1989)
[12] Todd, M.; Wang, Y., On combined phase 1-phase 2 projective methods for linear programming, Algorithmica, 9, 64-83, (1993) · Zbl 0767.90048
[13] Zhang, Y., On extending primal-dual interior-point algorithms from linear programming to semidefinite programming, SIAM J. Optim., 8, 356-386, (1998) · Zbl 0913.65050
[14] Hans, Y-J; Mittelmann, D., Interior point methods for second-order cone programming and OR applications, Comput. Optim. Appl., 28, 255-285, (2004) · Zbl 1084.90046
[15] Tang, J.; He, G.; Dong, L.; Fang, L., A new one-step smoothing newton method for second-order cone programming, Appl. Math., 57, 311-331, (2012) · Zbl 1265.90229
[16] Alzalg, B., Homogeneous self-dual algorithms for stochastic second-order cone programming, J. Optim. Theory Appl., 163, 148-164, (2014) · Zbl 1305.90315
[17] Alzalg, B., Decomposition-based interior point methods for stochastic quadratic second-order cone programming, Appl. Math. Comput., 249, 1-18, (2014) · Zbl 1338.90279
[18] Alzalg, B., Volumetric barrier decomposition algorithms for stochastic quadratic second-order cone programming, Appl. Math. Comput., 256, 494-508, (2015) · Zbl 1410.90133
[19] Kettab, S.; Benterki, D., A relaxed logarithmic barrier method for semidefinite programming, RAIRO Oper. Res., 42, 555-568, (2015) · Zbl 1327.90179
[20] Crouzeix, JP; Merikhi, B., A logarithm barrier method for semidefinite programming, RAIRO Oper. Res., 42, 123-139, (2008) · Zbl 1211.90158
[21] Monteiro, RD, Primal-dual path-following algorithms for semidefinite programming, SIAM J. Optim., 7, 663-678, (1997) · Zbl 0913.65051
[22] Helmberg, C.; Rendl, F.; Vanderbei, RJ; Wolkowicz, H., An interior-point methods for stochastic semidefinite programming, SIAM J. Optim., 6, 342-361, (1996) · Zbl 0853.65066
[23] Touil, I.; Benterki, D.; Yassine, A., A feasible primal-dual interior point method for linear semidefinite programming, J. Comput. Appl. Math., 312, 216-230, (2017) · Zbl 1355.90061
[24] Kebbiche, Z.; Keraghel, A.; Yassine, A., Extension of a projective interior point method for linearly constrained convex programming, Appl. Math. Comput., 193, 553-559, (2007) · Zbl 1193.90212
[25] Gahinet, P.; Nemirovski, A., The projective method for solving linear matrix inequalities, Math. Prog., 77, 163-190, (1997) · Zbl 0890.90142
[26] Behling, R.; Gonzaga, C.; Haeser, G., Primal-dual relationship between Levenberg-Marquardt and central trajectories for linearly constrained convex optimization, J. Optim. Theory Appl., 162, 705-717, (2014) · Zbl 1311.90098
[27] Gould, N.; Orban, D.; Robinson, D., Trajectory-following methods for large-scale degenerate convex quadratic programming, Math. Prog. Comput., 5, 113-142, (2013) · Zbl 1272.65051
[28] MOSEK is an optimization software designed to solve large-scale mathematical optimization problems. http://www.mosek.com/. Accessed 5 Oct 2017
[29] Toh, K.C., Todd, M.J., Tutuncu, R.H.: SDPT3 version 4.0-a MATLAB software for semidefinite-quadratic-linear programming, (2009). Available online at: http://www.math.nus.edu.sg/ mattohkc/sdpt3.html · Zbl 1334.90117
[30] Wolkowicz, H.; Styan, G-P-H, Bounds for eigenvalues using traces, Linear Algebra Appl., 29, 471-506, (1980) · Zbl 0435.15015
[31] Faraut, J., Korányi, A.: Analysis on Symmetric Cones. Oxford University Press, Oxford (1994) · Zbl 0841.43002
[32] Kojima, M.; Shindoh, S.; Hara, S., Interior-point methods for the monotone linear complementarity problem in symmetric matrices, SIAM J. Optim., 7, 86-125, (1997) · Zbl 0872.90098
[33] Lütkepohl, H.: Handbook of Matrices. Humboldt-Universität zu Berlin, Germany (1996) · Zbl 0856.15001
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.