Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

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

Highlights
Master Server

### Zentralblatt MATH Berlin [Germany]

© FIZ Karlsruhe GmbH

Zentralblatt MATH master server is maintained by the Editorial Office in Berlin, Section Mathematics and Computer Science of FIZ Karlsruhe and is updated daily.

Other Mirror Sites

Copyright © 2013 Zentralblatt MATH | European Mathematical Society | FIZ Karlsruhe | Heidelberg Academy of Sciences