8_214_zhang.dvi EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 3, No. 1, 2010, 98-106 ISSN 1307-5543 – www.ejpam.com On the Cross-Entropic Regularization Method for Solving Min- Max Problems Lili Zhang1∗, Jianyu Li2 and Xingsi Li3 1 Department of Applied Mathematics, Dalian University of Technology, Dalian, P. R. China 2 School of Mechanical Engineering, Tianjin University of Science and Technology, Tianjin, P. R. China 3 State Key Laboratory of Structural Analysis for Industrial Equipment, Department of Engineering Mechanics, Dalian University of Technology, Dalian, P. R. China Abstract. A smoothing method of multipliers which is a natural result of cross-entropic regulariza- tion for min-max problems is analyzed. As a smoothing technique, we first show how the smooth approximation yields the first order information on the behavior of max function. Then under suitable assumptions, some basic properties including the Hessian are given. At last, the condition number is analyzed, and the results reveal that the smoothing method of multipliers is stable for any fixed smoothing parameter. 2000 Mathematics Subject Classifications: 90C47; 41A46; 57R12 Key Words and Phrases: Min-Max Problem; Cross-Entropic Regularization; Smooth Approximation; Subgradient; Condition Number 1. Introduction A variety of scientific and engineering problems (such as the problems that arise in struc- tural optimization, synthesis of filters, antenna design etc) can be formulated as the following min-max problem (see [1], [2], [3], [4]): min x∈X max 1¶i¶m � fi (x) (1) where X is a common domain of the component functions fi(x), i = 1,2, ...m, which are usually assumed to be twice continuously differentiable. For a complete treatment of the min-max problems, see the books ([5], [6], [7]). ∗Corresponding author. Email address: jnlilizhang�163. om (L. Zhang) http://www.ejpam.com 98 c© 2009 EJPAM All rights reserved. L. Zhang, J. Li, X. Li / Eur. J. Pure Appl. Math, 3 (2010), 98-106 99 One major difficulty encountered in developing solution methods is the non-differentiability of the max function: F (x) := max 1¶i¶m � fi (x) (2) And along with non-smooth optimization methods, the smoothing technique has been used for the min-max since the early 70s([8]), (see also [3], [9], [10], [11], [12], [13]). Among them, a class called regularization methods has been developed base on approximating the max function by certain smooth functions([1], [2], [10], [15], [11], [13]). Gigola and Gomez ([10]), Hiriart-Urruty and Lemarechal ([14]) had given some regularization functions, but no explicit expressions of the smooth approximation functions were given in their work. Li ([15], [16]) used entropy function as the regularization function and derived a smooth and good ap- proximation function in explicit expression for the max function F (x)≈ 1 p ln m ∑ i=1 exp � p fi (x) � . This smooth approximation function is called aggregate function and instead of using the en- tropy regularization function, the cross-entropy regularization function can lead to another smooth and good approximation function which is a smooth approximation function of mul- tipliers and is called cross-entropy aggregate function: Fp (x ,λ) = 1 p ln m ∑ i=1 λi exp � p fi (x) � (3) Both the two smoothing approximation functions have a natural interpretation which fits the special structure of the min-max problem and apply to related problems. The function (3) is also proposed by Bertsekas ([1]) by means of a tedious derivation using the multiplier methods with an exponential penalty function. In this paper, we mainly investigate the approximation function (3), although the uniform convergence and the algorithmic convergence based on this function had been already given ([16], [1]), the main results in this paper have not appeared in either [16] or [1]. We first show how the smooth approximation yields the first order information on the behavior of max function. Then under suitable assumptions, some basic properties including the Hessian are given. As this smooth approximation function of multipliers is obtained by the cross-entropic regularization of the classical Lagrangian, if we treat this smooth approximation as a nonlinear Lagrangian function for the min-max problem, then based on the basic properties, a similar saddle point result can be obtained. At last, the condition number is analyzed, and the results reveal that the smoothing method of multipliers is stable for any fixed smoothing parameter. The rest of this paper is arranged as follows: Section 2 gives the problem formulation and some basic assumptions. Some basic results including the first order information, basic properties and the condition number are given in section 3. Section 4 is the conclusion. 2. Problem Formulation and Basic Assumptions Consider the min-max problem (1). The following are assumptions: Assumption 1. The optimal set X ∗ is not empty and bounded; L. Zhang, J. Li, X. Li / Eur. J. Pure Appl. Math, 3 (2010), 98-106 100 Without loss of generality we can assume that F(x∗) = 0. The min-max problem (1) has the classical Lagrangian function L (x ,λ) = m ∑ i=1 λi fi (x) for each x ∈ X , where λ denotes the Lagrangian multipliers that are restricted to fall within the simplex Λ ≡ ¨ λ|λ¾ 0; m ∑ i=1 λi = 1 « . The following Karush-Kuhn-Tucker (K−K−T) conditions for problem (1) hold true:          ∇x L (x∗,λ∗) = m ∑ i=1 λ∗i∇ fi (x ∗) = 0 λ∗i ≥ 0, i = 1,2, · · · , m, m ∑ i=1 λ∗i = 1 λ∗i fi (x ∗) = 0 i = 1,2, · · · , m (4) Let I (x∗) = � i| fi (x ∗) = F(x∗) is the active set at point x∗ and |I (x∗)| = r, where |Q| is the cardinal number of the set Q. Respectively, ∇ fI (x) = J � fI (x) � = � ∇ fi1 (x) · · ·∇ fir (x) �T , ik ∈ I (x) k = 1,2, · · · r; ∇ f (x) = J � f (x) � = � ∇ f1 (x) · · ·∇ fm (x) �T are their Jacobians. ∇ fI (x ∗) linear indepen- dence, and the pair (x∗,λ∗) satisfies the second order optimality conditions: ¬ ∇2 x x L � x∗,λ∗ � d , d ¶ ≥ ρ 〈d , d〉 ,ρ > 0,∀d 6= 0 :∇ fI � x∗ �T d = 0 (5) the strictly complementary condition is true: λ∗ ∈ Λ and λ∗i > 0, i ∈ I (x∗). Then the max function can be obtained as F (x) =max λ∈Λ L (x ,λ) , x ∈ X (6) Unfortunately, the above maximization rarely has an explicit solution. Therefore the regular- ization methods add some terms that are called regularization functions Lp (x ,λ) = L (x ,λ) + 1 p R � λ;µ � (7) where p > 0 is a control parameter, R is a regularization function, and µ is an optional parameter vector of R. Then, by carefully choosing the function R, maximizing the Lp(x ,λ) could result in a smooth approximation function. When R � λ,µ � = m ∑ i=1 λi ln λi µi , we have the following cross-entropic regularization formula: Fp � x ,µ � ≡max λ∈Λ ( L (x ,λ)− 1 p R � λ;µ � = m ∑ i=1 λi fi (x)− 1 p m ∑ i=1 λi ln λi µi ) (8) where µ is an additional control vector representing some known as priori information (dis- tribution). L. Zhang, J. Li, X. Li / Eur. J. Pure Appl. Math, 3 (2010), 98-106 101 A simple calculation results in the following solution: λ∗i = µi exp � p fi (x) � Z , i = 1,2, · · · , m (9) where Z = m ∑ i=1 µi exp � p fk (x) � . Substituting (9) into (8), we have the smooth approximation function of multiplier (3): Fp � x ,µ � = 1 p ln m ∑ i=1 µi exp � p fi (x) � . The reason for the name of the smooth approximation function of multiplier is that if the pair (x l ,µl) have been found already, we find the next approximation (x l+1,µl+1) by the following formulas: x l+1 = arg min x ¦ Fp � x ,µl �© (10) µl+1 i = µl i exp � p fi (x) � m ∑ k=1 µl k exp � p fk (x) � , i = 1,2, · · · , m (11) So µ is the Lagrangian multiplier in practice, we can just denote the smooth approximation function of multiplier as Fp (x ,λ) = 1 p ln m ∑ i=1 λi exp � p fi (x) � . 3. Main Results 3.1. First Order Information: Subgradient It is well known that the max function F(x) has discontinuous first derivatives at points where two or more of the components fi(x) are equal to F(x) even if each fi(x) is smooth with any order. So we first analyze whether the approximation function (3) could yield the first order information on the behavior of F(x). The results reveal that for the convex situation the subgradients of F(x) can be obtained from the gradients of smooth approximation function Fp(x). The first order behavior of convex non-smooth function around a point x is reflected by the the concepts of subgradients and subdifferential ([17] p214). Definition 1. A vector ω is said to be a subgradient of a convex function at a point x if f (z)− f (x)¾ 〈ω, z − x〉 ∀z ∈ X (12) The set of all subgradients of f at x is called the subdifferential of f at x and is denoted by ∂ f (x), i.e. ∂ f (x) := � ω| f (z)− f (x)¾ 〈ω, z − x〉 ∀z ∈ X (13) Theorem 1. For the max function F(x) and the smooth approximation function of multipliers Fp(x ,λ), the following statements are equivalent: L. Zhang, J. Li, X. Li / Eur. J. Pure Appl. Math, 3 (2010), 98-106 102 i) ω is a subgradient of F at x; ii) there is a weighted vector ξ, such that ω = ∑ i∈I(x) ξi∇ fi (x); iii)ω= lim p→∞ ¦ ∇x Fp (x ,λ) © Proof. The equivalence between (i) and (ii) is well known, and is obtained by applying standard calculus rules for computing subgradients ([17]). lim p→∞ ¦ ∇x Fp (x ,λ) © = lim p→∞      m ∑ i=1 λi exp � p fi (x) � m ∑ k=1 λk exp � p fk (x) � ∇ fi (x)      = ∑ i∈I(x) λi∇ fi (x) (14) as exp � p fi (x) � → p→∞ 0, i /∈ I (x) and λ ∈ Λ. Remark 1. In this proof, we use the assumption that F(x∗) = 0. In fact, without this assumption, we can also obtain the result in theorem 1 by subtracting F(x) both in the numerator and denominator in the middle part in formula (14). 3.2. Basic Properties For approximation function (3), the following results establish the basic properties of this function at any K − K − T pair (x∗,λ∗): Lemma 1. For any K − K − T pair (x∗,λ∗), the following hold for any p ≥ 0: i) Fp (x ∗,λ∗) = F (x∗) = 0; ii)∇x Fp � x∗,λ∗, p � = 0 Proof. i)Using the K − K − T condition (4) directly. ii) As the computation in subsection 3.1 we have ∇x Fp (x ,λ) = m ∑ i=1 λi exp � p fi (x) � m ∑ k=1 λk exp � p fk (x) � ∇ fi (x) = m ∑ i=1 λi∇ fi (x) m ∑ k=1 λk � exp � p fk (x) � − exp � p fi (x) �� (15) Applying the K − K − T condition, we have ∇x Fp � x∗,λ∗ � = m ∑ i=1 λ∗ i ∇ fi (x ∗) m ∑ k=1 λ∗ k � exp � p fk (x ∗) � − exp � p fi (x ∗) �� = 0 (16) L. Zhang, J. Li, X. Li / Eur. J. Pure Appl. Math, 3 (2010), 98-106 103 Theorem 2. Let (x∗,λ∗) be K − K − T pair of min-max problem (1). Assume that ∇ fi (x ∗) , i ∈ I (x∗) are linearly independent and x∗ satisfy the second-order sufficiency condition. Then the following hold: There exists ρ > 0 and p0 > 0, ¬ ∇2 x x Fp � x∗,λ∗ � d , d ¶ ≥ ρ 〈d , d〉 (17) for any fixed p ≥ p0 and d ∈ Rn. Proof. ∇2 x x Fp (x ,λ) = m ∑ i=1 λi exp � p fi (x) � m ∑ k=1 λk exp � p fk (x) � ∇2 fi (x)+ p m ∑ i=1 λi exp � p fi (x) � ∇ fi (x) T ∇ fi (x) m ∑ k=1 λk exp � p fk (x) � − p � m ∑ i=1 λi exp � p fi (x) � ∇ fi (x) �T m ∑ i=1 λi exp � p fi (x) � ∇ fi (x) � m ∑ k=1 λk exp � p fk (x) � �2 (18) and ∇2 x x Fp � x∗,λ∗ � = m ∑ i=1 λ∗i exp � p fi (x ∗) � m ∑ k=1 λ∗ k exp � p fk (x ∗) � ∇2 fi � x∗ � + p m ∑ i=1 λ∗i exp � p fi (x ∗) � ∇ fi (x ∗) T ∇ fi (x ∗) m ∑ k=1 λ∗ k exp � p fk (x ∗) � − p � m ∑ i=1 λ∗ i exp � p fi (x ∗) � ∇ fi (x ∗) �T m ∑ i=1 λ∗ i exp � p fi (x ∗) � ∇ fi (x ∗) � m ∑ k=1 λ∗ k exp � p fk (x ∗) � �2 (19) = ∇2 x x L � x∗,λ∗ � + p ∑ i∈I(x∗) λ∗i∇ fi � x∗ �T ∇ fi � x∗ � − p    ∑ i∈I(x∗) λ∗i∇ fi � x∗ �    T   ∑ i∈I(x∗) λ∗i∇ fi � x∗ �    (20) L. Zhang, J. Li, X. Li / Eur. J. Pure Appl. Math, 3 (2010), 98-106 104 as the convexity of the quadratic function, we have the inequality ∑ i∈I(x∗) λ∗i∇ fi � x∗ �T ∇ fi � x∗ � ≥    ∑ i∈I(x∗) λ∗i∇ fi � x∗ �    T   ∑ i∈I(x∗) λ∗i∇ fi � x∗ �    (21) combining the second order optimality condition we have ¬ ∇2 x x Fp � x∗,λ∗ � d , d ¶ ≥ ¬ ∇2 x x L � x∗,λ∗ � d , d ¶ ≥ ρ 〈d , d〉 (22) Corollary 1. if fi ∈ C2, ∇ fi (x ∗) , i ∈ I (x∗) are linearly independent and the second order sufficiently condition is satisfied, then for any λ > 0 and p > 0, the Hessian of Fp (x ,λ) is positive definite for any x ∈ Rn, i.e. Fp (x ,λ) is strictly convex in Rn and strongly convex on any bounded set in Rn. Remark 2. As the approximation function (3) is obtained by the cross-entropic regularization of classical lagrangian, so when we treat function (3) as a nonlinear lagrangian function of the min-max problem, under the same conditions in theorem 2, for p > p0 we can have the similar saddle point result Fp � x ,λ∗ � ≥ Fp � x∗,λ∗ � ≥ Fp � x∗,λ � ,∀x ∈ U (x ,ǫ) (23) 3.3. Condition Number Based on the analysis in subsection 3.2, we give the following result about the condition number. Theorem 3. Let (x∗,λ∗) be K − K − T pair of min-max problem (1), assume that ∇ fi (x ∗) , i ∈ I (x∗) are linearly independent and the second-order sufficiency condition is satis- fied, then there exists p0 and M0 ≥ τ0 ≥ 0 that M0 〈d , d〉 ¾ ¬ ∇2 x x Fp � x∗,λ∗ � d , d ¶ ¾ τ0 〈d , d〉 (24) is true for any fixed p ≥ p0. Proof. The right inequality is the result in theorem 2, and the left inequality follows from the formulas (20) and (21) if p ≥ p0 and p0 large enough. Corollary 2. If fi(x) are twice continuous differentiable and ǫ ≥ 0 is small enough then for any fixed p ≥ p0, there exists M ≥ τ ≥ 0 such that for any pair ω = (x ,λ) ∈ U (ω∗,ǫ) = {ω|ω−ω∗| ¶ ǫ} the following inequalities M 〈d , d〉 ¾ ¬ ∇2 x x Fp � x∗,λ∗ � d , d ¶ ¾ τ 〈d , d〉 ,∀d ∈ Rn (25) hold true. REFERENCES 105 So the theorem 3 and the corollary 2 mean that in the neighborhood of the K−K− T pair (x∗,λ∗) the condition number cond∇2 x x Fp (x ,λ)¶ τ M is stable for any fixed p ≥ p0. Remark 3. Only the first order information results in subsection 3.1 need the convexity assump- tion. The results in subsection 3.2 and 3.3 are true whether F(x) and all fi(x) are convex or not. 4. Concluding remarks As the uniform convergence and the algorithm are well known concepts, in this paper we have given some basic results that are required for the analysis of this research. It should be noticed that the efficiency of this smoothing method of multipliers depends on the parameter p. A similar parameter analysis in the nonlinear rescaling method for the constrained opti- mization problems is discussed in [18]. For this, some problems are investigated, such as, for the min-max problem to find an explicit general threshold value of p. The smoothing approx- imation has some properties that are related to the parameter p. The research (including the implementations, properties and so on) of the smoothing method of multipliers leads to an important subject for research. ACKNOWLEDGEMENTS The authors would like to thank the referees for their helpful sug- gestions. This work is supported by the National Natural Science Foundation of China Grant(No. 10902077, 60675046). References [1] D.P.Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Academic Press, Boston, MA, 1982. [2] C.Charalammbous, A.R.Conn, An efficient method to solve the Minimax problem di- rectly, SIAM Journal on Numerical Analysis, 15: 162-187 (1978). [3] E.Polak, D.Q.Mayne, J.E.Higgins, Superlinearly convergent algorithm for Min-max prob- lems, Journal of Optimization Theory and Applications, 69(3): 407-439 (1991). [4] A.Ben-Tal, A.Nemirovsky, Convex Optimization in Engineering: Modeling Analysis, Algo- rithms, Technion, Israel, 1998. [5] V.F.Demyanov, V.N.Molozemov, Introduction to Minimax, Wiley, New York, 1974. [6] D.Z.Du, P.M.Pardalos, Minimax and Applications, Kluwer Academic Publishers, Dor- drecht, 1995. [7] E.Polak, Optimization: Algorithm and Consistent Approximations, Springer Verlag, New York, 1997. REFERENCES 106 [8] R.Polyak, On the best convex Chebichev approximation, Soviet Mathematics Doklady, 12: 1441-1444 (1971). [9] G.Di.Phillo, P.L.Grippo, S.Lucidi, A smooth method for the finite Minimax problem, Mathematical Programming, 60: 187-214 (1993). [10] C.Gigola, S.Gomez, A regularization method for solving the finite convex Min-max prob- lem, SIAM Journal on Numerical Analysis, 27: 1621-1634 (1990). [11] R.A.Polyak, Smooth optimization methods for Minimax problems, SIAM Journal on Con- trol and Optimization, 26: 1274-1286 (1988). [12] A.Vardi, New Minimax algorithm, Journal of Optimization Theory and Applications, 75: 613-633 (1992). [13] I.Zang, A smoothing out technique for Min-max optimization, Mathematical Program- ming, 19: 61-77 (1980). [14] J.B.Hiriart-Urruty, C.Lemarechal, Convex analysis and minimization algorithm, Springer- Verlag, Berlin, 1993. [15] X S Li, Entropy and Optimization, Ph.D.Thesis, University of Livepool, United Kingdom, 1987. [16] X S Li, S C Fang, On the entropic regularization method for solving Min-Max problems with applications, Mathematical Methods of Operations Research, 46: 119-130 (1997). [17] R.T.Rockafellar, Convex Analysis, Princeton University Press, New Jersey, 1970. [18] I.Griva, R.A.Polyak, Primal-dual nonlinear rescaling method with dynamic scaling pa- rameter update, Mathematical Programming, 106: 237-259 (2006).