A full Nesterov-Todd step infeasible interior-point algorithm  for symmetric optimization based on a specific kernel function

Behrouz Kheirfam

doi:10.3934/naco.2013.3.601

Article Contents

2013, Volume 3, Issue 4: 601-614. Doi: 10.3934/naco.2013.3.601

This issue Previous Article Next Article Some properties of a class of $(F,E)$-$G$ generalized convex functions

A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function

Behrouz Kheirfam^1,

1.
Department of Mathematics, Tabriz University Tabriz

Received: November 2011

Revised: June 2013

Published: October 2013

Abstract / Introduction Related Papers Cited by

Abstract

We present a full Nesterov-Todd step infeasible interior-point algorithm based on a kernel function. Each main iteration of the algorithm consists of a feasibility step and some centering steps. We introduce a kernel function in the algorithm to induce the feasibility step. The iteration bound coincides with the best iteration bound for infeasible interior-point methods, that is, $O(r\log\frac{r}{\epsilon})$, where $r$ is the rank of Euclidean Jordan algebra.

Keywords:

Mathematics Subject Classification: Primary: 90C33, Secondary: 90C51.

Citation:

Related Papers

Cited by

References

[1]	J. Faraut and A. Korányi, "Analysis on Symmetric Cones," Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York, 1994.
[2]	L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms, J. Comput. Appl. Math., 86 (1997), 149-175.doi: 10.1016/S0377-0427(97)00153-2.
[3]	L. Faybusovich, A Jordan-algebraic approach to potential-reduction algorithms, Mathematicsche Zeitschrift, 239 (2002), 117-129.doi: 10.1007/s002090100286.
[4]	G. Gu, M. Zangiabadi and C. Roos, Full Nesterov-Todd step infeasible interior-point method for symmetric optimization, European J. Oper. Res., 214 (2011), 473-484.doi: 10.1016/j.ejor.2011.02.022.
[5]	B. Kheirfam, A full NT-step infeasible interior-point algorithm for semidefinite optimization based on a self-regular proximity, ANZIAM J., 53 (2011), 48-67.doi: 10.1017/S144618111200003X.
[6]	B. Kheirfam, Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step, Numer. Algorithms, 59 (2012), 589-606.doi: 10.1007/s11075-011-9506-1.
[7]	Z. Liu and W. Sun, A full-NT-step infeasible interior-point algorithm for SDP based on kernel functions, Appl. Math. Comput., 27 (2011), 4990-4999.doi: 10.1016/j.amc.2010.11.049.
[8]	Z. Liu, W. Sun and F. Tian, A full-Newton step infeasible interior-point algorithm for linear programming based on a kernel function, Appl. Math. Optim., 60 (2009), 237-251.doi: 10.1007/s00245-009-9069-x.
[9]	R. D. C. Monteiro and Y. Zhang, A unified analysis for a class of path-following primal-dual interior-point algorithms for semidefinite programming, Math. Program., 8 (1998), 281-299.doi: 10.1007/BF01580085.
[10]	Y. E. Nesterov and A. S. Nemirovskii, "Interior Point Polynomial Algorithms in Convex Programming," SIAM Stud. Appl. Math., SIAM, Philadelphia, 13 (1994).doi: 10.1137/1.9781611970791.
[11]	Y. E. Nesterov and M. J. Todd, Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res., 22 (1997), 1-42.doi: 10.1287/moor.22.1.1.
[12]	J. Peng, C. Roos and T. Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization, Math. Program., 93 (2002), 129-171.doi: 10.1007/s101070200296.
[13]	B. K. Rangarajan, Polynomial convergence of infeasible interior-point methods over symmetric cones, SIAM J. Optim., 16 (2006), 1211-1229.doi: 10.1137/040606557.
[14]	C. Roos, A full-Newton step O(n) infeasible interior-point algorithm for linear optimization, SIAM J. Optim., 16 (2006), 1110-1136.doi: 10.1137/050623917.
[15]	S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior-point algorithm to symmetric cones, Math. Program., 96 (2003), 409-438.doi: 10.1007/s10107-003-0380-z.
[16]	J. F. Sturm, Similarity and other spectral relations for symmetric cones, Algebra Appl., 312 (2000), 135-154.doi: 10.1016/S0024-3795(00)00096-3.
[17]	T. Tsuchiya, A convergence analysis of the scaling- invariant primal-dual path-following algorithms for second-order cone programming, Optim. Methods Sofw., 11-12 (1999), 141-182.doi: 10.1080/10556789908805750.
[18]	M. V. C. Vieira, "Jordan Algebraic Approach to Symmetric Optimization," Ph.D thesis, Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, The Netherlands, 2007.