Branch-and-bound decomposition approach for solving quasiconvex-concave programs
The quasiconvex-concave programming problems considered in this paper have the following form: \[ \min_{x,y}\quad f(x, y),\qquad \text{s.t.}\quad x\in X,\quad y\in Y, \qquad (x, y)\in C,\quad h_j(x, y)\leq 0,\quad j\in J, \] where \(X\subseteq \mathbb{R}^n\), \(Y\subseteq \mathbb{R}^m\), \(C\subseteq \mathbb{R}^n\times \mathbb{R}^m\) are given closed convex sets, and \(f\), \(h_j\), \(j\in J\), are quasiconvex-concave real- valued functions over \(X\times Y_0\). The set \(Y_0\subseteq \mathbb{R}^m\) is some convex set containing \(Y\), and \(J\) is a finite index set. The authors propose a class of branch-and-bound methods. The bounding operation is based upon a combination of relaxation with the fact that the minimum of a quasiconcave function over a polytope is attained at a vertex and the branching operation is designed as two alternative bisections which use current values of objective functions and constraints. Several important special cases such as certain d.c. programming problems, indefinite quadratic programming with one negative eigenvalue, affine multiplicative problems, fractional multiplicative optimization can be solved quite effectively by this approach.
scientific article; zbMATH DE number 638720