Global convergence analysis of the aggregate constraint homotopy method for nonlinear programming problems with both inequality and equality constraints. (English) Zbl 1402.90182
Summary: In this paper, we construct appropriate aggregate mappings and a new aggregate constraint homotopy (ACH) equation by converting equality constraints to inequality constraints and introducing two variable parameters. Then, we propose an ACH method for nonlinear programming problems with inequality and equality constraints. Under suitable conditions, we obtain the global convergence of this ACH method, which makes us prove the existence of a bounded smooth path that connects a given point to a Karush-Kuhn-Tucker point of nonlinear programming problems. The numerical tracking of this path can lead to an implementable globally convergent algorithm. A numerical procedure is given to implement the proposed ACH method, and the computational results are reported.
References:
| [1] | Karmarkar, N, A new polynomial-time algorithm for linear programming, Combinatorica, 14, 373-395, (1984) · Zbl 0557.90065 |
| [2] | Megiddo, N; Megiddo, N, Progress in mathematical programming, interior point and related methods, Pathways to the optimal set in linear programming, (1988), Springer, New York (NY) |
| [3] | Kojima, M; Mizuno, S; Yoshise, A; Megiddo, N, Progress in mathematical programming, A primal-dual interior point algorithm for linear programming, (1988), Springer, New York (NY) |
| [4] | Gonzaga, CC, Path following methods for linear programming, SIAM Rev, 34, 167-224, (1992) · Zbl 0763.90063 |
| [5] | Monteiro, RDC; Adler, I, Interior path following primal-dual algorithms, Part I: linear programming, Math Program, 44, 27-41, (1989) · Zbl 0676.90038 |
| [6] | Renegar, J, A polynomial-time algorithm based on newton’s method for linear programming, Math Program, 40, 59-93, (1988) · Zbl 0654.90050 |
| [7] | Monteiro, RDC; Adler, I, Interior path following primal-dual algorithms, Part II: convex quadratical programming, Math Program, 44, 43-66, (1989) · Zbl 0676.90039 |
| [8] | Kortanek, KO; Potra, F; Ye, Y, On some efficient interior point algorithms for nonlinear convex programming, Linear Algebra Appl, 152, 169-189, (1991) · Zbl 0741.65052 |
| [9] | McCormick, GP, The projective SUMT method for convex programming, Math Oper Res, 14, 203-223, (1989) · Zbl 0675.90067 |
| [10] | Monteiro, RDC; Adler, I, An extension of karmarkar type algorithm to a class of convex separable programming problems with global linear rate of convergence, Math Oper Res, 15, 408-422, (1990) · Zbl 0708.90068 |
| [11] | Zhu, J, A path following algorithm for a class of convex programming problems, ZOR-Methods Models Oper Res, 36, 359-377, (1992) · Zbl 0761.90078 |
| [12] | Kellogg, RB; Li, TY; Yorke, JA, A constructive proof of the Brouwer fixed-point theorem and computational results, SIAM J Numer Anal, 13, 473-483, (1976) · Zbl 0355.65037 |
| [13] | Smale, S, A convergent process of price adjustment and global Newton method, J Math Econ, 3, 1-14, (1976) · Zbl 0348.90017 |
| [14] | Chow, SN; Mallet-Paret, J; Yorke, JA, Finding zeros of maps: homotopy methods that are constructive with probability one, Math Comput, 32, 887-899, (1978) · Zbl 0398.65029 |
| [15] | Feng, GC; Lin, ZH; Yu, B, Existence of an interior pathway to a karush-Kuhn-Tucker point of a nonconvex programming problem, Nonlinear Anal, 32, 761-768, (1998) · Zbl 1060.90692 |
| [16] | Su, ML; Yu, B; Shi, SY, A boundary perturbation interior point homotopy method for solving fixed point problems, J Math Anal Appl, 377, 683-694, (2011) · Zbl 1211.65062 |
| [17] | Fan, XN; Yu, B, A smoothing homotopy method for solving variational inequalities, Nonlinear Anal, 70, 211-219, (2009) · Zbl 1153.90018 |
| [18] | Zhou, ZY; Yu, B, A smoothing homotopy method for variational inequality problems on polyhedral convex sets, J Glob Optim, 58, 151-168, (2014) · Zbl 1311.90157 |
| [19] | Yang, L; Yu, B, A homotopy method for nonlinear semidefinite programming, Comput Optim Appl, 56, 81-96, (2013) · Zbl 1298.90067 |
| [20] | Yu, B; Feng, GC; Zhang, SL, The aggregate constraint homotopy method for nonconvex nonlinear programming, Nonlinear Anal, 45, 839-847, (2001) · Zbl 1002.90092 |
| [21] | Li, XS, An aggregate constraint method for nonlinear programming, J Oper Res Soc, 42, 1003-1010, (1991) · Zbl 0742.90070 |
| [22] | Li, XS; Fang, SC, On the entropic regularization method for solving MIN-MAX problems with applications, Math Methods Oper Res, 46, 119-130, (1997) · Zbl 0886.90133 |
| [23] | Li, XS; Pan, S, Solving the finite MIN-MAX problem via an exponential penalty method, Comput Tech, 8, 3-15, (2003) · Zbl 1045.90084 |
| [24] | Polak, E; Royset, JO; Womersley, RS, Algorithms with adaptive smoothing for finite minimax problems, J Optim Theory Appl, 119, 459-484, (2003) · Zbl 1061.90117 |
| [25] | Liuzzi, G; Lucidi, S; Sclandrone, M, A derivative-free algorithm for linearly constrained finite minimax problems, SIAM J Optim, 16, 1054-1075, (2006) · Zbl 1131.90074 |
| [26] | Su, ML; Yu, B; Wang, J, Solving nonconvex nonlinear programming problems via a new aggregate constraint homotopy method, Nonlinear Anal, 73, 2558-2565, (2010) · Zbl 1210.65119 |
| [27] | Alidaee, B, Zero duality gap in surrogate constraint optimization: A concise review of models, Eur J Oper Res, 232, 241-248, (2014) · Zbl 1305.90001 |
| [28] | Dong, L; Yu, B; Zhao, GH, A spline smoothing homotopy method for nonconvex nonlinear programming, Optimization, 65, 1-21, (2015) |
| [29] | Xiao, Y; Xiong, HJ; Yu, B, A truncated aggregate smoothing Newton method for minimax problems, Appl Math Comput, 216, 1868-1879, (2010) · Zbl 1194.65083 |
| [30] | Xiong, HJ; Yu, B, An aggregate deformation homotopy method for constrained MIN-MAX-MIN problems with maxmin constraints, Comput Optim Appl, 47, 501-527, (2010) · Zbl 1208.90180 |
| [31] | Xiao, Y; Xiong, HJ; Yu, B, Truncated aggregate homotopy method for nonconvex nonlinear programming, Optim Methods Softw, 29, 160-176, (2014) · Zbl 1282.90209 |
| [32] | Zhu, ZC; Yu, B; Yang, L, Globally convergent homotopy method for designing piecewise linear deterministic contractual function, J Ind Manag Optim, 10, 717-741, (2014) · Zbl 1282.91178 |
| [33] | Zhu, ZC; Yu, B, Globally convergent homotopy algorithm for solving the KKT systems to the principal-agent bilevel programming, Optim Methods Softw, 32, 69-85, (2017) · Zbl 1364.90282 |
| [34] | Zhu, ZC; Yu, B, A modified homotopy method for solving the principal-agent bilevel programming problem, Comput Appl Math, 37, 541-566, (2018) · Zbl 1409.91157 |
| [35] | Heijer, CD; Rheinboldt, WC, On steplength algorithms for a class of continuation methods, SIAM Journal on Numerical Analysis, 18, 925-948, (1981) · Zbl 0472.65042 |
| [36] | Rheinboldt, WC; Melhem, RG, A comparison ofmethods for determining turning points of nonlinear equations, Computing, 29, 103-114, (1982) |
| [37] | Allgower, EL; Georg, K, Introduction to numerical continuation methods, (2003), Philadelphia, New York (NY) · Zbl 1036.65047 |
| [38] | Huang, Q; Zhu, Z; Wang, X, A predictor-corrector algorithm combined conjugate gradient with homotopy interior point for general nonlinear programming, Appl Math Comput, 219, 4379-4386, (2013) · Zbl 1401.90220 |
| [39] | Zhou, ZY; Yu, B; Shang, YF, A feasible set swelling homotopy method for general nonlinear programming, ICMT2011, 1884-1887, (2011) |
| [40] | Yang, L; Yu, B; Xu, Q, A combined homotopy infeasible interior method for nonconvex programming, Pac J Optim, 8, 89-101, (2012) · Zbl 1257.49032 |
| [41] | Yang, L; Yu, B; Xu, Q, A constraint shifting homotopy method for general non-linear programming, Optimization, 63, 585-600, (2014) · Zbl 1291.49024 |
| [42] | Wächter, A; Biegler, LT, Failure of global convergence for a class of interior point methods for nonlinear programming, Math Program, 88, 565-574, (2000) · Zbl 0963.65063 |
| [43] | Hock, W; Schittkowski, K, Test examples for nonlinear programming codes, 187, (1981), Springer-Verlag, Berlin · Zbl 0452.90038 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
