UABDivulga - Barcelona recerca i innovació

Mathematical Programming problems consist in computing maxima and minima of functions of one or several variables subject to constraints. Thus the general formulation of a mathematical program is

the existence of an optimal solution is guaranteed if S is compact and F is continuous on S: Mathematical Programming aims at finding, among the elements of S (which are called feasible solutions) those at which the objective function F attains the smallest value. Such solutions, if they exist, are called optimal solutions. One also considers the notion of so called local optimal solutions, in which one only compares the value the objective function takes at the local optimum with those it takes at neighboring feasible points. If the comparison is made with all feasible points, regardless the distance to the given point, then such a point is said to be a global optimum.

Clearly, every global optimum is a local optimum.
It is well known that if a problem is convex, i.e., if F is a convex function and S is a convex set, every local optimum is a global optimum, too. On the contrary, when these convexity assumptions do not hold, there may be local optima which fail to be global. Global optimization deals with the characterization and computation of global optima of nonconvex problems. Suppose that, using standard techniques in nonlinear programming, one obtains a stationary point of the program. At such stage the algorithm should stop, since no local procedure can tell us whether the obtained point is a global optimum or not or how to improve it in the latter case. Global optimization procedures must be able to improve any feasible solution, in case it is not a global optimum, or to make it evident that it is a global optimum if this is the case. Thus global optimization methods are substantially
di¤erent from local methods and use combinatorial tools like cutting-plane, branch and bound and branch and cut. All such techniques are expensive in terms of computational time.

When applying global optimization techniques for solving a nonconvex mathematical programming problem, one always tries to find some hidden convexity features of the problem. For instance, sometimes the objective function can be represented as a difference of convex functions, F(x) = f(x) - g(x), with f and g being convex; such a function F is called DC. In this case, if the feasible set S is convex, by introducing a new variable t one can transform the mathematical program

in an equivalent convex program with an additional "reverse convex" constraint (that is, an inequality defined by means of a convex function but with the inequality being in the opposite order it should have for the solution set to be convex):

"Equivalent", in this case, means that from every global minimum of (2) one can easily find a global minimum of (3) and viceversa. There are some e¢ cient global optimization algorithms for solving such convex programs with an additional reverse convex constraint. However, every DC function admits infinitely many representations as a di¤erence of convex functions; indeed, one can consider F(x) = f(x) + f(x) - (g(x) + f(x)); with f being an arbitrary convex function. Then the following questions arise:

1) Given a DC representation of the objective function of a mathematical programming problem, is it possible to find a better representation so as to improve the e¢ ciency of the algorithm we are going to use to solve the problem?

2) Among the DC representations of a given function, is there an optimal one?

In our paper we propose some necessary concepts to address the above questions in the case of polynomials of several variables and give a procedure for computing the best (in a certain sense) DC representation of an arbitrary polynomial function. We also describe some numerical experiments, which show the importance of an optimal DC representation from the point of view of computational effciency. One of the examples we examine in detail is a mathematical programming formulation of a hydroelectric generation problem.