Quasiconvex functions: how to separate, if you must!
DOI:
https://doi.org/10.24193/subbmath.2022.1.08Keywords:
Quasiconvex minimization, separation, quasidifferentiability.Abstract
Since quasiconvex functions have convex lower level sets it is possible to minimize them by means of separating hyperplanes. An example of such a procedure, well-known for convex functions, is the subgradient method. However, to find the normal vector of a separating hyperplane is in general not easy for the quasiconvex case. This paper attempts to gain some insight into the computational aspects of determining such a normal vector and the geometry of lower level sets of quasiconvex functions. In order to do so, the directional differentiability of quasiconvex functions is thoroughly studied. As a consequence of that study, it is shown that an important subset of quasiconvex functions belongs to the class of quasidifferentiable functions. The main emphasis is, however, on computing actual separators. Some important examples are worked out for illustration.
Mathematics Subject Classification (2010): 54AXX.
Received 13 December 2021; Accepted 07 February 2022.
References
Clarke, F.H., Optimization and Nonsmooth Analysis, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1983.
Crouzeix, J.-P., Some differentiability properties of quasiconvex functions on Rn, In: Optimization and Optimal Control (Proc. Conf., Math. Res. Inst., Oberwolfach, 1980), vol. 30 of Lecture Notes in Control and Information Sci., Springer, Berlin - New York, 1981, pp. 9-20.
Crouzeix, J.-P., About differentiability of order one of quasiconvex functions on Rn, J. Optim. Theory Appl., 36(1982), no. 3, 367-385.
Crouzeix, J.-P., A review of continuity and differentiability properties of quasiconvex functions on Rn, In: Convex Analysis and Optimization (London, 1980), vol. 57 of Res. Notes in Math., Pitman, Boston, Mass.-London, 1982, pp. 18-34.
Dem’yanov, V.F., Dixon, L.C.W., Quasidifferential Calculus, vol. 29, North-Holland Sole Distributor for the U.S.A., Elsevier Science Publishers, Amsterdam - New York, N.Y., USA, 1986.
Frenk, J.B.G., Dias, D.M.L., Gromicho, J.A.S., Duality theory for convex/quasiconvex functions and its application to optimization, In: S´andor Koml´osi, Tama´s Rapcsa´k, and Siegfried Schaible (eds.), Generalized Convexity, Springer, Berlin - Heidelberg, 1994, pp. 153-170.
Frenk, J.B.G., Gromicho, J.A.S., Plastria, F., Zhang, S., A deep cut ellipsoid algorithm and quasiconvex programming, In: Generalized Convexity (P´ecs, 1992), vol. 405 of Lecture Notes in Econom. and Math. Systems, Springer, Berlin, 1994, pp. 62-76.
Frenk, J.B.G., Gromicho, J.A.S., Zhang, S., A deep cut ellipsoid algorithm for convex programming: Theory and applications, Mathematical Programming, 63(1994), no. 1, 83-108.
Frenk, J.B.G., Gromicho, J.A.S., Zhang, S., General models in minmax planar location: Checking optimality conditions, Journal of Optimization Theory and Applications, 89(1996), no. 1, 65-87.
Frenk, J.B.G., Kassay, G., Introduction to convex and quasiconvex analysis, In: Nicolas Hadjisavvas, Sandor Komlosi, and Siegfried Schaible (eds.), Handbook of Generalized Convexity and Generalized Monotonicity, Springer, New York, 2005, pp. 3-87.
Gromicho, J.A.S., Quasiconvex Optimization and Location Theory, Applied Optimization, Springer, Boston, MA, 1998.
Hiriart-Urruty, J.P., Lemarechal, C., Convex Analysis and Minimization Algorithms I, Springer, Berlin - Heidelberg, 1993.
Hiriart-Urruty, J.P., Lemarechal, C., Convex Analysis and Minimization Algorithms II, Springer, Berlin - Heidelberg, 1993.
Luenberger, D.G., Ye, Y., Linear and Nonlinear Programming, Springer International Publishing, 2016.
Passy, U., Prisman, E.Z., Conjugacy in quasi-convex programming, Mathematical Programming, 30(1984), no. 2, 121-146.
Penot, J.P., Volle, M., On quasi-convex duality, Mathematics of Operations Research, 15(1990), no. 4, 597-625.
Plastria, F., Lower subdifferentiable functions and their minimization by cutting planes, Journal of Optimization Theory and Applications, 46(1985), no. 1, 37-53.
Polyak, B., A general method for solving extremum problems, Soviet Mathematics, Dok lady, 8(1967).
Ponstein, J., Seven kinds of convexity, SIAM Review, 9(1967), 115-119.
Pshenichnyi, B.N., Necessary Conditions for an Extremum, CRC Press, 2020.
Rockafellar, R.T., Convex Analysis: (PMS-28), Princeton Mathematical Series, Princeton University Press, 1997.
Shor, N.Z., Minimization Methods for Non-Differentiable Functions, Springer, Berlin - Heidelberg, 1985.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Studia Universitatis Babeș-Bolyai Mathematica
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
