Rev. Anal. Num´er. Th´eor. Approx., vol. 33 (2004) no. 2, pp. 167–174 ictp.acad.ro/jnaat
SOME PROCEDURES FOR SOLVING SPECIAL MAX-MIN FRACTIONAL RANK-TWO REVERSE-CONVEX
PROGRAMMING PROBLEMS
DOINA IONAC∗and S¸TEFAN T¸ IGAN†
Dedicated to Professor Elena Popoviciu on the occasion of her 80th birthday
Abstract. In this paper, we suggest some procedures for solving two special classes of max-min fractional reverse-convex programs. We show that a special bilinear fractional max-min reverse-convex program can be solved by a linear reverse-convex programming problem.
For a linear fractional max-min reverse-convex program, possessing two re- verse-convex sets, we propose a parametrical method. The particularity of this procedure is the fact that the max-min optimal solution of the original problem is obtained by solving at each iteration two linear reverse-convex programs with a rank-two monotonicity property.
MSC 2000. 26B25.
Keywords. Reverse-convex programming, max-min programming, bilinear fractional programs, linear fractional max-min programs.
1. INTRODUCTION
In this paper, we propose some methods for solving two special classes of max-min fractional reverse-convex programs.
LetX ⊆Rn, Y ⊆Rm be given convex sets. LetT be a reverse-convex set in Rn (i.e. the complement of a convex set inRn) and S be a reverse-convex set inRm andh:X×Y →R. The general max-min reverse-convex programming consists in finding an optimal max-min solution for:
PRC. max
x∈X∩T min
y∈Y∩Sh(x, y).
We recall (see, e.g. [14, 17]) that a point (x0, y0) ∈ (X∩T)×Y is said to be an optimal max-min solution for PRC problem, if the following two conditions hold:
(i) h(x0, y0) = max
x∈X∩T min
y∈Y∩Sh(x, y), (ii) min
y∈Y∩Sh(x0, y) =h(x0, y0).
∗Department of Mathematics, University of Oradea, e-mail: [email protected].
†University of Medicine and Pharmacy “Iuliu-Hat¸ieganu” Cluj-Napoca, Department of Medical Informatics and Biostatistics, e-mail: [email protected].
In the particular case, when PRC is a simple maximization problem only (i.e. Y has a single element,Xis a polyhedral set andT is a reverse-convex set defined by a convex or quasi-convex constraint which has a rank-two mono- tonicity property), we recall that procedures for solving the maximum (or minimum) reverse-convex programming problems were given, for instance, in the papers [4], [7], [8], [10], [18], [6]. Duality aspects of the reverse-convex pro- gramming can be found in the paper by Penot [9]. For the max-min reverse- convex programming we mention the refs. [5], [6].
In section 2, for a special fractional type of the objective function h and for some particular cases of the sets X, Y, T and S, we obtain a particular case of problem PRC of bilinear fractional form, for which we propose, in Section 3, a method of finding optimal max-min solutions by reducing these problems to the particular case whenXis a polyhedral set and T is a reverse- convex set defined by a convex or quasi-convex constraint that has a rank-two monotonicity property. These auxiliary problems can be solved by Kuno- Yamamoto procedure [8].
In section 4, we consider a max-min linear fractional reverse-convex pro- gramming problem, having two reverse-convex setsT andS, and for which we propose a parametric procedure.
Some concluding remarks are made in the last section.
2. BILINEAR FRACTIONALMAX-MINREVERSE-CONVEX PROGRAM PFM
Next we consider the following bilinear fractional max-min reverse-convex program (see, [6]) in which the reverse setS =Rm:
PFM. Find
(1) V = max
x∈X∩Tmin
y∈Y
yTCx+cTx+eTy+e0
max{αTi y+βi|i∈I}
!
whereI ={1,2, ..., r}, C∈Rm×n, c∈Rn, e, αi ∈Rm and e0, βi ∈R, (i∈I).
The sets X and Y are defined by
(2) X ={x∈Rn|Ax=a, x≥0},
(3) Y ={y∈Rm|Dy≥d, y≥0},
whereA∈Rs×n, a∈Rs, D∈Rq×m, d∈Rq. The reverse-convex set
(4) T ={x∈X0|f(x)≤0},
is defined by a functionf :Rn→R, which is continuous, strictly quasiconcave and has rank-two monotonicity on an open convex setX0⊆Rn, which includes the set X.
We recall thatf is said to be strictly quasiconcave onX0 if for eachx, y∈ X0 with f(x) 6= f(y) we have f((1−t)x +ty) > min{f(x), f(y)}, for any t∈(0,1).
Definition 1. [8] The function f possess a rank-two monotonicity on X0 with respect to linearly independent vectors λ1, λ2 ∈ Rn, if for any points x0, x00∈X0, the inequality λix0 ≤λix00, i= 1,2 implies f(x0)≤f(x00).
We have the following representation for a functionf possessing a rank-two monotonicity onX0 with respect to linearly independent vectorsλ1, λ2 ∈Rn. Lemma 2. [8] If the function f possess a rank-two monotonicity on X0 with respect to linearly independent vectors λ1, λ2 ∈ Rn, then there exists a function g : R2 → R, which is continuous and strictly quasiconcave on Γ0 ={(λ1x, λ2x)|x∈X0} and satisfies the following two conditions:
(i) f(x) =g(λ1x, λ2x), for x∈X0, (ii) g(θ)≤g(η) ifθ, η∈Γ0 andθ≤η.
Concerning the problemPFM, we make the following assumptions:
A1. Y is a bounded non-empty set,
A2. the function f is continuous, strictly quasi-concave and has rank-two monotonicity on the open convex set X0,
A3. max{αiy+βi|i∈I}>0, ∀y∈Y.
3. LINEAR REVERSE-CONVEX PROGRAMMING APPROACH
We proposed in [6] a procedure for solving problem PFM based on the Charnes-Cooper [1] variable change.
Thus, if we perform in the problem (1)–(4), the Charnes-Cooper variable change v = ty, t ≥ 0, v ∈ Rs, (see, also Schaible [11], Stancu-Minasian [12]
and Tigan [14], [16]) it follows by assumptions A1 and A3 that problemPFM is equivalent with:
PA. Find
(5) V0 = max
x∈X∩T min
(v,t)∈Y0
vTCx+cTxt+eTv+e0t, where the setY0 is defined by:
(6) Dv−dt≥0,
(7) max{αiTv+βit|i∈I} ≥1,
(8) v≥0, t≥0.
We can show, by assumptions A1 and A3, that V = V0 and that for any optimal max-min solution (x∗, y∗) of problem PFM there exists an optimal max-min solution (x∗, v∗, t∗) of problemPAsuch thaty∗= vt∗∗ and conversely.
By Golstein [3] (see, also T¸ igan and Stancu-Minasian [17]), the constraint (7) in Problem PA can be rewritten as the following maximum bilinear con- straint:
(9) max
θ∈Z r
X
i=1
θi(αiv+βit−1)≥0,
whereZ ={θ∈Rr|Pr
i=1
θi = 1, θi ≥0, i= 1,2, ..., r}.
Let us denote
(10) ψ(v, t) = max
θ∈Z r
X
i=1
θi(αTi v+βit−1),∀(v, t)∈Y0. By linear programming duality, for any (v, t)∈Y0,we have
(11) ψ(v, t) = minw
subject to
(12) w≥αTi v+βit−1,∀i∈I, w≥0.
From (10)–(12), it follows that the inequation (9) can be expressed by the following system:
w≥0,
w≥αTi v+βit−1,∀i∈I.
Therefore, problem PA can be reduced to the following max-min bilinear reverse-convex program
PMM1. Find
(13) V0 = max
x∈X∩T min
(v,t,w)∈Y00
vT(Cx+e) +t(cTx+e0),
where the setY00 is defined by:
(14) Dv−dt≥0,
(15) w≥αTi v+βit−1,∀i∈I
(16) v≥0, t≥0, w≥0.
From (13)–(16), by linear programming duality, for anyx∈X∩T, problem PMM1can be transformed into the following linear reverse-convex program:
PML. Find
(17) V0 = max
x,u,z(−z1−z2−...−zr), subject to
uTD−zTΩ≤Cx+e,
−uTd−zTΛ≤cTx+e0,i∈I x∈X∩T,
u≥0, z≥0, u∈Rq, z∈Rr.
In problem PML,we denote by Ω ∈ Rr×s the matrix having the rows αi
(i∈I), and by Λ the vector Λ = (β1, ..., βr)T ∈Rr. Therefore, we proved the following theorem:
Theorem 3. If the problem PFM satisfies the assumptions A1-A3, then problem PFMcan be solved by solving the linear reverse-convex program with a rank-two monotonicity PML.
In order to solve problem PFM, a procedure similar to Algorithm 1 can be used, by replacing in step1 the problemPLC by the linear reverse-convex programming problem PML.
Algorithm 1. Step 1. Solve the linear reverse-convex programs with a rank-two monotonicity PML.
If V < ∞ and the feasible set X0 of PML is non-empty, let x∗ be the corresponding component of an optimal solution of problem PML.
If X =∅, then take V =−∞.
Step 2. i) If −∞ < V <∞, then (x∗, y∗) is an optimal solution of max- min problem PFM, where y∗ is an optimal solution of the generalized linear- fractional program PFA.
ii) If V =−∞, then PFMis unfeasible.
iii) If V =∞, then PFMhas an infinite optimum.
We make the remark that auxiliary linear reverse-convex programming problem PML in Algorithm 1 is simpler than the auxiliary linear reverse- convex programming problem in the algorithm proposed for this problem in [6]. Indeed, problemPMLhas onlys+rlinear constraints the auxiliary prob- lem in [6] posses (s+ 2)r linear constraints. Therefore, Algorithm 1 seems to be more efficient than algorithm proposed for this problem in [6].
4. MAX-MIN LINEAR FRACTIONAL REVERSE-CONVEX PROGRAMMING WITH TWO SEPARATE REVERSE-CONVEX FEASIBLE SETS
In this section, we consider the following max-min linear fractional program GLF. Find
x∈X∩Tmax min
y∈Y∩Sh(x, y) where
h(x, y) = αTx+βTy+β0
γTx+ηTy+η0
,
verifying the condition
γTx+ηTy+η0>0, ∀x∈X, ∀y∈Y.
In problemGLF,X and S are defined by
(18) X ={x∈Rn|Ax=a, x≥0}, (19) Y ={y∈Rm|By=b, y≥0},
where A ∈Rs×n, B ∈ Rp×m, a∈ Rs, b ∈ Rp, α, γ ∈ Rn, β, η ∈ Rm, β0, η0 ∈R, are given matrices, vectors and real constants respectively.
The reverse-convex set
(20) T ={x∈X0|f(x)≤0},
is defined by a functionf :Rn→R, which is continuous, strictly quasiconcave and has rank-two monotonicity on an open convex setX0⊆Rn, which includes the set X and the reverse-convex set
(21) S={y∈Y0|f1(y)≤0},
is defined by a function f1 :Rm →R, which is continuous, strictly quasicon- cave and has rank-two monotonicity on an open convex set Y0 ⊆Rm, which includes the set Y.
For solving problemGLFwe can use a parametric procedure (see, [2], [13], [15]), by which an approximate optimal solution could be found by solving a sequence of the auxiliary reverse-convex programs each of them having only one reverse-convex constraint.
Algorithm 2. Let ε > 0 be a given positive real number, representing a level of approximation to be attain by algorithm.
1. Find a point x0 ∈X∩T and a pointy0∈Y ∩S and set k:= 0.
2. Take
tk=h(xk, yk).
3. Find
(22) F(tk) = max
x∈X∩T min
y∈Y∩S[(α−tkγ)x+ (β−tkη)y+β0−tkη0].
But the max-min program (22) can be transformed into the following two linear reverse-convex programs
PL1. Find
(23) max
x (α−tkγ)x subject to
(24) x∈X∩T.
PL2. Find
(25) min
y [(β−tkη)y+β0−tkη0] subject to
(26) y ∈Y ∩S.
Let xk+1, yk+1 be an optimal solution of the linear reverse-convex pro- gram (23)–(24) and (25)–(26), respectively. Obviously, we have F(tk) = (α−tkγ)xk+1+ (β−tkη)yk+1+β0−tkη0.
4. i) If F(tk) ≤ε, then (xk+1, yk+1) is an approximate optimal solution of problem GLF.
ii) If F(tk)> ε, then take k:=k+1 and go to the step 2.
5. CONCLUSIONS
In this paper we consider two fractional max-min reverse-convex program- ming problems.
Firstly, we give a new procedure for solving a particular class of max- min bilinear fractional reverse-convex programming problems. The partic- ularity of this procedure is the fact that the max-min optimal solution of the original problem is obtained by solving a single linear reverse-convex pro- gram with a rank-two monotonicity with an algorithm proposed by Kuno and Yamamoto [8].
Secondly, we consider a parametric procedure for solving a particular class of max-min linear fractional reverse-convex programming problems, possessing two reverse-convex feasible sets. The particularity of this procedure is the fact that the max-min optimal solution of the original problem is obtained by solving at each iteration two linear reverse-convex programs with a rank-two monotonicity with the algorithm of Kuno and Yamamoto.
REFERENCES
[1] Charnes, A., Cooper,W.W., Programming with linear fractional functionals, Naval Res. Logist. Quart.,9, 1–2, pp. 181–186, 1962.
[2] Crouzeix, J.P., Ferland, J.A. and Schaible, S.,An algorithm for generalized frac- tional programs, J. Optim. Theory Appl.,47, 1, pp. 35–49, 1985.
[3] Golstein, E.G., Duality theory in mathematical programming and its applications, Nauka, Moskva, 1971 (in Russian).
[4] Hillestad, R.J., Jacobsen S.E., Linear programs with an additional reverse-convex constraint, Applied Mathematics and Optimization,6, pp. 257–269, 1980.
[5] Ionac, D.,Aspecte privind analiza unor probleme de programare matematic˘a, ed. Treira, Oradea, 2000 (in Romanian).
[6] Ionac, D. and Tigan, S., Solving procedures for some max-min reverse-convex pro- grams, Proc. of the “Tiberiu Popoviciu” Itinerant Seminar on functional Equations, Approximation and Convexity, Editura SRIMA, Cluj-Napoca, Romania, pp. 105–118, 2002.
[7] Kuno,T.,Globally determining a minimum area rectangle enclosing the projection of a higher-dimensional set, Operations Research Letters,13, pp. 295–303, 1993.
[8] Kuno,T. andYamamotoY.,A finite algorithm for globally optimizing a class of rank- two reverse-convex programming, Journal of Global Optimization,12, 3, pp. 247–265, 1998.
[9] Penot, J.-P.,Duality for anticonvex programs, Journal of Global Optimization,19, pp.
163–182, 2001.
[10] Pferschy,U. andTuy, H.,Linear programs with an additional rank-two reverse-convex constraint, Journal of Global Optimization,4, pp. 441–454, 1994.
[11] Schaible, S.,Nonlinear fractional programming, Oper. Res. Verfahren,19, pp. 109–115, 1974.
[12] Stancu-Minasian, I.M., Fractional Programming Theory, Methods and Applications, Kluwer Academic Publishers, Dordrecht, 1997.
[13] Tigan, S.,Sur une methode de resolution d’un probl`eme d’optimisation par segments, Rev. Anal. Num´er. Th´eor. Approx.,4, no. 1, pp. 87–97, 1975.
[14] Tigan, S.,On the max-min nonlinear fractional problem, Rev. Anal. Num´er. Th´eor.
Approx.,9, no. 2, pp. 283–288, 1980.
[15] Tigan,S., A parametrical method for max-min nonlinear fractional problems, Proc. of the Itinerant Seminar on functional Equations, Approximation and Convexity, “Babe¸s- Bolyai” University, Cluj-Napoca, pp. 175–184, 1983.
[16] Tigan,S.,Asupra unor probleme fract¸ionare de maximin, Studii ¸si Cercet˘ari de Calcul Economic ¸si Calcul Economic, 1–2, pp. 53–57, 1992.
[17] Tigan, S. and Stancu-Minasian, I.M., Methods for solving stochastic bilinear frac- tional max-min problems, Recherche Op´erationnelle / Operations Research, 30, no. 1, pp. 81–98, 1996.
[18] Tuy, H., Convex programs with an additional reverse-convex constraint, Journal of Optimization Theory and Applications,52, pp. 463–486, 1987.
Received by the editors: May 11, 2004.
