American Institute of Mathematical Sciences

Advanced
March  2020, 16(2): 1009-1035. doi: 10.3934/jimo.2018190

A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs

Yu-Hong Dai 1,2, , Xin-Wei Liu 3,, and  Jie Sun 4,5,6,

1. 

LSEC, ICMSEC, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China
2. 

School of Mathematical Sciences, University of Chinese Academy of Sciences
3. 

Institute of Mathematics, Hebei University of Technology, Tianjin 300401, China
4. 

Institute of Mathematics, Hebei University of Technology, Tianjin China
5. 

School of Science, Curtin University, Perth, Australia
6. 

School of Business, National University of Singapore, Singapore

*Corresponding author

Received  July 2018 Revised  August 2018 Published  March 2020 Early access  December 2018

Fund Project: The first draft of this paper was completed on December 2, 2014. The first author is supported by the Chinese NSF grants (nos. 11631013, 11331012 and 81173633) and the National Key Basic Research Program of China (no. 2015CB856000). The second author is supported by the Chinese NSF grants (nos. 11671116 and 11271107) and the Major Research Plan of the NSFC (no. 91630202). The third author is supported by Grant DP-160101819 of Australia Research Council

With the help of a logarithmic barrier augmented Lagrangian function, we can obtain closed-form solutions of slack variables of logarithmic-barrier problems of nonlinear programs. As a result, a two-parameter primal-dual nonlinear system is proposed, which corresponds to the Karush-Kuhn-Tucker point and the infeasible stationary point of nonlinear programs, respectively, as one of two parameters vanishes. Based on this distinctive system, we present a primal-dual interior-point method capable of rapidly detecting infeasibility of nonlinear programs. The method generates interior-point iterates without truncation of the step. It is proved that our method converges to a Karush-Kuhn-Tucker point of the original problem as the barrier parameter tends to zero. Otherwise, the scaling parameter tends to zero, and the method converges to either an infeasible stationary point or a singular stationary point of the original problem. Moreover, our method has the capability to rapidly detect the infeasibility of the problem. Under suitable conditions, the method can be superlinearly or quadratically convergent to the Karush-Kuhn-Tucker point if the original problem is feasible, and it can be superlinearly or quadratically convergent to the infeasible stationary point when the problem is infeasible. Preliminary numerical results show that the method is efficient in solving some simple but hard problems, where the superlinear convergence to an infeasible stationary point is demonstrated when we solve two infeasible problems in the literature.

Keywords: Nonlinear programming, constrained optimization, infeasibility, interior-point method, global and local convergence.
Mathematics Subject Classification: Primary: 90C30, 90C51; Secondary: 90C26.
Citation: 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
References:
[1]

R. Andreani, E. G. Birgin, J. M. Martinez and M. L. Schuverdt, Augmented Lagrangian methods under the constant positive linear dependence constraint qualification, Math. Program., 111 (2008), 5-32.  doi: 10.1007/s10107-006-0077-1.

[2]

P. Armand and J. Benoist, A local convergence property of primal-dual methods for nonlinear programming, Math. Program., 115 (2008), 199-222.  doi: 10.1007/s10107-007-0136-2.

[3]

P. Armand, J. C. Gilbert and S. Jan-Jégou, A feasible BFGS interior point algorithm for solving convex minimization problems, SIAM J. Optim., 11 (2000), 199-222.  doi: 10.1137/S1052623498344720.

[4]

I. Bongartz, A. R. Conn, N. I. M. Gould and P. L. Toint, CUTE: Constrained and Unconstrained Testing Environment, ACM Tran. Math. Software, 21 (1995), 123-160. 

[5]

J. V. Burke, F. E. Curtis and H. Wang, A sequential quadratic optimization algorithm with rapid infeasibility detection, SIAM J. Optim., 24 (2014), 839-872.  doi: 10.1137/120880045.

[6]

J. V. Burke and S. P. Han, A robust sequential quadratic programming method, Math. Program., 43 (1989), 277-303.  doi: 10.1007/BF01582294.

[7]

R. H. Byrd, Robust Trust-Region Method for Constrained Optimization, Paper presented at the SIAM Conference on Optimization, Houston, TX, 1987.

[8]

R. H. Byrd, F. E. Curtis and J. Nocedal, Infeasibility detection and SQP methods for nonlinear optimization, SIAM J. Optim., 20 (2010), 2281-2299.  doi: 10.1137/080738222.

[9]

R. H. Byrd, J. C. Gilbert and J. Nocedal, A trust region method based on interior point techniques for nonlinear programming, Math. Program., 89 (2000), 149-185.  doi: 10.1007/PL00011391.

[10]

R. H. Byrd, M. E. Hribar and J. Nocedal, An interior point algorithm for large-scale nonlinear programming, SIAM J. Optim., 9 (1999), 877-900.  doi: 10.1137/S1052623497325107.

[11]

R. H. Byrd, G. Liu and J. Nocedal, On the local behaviour of an interior point method for nonlinear programming, In, Numerical Analysis 1997 (eds. D. F. Griffiths and D. J. Higham), Addison-Wesley Longman, Reading, MA, 380 (1998), 37-56.

[12]

R. H. Byrd, M. Marazzi and J. Nocedal, On the convergence of Newton iterations to non-stationary points, Math. Program., 99 (2004), 127-148.  doi: 10.1007/s10107-003-0376-8.

[13]

L. F. Chen and D. Goldfarb, Interior-point $\ell_2$-penalty methods for nonlinear programming with strong global convergence properties, Math. Program., 108 (2006), 1-36.  doi: 10.1007/s10107-005-0701-5.

[14]

F. E. Curtis, A penalty-interior-point algorithm for nonlinear constrained optimization, Math. Program. Comput., 4 (2012), 181-209.  doi: 10.1007/s12532-012-0041-4.

[15]

A. S. El-Bakry, R. A. Tapia, T. Tsuchiya and Y. Zhang, On the formulation and theory of the Newton interior-point method for nonlinear programming, J. Optim. Theory Appl., 89 (1996), 507-541.  doi: 10.1007/BF02275347.

[16]

A. V. Fiacco and G. P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley and Sons, New York, 1968; republished as Classics in Appl. Math. 4, SIAM, Philadelphia, 1990. doi: 10.1137/1.9781611971316.

[17]

R. Fletcher, Practical Methods for Optimization. Vol. 2: Constrained Optimization, John Wiley and Sons, Chichester, 1980.

[18]

A. Forsgren and P. E. Gill, Primal-dual interior methods for nonconvex nonlinear programming, SIAM J. Optim., 8 (1998), 1132-1152.  doi: 10.1137/S1052623496305560.

[19]

A. Forsgren, Ph. E. Gill and M. H. Wright, Interior methods for nonlinear optimization, SIAM Review, 44 (2002), 525-597.  doi: 10.1137/S0036144502414942.

[20]

D. M. Gay, M. L. Overton and M. H. Wright, A primal-dual interior method for nonconvex nonlinear programming, in Advances in Nonlinear Programming, (ed. Y.-X. Yuan), Kluwer Academic Publishers, Dordrecht, 14 (1998), 31-56. doi: 10.1007/978-1-4613-3335-7_2.

[21]

E. M. Gertz and Ph. E. Gill, A primal-dual trust region algorithm for nonlinear optimization, Math. Program., 100 (2004), 49-94.  doi: 10.1007/s10107-003-0486-3.

[22]

N. I. M. Gould, D. Orban and Ph. L. Toint, An interior-point $\ell_1$-penalty method for nonlinear optimization, in Recent Developments in Numerical Analysis and Optimization, Proceedings of NAOIII 2014, Springer, Verlag, 134 (2015), 117-150. doi: 10.1007/978-3-319-17689-5_6.

[23]

W. Hock and K. Schittkowski, Test Examples for Nonlinear Programming Codes, Lecture Notes in Eco. and Math. Systems 187, Springer-Verlag, Berlin, New York, 1981. doi: 10.1007/BF00934594.

[24]

X.-W. Liu, G. Perakis and J. Sun, A robust SQP method for mathematical programs with linear complementarity constraints, Comput. Optim. Appl., 34 (2006), 5-33.  doi: 10.1007/s10589-005-3075-y.

[25]

X.-W. Liu and J. Sun, A robust primal-dual interior point algorithm for nonlinear programs, SIAM J. Optim., 14 (2004), 1163-1186.  doi: 10.1137/S1052623402400641.

[26]

X.-W. Liu and Y.-X. Yuan, A robust algorithm for optimization with general equality and inequality constraints, SIAM J. Sci. Comput., 22 (2000), 517-534.  doi: 10.1137/S1064827598334861.

[27]

X.-W. Liu and Y.-X. Yuan, A null-space primal-dual interior-point algorithm for nonlinear optimization with nice convergence properties, Math. Program., 125 (2010), 163-193.  doi: 10.1007/s10107-009-0272-y.

[28]

J. Nocedal, F. Öztoprak and R. A. Waltz, An interior point method for nonlinear programming with infeasibility detection capabilities, Optim. Methods Softw., 29 (2014), 837-854.  doi: 10.1080/10556788.2013.858156.

[29]

J. Nocedal and S. Wright, Numerical Optimization, Springer-Verlag New York, Inc., 1999. doi: 10.1007/b98874.

[30] J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York and London, 1970. 
[31]

D. F. Shanno and R. J. Vanderbei, Interior-point methods for nonconvex nonlinear programming: Orderings and higher-order methods, Math. Program., 87 (2000), 303-316.  doi: 10.1007/s101070050116.

[32]

P. Tseng, Convergent infeasible interior-point trust-region methods for constrained minimization, SIAM J. Optim., 13 (2002), 432-469.  doi: 10.1137/S1052623499357945.

[33]

M. Ulbrich, S. Ulbrich and L. N. Vicente, A globally convergent primal-dual interior-point filter method for nonlinear programming, Math. Program., 100 (2004), 379-410.  doi: 10.1007/s10107-003-0477-4.

[34]

A. Wächter and L. T. Biegler, Failure of global convergence for a class of interior point methods for nonlinear programming, Math. Program., 88 (2000), 565-574.  doi: 10.1007/PL00011386.

[35]

A. Wächter and L. T. Biegler, Line search filter methods for nonlinear programming: Motivation and global convergence, SIAM J. Optim., 16 (2005), 1-31.  doi: 10.1137/S1052623403426556.

[36]

A. Wächter and L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106 (2006), 25-57.  doi: 10.1007/s10107-004-0559-y.

[37]

M. H. Wright, Why a pure primal Newton barrier step may be infeasible?, SIAM J. Optim., 5 (1995), 1-12.  doi: 10.1137/0805001.

[38]

S. J. Wright, On the convergence of the Newton/Log-barrier method, Math. Program., 90 (2001), 71-100.  doi: 10.1007/PL00011421.

[39]

Y.-X. Yuan, On the convergence of a new trust region algorithm, Numer. Math., 70 (1995), 515-539.  doi: 10.1007/s002110050133.

[40]

Y. Zhang, Solving large-scale linear programs by interior-point methods under the MATLAB environment, Optim. Methods Softw., 10 (1998), 1-31. doi: 10.1080/10556789808805699.

show all references

References:
[1]

R. Andreani, E. G. Birgin, J. M. Martinez and M. L. Schuverdt, Augmented Lagrangian methods under the constant positive linear dependence constraint qualification, Math. Program., 111 (2008), 5-32.  doi: 10.1007/s10107-006-0077-1.

[2]

P. Armand and J. Benoist, A local convergence property of primal-dual methods for nonlinear programming, Math. Program., 115 (2008), 199-222.  doi: 10.1007/s10107-007-0136-2.

[3]

P. Armand, J. C. Gilbert and S. Jan-Jégou, A feasible BFGS interior point algorithm for solving convex minimization problems, SIAM J. Optim., 11 (2000), 199-222.  doi: 10.1137/S1052623498344720.

[4]

I. Bongartz, A. R. Conn, N. I. M. Gould and P. L. Toint, CUTE: Constrained and Unconstrained Testing Environment, ACM Tran. Math. Software, 21 (1995), 123-160. 

[5]

J. V. Burke, F. E. Curtis and H. Wang, A sequential quadratic optimization algorithm with rapid infeasibility detection, SIAM J. Optim., 24 (2014), 839-872.  doi: 10.1137/120880045.

[6]

J. V. Burke and S. P. Han, A robust sequential quadratic programming method, Math. Program., 43 (1989), 277-303.  doi: 10.1007/BF01582294.

[7]

R. H. Byrd, Robust Trust-Region Method for Constrained Optimization, Paper presented at the SIAM Conference on Optimization, Houston, TX, 1987.

[8]

R. H. Byrd, F. E. Curtis and J. Nocedal, Infeasibility detection and SQP methods for nonlinear optimization, SIAM J. Optim., 20 (2010), 2281-2299.  doi: 10.1137/080738222.

[9]

R. H. Byrd, J. C. Gilbert and J. Nocedal, A trust region method based on interior point techniques for nonlinear programming, Math. Program., 89 (2000), 149-185.  doi: 10.1007/PL00011391.

[10]

R. H. Byrd, M. E. Hribar and J. Nocedal, An interior point algorithm for large-scale nonlinear programming, SIAM J. Optim., 9 (1999), 877-900.  doi: 10.1137/S1052623497325107.

[11]

R. H. Byrd, G. Liu and J. Nocedal, On the local behaviour of an interior point method for nonlinear programming, In, Numerical Analysis 1997 (eds. D. F. Griffiths and D. J. Higham), Addison-Wesley Longman, Reading, MA, 380 (1998), 37-56.

[12]

R. H. Byrd, M. Marazzi and J. Nocedal, On the convergence of Newton iterations to non-stationary points, Math. Program., 99 (2004), 127-148.  doi: 10.1007/s10107-003-0376-8.

[13]

L. F. Chen and D. Goldfarb, Interior-point $\ell_2$-penalty methods for nonlinear programming with strong global convergence properties, Math. Program., 108 (2006), 1-36.  doi: 10.1007/s10107-005-0701-5.

[14]

F. E. Curtis, A penalty-interior-point algorithm for nonlinear constrained optimization, Math. Program. Comput., 4 (2012), 181-209.  doi: 10.1007/s12532-012-0041-4.

[15]

A. S. El-Bakry, R. A. Tapia, T. Tsuchiya and Y. Zhang, On the formulation and theory of the Newton interior-point method for nonlinear programming, J. Optim. Theory Appl., 89 (1996), 507-541.  doi: 10.1007/BF02275347.

[16]

A. V. Fiacco and G. P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley and Sons, New York, 1968; republished as Classics in Appl. Math. 4, SIAM, Philadelphia, 1990. doi: 10.1137/1.9781611971316.

[17]

R. Fletcher, Practical Methods for Optimization. Vol. 2: Constrained Optimization, John Wiley and Sons, Chichester, 1980.

[18]

A. Forsgren and P. E. Gill, Primal-dual interior methods for nonconvex nonlinear programming, SIAM J. Optim., 8 (1998), 1132-1152.  doi: 10.1137/S1052623496305560.

[19]

A. Forsgren, Ph. E. Gill and M. H. Wright, Interior methods for nonlinear optimization, SIAM Review, 44 (2002), 525-597.  doi: 10.1137/S0036144502414942.

[20]

D. M. Gay, M. L. Overton and M. H. Wright, A primal-dual interior method for nonconvex nonlinear programming, in Advances in Nonlinear Programming, (ed. Y.-X. Yuan), Kluwer Academic Publishers, Dordrecht, 14 (1998), 31-56. doi: 10.1007/978-1-4613-3335-7_2.

[21]

E. M. Gertz and Ph. E. Gill, A primal-dual trust region algorithm for nonlinear optimization, Math. Program., 100 (2004), 49-94.  doi: 10.1007/s10107-003-0486-3.

[22]

N. I. M. Gould, D. Orban and Ph. L. Toint, An interior-point $\ell_1$-penalty method for nonlinear optimization, in Recent Developments in Numerical Analysis and Optimization, Proceedings of NAOIII 2014, Springer, Verlag, 134 (2015), 117-150. doi: 10.1007/978-3-319-17689-5_6.

[23]

W. Hock and K. Schittkowski, Test Examples for Nonlinear Programming Codes, Lecture Notes in Eco. and Math. Systems 187, Springer-Verlag, Berlin, New York, 1981. doi: 10.1007/BF00934594.

[24]

X.-W. Liu, G. Perakis and J. Sun, A robust SQP method for mathematical programs with linear complementarity constraints, Comput. Optim. Appl., 34 (2006), 5-33.  doi: 10.1007/s10589-005-3075-y.

[25]

X.-W. Liu and J. Sun, A robust primal-dual interior point algorithm for nonlinear programs, SIAM J. Optim., 14 (2004), 1163-1186.  doi: 10.1137/S1052623402400641.

[26]

X.-W. Liu and Y.-X. Yuan, A robust algorithm for optimization with general equality and inequality constraints, SIAM J. Sci. Comput., 22 (2000), 517-534.  doi: 10.1137/S1064827598334861.

[27]

X.-W. Liu and Y.-X. Yuan, A null-space primal-dual interior-point algorithm for nonlinear optimization with nice convergence properties, Math. Program., 125 (2010), 163-193.  doi: 10.1007/s10107-009-0272-y.

[28]

J. Nocedal, F. Öztoprak and R. A. Waltz, An interior point method for nonlinear programming with infeasibility detection capabilities, Optim. Methods Softw., 29 (2014), 837-854.  doi: 10.1080/10556788.2013.858156.

[29]

J. Nocedal and S. Wright, Numerical Optimization, Springer-Verlag New York, Inc., 1999. doi: 10.1007/b98874.

[30] J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York and London, 1970. 
[31]

D. F. Shanno and R. J. Vanderbei, Interior-point methods for nonconvex nonlinear programming: Orderings and higher-order methods, Math. Program., 87 (2000), 303-316.  doi: 10.1007/s101070050116.

[32]

P. Tseng, Convergent infeasible interior-point trust-region methods for constrained minimization, SIAM J. Optim., 13 (2002), 432-469.  doi: 10.1137/S1052623499357945.

[33]

M. Ulbrich, S. Ulbrich and L. N. Vicente, A globally convergent primal-dual interior-point filter method for nonlinear programming, Math. Program., 100 (2004), 379-410.  doi: 10.1007/s10107-003-0477-4.

[34]

A. Wächter and L. T. Biegler, Failure of global convergence for a class of interior point methods for nonlinear programming, Math. Program., 88 (2000), 565-574.  doi: 10.1007/PL00011386.

[35]

A. Wächter and L. T. Biegler, Line search filter methods for nonlinear programming: Motivation and global convergence, SIAM J. Optim., 16 (2005), 1-31.  doi: 10.1137/S1052623403426556.

[36]

A. Wächter and L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106 (2006), 25-57.  doi: 10.1007/s10107-004-0559-y.

[37]

M. H. Wright, Why a pure primal Newton barrier step may be infeasible?, SIAM J. Optim., 5 (1995), 1-12.  doi: 10.1137/0805001.

[38]

S. J. Wright, On the convergence of the Newton/Log-barrier method, Math. Program., 90 (2001), 71-100.  doi: 10.1007/PL00011421.

[39]

Y.-X. Yuan, On the convergence of a new trust region algorithm, Numer. Math., 70 (1995), 515-539.  doi: 10.1007/s002110050133.

[40]

Y. Zhang, Solving large-scale linear programs by interior-point methods under the MATLAB environment, Optim. Methods Softw., 10 (1998), 1-31. doi: 10.1080/10556789808805699.

Table 1.  Output for test problem (TP1)
$ l $ $ f_l $ $ v_l $ $ \|\phi_l\|_{\infty} $ $ \|\psi_l\|_{\infty} $ $ \beta_l $ $ \rho_l $ $ k $
0 5 16.6132 129.6234 129.6234 0.1000 3.3226 -
1 0.1606 2.0205 4.8082 0.7313 0.1000 0.0972 3
2 -0.0149 2.0002 0.0989 0.0445 0.1000 0.0020 4
3 -0.0036 2.0000 0.0029 0.0018 0.1000 3.1595e-06 3
4 -0.0029 2.0000 3.1674e-06 2.8185e-06 0.1000 1.0000e-09 1
5 0.0018 2.0000 1.0011e-09 6.7212e-10 - - -
Table Options

Download as excel

$ l $ $ f_l $ $ v_l $ $ \|\phi_l\|_{\infty} $ $ \|\psi_l\|_{\infty} $ $ \beta_l $ $ \rho_l $ $ k $
0 5 16.6132 129.6234 129.6234 0.1000 3.3226 -
1 0.1606 2.0205 4.8082 0.7313 0.1000 0.0972 3
2 -0.0149 2.0002 0.0989 0.0445 0.1000 0.0020 4
3 -0.0036 2.0000 0.0029 0.0018 0.1000 3.1595e-06 3
4 -0.0029 2.0000 3.1674e-06 2.8185e-06 0.1000 1.0000e-09 1
5 0.0018 2.0000 1.0011e-09 6.7212e-10 - - -
Table 2.  Output for test problem (TP2)
$ l $ $ f_l $ $ v_l $ $ \|\phi_l\|_{\infty} $ $ \|\psi_l\|_{\infty} $ $ \beta_l $ $ \rho_l $ $ k $
0 -20 126.6501 2.8052e+03 2.8052e+03 0.1000 6.3325 -
1 -172.5829 172.7978 1.0948e+03 6.2866 0.1000 0.8719 6
2 0.2155 0.7149 1.4269 0.7894 0.1000 0.3895 1
3 -0.1364 0.5550 0.3865 0.3865 0.0100 0.3895 3
4 -0.1416 0.5223 0.2864 0.2648 0.0100 0.1512 1
5 -0.1472 0.5140 0.1446 0.1446 0.0100 0.0209 4
6 -0.1997 0.4472 0.0084 0.0016 0.0100 2.6880e-06 3
7 -0.1999 0.4472 2.4923e-06 2.4923e-06 0.0100 1.0000e-09 1
8 -0.1999 0.4472 9.2732e-10 9.2732e-10 - - -
Table Options

Download as excel

$ l $ $ f_l $ $ v_l $ $ \|\phi_l\|_{\infty} $ $ \|\psi_l\|_{\infty} $ $ \beta_l $ $ \rho_l $ $ k $
0 -20 126.6501 2.8052e+03 2.8052e+03 0.1000 6.3325 -
1 -172.5829 172.7978 1.0948e+03 6.2866 0.1000 0.8719 6
2 0.2155 0.7149 1.4269 0.7894 0.1000 0.3895 1
3 -0.1364 0.5550 0.3865 0.3865 0.0100 0.3895 3
4 -0.1416 0.5223 0.2864 0.2648 0.0100 0.1512 1
5 -0.1472 0.5140 0.1446 0.1446 0.0100 0.0209 4
6 -0.1997 0.4472 0.0084 0.0016 0.0100 2.6880e-06 3
7 -0.1999 0.4472 2.4923e-06 2.4923e-06 0.0100 1.0000e-09 1
8 -0.1999 0.4472 9.2732e-10 9.2732e-10 - - -
Table 3.  Output for test problem (TP4)
$ l $ $ f_l $ $ v_l $ $ \|\phi_l\|_{\infty} $ $ \|\psi_l\|_{\infty} $ $ \beta_l $ $ \rho_l $ $ k $
0 20 2.8284 9.9557 9.9557 0.1000 1 -
1 0.2305 0.4167 0.8900 0.7008 0.0100 1 4
2 0.1652 0.1687 0.1631 0.0771 0.0100 0.3268 4
3 0.1690 0.1630 0.0503 0.0022 0.0100 4.7328e-06 1
4 0.8561 2.9531e-04 3.1379e-06 3.1379e-06 0.0100 1.0000e-09 14
5 0.9028 1.2372e-04 9.3463e-08 9.3463e-08 - - -
Table Options

Download as excel

$ l $ $ f_l $ $ v_l $ $ \|\phi_l\|_{\infty} $ $ \|\psi_l\|_{\infty} $ $ \beta_l $ $ \rho_l $ $ k $
0 20 2.8284 9.9557 9.9557 0.1000 1 -
1 0.2305 0.4167 0.8900 0.7008 0.0100 1 4
2 0.1652 0.1687 0.1631 0.0771 0.0100 0.3268 4
3 0.1690 0.1630 0.0503 0.0022 0.0100 4.7328e-06 1
4 0.8561 2.9531e-04 3.1379e-06 3.1379e-06 0.0100 1.0000e-09 14
5 0.9028 1.2372e-04 9.3463e-08 9.3463e-08 - - -
Table 4.  The last $ 4 $ inner iterations corresponding to $ l = 4 $ for test problem (TP4)
$ k $ $ f_k $ $ v_k $ $ \|\phi_k\|_{\infty} $ $ \|\psi_k\|_{\infty} $ $ x_{k1} $ $ x_{k2} $
11 0.8500 5.7136e-04 5.6703e-04 5.6703e-04 1.0780 0.0001
12 0.8548 3.0434e-04 1.2222e-05 1.2222e-05 1.0754 -0.0002
13 0.8556 2.9845e-04 6.2125e-06 6.2125e-06 1.0750 -0.0002
14 0.8561 2.9531e-04 3.1379e-06 3.1379e-06 1.0747 -0.0002
Table Options

Download as excel

$ k $ $ f_k $ $ v_k $ $ \|\phi_k\|_{\infty} $ $ \|\psi_k\|_{\infty} $ $ x_{k1} $ $ x_{k2} $
11 0.8500 5.7136e-04 5.6703e-04 5.6703e-04 1.0780 0.0001
12 0.8548 3.0434e-04 1.2222e-05 1.2222e-05 1.0754 -0.0002
13 0.8556 2.9845e-04 6.2125e-06 6.2125e-06 1.0750 -0.0002
14 0.8561 2.9531e-04 3.1379e-06 3.1379e-06 1.0747 -0.0002
[1]

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

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

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

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

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

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

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

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

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

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

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353
[12]

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

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

Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2675-2701. doi: 10.3934/jimo.2019075
[15]

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

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

Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial and Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775
[18]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial and Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485
[19]

Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (273)
  • HTML views (1074)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy