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

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

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

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

[5]

L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms, Positivity, 1 (1997), 331-357.  doi: 10.1023/A:1009701824047.  Google Scholar

[6]

B. Kheirfam, An interior-point method for Cartesian $P_*(κ)$ -linear complementarity problem over symmetric cones, ORiON, 30 (2014), 41-58.   Google Scholar

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

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

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

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

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

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

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

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

[15]

B. Kheirfam, A full Nesterov-Todd step interior-point method for circular cone optimization, Commun. Comb. Optim., 1 (2016), 83-102.   Google Scholar

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[5]

L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms, Positivity, 1 (1997), 331-357.  doi: 10.1023/A:1009701824047.  Google Scholar

[6]

B. Kheirfam, An interior-point method for Cartesian $P_*(κ)$ -linear complementarity problem over symmetric cones, ORiON, 30 (2014), 41-58.   Google Scholar

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

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

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

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

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

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

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

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

[15]

B. Kheirfam, A full Nesterov-Todd step interior-point method for circular cone optimization, Commun. Comb. Optim., 1 (2016), 83-102.   Google Scholar

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[1]

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
[2]

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
[3]

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
[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 & 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 & 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 & 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 & 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 & 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 & 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 & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[11]

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
[12]

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
[13]

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
[14]

Yu-Lin Chang, Chin-Yu Yang. Some useful inequalities via trace function method in Euclidean Jordan algebras. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 39-48. doi: 10.3934/naco.2014.4.39
[15]

A. V. Borisov, I. S. Mamaev, S. M. Ramodanov. Dynamics of a circular cylinder interacting with point vortices. Discrete & Continuous Dynamical Systems - B, 2005, 5 (1) : 35-50. doi: 10.3934/dcdsb.2005.5.35
[16]

Gaik Ambartsoumian, Leonid Kunyansky. Exterior/interior problem for the circular means transform with applications to intravascular imaging. Inverse Problems & Imaging, 2014, 8 (2) : 339-359. doi: 10.3934/ipi.2014.8.339
[17]

Shenggui Zhang. A sufficient condition of Euclidean rings given by polynomial optimization over a box. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 93-101. doi: 10.3934/naco.2014.4.93
[18]

Liming Sun, Li-Zhi Liao. An interior point continuous path-following trajectory for linear programming. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1517-1534. doi: 10.3934/jimo.2018107
[19]

Zheng-Hai Huang, Shang-Wen Xu. Convergence properties of a non-interior-point smoothing algorithm for the P*NCP. Journal of Industrial & Management Optimization, 2007, 3 (3) : 569-584. doi: 10.3934/jimo.2007.3.569
[20]

Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283

 Impact Factor: 

Tools

Metrics

  • PDF downloads (218)
  • HTML views (234)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy