Global minimization of a difference of two convex functions. (English) Zbl 0619.90061

Tuy, Hoang

Math. Program. Study 30, 150-182 (1987).

The paper presents a method for global minimization of a difference of two convex functions over a convex polyhedral subset of \(R^ n\). Considering such problems is motivated by the fact that the set of all continuous real-valued functions over a fixed compact and convex subset K of \(R^ n\) that can be expressed as the difference of two convex functions over K, is dense in the space of the continuous functions C(K). It is first shown that the original problem can be reduced to a concave minimum problem with implicitely defined constraints. Then the method is described and its convergence is proved. The main idea is to decompose the problem into several standard minimum problems. Some extensions and applications to concrete problems as well as a simple numerical example are discussed.

Reviewer: A.L.Dontchev

MSC:

90C30	Nonlinear programming
49M37	Numerical methods based on nonlinear programming
65K05	Numerical mathematical programming methods

Keywords:

outer approximations; generalized Benders’ decomposition; concave minimization; indefinite quadratic programming; convex polyhedral domain; difference of two convex functions