Method for minimizing a convex-concave function over a convex set. (English) Zbl 0743.90101

Muu, L. D.; Oettli, W.

J. Optimization Theory Appl. 70, No. 2, 377-384 (1991).

A branch-and-bound algorithm is proposed for minimizing a convex-concave function over a convex set. For a special case, the minimization of a function which is representable as the difference of two convex functions, the subproblems related to the bounding operation can be solved effectively. A convergence result is given, and the algorithm is illustrated with a numerical example.

Reviewer: P.Pan (Nanjing)

MSC:

90C30	Nonlinear programming
90-08	Computational methods for problems pertaining to operations research and mathematical programming
65K05	Numerical mathematical programming methods

Keywords:

global optimization; branch-and-bound; convex-concave function; difference of two convex functions; convergence

References:

[1]	Muu, L. D., andOettli, W.,An Algorithm for Indefinite Quadratic. Programming with Convex Constraints, Operations Research Letters, Vol. 10, 1991 (in press). · Zbl 0748.90049
[2]	Hiriart-Urruty, J.-B.,Generalized Differentiability, Duality, and Optimization for Problems Dealing with Differences of Convex Functions, Convexity and Duality in Optimization, Edited by J. Ponstein, Springer-Verlag, Berlin, Germany, pp. 37-69, 1986.
[3]	Tuy, H.,Global Minimization of a Difference of Two Convex Functions, Mathematical Programming Study, Vol. 30, pp. 150-182, 1987. · Zbl 0619.90061
[4]	Pardalos, P. M., andRosen, J. B.,Constrained Global Optimization: Algorithms and Applications, Springer-Verlag, Berlin, Germany, 1987. · Zbl 0638.90064
[5]	Rosen, J. B., andPardalos, P. M.,Global Minimization of Large-Scale Constrained Concave Quadratic Problems by Separable Programming, Mathematical Programming, Vol. 34, pp. 163-174, 1986. · Zbl 0597.90066
[6]	Benson, H. P.,On the Convergence of Two Branch-and-Bound Algorithms for Nonconvex Programming Problems, Journal of Optimization Theory and Applications, Vol. 36, pp. 129-134, 1982. · Zbl 0453.65046
[7]	Horst, R.,Deterministic Global Optimization with Partition Sets Whose Feasibility is Not Known: Application to Concave Minimization, Reverse Convex Constraints, DC-Programming, and Lipschitzian Optimization, Journal of Optimization Theory and Applications, Vol. 58, pp. 11-37, 1988. · Zbl 0621.90064
[8]	Horst, R., andTuy, H.,On the Convergence of Global Methods in Multiextremal Optimization, Journal of Optimization Theory and Applications, Vol. 54, pp. 253-271, 1987. · Zbl 0595.90079