Nonconvex Optimization Problems

Common methods for identifying global optimal points and values of nonconvex optimization problems are based on branch-and-bound ideas. This chapter presents the \(\alpha \) BB method as an exemplary branch-and-bound procedure. One way to efficiently calculate the lower bounds required there is based on the convex relaxation of nonconvex sets and functions, for which the \(\alpha \) BB method uses techniques of interval arithmetic. The chapter discusses the branch-and-bound techniques in a first step only for the simplest case of problems with box-shaped feasible sets, before considering the necessary modifications for the case of convex feasible sets and finally for general nonconvex problems. The chapter concludes with a discussion of some possibilities to exploit the Lipschitz continuity of the defining functions in addition to or alternatively to their convexity in branch-and-bound procedures.