A feasible proximal bundle algorithm with convexification for nonsmooth, nonconvex semi-infinite programming. (English) Zbl 1489.65088
Summary: We propose a new numerical method for semi-infinite optimization problems whose objective function is a nonsmooth function. Existing numerical methods for solving semi-infinite programming (SIP) problems make strong assumptions on the structure of the objective function, e.g., differentiability, or are not guaranteed to furnish a feasible point on finite termination. In this paper, we propose a feasible proximal bundle method with convexification for solving this class of problems. The main idea is to derive upper bounding problems for the SIP by replacing the infinite number of constraints with a finite number of convex relaxation constraints, introduce improvement functions for the upper bounding problems, construct cutting plane models of the improvement functions, and reformulate the cutting plane models as quadratic programming problems and solve them. The convex relaxation constraints are constructed with ideas from the \(\alpha\) BB method of global optimization. Under mild conditions, we showed that every accumulation point of the iterative sequence is an \(\epsilon\)-stationary point of the original SIP problem. Under slightly stronger assumptions, every accumulation point of the iterative sequence is a local solution of the original SIP problem. Preliminary computational results on solving nonconvex, nonsmooth constrained optimization problems and semi-infinite optimization problems are reported to demonstrate the good performance of the new algorithms.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C34 | Semi-infinite programming |
| 90C26 | Nonconvex programming, global optimization |
Keywords:
nonsmooth nonconvex optimization; semi-infinite programming; bundle methods; convexification approximationSoftware:
SLQP-GSReferences:
| [1] | Adjiman, CS; Androulakis, IP; Floudas, CA, A global optimization method, αBB, for general twice-differentiable constrained NLPs-I: theoretical advances, Comput. Chem. Eng., 22, 1137-1158 (1998) · doi:10.1016/S0098-1354(98)00027-1 |
| [2] | Adjiman, CS; Androulakis, IP; Floudas, CA, A global optimization method, αBB, for general twice-differentiable constrained NLPs-II: implementation and computational results, Comput. Chem. Eng., 22, 1159-1179 (1998) · doi:10.1016/S0098-1354(98)00218-X |
| [3] | Bagirov, A.; Karmitsa, N.; Mäkelä, MM, Introduction to Nonsmooth Optimization: Theory, Practice and Software (2014), Cham: Springer, Cham · Zbl 1312.90053 · doi:10.1007/978-3-319-08114-4 |
| [4] | Bhattacharjee, B.; Green, JrWH; Barton, PI, Interval methods for semi-infinite programs, Comput. Optim. Appl., 30, 63-93 (2005) · Zbl 1130.90048 · doi:10.1007/s10589-005-4556-8 |
| [5] | Bhattacharjee, B.; Lemonidis, P.; Green, WHJr; Barton, PI, Global solution of semi-infinite programs, Math. Program., 103, 283-307 (2005) · Zbl 1090.90188 · doi:10.1007/s10107-005-0583-6 |
| [6] | Clarke, FH; Ledyaev, YS; Stern, RJ; Wolenski, PR, Nonsmooth Analysis and Control Theory (1998), New York: Springer, New York · Zbl 1047.49500 |
| [7] | Daniilidis, A.; Georgiev, P., Approximate convexity and submonotonicity, J. Math. Anal. Appl., 291, 1, 292-301 (2004) · Zbl 1048.49008 · doi:10.1016/j.jmaa.2003.11.004 |
| [8] | Djelassi, H.; Mitsos, A., A hybrid discretization algorithm with guaranteed feasibility for the global solution of semi-infinite programs, J Glob Optim., 68, 227-253 (2017) · Zbl 1380.90267 · doi:10.1007/s10898-016-0476-7 |
| [9] | Floudas, CA; Stein, O., The adaptive convexification algorithm: a feasible point method for semi-infinite programming, SIAM J. Optim., 18, 1187-1208 (2007) · Zbl 1216.90094 · doi:10.1137/060657741 |
| [10] | Fuduli, A.; Gaudioso, M.; Giallombardo, G.; Miglionico, G., A partially inexact bundle method for convex semi-infinite minmax problems, Commun. Nonlinear Sci. Numer. Simul., 21, 172-180 (2015) · Zbl 1338.90451 · doi:10.1016/j.cnsns.2014.07.033 |
| [11] | Gustafson, S.-Å., Kortanek, K.: Semi-infinite programming and applications. In: Mathematical Programming The State of the Art, pp 132-157. Springer, Berlin (1983) · Zbl 0546.49013 |
| [12] | Hare, W.; Sagastizábal, C., A redistributed proximal bundle method for nonconvex optimization, SIAM J. Optim., 20, 5, 2442-2473 (2010) · Zbl 1211.90183 · doi:10.1137/090754595 |
| [13] | Hare, W.; Sagastizábal, C.; Solodov, M., A proximal bundle method for nonsmooth nonconvex functions with inexact information, Comput. Optim. Appl., 63, 1-28 (2016) · Zbl 1343.90069 · doi:10.1007/s10589-015-9762-4 |
| [14] | Hettich, R., An implementation of a discretization method for semi-infinite programming, Math. Program., 34, 3, 354-361 (1986) · Zbl 0592.90061 · doi:10.1007/BF01582235 |
| [15] | Hettich, R.; Kortanek, KO, Semi-infinite programming: theory, methods, and applications, Soc. Ind. Appl. Math., 35, 3, 380-429 (1993) · Zbl 0784.90090 |
| [16] | Hoseini Monjezi, N., Nobakhtian, S.: A filter proximal bundle method for nonsmooth nonconvex constrained optimization. J. Glob. Optim. (2020) · Zbl 1465.90073 |
| [17] | Hoseini Monjezi, N.; Nobakhtian, S., A new infeasible proximal bundle algorithm for nonsmooth nonconvex constrained optimization, Comput Optim Appl., 74, 443-480 (2019) · Zbl 1425.90084 · doi:10.1007/s10589-019-00115-8 |
| [18] | Karas, E.; Ribeiro, A.; Sagastizábal, C.; Solodov, M., A bundle-filter method for nonsmooth convex constrained optimization, Math. Program., 116, 297-320 (2009) · Zbl 1165.90024 · doi:10.1007/s10107-007-0123-7 |
| [19] | Karmitsa, N.: Test problems for large-scale nonsmooth minimization. Reports of the Department of Mathematical Information Technology, Series B, Scientific computing, No. B 4/2007 (2007) |
| [20] | Kiwiel, KC, Methods of Descent for Nondifferentiable Optimization, vol. 1133 (2006), Berlin, Heidelberg: Springer, Berlin, Heidelberg |
| [21] | Kortanek, KO; No, H., A central cutting plane algorithm for convex semi-infinite programming problems, SIAM J. Optim., 3, 4, 901-918 (1993) · Zbl 0790.90070 · doi:10.1137/0803047 |
| [22] | López, M.; Still, G., Semi-infinite programming, Eur. J. Oper. Res., 180, 2, 491-518 (2007) · Zbl 1124.90042 · doi:10.1016/j.ejor.2006.08.045 |
| [23] | Lv, J.; Pang, LP; Meng, FY, A proximal bundle method for constrained nonsmooth nonconvex optimization with inexact information, J. Global Optim., 70, 517-549 (2018) · Zbl 1390.90448 · doi:10.1007/s10898-017-0565-2 |
| [24] | Lv, J.; Pang, LP; Xu, N.; Xiao, ZH, An infeasible bundle method for nonconvex constrained optimization with application to semi-infinite programming problems, Numer. Algorithms, 80, 397-427 (2019) · Zbl 1410.90169 · doi:10.1007/s11075-018-0490-6 |
| [25] | Meng, FY; Pang, LP; Lv, J.; Wang, JH, An approximate bundle method for solving nonsmooth equilibrium problems, J. Global Optim., 68, 537-562 (2017) · Zbl 1369.90123 · doi:10.1007/s10898-016-0490-9 |
| [26] | Mifflin, R., Semismooth and semiconvex functions in constrained optimization, SAIM J. Control Optim., 15, 6, 959-972 (1977) · Zbl 0376.90081 · doi:10.1137/0315061 |
| [27] | Mitsos, A., Global optimization of semi-infinite programs via restriction of the right-hand side, Optimization, 60, 10-11, 1291-1308 (2011) · Zbl 1231.90361 · doi:10.1080/02331934.2010.527970 |
| [28] | Mitsos, A., Djelassi, H.: A Test Set of Semi-Infinite Programs. Process Systems Engineering (AVT.SVT), RWTH Aachen University, Aachen, Germany. http://web.mit.edu/mitsos/www/pubs/siptestset.pdf (2016) · Zbl 1380.90267 |
| [29] | Mitsos, A.; Lemonidis, P.; Lee, CK; Barton, PI, Relaxation-based bounds for semi-infinite programs, SIAM J. Optim., 19, 77-113 (2007) · Zbl 1163.90035 · doi:10.1137/060674685 |
| [30] | Mitsos, A.; Tsoukalas, A., Global optimization of generalized semi-infinite programs via restriction of the right hand side, J. Glob. Optim., 61, 1, 1-17 (2015) · Zbl 1312.90063 · doi:10.1007/s10898-014-0146-6 |
| [31] | Pang, LP; Lv, J.; Wang, JH, Constrained incremental bundle method with partial inexact oracle for nonsmooth convex semi-infinite programming problems, Comput. Optim. Appl., 64, 2, 433-465 (2016) · Zbl 1370.90278 · doi:10.1007/s10589-015-9810-0 |
| [32] | Pang, L.; Wu, Q.; Wang, J., A discretization algorithm for nonsmooth convex semi-infinite programming problems based on bundle methods, Comput Optim Appl., 76, 125-153 (2020) · Zbl 1433.90175 · doi:10.1007/s10589-020-00170-6 |
| [33] | Polyak, BT, Introduction to Optimization (1987), New York: Optimization Software, Inc., Publications Division, New York · Zbl 0708.90083 |
| [34] | Rustem, B.; Nguyen, Q., An algorithm for the inequality-constrained discrete min-max problem, SIAM J. Optim., 8, 265-283 (1998) · Zbl 0911.90310 · doi:10.1137/S1056263493260386 |
| [35] | Sagastizábal, C.; Solodov, M., An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or a filter, SIAM J. Optim., 16, 1, 146-169 (2005) · Zbl 1114.90093 · doi:10.1137/040603875 |
| [36] | Shiu, TJ; Wu, SY, Relaxed cutting plane method with convexification for solving nonlinear semi-infinite programming problems, Comput Optim Appl., 53, 91-113 (2012) · Zbl 1259.90148 · doi:10.1007/s10589-011-9452-9 |
| [37] | Spingarn, JE, Submonotone subdifferentials of Lipschitz functions, Trans. Am. Math. Soc., 264, 77-89 (1981) · Zbl 0465.26008 · doi:10.1090/S0002-9947-1981-0597868-8 |
| [38] | Stein, O.; Steuermann, P., The adaptive convexification algorithm for semi-infinite programming with arbitrary index sets, Math. Program., 136, 183-207 (2012) · Zbl 1263.90106 · doi:10.1007/s10107-012-0556-5 |
| [39] | Still, G., Discretization in semi-infinite programming: the rate of convergence, Math. Programm., 91, 1, 53-69 (2001) · Zbl 1051.90023 · doi:10.1007/s101070100239 |
| [40] | Tang, C.; Liu, S.; Jian, J., A feasible SQP-GS algorithm for nonconvex, nonsmooth constrained optimization, Numer Algor., 65, 1-22 (2014) · Zbl 1285.65036 · doi:10.1007/s11075-012-9692-5 |
| [41] | Wang, SX; Yuan, YX, Feasible method for semi-infinite programs, SIAM J. Optim., 25, 4, 2537-2560 (2015) · Zbl 1329.90148 · doi:10.1137/140982143 |
| [42] | Xu, MW; Wu, SY; Ye, JJ, Solving semi-infinite programs by smoothing projected gradient method, Comput. Optim. Appl., 59, 591-616 (2014) · Zbl 1308.65101 · doi:10.1007/s10589-014-9654-z |
| [43] | Yang, Y.; Pang, L.; Ma, X., Constrained Nonconvex Nonsmooth Optimization via Proximal Bundle Method, J Optim Theory Appl., 163, 900-925 (2014) · Zbl 1302.90162 · doi:10.1007/s10957-014-0523-9 |
| [44] | Zhang, LP; Wu, SY; López, MA, A new exchange method for convex semi-infinite programming, SIAM J. Optim., 20, 6, 2959-2977 (2010) · Zbl 1229.90247 · doi:10.1137/090767133 |
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.
