Branch-and-bound decomposition approach for solving quasiconvex-concave programs
type: Item
instance of: scholarly article
title: Branch-and-bound decomposition approach for solving quasiconvex-concave programs
zbMATH Open document ID: 0827.90117
DOI: 10.1007/BF02191854
published in: Journal of Optimization Theory and Applications
publication date: 1995-12-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C26
Mathematics Subject Classification ID: 90C30
Mathematics Subject Classification ID: 90C32
zbMATH DE Number: 638720
zbMATH Keywords: global optimization
zbMATH Keywords: quasiconvex-concave programming
zbMATH Keywords: branch-and-bound
zbMATH Keywords: d.c. programming
zbMATH Keywords: indefinite quadratic programming
author: Reiner Horst
author: Le Dung Muu
author: Michael Nast
MaRDI profile type: Publication
cites work: Constrained global optimization: algorithms and applications
cites work: Q3997222
cites work: A new reformulation-linearization technique for bilinear programming problems
cites work: Global minimization of a difference of two convex functions
cites work: On solving a d.c. programming problem by a sequence of linear programs
cites work: Parametric simplex algorithms for solving a special class of nonconvex minimization problems
cites work: A parametric successive underestimation method for convex multiplicative programming problems
cites work: A global optimization approach for solving the convex multiplicative programming problem
cites work: An efficient solution method for rank two quasiconcave minimization problems
cites work: Algorithms for the vector maximization problem
cites work: Q3815146
cites work: Multiple-criteria decision making. Concepts, techniques, and extensions. With the assistance of Yoon-Ro Lee and Antonie Stam
cites work: Optimization over the efficient set
cites work: An all-linear programming relaxation algorithm for optimizing over the efficient set
cites work: A finite, nonadjacent extreme-point search algorithm for optimization over the efficient set
cites work: Optimization of pipe networks
cites work: Method for minimizing a convex-concave function over a convex set
cites work: Convergence and restart in branch-and-bound algorithms for global optimization. Application to concave minimization and d.c. optimization problems
cites work: Deterministic global optimization with partition sets whose feasibility is not known: Application to concave minimization, reserve convex constraints, DC-programming and Lipschitzian optimization
cites work: Convex Analysis
cites work: On finding new vertices and redundant constraints in cutting plane algorithms for global optimization
cites work: On-line and off-line vertex enumeration by adjacency lists
description: scientific article; zbMATH DE number 638720