Optimization of the Norm of a Vector-Valued DC Function and Applications

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS: Vol. 107, No. 2, pp. 245–260, NOVEMBER 2000 Optimization of the Norm of a Vector-Valued DC Function and Applications 1 R. B LANQUERO 2 AND E. C ARRIZOSA 3 Communicated by P. Pardalos Abstract. In this paper, we show that a DC representation can be obtained explicitly for the composition of a gauge with a DC mapping, so that the optimization of certain functions involving termsof this kind can be made by using standard DC optimization techniques. Applications to facility location theory and multiple-criteria decision making are presented. Key Words. Global optimization, difference of convex functions, location theory, multiple-criteria decision making. 1. Problem Formulation DC functions (functions ψ that can be written as the difference of two convex functions ψ + , ψ − ) constitute a wide class of functions that plays an important role within the field of global optimization (Refs. 1–3). Among other properties, the class of DC functions is closed under certain operations. For instance, Proposition 4 in Ref. 3 asserts that the composition of DC functions is also a DC function. Since the proof is based on the fact that any locally DC function on a convex set is also DC (Ref. 4), it is a nonconstructive proof; i.e., it does not provide a DC decomposition for ψ G γ ªf, even when DC decompositions for fand γ are known. From an optimization point of view, this is an important drawback, since most powerful DC optimization techniques, such as branch-and-bound methods (Ref. 1), need a DC representation of the function under study. For this reason, specific methods for obtaining DC decompositions have been proposed for particular functions γ ; see for example Propositions 3.5–3.7 in Ref. 5. 1 This research was partially supported by Grant PB96-1416-CO2-02, DGES, Madrid, Spain. 2 Professor, Facultad de Matema ´ticas, Universidad de Sevilla, Sevilla, Spain. 3 Professor, Facultad de Matema ´ticas, Universidad de Sevilla, Sevilla, Spain. 245 0022-3239兾00兾1100-0245$18.00兾02000 Plenum Publishing Corporation JOTA: VOL. 107, NO. 2, NOVEMBER 2000246 In this paper, we consider the particular case of compositions of DC functions in which the outer function γ is a gauge, that is, a convex function γ :⺢ m → ⺢,defined as γ (x)Ginf{tH0:x∈tB}, x∈⺢ m , (1) where Bis a convex set, the interior of which contains the origin (Refs. 6–7).By Theorem 14.5 in Ref. 7, every gauge γ can be written as γ (x)Gmax{〈u,x〉:u∈B 0 }, x∈⺢ m , (2) where 〈·,·〉denotes the usual scalar product and B 0 is the polar set of B, that is B 0 G{v:〈v,x〉⁄1,∀x∈B}. Using this property, the proof of Proposition 4 in Ref. 3 can be rewritten for this particular case, yielding a global DC decomposition for γ ªf,as shown below. Proposition 1.1. Let Ω⊂⺢ n be a convex set. Let γ :⺢ m → ⺢be a gauge in ⺢ m with unit ball B, let fG(f 1 ,...,f m ):Ω → ⺢ m be a DC vector-valued function, with known DC decomposition, f i Gf + i Af − i , with f + i and f − i convex. For any iG1,...,m, let M i ¤max{ γ (e i ), γ (−e i )}, where e i is the ith unit vector of ⺢ m . Then, γ ªf:Ω → ⺢is a DC function, and a DC decomposition for it is given by γ ªfGgAh, (3) with gG γ ªfC ∑ m iG1 M i (f + i Cf − i ), hG ∑ m iG1 M i (f + i Cf − i ). Proof. First, observe that a finite M i ¤max{ γ (e i ), γ (−e i )} can be chosen, since the origin is an interior point of Band, therefore, the polar set B 0 is bounded. From (2), the gauge γ can be globally represented as a pointwise maximum of the affine functions ϕ u , JOTA: VOL. 107, NO. 2, NOVEMBER 2000 247 γ (y)Gmax u∈B 0 ϕ u (y), ∀y∈⺢ m , where ϕ u (y)G〈u,y〉. Then, ϕ u (f 1 ,...,f m )G ∑ m iG1 u i f + i A ∑ m iG1 u i f − i G ∑ m iG1 (M i Cu i )f + i C ∑ m iG1 (M i Au i )f − i A ∑ m iG1 M i (f + i Cf − i ) Since M i ¤ γ (e i )Gmax u∈B 0 u i and M i ¤ γ (−e i )Gmax u∈B 0 −u i , it follows that ªfcan be written as the difference of two convex functions, namely, ϕ u ªfGp u Aq, where p u G ∑ m iG1 (M i Cu i )f + i C ∑ m iG1 (M i Au i )f − i , qG ∑ m iG1 M i (f + i Cf − i ). Then, γ ªfGmax u∈B 0 ϕ u (f 1 ,...,f m ) Gmax u∈B 0 (p u Aq) G 冢 max u∈B 0 p u 冣 Aq G( γ ªfCq)Aq, and the result holds. 䊐 JOTA: VOL. 107, NO. 2, NOVEMBER 2000248 This provides immediately DC decompositions for important classes of DC vector-valued functions. In particular, if the gauge γ is an L p -norm, it can be taken M i G1, for every i, yielding the following corollary. Corollary 1.1. Let f 1 ,...,f m be DC functions on the convex set Ω, with DC decompositions f i Gf + i Af − i ,iG1,...,m. Then, for any p, 1⁄p⁄S,兩兩 f兩兩 p is DC on Ω, a DC decomposition being given by 兩兩 f兩兩 p GgAh, with gG兩兩 f兩兩 p C ∑ m iG1 (f + i Cf − i ), hG ∑ m iG1 (f + i Cf − i ). The result in Proposition 1.1 can be strengthened if further assumptions are made on the gauge γ in use. Indeed, the proof above can be rewritten e.g. for the case in which the polar ball B 0 is contained in the positive orthant. Proposition 1.2. Let Ω⊂⺢ n be a convex set. Let γ :⺢ m → ⺢be a gauge in ⺢ m with unit ball B, such that B 0 ⊂⺢ m C . Let fG(f 1 ,...,f m ):Ω → ⺢ m be a DC vector-valued function, with known DC decomposition, f i Gf + i Af − i , with f + i and f − i convex. For any iG1,...,m, let M i ¤ γ (e i ), where e i is the ith unit vector of ⺢ m . Then, γ ªf:Ω → ⺢is a DC function, and a DC decomposition for it is given by γ ªfGgAh, (4) with gG γ ªfC ∑ m iG1 M i f − i ,hG ∑ m iG1 M i f − i . As a nontrivial application, let us obtain a DC decomposition for the kth function: given fG(f 1 ,...,f m ), let ( f (1) (x),...,f (m) (x)) be the arrangement of ( f 1 (x),...,f m (x)) with f (1) (x)¤f (2) (x)¤···¤f (m) (x). Then, we have the following proposition. JOTA: VOL. 107, NO. 2, NOVEMBER 2000 249 Proposition 1.3. Let Ω⊂⺢ n be a convex set. Let fG (f 1 ,...,f m ):Ω → ⺢ m be a DC vector-valued function, with known DC decomposition f i Gf + i Af − i , with f + i and f − i convex. Let hG ∑ m iG1 f − i and, for any kG1,...,m, let g k Gf (1) Cf (2) C···f (k) C ∑ m iG1 f − i . Then, a DC decomposition for f (1) Cf (2) C···Cf (k) is given by f (1) Cf (2) C···Cf (k) Gg k Ah. (5) In particular, a DC decomposition for f (k) is given by f (k) G(g k Ch)A(g kA1 Ch). (6) Proof. The decomposition (5) follows from the fact that f (1) C···Cf (k) Gmax 冦 〈f,u〉: ∑ m iG1 u i Gk,0⁄u i ⁄1,∀i 冧 . Thus, we can use Proposition 1.3 for B 0 given by B 0 G 冦 u∈⺢ m : ∑ m iG1 u i Gk,0⁄u i ⁄1,∀i 冧 . The decomposition (6) follows from (5) and the fact that f (k) G[f (1) C···Cf (k) ]A[f (1) C···Cf (kA1) ]. 䊐 2. Applications In this section, we analyze applications to the fields of location theory and multiple-criteria decision making that justify the interest of Proposition 1.1. 2.1. Facility Location. As an application of Proposition 1.1 to facility location theory, we consider the Fermat–Weber problem with forbidden regions and mixed gauges. The aim is to find a location outside int(S), the interior of a region S, for a new facility in the plane in such a way that the weighted sum of the distances between the facility and the demand points JOTA: VOL. 107, NO. 2, NOVEMBER 2000250 (fixed facilities) is minimized; that is, we have to solve the optimization problem min 冦 ∑ n iG1 γ i (xAa i ):x∈⺢ 2 \int(S) 冧 , (7) were γ i is a gauge measuring the distance from any point in the plane to a i , xis the unknown location of the new facility, a i is the location of the ith demand point, and Sis a subset of ⺢ 2 that can be represented as the union of mpairwise disjoint connected (not necessarily convex) sets, SG* m jG1 S j . The usual strategy for finding an optimal solution of (7) consists of first solving the unconstrained problem, and then checking if any element in the set X* of optimal solutions is a feasible point for problem (7). If this is the case, then we have an optimal location for the restricted problem. In other cases, the convexity of the objective function allows us to ensure the existence of an optimal solution belonging to bd(S), the boundary of S; thus, we just need to solve, for jG1,...,m, min 冦 ∑ n iG1 γ i (xAa i ):x∈bd(S j ) 冧 . (8) Most papers in the literature do not address the problem in its full generality, since they impose strong assumptions on the gauge (assumed to be the L 1 norm or L 2 norm) and the forbidden region, which is considered to have an extremely simple form (a polyhedron or a circle); see Refs. 8– 10. Suppose that a parametric description for bd(S j ) is known; i.e., we have a function w j :[0,1] >⺢ 2 parametrizing bd(S j ). Then, (8) can be written as min 0⁄t⁄1 ∑ n iG1 γ i (w j (t)Aa i ), (9) which is a one-dimensional optimization problem whose objective function will be multimodal in general, so global optimization techniques must be used for its solution. In the particular case in which w j is a DC function with a known DC decomposition, Proposition 1.1 provides a DC representation for the objective of (9), so the optimal solution can be obtained by solving a DC univariate problem. Several results given in the literature enable us to obtain such DC decomposition, either directly or by using simpler functions with known representation (Refs. 1, 3, 5, 11, 12). For instance, if w j is twice continuously JOTA: VOL. 107, NO. 2, NOVEMBER 2000 251 differentiable and K¤0 is a bound for the second derivative, a DC decomposition for w j is given by w j (t)G[w j (t)C(1兾2)Kt 2 ]A(1兾2)Kt 2 . (10) Example 2.1. As illustration of this technique, we have considered the following Weber problem with a forbidden region: min ∑ 3 iG1 ω i 兩兩xAa i 兩兩 2 , s.t. x∈⺢ 2 \int(S), where a 1 G(0,3), a 2 G(−2,4), a 3 G(4,−2), w 1 G2, w 2 G3, w 3 G2, and Sis the region enclosed by the curve R, a parametric description of which is given by RG{(u(t),v(t)),t∈[0,1]}, with u(t)G5cos(8 π t)cos(2 π t), v(t)G5cos(8 π t)sin(2 π t). The optimal solution for the unconstrained problem is a 1 G(0,3), an interior point of S(see Fig. 1), so the optimal solution for the constrained problem will be located at its boundary. Fig. 1. Forbidden region and demand points, Example 2.1. JOTA: VOL. 107, NO. 2, NOVEMBER 2000252 Taking into account that a parametric description for bd(S) is already given, the optimal solution can be computed by solving min t∈[0,2 π ] F(t)_ ∑ 3 iG1 ω i 兩兩(u(t)Aa i1 ,v(t)Aa i2 )兩兩 2 . The objective is a multimodal function, as can be seen in Fig. 2, so the use of global optimization techniques is required. Since uand vare C 2 in [0,1], they are DC functions and (10) provides the DC decomposition u(t)Gu C (t)Au − (t), v(t)Gv + (t)Av − (t), with u + (t)G5cos(8 π t)cos(2 π t)C170 π 2 t 2 ,u − (t)G170 π 2 t 2 , v + (t)G5cos(8 π t)sin(2 π t)C170 π 2 t 2 ,v − (t)G170 π 2 t 2 . Hence, by Corollary 1.1, it can be claimed that [F(t)Ch(t)]Ah(t)isa DC decomposition for F, with h(t)G7[u + (t)Cv + (t)Cu − (t)Cv − (t)]A16 G7[5cos(8 π t)cos(2 π t)C5cos(8 π t)sin(2 π t)C680 π 2 t 2 ]A16. An (-optimal solution for the problem above has been obtained by using a covering algorithm (Ref. 13), yielding t*G0.28527653858, Fig. 2. Objective function over bd(S), Example 2.1. JOTA: VOL. 107, NO. 2, NOVEMBER 2000 253 which corresponds to the point x*G(−0.6947487405,3.082955211). 䊐 Whereas it might be the case, as in Example 2.1, that a DC parametrization of bd(S j ) is already given, in general such parametrization must also be determined. Fortunately, this is an easy task when S j is a convex and compact set. Indeed, assuming without loss of generality that the origin is an interior point of S j , we have the following parametric description of its boundary: ω j (t)G[cos(2 π t)兾 γ j (cos2 π t,sin2 π t), sin(2 π t)兾 γ j (cos2 π t,sin2 π t)], t∈[0,1], (11) where γ j is the gauge with unit ball S j . Both cos(2 π t) and sin(2 π t) are DC functions; so, by Proposition 1.1, γ j (cos2 π t,sin2 π t) is also DC (with a DC decomposition at hand); thus, every component of (11) is the quotient of two DC functions, thus DC. In order to solve (9) with the ω j (t) in (11) via e.g. a branch-and-bound method, we will simply need a DC decomposition and a procedure for evaluating the objective function and constructing the subgradients at given points. In the search of a DC representation for every component of w,it suffices to obtain a DC decomposition for the quotient of a convex function and a DC function, since the numerators of (11) can be expressed easily as the difference of two convex functions. In order to achieve this, we need the following lemma. Lemma 2.1. Let Ube a bounded set with U⊂{(x,y,z)∈⺢ 3 :yAz¤ α }, where α H0, and let u:U>⺢be defined as u(x,y,z)Gx·(yAz) −1 . Then, there exist ρ *, A,B,C∈⺢such that u + (x,y,z)Gu(x,y,z)C(1兾2) ρ *(x 2 Cy 2 Cz 2 )CAxCByCCz, u − (x,y,z)G(1兾2) ρ *(x 2 Cy 2 Cz 2 )CAxCByCCz are convex and increasing componentwise functions. Proof. The Hessian matrix for uis given by HG[1兾(yAz) 2 ] 冤 0−11 −12x兾(yAz)−2x兾(yAx) 1−2x兾(yAz)2x兾(yAz) 冥 , JOTA: VOL. 107, NO. 2, NOVEMBER 2000260 4. H ARTMAN , P., On Functions Representable as a Difference of Convex Functions, Pacific Journal of Mathematics, Vol. 9, pp.707–713, 1959. 5. T UY ,H.,Convex Analysis and Global Optimization, Kluwer Academic Publishers, Dordrecht, Holland, 1998. 6. M ICHELOT ,C.,The Mathematics of Continuous Location, Studies in Locational Analysis, Vol. 5, pp.59–83, 1993. 7. R OCKAFELLAR , R. T., Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970. 8. A NEJA , Y. P., and P ARLAR ,M.,Algorithms for Weber Facility Location in the Presence of Forbidden Regions and兾or Barriers to Travel, Transportation Science, Vol. 28, pp.70–76, 1994. 9. B RIMBERG , J., and W ESOLOWSKY ,G.O.,The Rectilinear Distance Minimum Problem with Minimum Distance Constraints, Location Science, Vol. 3, pp.203– 215, 1995. 10. H AMACHER , H. W., and N ICKEL , S., Restricted Planar Location Problems and Applications, Naval Research Logistics, Vol. 42, pp.967–992, 1995. 11. B ITTNER , L., Some Representation Theorems for Functions and Sets and Their Application to Nonlinear Programming, Numerische Mathematik, Vol. 16, pp.32–51, 1970. 12. H IRIART -U RRUTY ,J.B.,Generalized Differentiability, Duality, and Optimization for Problems Dealing with Differences of Convex Functions, Convexity and Duality in Optimization, Edited by J. Ponstein, Springer Verlag, Berlin, Germany, pp.37–69, 1985. 13. B LANQUERO , R., and C ARRIZOSA , E., On Covering Methods for DC Optimization, To appear in Journal of Global Optimization. 14. H IRIART -U RRUTY . J. B., Convex Analysis and Minimization Algorithms, I, Springer Verlag, Berlin, Germany, 1993. 15. B AZARAA , M. S., S HERALI , H. D., and S HETTY ,C.M.,Nonlinear Programming: Theory and Algorithms, John Wiley and Sons, New York, NY, 1993. 16. Z ELENY ,M.,Compromise Programming, Multiple-Criteria Decision Making, Edited by J. L. Cochrane, and M. Zeleny, University of South Carolina Press, Columbia, South Carolina, pp.262–301, 1973. 17. Z ELENY ,M.,A Concept of Compromise Solutions and the Method of the Displaced Ideal, Computers and Operations Research, Vol. 1, pp.479–496, 1974. 18. Z ELENY ,M.,Multiple-Criteria Decision Making, Springer Verlag, Berlin, Germany, 1976. 19. R OMERO ,C.,Handbook of Critical Issues in Goal Programming, Pergamon Press, Oxford, England, 1991. 20. S ABER , H. M., and R AVINDRAN ,A.,Nonlinear Goal Programming Theory and Practice: A Survey, Computers and Operations Research, Vol. 20, pp.275–291, 1993. 21. S ABER , H. M., and R AVINDRAN ,A.,A Partitioning Gradient Based (PGB) Algorithm for Solving Nonlinear Goal Programming Problems, Computers and Operations Research, Vol. 23, pp.141–152, 1995.