×

Interior quasi-subgradient method with non-Euclidean distances for constrained quasi-convex optimization problems in Hilbert spaces. (English) Zbl 1493.90140

Summary: An interior quasi-subgradient method is proposed based on the proximal distance to solve constrained nondifferentiable quasi-convex optimization problems in Hilbert spaces. It is shown that a newly introduced generalized Gâteaux subdifferential is a subset of a quasi-subdifferential. The convergence properties, including the global convergence and iteration complexity, are investigated under the assumption of the Hölder condition of order \(p\), when using the constant/diminishing/dynamic stepsize rules. Convergence rate results are obtained by assuming a Hölder-type weak sharp minimum condition relative to an induced proximal distance.

MSC:

90C26 Nonconvex programming, global optimization
90C48 Programming in abstract spaces
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alber, YI; Iusem, AN; Solodov, MV, On the projected subgradient method for nonsmooth convex optimization in a Hilbert space, Math. Program., 81, 23-35 (1998) · Zbl 0919.90122
[2] Agrawal, A.; Boyd, S., Disciplined quasiconvex programming, Optim. Lett., 14, 1643-1657 (2020) · Zbl 1459.90148
[3] Auslender, A.; Teboulle, M., Interior gradient and \(\epsilon \)-subgradient descent methods for constrained convex minimization, Math. Oper. Res., 29, 1, 1-26 (2004) · Zbl 1082.90087
[4] Auslender, A.; Teboulle, M., Interior projection-like methods for monotone variational inequalities, Math. Program., 104, 39-68 (2005) · Zbl 1159.90517
[5] Auslender, A.; Teboulle, M., Interior gradient and proximal methods for convex and conic optimization, SIAM J. Optim., 16, 3, 697-725 (2006) · Zbl 1113.90118
[6] Auslender, A.; Teboulle, M., Projected subgradient methods with non-Euclidean distances for non-differentiable convex minimization and variational inequalities, Math. Program., 120, 27-48 (2009) · Zbl 1190.90118
[7] Auslender, A.; Teboulle, M.; Ben-Tiba, S., Interior proximal and multiplier methods based on second order homogeneous kernels, Math. Oper. Res., 24, 3, 645-668 (1999) · Zbl 1039.90518
[8] Auslender, A.; Teboulle, M.; Ben-Tiba, S., A logarithmic-quadratic proximal method for variational inequalities, Comput. Optim. Appl., 12, 31-40 (1999) · Zbl 1039.90529
[9] Aussel, D.; Hadjisavvas, N., Adjusted sublevel sets, normal operator, and quasi-convex programming, SIAM J. Optim., 16, 2, 358-367 (2005) · Zbl 1098.49015
[10] Aussel, D.; Pištěk, M., Limiting normal operator in quasiconvex analysis, Set-Valued Var. Anal., 23, 4, 669-685 (2015) · Zbl 1330.49011
[11] Avriel, M.; Diewert, WE; Schaible, S.; Zang, I., Gener. Concavity (1988), New York: Plenum Press, New York · Zbl 0679.90029
[12] Barty, K.; Roy, J-S; Strugarek, C., Hilbert-valued perturbed subgradient algorithms, Math. Oper. Res., 32, 3, 551-562 (2007) · Zbl 1341.90093
[13] Bauschke, HH; Bolte, J.; Teboulle, M., A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications, Math. Oper. Res., 42, 2, 330-348 (2017) · Zbl 1364.90251
[14] Bauschke, HH; Combettes, PL, Convex analysis monotone operator theory in hilbert spaces (2011), New York: Springer, New York · Zbl 1218.47001
[15] Beck, A.; Teboulle, M., Mirror descent and nonlinear projected subgradient methods for convex optimization, Oper. Res. Lett., 31, 3, 167-175 (2003) · Zbl 1046.90057
[16] Ben-tal, A.; Margalit, T.; Nemirovski, A., The ordered subsets mirror descent optimization method with applications to tomography, SIAM J. Optim., 12, 79-108 (2001) · Zbl 0992.92034
[17] Bertsekas, DP, Convex optimization ang algorithms (2015), Massachusetts: Athena Scientific, Massachusetts · Zbl 1347.90001
[18] Bolte, J.; Nguyen, TP; Peypouquet, J.; Suter, BW, From error bounds to the complexity of first-order descent methods for convex functions, Math. Program., 165, 2, 471-507 (2017) · Zbl 1373.90076
[19] Bregman, LM, The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Comput. Math. Math. Phys., 7, 3, 200-217 (1967) · Zbl 0186.23807
[20] Brito, AS; da Cruz Neto, JX; Lopes, JO; Oliveira, PR, Interior proximal algorithm for quasiconvex programming problems and variational inequalities with linear constraints, J. Optim. Theory Appl., 154, 1, 217-234 (2012) · Zbl 1273.90238
[21] Burachik, R. S.: Generalized Proximal Point Method for the Variational Inequality Problem. PhD Thesis, (1995)
[22] Burachik, RS; Dutta, J., Inexact proximal point methods for variational inequality problems, SIAM J. Optim., 20, 5, 2653-2678 (2010) · Zbl 1255.65108
[23] Burachik, RS; Iusem, AN, A generalized proximal point algorithm for the variational inequality problem in a Hilbert space, SIAM J. Optim., 8, 1, 197-216 (1998) · Zbl 0911.90273
[24] Burachik, RS; Scheimberg, S., A proximal point method for the variational inequality problem in Banach spaces, SIAM J. Control Optim., 39, 5, 1633-1649 (2001) · Zbl 0988.90045
[25] Censor, Y.; Segal, A., Algorithms for the quasiconvex feasibility problem, J. Comput. Appl. Math., 185, 1, 34-50 (2006) · Zbl 1080.65047
[26] Chen, G.; Teboulle, M., Convergence analysis of a proximal-like minimization algorithm using bregman functions, SIAM J. Optim., 3, 3, 538-543 (1993) · Zbl 0808.90103
[27] Crouzeix, J-P; Martinez-Legaz, J-E; Volle, M., Generalized convexity. Generalized monotonicity (1998), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 0897.00032
[28] Cunha, FGM; da Cruz Neto, JX; Oliveira, PR, A proximal point algorithm with a \(\phi \)-divergence for quasiconvex programming, Optimization, 59, 5-6, 777-792 (2010) · Zbl 1194.90098
[29] Ermoliev, YM, Methods of solution of nonlinear extremal problems, Cybern. Syst. Anal., 2, 1-14 (1966)
[30] Greenberg, HJ; Pierskalla, WP, Quasiconjugate functions and surrogate duality, Cahiers Centre Études Rech. Opertionnelle, 15, 437-448 (1973) · Zbl 0276.90051
[31] Hadjisavvas, N.; Komlósi, S.; Schaible, S., Handbook of generalized convexity and generalized monotonicity (2005), New York: Springer-Verlag, New York · Zbl 1070.26002
[32] Hu, Y.; Li, C.; Yang, X., On convergence rates of linearized proximal algorithms for convex composite optimization with applications, SIAM J. Optim., 26, 2, 1207-1235 (2016) · Zbl 1338.65159
[33] Hu, Y.; Li, J.; Yu, CKW, Convergence rates of subgradient methods for quasi-convex optimization problems, Comput. Optim. Appl., 77, 1, 183-212 (2020) · Zbl 1447.90039
[34] Hu, Y.; Yang, X.; Sim, C-K, Inexact subgradient methods for quasi-convex optimization problems, Eur. J. Oper. Res., 240, 2, 315-327 (2015) · Zbl 1357.90116
[35] Hu, Y.; Yu, CKW; Yang, X., Incremental quasi-subgradient methods for minimizing the sum of quasi-convex functions, J. Global Optim., 75, 4, 1003-1028 (2019) · Zbl 1432.90112
[36] Ke, Q.; Kanade, T., Quasiconvex optimization for robust geometric reconstruction, IEEE Trans. Pattern Anal. Mach. Intell., 29, 10, 1834-1847 (2007)
[37] Kiwiel, KC, Convergence and efficiency of subgradient methods for quasiconvex minimization, Math. Program., 90, 1-25 (2001) · Zbl 0986.90034
[38] Kiwiel, KC, Convergence of approximate and incremental subgradient methods for convex optimization, SIAM J. Optim., 14, 3, 807-840 (2004) · Zbl 1063.90039
[39] Konnov, IV, On properties of supporting and quasi-supporting vectors, J. Math. Sci., 71, 2760-2763 (1994) · Zbl 1264.90141
[40] Konnov, IV, On convergence properties of a subgradient method, Optim. Methods Softw., 18, 1, 53-62 (2003) · Zbl 1062.90048
[41] López, J.; Papa Quiroz, EA, Construction of proximal distances over symmetric cones, Optimization, 66, 8, 1301-1321 (2017) · Zbl 1407.90309
[42] Nedić, A.; Bertsekas, DP, Incremental subgradient methods for nondifferentiable optimization, SIAM J. Optim., 12, 1, 109-138 (2001) · Zbl 0991.90099
[43] Nemirovsky, AS; Yudin, DB, Problem complexity and method efficiency in optimization (1983), New York: Wiley, New York · Zbl 0501.90062
[44] Pan, S.; Chen, J-S, Entropy-like proximal algorithms based on a second-order homogeneous distance function for quasi-convex programming, J. Global Optim., 39, 555-575 (2007) · Zbl 1190.90144
[45] Papa Quiroz, E.A., López, J., Borda, D., Collantes, F.: A proximal method for multiobjective quasiconvex minimization on the nonnegative orthant and its application to demand theory in microeconomy. Presented at the (2020)
[46] Papa Quiroz, E. A., López Luis, J., and Cano Lengua, M. A.: A proximal multiplier method for convex separable symmetric cone optimization. In Proceeding of 5th International Conference on Multimedia Systems and Signal Processing, ACM International Conference Proceeding Series, 92-97, 2020
[47] Papa Quiroz, EA; Oliveira, PR, An extension of proximal methods for quasiconvex minimization on the nonnegative orthant, Eur. J. Oper. Res., 216, 1, 26-32 (2012) · Zbl 1242.90166
[48] Papa Quiroz, EA; Ramirez, LM; Oliveira, PR, An inexact algorithm with proximal distances for variational inequalities, RAIRO Oper. Res., 52, 1, 159-176 (2018) · Zbl 1397.65099
[49] Papa Quiroz, EA; Ramirez, LM; Oliveira, PR, An inexact proximal method for quasiconvex minimization, Eur. J. Oper. Res., 246, 3, 721-729 (2015) · Zbl 1346.90689
[50] Papa Quiroz, EA; Sarmiento, O.; Oliveira, PR, An inexact proximal decomposition method for variational inequalities with separable structure, RAIRO Oper. Res., 55, S873-S884 (2021) · Zbl 1472.90142
[51] Penot, J.-P.: Are generalized derivatives useful for generalized convex functions? In M. V. J.-P. Crouzeix, J.E. Martinez-Legaz, editor, Generalized Convexity, Generalized Monotonicity: Recent Results, pages 3-59. Kluwer Academic Publishers, (1998) · Zbl 0957.49013
[52] Polyak, BT, A general method for solving extremum problems, Soviet Math. Doklady, 8, 593-597 (1967) · Zbl 0177.15102
[53] Polyak, BT, Introduction to optimization (1987), New York: Optimization Software, New York · Zbl 0708.90083
[54] Rabier, PJ, Differentiability of quasiconvex functions on separable Banach spaces, Israel J. Math., 207, 11-51 (2015) · Zbl 1331.46032
[55] Sarmiento, O.; Papa Quiroz, EA; Oliveira, PR, A proximal multiplier method for separable convex minimization, Optimization, 65, 2, 501-537 (2016) · Zbl 1338.52012
[56] Sarmiento, O.; Papa Quiroz, EA; Oliveira, PR, Convergence rate of a proximal multiplier algorithm for separable convex minimization, Optimization, 66, 2, 251-270 (2017) · Zbl 1366.90165
[57] Shor, NZ, Minimization methods for non-differentiable functions (1985), New York: Springer-Verlag, New York · Zbl 0561.90058
[58] Solodov, MV; Zavriev, SK, Error stability properties of generalized gradient-type algorithms, J. Optim. Theory Appl., 98, 663-680 (1998) · Zbl 0913.90245
[59] Souza, S., d. S., Oliveira, P. R., da Cruz Neto, J. X., and Soubeyran, A.: A proximal method with separable Bregman distances for quasiconvex minimization over the nonnegative orthant. Eur. J. Oper. Res. 201(2), 365-376 (2010) · Zbl 1217.90158
[60] Stancu-Minasian, IM, Fractional programming (1997), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 0899.90155
[61] Teboulle, M., Convergence of proximal-like algorithms, SIAM J. Optim., 7, 4, 1069-1083 (1997) · Zbl 0890.90151
[62] Yu, CKW; Hu, Y.; Yang, X.; Choy, SK, Abstract convergence theorem for quasi-convex optimization problems with applications, Optimization, 68, 7, 1289-1304 (2019) · Zbl 1422.90057
[63] Zhou, Z.; So, AM-C, A unified approach to error bounds for structured convex optimization problems, Math. Program., 165, 2, 689-728 (2017) · Zbl 1380.65109
[64] Zălinescu, C., Convex analysis in general vector spaces (2002), Singapore: World Scientific, Singapore · Zbl 1023.46003
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.