Direct Global Optimization Algorithm
- PDF / 14,930,403 Bytes
- 165 Pages / 594 x 828 pts Page_size
- 33 Downloads / 228 Views
• If(x)l, max{O, f ( x ) ) , and inf{O, f ( x ) ) ;
gramming, D CP A function is called d.c. if it can be represented as the difference of two convex functions. Frequently, mathematical programming problems dealing with d.c. functions are called d.c. programming problems (d.c. programs). Theoretically, the set of d.c. functions defined on a compact convex set of R n is dense in the set of continuous functions on this set. Therefore, in principle, every continuous function can be approximated by a d.c. function with any desired precision. Of course, finding an explicit d.c. representation of a continuous function is in general a hard problem. However, it is pointed out in literature that the class of applicable d.c. programming problems is quite comprehensive. Applications of d.c. programming include indefinite quadratic programs, programming problems with constraints of complementarity type, design centering problems, location problems, packing problems, and optimization over efficient sets.
• the product
D . C . F u n c t i o n s . Let C be a convex subset of R n. A real-valued function f : C --+ R is called d.c. on C if there exist two convex functions g, h: C --+ R such that f can be expressed in the form f ( x ) = g ( x ) - h(x). If C = R n, then f is simply called a d.c. function. Each representation of the form g ( x ) - h(z) is said to be a d.c. decomposition of f. Let f, fi: R n --+ R (i = 1 , . . . , m ) be d.c. and let g: R --+ R be convex. Then the following functions are also d.c.:
•
~-~i~=1)~ifi(x),
• maxi=l,...,m
()~i E R, i = 1, .... , m);
fi(x) and mini=l,...,m fi(x);
• (g o f ) ( x )
I-[i~1fi(x);
and
= g(f(x)).
For each of the functions defined above, an explicit d.c. decomposition can be constructed [18], [12]. D.C. Programming P r o b l e m s . The general form of d.c. programming problems is given by inf{f0(x): x E X, fi(x) _< 0, i = 1 , . . . , m ) } ,
(1) where fi = g i - hi (i = 0 , . . . , m) are d.c. functions and X is a closed convex subset of R n. Every problem of the form (1) can be transformed into one of the following problems: inf{c(x): x e X, ¢(x) < 0},
(2)
inf{¢(z):x
(3)
e X, ~(x) < 0},
where the function c is linear or. convex, ¢ concave, and w convex. Often, (2) is called the canonical d.c. program, and (3) the concave programming problem. Optimality gram
C o n d i t i o n s . Consider the d.c. pro-
w* = i n f { g ( x ) - h(x): x e X } ,
(4)
where g, h are convex functions and X is a closed convex set. An optimality condition to (4) is formulated as follows. Assume that (4) is solvable. Then a point x* C X is an optimal solution to it if and only if there is a t* C R such that O-inf
- h ( x ) + t"
g(x) - t
Data Loading...
