×

Minimization of marginal functions in mathematical programming based on continuous outer subdifferentials. (English) Zbl 1406.90116

The author presents a new approach to develop a converging descent method for a class of nonsmooth functions, specifically, marginal functions. This approach constructs a continuous outer subdifferential (COS) for the marginal functions based on a superset of the symmetric subdifferential. It is shown that this construction is also suitable for the Clarke subdifferential. A conceptual minimization algorithm based on the COS is proposed and the global convergence of this algorithm is shown for marginal functions. Especially, neither semismoothness nor calculation of exact subgradients are required. Also, numerical results are given.

MSC:

90C30 Nonlinear programming
90C31 Sensitivity, stability, parametric optimization

Software:

GradSamp
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bonnans, J.; Shapiro, A., Perturbation analysis of optimization problems (2000), New York: Springer, New York · Zbl 0966.49001
[2] Borwein, J., Stability and regular points of inequality systems, J Optim Theory Appl, 48, 1, 9-52 (1986) · Zbl 0557.49020
[3] Clarke, Fh, Functional analysis, calculus of variations and optimal control (2013), London: Springer, London · Zbl 1277.49001
[4] Dubeau, F.; Gauvin, J., Differential properties of the marginal function in mathematical programming, Math Program Study, 19, 101-119 (1982) · Zbl 0502.90072
[5] Dubeau, F.; Gauvin, J., Some examples and counterexamples for the stability analysis of nonlinear programming problems, Math Program Study, 21, 69-78 (1984) · Zbl 0553.49019
[6] Mordukhovich, Bs, Variational analysis and generalized differentiation I (2006), Berlin: Springer, Berlin
[7] Mordukhovich, Bs, Variational analysis and generalized differentiation II (2006), Berlin: Springer, Berlin
[8] Mordukhovich, Bs; Nam, Nm; Yen, Nd, Subgradients of marginal functions in parametric mathematical programming, Math Program, 116, 1, 369-396 (2009) · Zbl 1177.90377
[9] Rockafellar, R., Lagrange multipliers and subderivatives of optimal value functions in nonlinear programming, Math Program Stud, 17, 28-66 (1982) · Zbl 0478.90060
[10] Rockafellar, R., Directional differentiability of the optimal value function in a nonlinear programming problem, Math Program Stud, 21, 213-226 (1984) · Zbl 0546.90088
[11] Rockafellar, Rt; Wets, Rjb, Variational analysis (2009), Berlin: Springer, Berlin
[12] Thibault, L., On subdifferentials of optimal value functions, SIAM J Control Optim, 29, 5, 1019-1036 (1991) · Zbl 0734.90093
[13] Bagirov, Am; Karmitsa, N.; Mäkelä, Mm, Introduction to nonsmooth optimization (2014), Cham: Springer, Cham · Zbl 1312.90053
[14] Demyanov, Vf; Malozemov, Vn, Einführung in minimax-probleme (1975), Leipzig: Akademische Verlagsgesellschaft Geest & Portig K.-G., Leipzig · Zbl 0328.90062
[15] Hiriart-Urruty, Jb; Lemaréchal, C., Convex analysis and minimization algorithms II (1993), Berlin: Springer, Berlin · Zbl 0795.49001
[16] Hiriart-Urruty, Jb; Lemaréchal, C., Convex analysis and minimization algorithms I (1996), Berlin: Springer, Berlin
[17] Kiwiel, Kc, Methods of descent for nondifferentiable optimization (1985), Berlin: Springer, Berlin · Zbl 0561.90059
[18] Lemaréchal, C.; Nemirovskii, A.; Nesterov, Y., New variants of bundle methods. mathematical programming, Math Program, 69, 1, 111-147 (1995) · Zbl 0857.90102
[19] Lemaréchal, C.; Zowe, J., A condensed introduction to bundle methods in nonsmooth optimization, Alg Continuous Optim, 434, 357-382 (1994) · Zbl 0828.90124
[20] Mäkelä, Mm; Neittaanmäki, P., Nonsmooth optimization (1992), Singapore: World Scientific, Singapore · Zbl 0757.49017
[21] Rockafellar, Rt, Monotone operators and the proximal point algorithm, SIAM J Control Optim, 14, 5, 877-898 (1976) · Zbl 0358.90053
[22] 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
[23] Haarala, N.; Miettinen, K.; Mäkelä, Mm, Globally convergent limited memory bundle method for large-scale nonsmooth optimization, Math Program, 109, 1, 181-205 (2007) · Zbl 1278.90451
[24] Karmitsa, N., Diagonal bundle method for nonsmooth sparse optimization, J Optim Theory Appl, 166, 3, 889-905 (2015) · Zbl 1323.65069
[25] Karmitsa, N., Diagonal discrete gradient bundle method for derivative free nonsmooth optimization, Optimization, 65, 8, 1599-1614 (2016) · Zbl 1397.90309
[26] Lukšan, L.; Vlček, J., Globally convergent variable metric method for nonconvex nondifferentiable unconstrained minimization, J Optim Theory Appl, 111, 2, 407-430 (2001) · Zbl 1029.90060
[27] Bagirov, Am, Continuous subdifferential approximations and their applications, J Math Sci, 115, 5, 2567-2609 (2003) · Zbl 1039.49020
[28] Bagirov, Am; Ganjehlou, An, An approximate subgradient algorithm for unconstrained nonsmooth, nonconvex optimization, Math Methods Oper Res, 67, 2, 187-206 (2008) · Zbl 1155.90014
[29] Burke, J.; Lewis, A.; Overton, M., A robust gradient sampling algorithm for nonsmooth, nonconvex optimization, SIAM J Optim, 15, 3, 751-779 (2005) · Zbl 1078.65048
[30] Aubin, Jp; Frankowska, H., Set-valued analysis (1990), Boston: Birkhäuser, Boston · Zbl 0713.49021
[31] Rockafellar, Rt, Convex analysis (1970), Princeton: Princeton University Press, Princeton · Zbl 0193.18401
[32] Clarke, Fh, Optimization and nonsmooth analysis (1983), New York: Wiley, New York · Zbl 0582.49001
[33] Mordukhovich, B.; Shao, Y., On nonconvex subdifferentials calculus in Banach spaces, J Convex Anal, 2, 1, 211-227 (1995) · Zbl 0838.49013
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.