Optimization on Low Rank Nonconvex Structures

As optimization methods become widely used in engineering, economics and other sciences, an increasing number of problems are encountered that cannot be solved successfully by standard techniques of linear and nonlinear programming. These are nonconvex global optimization problems whose distinguishing feature is multiextremality, i.e. the presence of many local optima which fail to be global. In this Chapter we shall introduce various models of global optimization arising from applications and show the common general mathematical structure underlying all these problems, despite their great diversity. This general mathematical structure gives insight into the nature of global optimization and provides the foundation for a unified approach which consists in reducing every nonconvex global optimization problem to a canonical form, namely: minimizing (or maximizing) a linear function over a difference of two convex sets. While many general purpose algorithms of global optimization are available (cf. Horst and Tuy (1993), most of them are able to solve practically only problem instances of very limited size, as would be expected from the NP-hardness of these problems. On the other hand, the physical context of the model usually imposes additional structures on the problem, making it much more tractable. Therefore, for the applications it is important to study problems with special structures, yet of relevant practical interest. Most of these problems can be decomposed into subproblems whose nonconvex component is located in a space of low dimension and hence can be efficiently solved by specialized algorithms.

Convex sets and convex functions play a fundamental role in optimization. However, many important properties of convex functions are actually shared by a larger class of functions, called quasi-convex functions.

A striking fact about nonconvex global optimization which was shown in Chapter 1 is that, with all their diversity, virtually every nonconvex optimization problem can be described in terms of d.c. functions (differences of convex functions) and/or d.c. sets (differences of convex sets). This pervasiveness of the d.c. structure makes it a very convenient framework for a unified approach to an extremely broad class of problems at first sight very different from each other. For the design of efficient solution methods for these problems, it is, therefore, necessary to understand the d.c. structure.

One of the most fertile ideas in optimization is the concept of duality. Using the dual correspondence between points and hyperplanes in the characterization of convex sets, one can associate to a mathematical program a new program, called its dual. The attractiveness of this approach is that quite often the solution of a given problem can be obtained by solving the dual which may be more transparent or simpler than the original (primal) problem.

A common approach to many structured problems is partitioning in which the set of variables is split into two groups in such a way that the problem becomes remarkably easier when the values of the variables in the first group (which are called complicating variables) are temporarily fixed. Fundamental partitioning methods for mixed integer linear programming problems were developed in the 60’s (Benders (1962), Rosen (1964), Ritter (1967)) and ever since extended to nonlinear programming with many applications (Balas (1970), Geoffrion (1970), (1972)), Fleischmann (1973), Tind and Wolsey (1981), Burkard et al. (1985), Tuy (1987).

Nonconvex global optimization is based on global search methods which are quite different from local search procedures commonly used in classical mathematical programming. Although specific problems can be efficiently handled only by methods which take advantage of their particular structure, there are some general principles guiding global search processes. Furthermore, a general approach to low rank nonconvex problems is to transform a given problem of this class into a sequence of subproblems of low dimension, whose data are adaptively generated from those of the original problem. These subproblems of low dimension are often solved by a specialized version of some general purpose method.

This chapter is devoted to a class of global optimization problems which can be solved by variants of parametric simplex algorithms or by other parametrization techniques.

Multiplicative programming problems are minimization problems containing a product of several convex functions either in its objective function or in its constraints.

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)).

In the preceding chapter (section 9.7) we showed how general d.c. algorithms can be specialized to produce decomposition methods for convex programs with an additional monotonic reverse convex constraint. In this chapter we extend two classical decomposition methods for convex programming to reverse convex programming. The first method is the price-directive approach represented by Dantzig-Wolfe’s column generation method and the second is the resource-directive approach represented by Benders’ partitioning method. Both methods are important not only for computational purpose but also for the conceptual analysis of hierarchical planning. In fact, they can be interpreted as coordination mechanisms for the decentralization of large-scale organizations (see, e.g., Dantzig (1963), Lasdon (1970), Dirickx and Jennergren (1979). In the price-directive decomposition the center issues prices for the utilization of joint resources and the subsystems suggest the sizes of their activities based on these prices. In the resource-directive decomposition the center specifies the distribution of common production factors and this distribution is determined iteratively on the basis of price-information from the subsystems.

Dynamic Programming (DP) is a useful approach to multi-stage decision problems. On the basis of Bellman’s optimality principle such a problem can be decomposed into subproblems through recursive formulae. Bellman (1957), 1957a and Dantzig (1957) introduced a DP method for integer-variable linear programs. This method yields pseudo-polynomial algorithms when the number of constraints is fixed (Papadimitriou (1981)). In the class of linear programs, problems with a staircase structure can be efficiently treated by DP methods which can be interpreted as iterative predictor-corrector processes using a pricing mechanism for subproblems at individual stages (e.g., Dantzig (1963), Ho and Manne (1974), Ho (1978), Ho and Loute (1980), Abrahamson (1981) . Various applications of DP have also been developed in production planning (Manne (1958) , Wagner and Whitin (1959), Clark and Scarf (1960), Veinott (1965), 1969), Bessler and Veinott (1966), Zangwill (1965), 1966) (1969), Konno (1973), (1988), Bitran and Yanasse (1982), Bitran et al. (1984),... In particular, polynomial algorithms have been obtained for concave cost lotsizing problems and their extensions (e.g., Wagner and Whitin (1959), Zangwill (1965), (1966), (1959), Dreyfus and Law (1977).

Low rank nonconvex problems occur in many practical applications. In this chapter we discuss problems of continuous location which are highly nonconvex by their geometric nature, however can often be efficiently solved due to the low dimensionality of the underlying space.

This last chapter is devoted to two problems of practical interest which have been the subject of extensive research in recent years. These problems are closely related to each other and can be reformulated as convex programs with an additional reverse convex constraint. Due to the special structure of the latter constraint, both problems can be efficiently handled by low rank nonconvex optimization technique.