-
Previous Article
The optimal stabilization of orbital motion in a neighborhood of collinear libration point
- NACO Home
- This Issue
-
Next Article
Computational networks and systems-homogenization of self-adjoint differential operators in variational form on periodic networks and micro-architectured systems
An infeasible full NT-step interior point method for circular optimization
1. | Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, I. R. Iran |
2. | College of Mathematics, Physics and Statistics, Shanghai University of Engineering Science, Shanghai, 201620, China |
In this paper, we design a primal-dual infeasible interior-point method for circular optimization that uses only full Nesterov-Todd steps. Each main iteration of the algorithm consisted of one so-called feasibility step. Furthermore, giving a complexity analysis of the algorithm, we derive the currently best-known iteration bound for infeasible interior-point methods.
References:
[1] |
B. Alzalg, Primal-dual path-following algorithm for circular programming, Available from: http://www.optimization-online.org/DB_FILE/2015/07/4998.pdf. |
[2] |
B. Alzalg, The circular cone: A new paradigm for symmetric cone in a Euclidean Jordan algebra, Available from: http://www.optimization-online.org/DB_HTML/2015/07/5027.html. |
[3] |
Y. Bai, P. Ma and J. Zhang,
A polynomial-time interior-point method for circular cone programming based on kernel functions, J. Ind. Manag. Optim., 12 (2015), 739-756.
doi: 10.3934/jimo.2016.12.739. |
[4] |
X. N. Chi, H. J. Wei, Y. Q. Feng and J. W. Chen,
Variational inequality formulation of circular cone eigenvalue complementarity problems,
Fixed Point Theory Appl., 2016: 31 (2016).
doi: 10.1186/s13663-016-0514-7. |
[5] |
L. Faybusovich,
Euclidean Jordan algebras and interior-point algorithms, Positivity, 1 (1997), 331-357.
doi: 10.1023/A:1009701824047. |
[6] |
B. Kheirfam,
An interior-point method for Cartesian $P_*(κ)$
-linear complementarity problem over symmetric cones, ORiON, 30 (2014), 41-58.
|
[7] |
B. Kheirfam,
A full NT-step infeasible interior-point algorithm for semidefinite optimization based on a self-regular proximity, The ANZIAM J., 53 (2011), 48-67.
doi: 10.1017/S144618111200003X. |
[8] |
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. |
[9] |
B. Kheirfam,
A new complexity analysis for full-Newton step infeasible interior-point algorithm for horizontal linear complementarity problems, J. Optim. Theory Appl., 161 (2014), 853-869.
doi: 10.1007/s10957-013-0457-7. |
[10] |
B. Kheirfam,
A new infeasible interior-point method based on Darvay's technique for symmetric optimization}, Ann. Oper. Res., 211 (2013), 209-224.
doi: 10.1007/s10479-013-1474-5. |
[11] |
B. Kheirfam,
Simplified analysis of a full Nesterov-Todd step infeasible interior-point method for symmetric optimization,
Asian-Eur. J. Math., 8 (2015), 1550071 (14 pages).
doi: 10.1142/S1793557115500710. |
[12] |
B. Kheirfam,
An improved full-Newton step $O(n)$ infeasible interior-point method for horizontal linear complementarity problem, Numer. Algorithms, 71 (2016), 491-503.
doi: 10.1007/s11075-015-0005-7. |
[13] |
B. Kheirfam,
A full step infeasible interior-point method for Cartesian $P_*(κ)$
-SCLCP, Optim. Letters, 10 (2016), 591-603.
doi: 10.1007/s11590-015-0884-5. |
[14] |
B. Kheirfam,
An improved and modified infeasible interior-point method for symmetric optimization,
Asian-Eur. J. Math., 9 (2016), 1650059 (13 pages).
doi: 10.1142/S1793557116500595. |
[15] |
B. Kheirfam,
A full Nesterov-Todd step interior-point method for circular cone optimization, Commun. Comb. Optim., 1 (2016), 83-102.
|
[16] |
B. Kheirfam and N. Mahdavi-Amiri,
A new interior-point algorithm based on modified Nesterov-Todd direction for symmetric cone linear complementarity problem, Optim. Letters, 8 (2014), 1017-1029.
doi: 10.1007/s11590-013-0618-5. |
[17] |
B. Kheirfam and N. Mahdavi-Amiri,
A full Nesterov-Todd step infeasible interior-point algorithm for symmetric cone linear complementarity problem, Bull. Iranian Math. Soc., 40 (2014), 541-564.
|
[18] |
X. Miao, S. Guo, N. Qi and J. S. Chen,
Constructions of complementarity functions and merit functions for circular cone complementarity problem, Comput. Optim. Appl., 63 (2016), 495-522.
doi: 10.1007/s10589-015-9781-1. |
[19] |
R. D. C. Monteiro and Y. Zhang,
A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming, Math. Program., 81 (1998), 281-299.
doi: 10.1007/BF01580085. |
[20] |
Y. E. Nesterov and M. J. Todd,
Primal-dual interior-point methods for self-scaled cones, SIAM J. Optim., 8 (1998), 324-364.
doi: 10.1137/S1052623495290209. |
[21] |
B. K. Rangarajan,
Polynomial convergence of infeasible-interior-point methods over symmetric cones, SIAM J. Optim., 16 (2006), 1211-1229.
doi: 10.1137/040606557. |
[22] |
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. |
[23] |
C. Roos,
An improved and simplified full-Newton step $O(n)$ infeasible interior-point method for linear optimization, SIAM J. Optim., 25 (2015), 102-114.
doi: 10.1137/140975462. |
[24] |
C. Roos, T. Terlaky and J-Ph. Vial,
Theory and Algorithms for Linear Optimization. An Interior-Point Approach, John Wiley and Sons, Chichester, UK, 1997. |
[25] |
S. H. Schmieta and F. Alizadeh,
Extension of primal-dual interior point methods to symmetric cones, Math. Program., 96 (2003), 409-438.
doi: 10.1007/s10107-003-0380-z. |
[26] |
G. Q. Wang, L. C. Kong, J. Y. Tao and G. Lesaja,
Improved complexity analysis of full Nesterov-Todd step feasible interior-point method for symmetric optimization, J. Optim. Theory Appl., 166 (2015), 588-604.
doi: 10.1007/s10957-014-0696-2. |
[27] |
G. Q. Wang and G. Lesaja,
Full Nesterov-Todd step feasible interior-point method for the Cartesian $P_*(κ)$
-SCLCP, Optim. Methods & Softw., 28 (2013), 600-618.
doi: 10.1080/10556788.2013.781600. |
[28] |
G. Q. Wang, C. J. Yu and K. L. Teo,
A new full Nesterov-Todd step feasible interior-point method for convex quadratic symmetric cone optimization, Appl. Math. Comput., 221 (2013), 329-343.
doi: 10.1016/j.amc.2013.06.064. |
[29] |
J. Zhou, J. S. Chen and B. S. Mordukhovich,
Variational analysis of circular cone programs, Optimization, 64 (2014), 113-147.
doi: 10.1080/02331934.2014.951043. |
show all references
References:
[1] |
B. Alzalg, Primal-dual path-following algorithm for circular programming, Available from: http://www.optimization-online.org/DB_FILE/2015/07/4998.pdf. |
[2] |
B. Alzalg, The circular cone: A new paradigm for symmetric cone in a Euclidean Jordan algebra, Available from: http://www.optimization-online.org/DB_HTML/2015/07/5027.html. |
[3] |
Y. Bai, P. Ma and J. Zhang,
A polynomial-time interior-point method for circular cone programming based on kernel functions, J. Ind. Manag. Optim., 12 (2015), 739-756.
doi: 10.3934/jimo.2016.12.739. |
[4] |
X. N. Chi, H. J. Wei, Y. Q. Feng and J. W. Chen,
Variational inequality formulation of circular cone eigenvalue complementarity problems,
Fixed Point Theory Appl., 2016: 31 (2016).
doi: 10.1186/s13663-016-0514-7. |
[5] |
L. Faybusovich,
Euclidean Jordan algebras and interior-point algorithms, Positivity, 1 (1997), 331-357.
doi: 10.1023/A:1009701824047. |
[6] |
B. Kheirfam,
An interior-point method for Cartesian $P_*(κ)$
-linear complementarity problem over symmetric cones, ORiON, 30 (2014), 41-58.
|
[7] |
B. Kheirfam,
A full NT-step infeasible interior-point algorithm for semidefinite optimization based on a self-regular proximity, The ANZIAM J., 53 (2011), 48-67.
doi: 10.1017/S144618111200003X. |
[8] |
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. |
[9] |
B. Kheirfam,
A new complexity analysis for full-Newton step infeasible interior-point algorithm for horizontal linear complementarity problems, J. Optim. Theory Appl., 161 (2014), 853-869.
doi: 10.1007/s10957-013-0457-7. |
[10] |
B. Kheirfam,
A new infeasible interior-point method based on Darvay's technique for symmetric optimization}, Ann. Oper. Res., 211 (2013), 209-224.
doi: 10.1007/s10479-013-1474-5. |
[11] |
B. Kheirfam,
Simplified analysis of a full Nesterov-Todd step infeasible interior-point method for symmetric optimization,
Asian-Eur. J. Math., 8 (2015), 1550071 (14 pages).
doi: 10.1142/S1793557115500710. |
[12] |
B. Kheirfam,
An improved full-Newton step $O(n)$ infeasible interior-point method for horizontal linear complementarity problem, Numer. Algorithms, 71 (2016), 491-503.
doi: 10.1007/s11075-015-0005-7. |
[13] |
B. Kheirfam,
A full step infeasible interior-point method for Cartesian $P_*(κ)$
-SCLCP, Optim. Letters, 10 (2016), 591-603.
doi: 10.1007/s11590-015-0884-5. |
[14] |
B. Kheirfam,
An improved and modified infeasible interior-point method for symmetric optimization,
Asian-Eur. J. Math., 9 (2016), 1650059 (13 pages).
doi: 10.1142/S1793557116500595. |
[15] |
B. Kheirfam,
A full Nesterov-Todd step interior-point method for circular cone optimization, Commun. Comb. Optim., 1 (2016), 83-102.
|
[16] |
B. Kheirfam and N. Mahdavi-Amiri,
A new interior-point algorithm based on modified Nesterov-Todd direction for symmetric cone linear complementarity problem, Optim. Letters, 8 (2014), 1017-1029.
doi: 10.1007/s11590-013-0618-5. |
[17] |
B. Kheirfam and N. Mahdavi-Amiri,
A full Nesterov-Todd step infeasible interior-point algorithm for symmetric cone linear complementarity problem, Bull. Iranian Math. Soc., 40 (2014), 541-564.
|
[18] |
X. Miao, S. Guo, N. Qi and J. S. Chen,
Constructions of complementarity functions and merit functions for circular cone complementarity problem, Comput. Optim. Appl., 63 (2016), 495-522.
doi: 10.1007/s10589-015-9781-1. |
[19] |
R. D. C. Monteiro and Y. Zhang,
A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming, Math. Program., 81 (1998), 281-299.
doi: 10.1007/BF01580085. |
[20] |
Y. E. Nesterov and M. J. Todd,
Primal-dual interior-point methods for self-scaled cones, SIAM J. Optim., 8 (1998), 324-364.
doi: 10.1137/S1052623495290209. |
[21] |
B. K. Rangarajan,
Polynomial convergence of infeasible-interior-point methods over symmetric cones, SIAM J. Optim., 16 (2006), 1211-1229.
doi: 10.1137/040606557. |
[22] |
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. |
[23] |
C. Roos,
An improved and simplified full-Newton step $O(n)$ infeasible interior-point method for linear optimization, SIAM J. Optim., 25 (2015), 102-114.
doi: 10.1137/140975462. |
[24] |
C. Roos, T. Terlaky and J-Ph. Vial,
Theory and Algorithms for Linear Optimization. An Interior-Point Approach, John Wiley and Sons, Chichester, UK, 1997. |
[25] |
S. H. Schmieta and F. Alizadeh,
Extension of primal-dual interior point methods to symmetric cones, Math. Program., 96 (2003), 409-438.
doi: 10.1007/s10107-003-0380-z. |
[26] |
G. Q. Wang, L. C. Kong, J. Y. Tao and G. Lesaja,
Improved complexity analysis of full Nesterov-Todd step feasible interior-point method for symmetric optimization, J. Optim. Theory Appl., 166 (2015), 588-604.
doi: 10.1007/s10957-014-0696-2. |
[27] |
G. Q. Wang and G. Lesaja,
Full Nesterov-Todd step feasible interior-point method for the Cartesian $P_*(κ)$
-SCLCP, Optim. Methods & Softw., 28 (2013), 600-618.
doi: 10.1080/10556788.2013.781600. |
[28] |
G. Q. Wang, C. J. Yu and K. L. Teo,
A new full Nesterov-Todd step feasible interior-point method for convex quadratic symmetric cone optimization, Appl. Math. Comput., 221 (2013), 329-343.
doi: 10.1016/j.amc.2013.06.064. |
[29] |
J. Zhou, J. S. Chen and B. S. Mordukhovich,
Variational analysis of circular cone programs, Optimization, 64 (2014), 113-147.
doi: 10.1080/02331934.2014.951043. |
[1] |
Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control and Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601 |
[2] |
Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial and Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103 |
[3] |
Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211 |
[4] |
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 and Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101 |
[5] |
Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control and Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015 |
[6] |
Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial and Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739 |
[7] |
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 and Management Optimization, 2021 doi: 10.3934/jimo.2021082 |
[8] |
Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial and Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949 |
[9] |
Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial and Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891 |
[10] |
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 and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37 |
[11] |
Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022 doi: 10.3934/naco.2022003 |
[12] |
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 and Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190 |
[13] |
Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011 |
[14] |
A. S. Dzhumadil'daev. Jordan elements and Left-Center of a Free Leibniz algebra. Electronic Research Announcements, 2011, 18: 31-49. doi: 10.3934/era.2011.18.31 |
[15] |
Yu-Lin Chang, Chin-Yu Yang. Some useful inequalities via trace function method in Euclidean Jordan algebras. Numerical Algebra, Control and Optimization, 2014, 4 (1) : 39-48. doi: 10.3934/naco.2014.4.39 |
[16] |
A. V. Borisov, I. S. Mamaev, S. M. Ramodanov. Dynamics of a circular cylinder interacting with point vortices. Discrete and Continuous Dynamical Systems - B, 2005, 5 (1) : 35-50. doi: 10.3934/dcdsb.2005.5.35 |
[17] |
Gaik Ambartsoumian, Leonid Kunyansky. Exterior/interior problem for the circular means transform with applications to intravascular imaging. Inverse Problems and Imaging, 2014, 8 (2) : 339-359. doi: 10.3934/ipi.2014.8.339 |
[18] |
Shenggui Zhang. A sufficient condition of Euclidean rings given by polynomial optimization over a box. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 93-101. doi: 10.3934/naco.2014.4.93 |
[19] |
Liming Sun, Li-Zhi Liao. An interior point continuous path-following trajectory for linear programming. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1517-1534. doi: 10.3934/jimo.2018107 |
[20] |
Zheng-Hai Huang, Shang-Wen Xu. Convergence properties of a non-interior-point smoothing algorithm for the P*NCP. Journal of Industrial and Management Optimization, 2007, 3 (3) : 569-584. doi: 10.3934/jimo.2007.3.569 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]