×

zbMATH — the first resource for mathematics

A discretization algorithm for nonsmooth convex semi-infinite programming problems based on bundle methods. (English) Zbl 1433.90175
Summary: We propose a discretization algorithm for solving a class of nonsmooth convex semi-infinite programming problems that is based on a bundle method. Instead of employing the inexact calculation to evaluate the lower level problem, we shall carry out a discretization scheme. The discretization method is used to get a number of discretized problems which are solved by the bundle method. In particular, the subproblem used to generate a new point is independent of the number of constraints of the discretized problem. We apply a refinement-step which can be used to guarantee the convergence of the bundle method for the discretized problems as well as reduce the cost of the evaluations for the constraint functions during iteration. In addition we adopt an aggregation technique to manage the bundle information coming from previous steps. Both theoretical convergence analysis and preliminary computational results are reported. The results obtained have shown the good performance of the new algorithm.
MSC:
90C34 Semi-infinite programming
90C25 Convex programming
90C56 Derivative-free methods and methods using generalized derivatives
Software:
PLCP; SQPlab
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bagirov, A.; Karmitsa, N.; Mäkelä, MM, Introduction to Nonsmooth Optimization: Theory, Practice and Software (2014), Cham: Springer, Cham
[2] Barrodale, I.; Delves, LM; Mason, JC, Linear chebyshev approximation of complex-valued functions, Math. Comput., 32, 853-863 (1978) · Zbl 0381.65007
[3] Bonnans, JF; Gilbert, JC; Lemarchal, C.; Sagastizbal, CA, Numerical Optimization: Theoretical and Practical Aspects (2006), Berlin: Springer, Berlin
[4] Dam, HH; Teo, KL; Nordebo, S.; Cantoni, A., The dual parameterization approach to optimal least square fir filter design subject to maximum error constraints, IEEE Trans. Signal Process., 48, 8, 2314-2320 (2000) · Zbl 0981.94003
[5] Gustafson, SÅ; Kortanek, K.; Bachem, A.; Korte, B.; Grötschel, M., Semi-infinite programming and applications, Mathematical Programming the State of the Art, 132-157 (1983), Berlin: Springer, Berlin
[6] Hare, W.; Sagastizábal, C., A redistributed proximal bundle method for nonconvex optimization, SIAM J. Optim., 20, 5, 2442-2473 (2010) · Zbl 1211.90183
[7] Hettich, R., An implementation of a discretization method for semi-infinite programming, Math. Program., 34, 3, 354-361 (1986) · Zbl 0592.90061
[8] Hettich, R.; Kortanek, KO, Semi-infinite programming: theory, methods, and applications, Soc. Ind. Appl. Math., 35, 3, 380-429 (1993) · Zbl 0784.90090
[9] Kelley, JE, The cutting-plane method for solving convex programs, Soc. Ind. Appl. Math., 8, 4, 703-712 (1960) · Zbl 0098.12104
[10] Kiwiel, KC, Exact penalty functions in proximal bundle methods for constrained convex nondifferentiable minimization, Math. Program., 52, 1, 285-302 (1991) · Zbl 0754.90045
[11] Kiwiel, KC, Methods of Descent for Nondifferentiable Optimization (2006), Berlin: Springer, Berlin
[12] 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
[13] Liu, Z.; Gong, YH, Semi-infinite quadratic optimisation method for the design of robust adaptive array processors, IEE Proc. Radar Signal Process., 137, 177-182 (1990)
[14] López, M.; Still, G., Semi-infinite programming, Eur. J. Oper. Res., 180, 2, 491-518 (2007) · Zbl 1124.90042
[15] 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 (2018) · Zbl 1410.90169
[16] Mehrotra, S.; Papp, D., A cutting surface algorithm for semi-infinite convex programming with an application to moment robust optimization, SIAM J. Optim., 24, 4, 1670-1697 (2014) · Zbl 1330.90119
[17] Okuno, T.; Fukushima, M., Local reduction based SQP-type method for semi-infinite programs with an infinite number of second-order cone constraints, J. Glob. Optim., 60, 1, 25-48 (2014) · Zbl 1327.90343
[18] Okuno, T.; Hayashi, S.; Fukushima, M., A regularized explicit exchange method for semi-infinite programs with an infinite number of conic constraints, SIAM J. Optim., 22, 3, 1009-1028 (2012) · Zbl 1262.90177
[19] 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
[20] Polyak, B.T.: Subgradient methods: a survey of Soviet research. In: Nonsmooth Optimization (Proceedings of the IIASA Workshop, Laxenburg, 1977), IIASA Proc. Ser., vol. 3, pp. 5-29. Pergamon, Oxford (1978)
[21] Potchinkov, A.; Reemtsen, R., The design of fir filters in the complex plane by convex optimization, Sig. Process., 46, 2, 127-146 (1995) · Zbl 0875.93531
[22] 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
[23] Schramm, H.; Zowe, J., A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results, SIAM J. Optim., 2, 1, 121-152 (1992) · Zbl 0761.90090
[24] Still, G., Discretization in semi-infinite programming: the rate of convergence, Math. Program., 91, 1, 53-69 (2001) · Zbl 1051.90023
[25] Tichatschke, R.; Nebeling, V., A cutting-plane method for quadratic semi infinite programming problems, Optimization, 19, 6, 803-817 (1988) · Zbl 0664.90073
[26] Žaković, S.; Rustem, B., Semi-infinite programming and applications to minimax problems, Ann. Oper. Res., 124, 1, 81-110 (2003) · Zbl 1074.90554
[27] Zhang, LP; Wu, SY, An efficient algorithm for min-max convex semi-infinite programming problems, Numer. Funct. Anal. Optim., 37, 8, 1037-1053 (2016) · Zbl 1348.90574
[28] 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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.