American Institute of Mathematical Sciences

Advanced
  • 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
June  2017, 7(2): 171-184. doi: 10.3934/naco.2017011

An infeasible full NT-step interior point method for circular optimization

Behrouz Kheirfam 1,, and  Guoqiang Wang 2,

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

* Corresponding author: Behrouz Kheirfam

Received  July 2016 Revised  May 2017 Published  June 2017

Fund Project: The second author was supported by National Natural Science Foundation of China (No. 11471211) and Shanghai Natural Science Fund Project (No. 14ZR1418900).

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.

Keywords: Circular optimization, Euclidean Jordan algebra, Infeasible interior-point methods.
Mathematics Subject Classification: 90C51.
Citation: Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control and Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011
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

  • PDF downloads (253)
  • HTML views (236)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy