Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1198.90318
Hager, William W.; Phan, Dzung T.
An ellipsoidal branch and bound algorithm for global optimization. (English)
[J] SIAM J. Optim. 20, No. 2, 740-758 (2009). ISSN 1052-6234; ISSN 1095-7189/e

A branch and bound algorithm is developed for the global optimization problem of minimizing a weakly convex function $f$ over a compact set $\Omega$ from $\Bbb R^{n}$. Starting with a known ellipsoid $E$ containing $\Omega$, the algorithm uses successive ellipsoidal bisections of $E$ as proposed by {\it L. T. H. An} [Math. Progr. 87, 401--426 (2000; Zbl 0952.90031)]. To obtain a lower bound for $f(x)$ over an ellipsoid, $f$ is written as the sum of a convex and a concave function and the concave term is underestimated by an affine function. Convergence of the general algorithm is verified. Furthermore, for the special case that both $f$ and $\Omega$ are convex, an algorithm is presented which generalizes the ball approximation algorithm by {\it A. Lin} and {\it S.P. Han} [SIAM J. Optim. 15, 129--138 (2005; Zbl 1077.90045)] in the sense that the norm objective in the original algorithm is replaced by an arbitrary convex function. The numerical performance of this new ball approximation algorithm is compared with that of SEDUMI 1.1 (see http://sedumi.ie.lehigh.edu/) and that of two gradient projection algorithms where the algorithms are applied to a number of quadratically constrained quadratic optimization problems. Moreover, the branch and bound algorithm is compared with a scheme given in the above mentioned paper by {\it L. T. H. An} [loc. cit.].
[Rembert Reemtsen (Cottbus)]

MSC 2000:: *90C25 Convex programming
90C26 Nonconvex programming
90C30 Nonlinear programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords: global optimization; branch and bound; affine underestimation; convex relaxation; ball approximation; weakly convex

Citations: Zbl 0952.90031; Zbl 1077.90045

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]