Monotonic Problems

The parametric method developed in Chapters 7 and 8 offers a remarkably efficient tool to handle a class of large scale global optimization problems of practical interest. A natural question arises as to whether this method is strictly specific to the multiplicative structure, or it can be extended to a wider class of problems. In fact, a variety of quite different problems which have anything to do with the multiplicative structure appear to be solvable by the same method, in just the same manner. Examples include quadratic programming problems with just one negative eigenvalue (Tuy and Tam (1992) ), certain variants of minimum concave-cost network flow problems for which even strongly polynomial algorithms have been obtained via the parametric approach (Tuy, Dan and Ghannadan (1992), Klinz and Tuy (1993)), and also large scale d.c. optimization problems with relatively few nonconvex variables, which can be practically reduced to global optimization problems in low dimension (see e.g. Tuy (1991)).