 |
||||||
| Takahito Kuno and Hidetoshi Nagai | ||||||
| Key words: | ||||||
| global optimization, concave minimization, low-rank nonconvexity, branch-and-bound algorithm, Lagrangian relaxation | ||||||
| Mathematices Subject Classification: 90-08, 90C26, 90C30, 90C57 | ||||||
|
||||||
| Takahito Kuno and Hidetoshi Nagai | ||||||
| Key words: | ||||||
| global optimization, concave minimization, low-rank nonconvexity, branch-and-bound algorithm, Lagrangian relaxation | ||||||
| Mathematices Subject Classification: 90-08, 90C26, 90C30, 90C57 | ||||||
|
||||||||||||||||||||||||||||||||||||||||
| Abstract: | |||
| In this paper, we develop a simplicial branch-and-bound algorithm with two-phase bounding operation for solving a class of concave minimization problems to which many of problems with low rank nonconvexity reduce. In the first phase of the bounding operation, we enlarge the feasible set of each linear programming relaxed problem to facilitate application of some procedures for improving the efficiency. In the second phase, we tighten the lower bound deteriorated by this enlargement, using a Lagrangian relaxation. Computational results indicate that the proposed algorithm is promising, compared with a standard simplicial branch-and-bound algorithm. | |||
| A simplicial algorithm with two-phase bounding operation for a class of concave minimization problems | |
| Special Issue in Honor of the 65th Birthday of Hiroshi Konno | |||
| Volume 1, Number 2, May 2005, pp. 277-296 | |||