2013, 3(4): 601-614. doi: 10.3934/naco.2013.3.601

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

1. 

Department of Mathematics, Tabriz University Tabriz

Received  November 2011 Revised  June 2013 Published  October 2013

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.
Citation: Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601
References:
[1]

J. Faraut and A. Korányi, "Analysis on Symmetric Cones," Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York, 1994.  Google Scholar

[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.  Google Scholar

[3]

L. Faybusovich, A Jordan-algebraic approach to potential-reduction algorithms, Mathematicsche Zeitschrift, 239 (2002), 117-129. doi: 10.1007/s002090100286.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

show all references

References:
[1]

J. Faraut and A. Korányi, "Analysis on Symmetric Cones," Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York, 1994.  Google Scholar

[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.  Google Scholar

[3]

L. Faybusovich, A Jordan-algebraic approach to potential-reduction algorithms, Mathematicsche Zeitschrift, 239 (2002), 117-129. doi: 10.1007/s002090100286.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[1]

Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial & Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103

[2]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101

[3]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[4]

Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011

[5]

Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021082

[6]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891

[7]

Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739

[8]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015

[9]

Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial & Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190

[10]

Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011

[11]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211

[12]

Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial & Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949

[13]

Mariantonia Cotronei, Tomas Sauer. Full rank filters and polynomial reproduction. Communications on Pure & Applied Analysis, 2007, 6 (3) : 667-687. doi: 10.3934/cpaa.2007.6.667

[14]

Nadia Hazzam, Zakia Kebbiche. A primal-dual interior point method for $ P_{\ast }\left( \kappa \right) $-HLCP based on a class of parametric kernel functions. Numerical Algebra, Control & Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053

[15]

Luc Robbiano. Counting function for interior transmission eigenvalues. Mathematical Control & Related Fields, 2016, 6 (1) : 167-183. doi: 10.3934/mcrf.2016.6.167

[16]

Jon Aaronson, Michael Bromberg, Nishant Chandgotia. Rational ergodicity of step function skew products. Journal of Modern Dynamics, 2018, 13: 1-42. doi: 10.3934/jmd.2018012

[17]

Xin Guo, Lexin Li, Qiang Wu. Modeling interactive components by coordinate kernel polynomial models. Mathematical Foundations of Computing, 2020, 3 (4) : 263-277. doi: 10.3934/mfc.2020010

[18]

Andrew J. Steyer, Erik S. Van Vleck. Underlying one-step methods and nonautonomous stability of general linear methods. Discrete & Continuous Dynamical Systems - B, 2018, 23 (7) : 2859-2877. doi: 10.3934/dcdsb.2018108

[19]

Kyoungsun Kim, Gen Nakamura, Mourad Sini. The Green function of the interior transmission problem and its applications. Inverse Problems & Imaging, 2012, 6 (3) : 487-521. doi: 10.3934/ipi.2012.6.487

[20]

Yoonsang Lee, Bjorn Engquist. Variable step size multiscale methods for stiff and highly oscillatory dynamical systems. Discrete & Continuous Dynamical Systems, 2014, 34 (3) : 1079-1097. doi: 10.3934/dcds.2014.34.1079

 Impact Factor: 

Metrics

  • PDF downloads (46)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]