Abstract
In this article we provide an algorithm, where to escape from a local maximum y of convex function f over D, we (locally) solve piecewise convex maximization max{min{f (x) − f (y), p y (x)} | x ∈ D} with an additional convex function p y (·). The last problem can be seen as a strictly convex improvement of the standard cutting plane technique for convex maximization. We report some computational results, that show the algorithm efficiency.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Altannar Ch., Barsbold B., Enkhbat R.: A global method for solving the convex quadratic maximization problem. Mong. Math. J. 7, 19–27 (2003)
Audet C., Hansen P., Messine F.: Extremal problems for convex polygons. J. Global Optim. 38(2), 163–179 (2007)
Benson, H.P.: Concave minimization: theory, applications and algorithms. In: Handbook of Global Optimization. Kluwer Academic, Dordrecht/Boston/London (1995)
Bulatov, V.P., Kasinskaya, L.I.: Some methods of minimization of a concave function on a convex polyhedron and their application. In: Methods of Optimization and their Applications, pp. 71–80. “Nauka” Sibirsk. Otdel., Novosibirsk (1982)
Bulatov, V.P.: Metody pogruzheniya v zadachakh optimizatsii. Izdat. “Nauka” Sibirsk. Otdel., Novosibirsk (1977).
Chen P.-C., Hansen P., Jaumard B.: On-line and off-line vertex enumeration by adjacency lists. Oper. Res. Lett. 10(7), 403–409 (1991)
Chinchuluun A., Rentsen E., Pardalos P.M.: A note on the maximization of strongly convex functions. Int. J. Pure Appl. Math. 20(4), 529–538 (2005)
Chinchuluun, A., Rentsen, E., Pardalos, P.M.: A numerical method for concave programming problems. In: Continuous Optimization, vol. 99 of Appl. Optim., pp. 251–273. Springer, New York (2005)
Dür M., Horst R., Locatelli M.: Necessary and sufficient global optimality conditions for convex maximization revisited. J. Math. Anal. Appl. 217(2), 637–649 (1998)
Enkhbat R., Barsbold B., Kamada M.: A numerical approach for solving some convex maximization problems. J. Global Optim. 35(1), 85–101 (2006)
Enhbat R.: An algorithm for maximizing a convex function over a simple set. J. Global Optim. 8(4), 379–391 (1996)
Enkhbat, R.: Algorithm for global maximization of convex functions over sets of special structures. Ph.D. thesis, Irkutsk State University (1991)
Floudas C.A., Pardalos P.M.: A Collection of Test Problems for Constrained Global Optimization Algorithms, vol. 455 of Lecture Notes in Computer Science. Springer, Berlin (1990)
Floudas C.A., Pardalos P.M., Adjiman C.S., Esposito W.R., Gümüş Z.H., Harding S.T., Klepeis J.L., Meyer C.A., Schweiger C.A.: Handbook of Test Problems in Local and Global Optimization, vol. 33 of Nonconvex Optimization and its Applications. Kluwer Academic, Dordrecht (1999)
Fortin D., Tsevendorj I.: Piecewise-convex maximization problems: algorithm and computational experiments. J. Global Optim. 24(1), 61–77 (2002)
Fortin D., Tseveendorj I.: Piecewise-convex maximization approach to multiknapsack. Optimization 58(7), 883–895 (2009)
Horst R., Pardalos P.M., Thoai N.V.: Introduction to Global Optimization, vol. 3 of Nonconvex Optimization and its Applications. Kluwer Academic, Dordrecht (1995)
Horst R., Hoang T.: Global Optimization, 2nd edn. Springer, Berlin (1993) Deterministic approaches
Hiriart-Urruty, J.-B.: Conditions for Global Optimality. In: Handbook of Global Optimization, vol. 2 of Nonconvex Optim. Appl., pp. 1–26. Kluwer Academic, Dordrecht (1995)
Hiriart-Urruty J.-B., Ledyaev Y.S.: A note on the characterization of the global maxima of a (tangentially) convex function over a convex set. J. Convex Anal. 3(1), 55–61 (1996)
Strekalovsky A.S.: Global optimality conditions for nonconvex optimization. J. Global Optim. 12(4), 415–434 (1998)
Strekalovskii A.S.: Elements of Nonconvex Optimization (in russian). NAUKA, Novosibirsk (2003)
Tsevendorj I.: On the conditions for global optimality. J. Mong. Math. Soc. 2, 58–61 (1998)
Tsevendorj I.: Piecewise-convex maximization problems: global optimality conditions. J. Global Optim. 21(1), 1–14 (2001)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fortin, D., Tseveendorj, I. Piece adding technique for convex maximization problems. J Glob Optim 48, 583–593 (2010). https://doi.org/10.1007/s10898-009-9506-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-009-9506-z
Keywords
- Global search algorithm
- Local search algorithm
- Nonconvex optimization
- Convex maximization
- Piecewise convex maximization