Duality for extended infinite monotropic optimization problems
- PDF / 404,089 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 36 Downloads / 232 Views
Series B
Duality for extended infinite monotropic optimization problems Dinh The Luc1,2 · Michel Volle3 Received: 19 October 2019 / Accepted: 21 August 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract We establish necessary and sufficient conditions for strong duality of extended monotropic optimization problems with possibly infinite sum of separable functions. The results are applied to a minimization problem of the infinite sum of proper convex functions. We consider a truncation method for duality and obtain the zero duality gap by using only dual variable of finite support. An application to minimum cost flow problems in infinite networks is also discussed. Keywords Monotropic optimization · Strong duality · Zero duality gap · Minimum cost flow · Infinite network Mathematics Subject Classification 90C30 · 90C46 · 90N15
1 Introduction The classical monotropic programming problem, introduced and analyzed by Rockafellar [16], is formulated as follows
To Marco Lopez on occasion of his 70th birthday
B
Michel Volle [email protected] Dinh The Luc [email protected]
1
Parametric MultiObjective Optimization Research Group, Ton Duc Thang University, Ho Chi Minh City, Vietnam
2
Faculty of Mathematics and Statistics, Ton Duc Thang University, Ho Chi Minh City, Vietnam
3
LMA EA 2151, Avignon University, Avignon, France
123
D. T. Luc, M. Volle
minimize
m
f i (xi )
i=1
subject tox ∈ S, where x = (x1 , ..., xm ) ∈ Rm , f i , i = 1, ..., m are convex functions on R and S is a subspace of Rm . Monotropic problems have originally arisen from minimum cost network flow problems [15,17] and form a particular class of separable convex programming with a lot of applications (see [2,3,5,6,8] and references given therein). Many duality results that are important in development of computing methods have been recently obtained in [2,3,6,8], in which considerable effort focuses on countably infinite monotropic problems. Optimization problems involving a countably infinite number of variables and a countably infinite number of constraints, are often met in infinite dimensional linear programming, infinite networks and hypernetworks, infinite-horizon planning, Markov decision processes, robust optimization and many other fields ([10,17–20]). While under relatively mild conditions, zero duality gap does hold for monotropic problems in finite dimension (Theorem 11D [16]), it is not the case in the infinite dimension. To the best of our knowledge, [6] is the first work that carefully analyzes Fenchel duality for generalized monotropic problems with infinite sums in the framework of proper convex and lower semicontinuous functions. They obtain strong duality under a constraint qualification on the closedness of the sum of the conjugates of the convex functions and generalize the results of finite sums of [3,5]. Another method has been recently utilized in [8] to establish zero duality gap and strong duality for infinite monotropic problems over i
Data Loading...
