滋賀大学学術情報リポジトリ

105

An Algorithm for Fractional Programming

Problems over a Finite Jump System

Takeshi Naitoh

Abstract

For solving fractional programming problems, Newton's method is often

used, but it is difficult to estimate a number of iterations of Newton's

method. In the case of solving O-1 linear fractional programming problems,

T. Radzik [19] and T. Matsui, Y. Saruwatari, and M. Shigeno [16] showed

that Newton's method terminates in a strongly polynomial number of

lteratlons.

For a given nonempty finite set E, we consider fractional programming

problems over a finite jump system with the class of objective functions as given in the:

2fe(x(e))

eEIE

2 ge (x (e) )

eEE

i

where for each e E E, fe is a concave function on R, g, is a convex function

on R, and fe(x(e)), g.(x(e))EiZ. In this paper, we introduce resource

allocation problems over the special class of a finite jump system. More-over, we show that Newton's method for fractional programming problems

106 ltR.imk ag290e

1. Introduction

A. Bouchet and W. H. Cunningham [3] have introducedaconcept of jump

system. A jump system is a pair (E,j:') of a finite set E and a set f of

integral points in ZE satisfying an exchange axiom. The convex hull Co (.1 )

of .1 is a polypseudomatroid ([3]), i.e., for a given finite jump system

(E,f) there exists a bisubmodular function f : 3E . Z such that

Co (1') = {xjxE RE, V(X, Y) E 3E : x(X) - x( Y) sg f(X, Y) } (1.1)

(a precise definition of bisubmodular function will be given later).

Recently, we presented a greedy algorithm for minimizing a separable convex function over a finite jump system [2]. Moreover, we examined the

behavior of the greedy algorithm and show that the greedy algorithm

terminates after changing an initial feasible solution at most

2{f({e},Åë) +f(Åë,{e})} (12)

eEE

tlmes.

For solving fractional programming problems, Newton's method is

often used, but it is difficult to estimate a number of iterations of Newton's

method. Recently, T. Radzik [19] and T. Matsui, Y. Saruwatari, and

M. Shigeno [16] showed that Newton's method terminates in a strongly

polynomial number of iterations in the case of solving O-1 linear fractional

programming problems :

n

2 aixi

LFCO:Maximize i=i

n

2 bixz

i=1

subject to xEx,

An Algorithm for Fractional Programming Problems over a Finite Jump Systern 107

where a= (ai,•••,a.) EZ", b= (bi,•••,b.) EZ", x is an arbitrary subset il

of {O,1}", and 2bix, > O (Vx Ex).

I=1

For each eE E, Iet fe be a concave function on R, ge be a convex

function on R, and f.(x(e)),g.(x(e)) EZ. Especially, when E = {1,•t•,n},

n

_{2fe(x(e)) is denoted by 2i•(xi). In this paper, we introduce resource}

eEE i=:1

allocation problems over the special class of a finite jump system.

More-over, we consider Newton's method for fractional programming problems

over a finite jump system :

2fe(x(e))

eEE

SCFP : Maximize

2 ge (x (e) )

eEE

subjectto xE-,

where 2g.(x(e)) > O (Vx E jr). We show that Newton's method for the

eEE

problem SCFP terminates in a finite number of iterations.

2. Definitions and Preliminaries

Let E be a nonempty finite set. Denote by 3E the set of all the ordered pairs

(X,Y) of disjoint subsets X and Y of E. Letf : 3E . Z be a function from

3E to the set Z of integers such that f(Åë,Åë) = O and for each (Xi, Yi) E 3E

(i = 1,2)

f(X,, Y,) +f(X2, Y2)

2f((X, U X,) - (Y, U Y,),(Y, U Y,) - (X, U X,))

+f(X,nX,, Y,n Y,). (2.1)

We call such an f a bisubmodular function, which was first considered by R. Chandrasekaran and S. N. Kabadi [5]. Define a polyhedron

los etft lip. ue ag 2go e

P. (f) = {xlxE ZE, V(X, Y) EI 3E : x(X) - x( Y) s{l f(X, Y) } (2.2)

associated with f, where for any X g E

x(X) = 2x(e) (x(l) ;- O)

eEE

and x EiiZE. We call the polyhedron P. V) an integral bisubmodular Polyhe-dron.

A. Bouchet and W. H. Cunningham [3] introduced a concept of iumP

system. A steP is a (O,Å}1)-vector with a unique nonzero component. Denote

by S the set of all the steps in ZE. For any x,yEiZE a stop sfrom x to y

is a step such that

2lx(e) +s(e) -y(e) i= 2 lx(e) -y(e) l- 1.

eEE eEE

We denote by St(x,y) the set of all the steps from x to y. A 1'umP system on a finite set E is a pair (E,.1 ) of E and .7 g;; ZE which satisfies the followjng 2-steP atiDm :

(2-SA) For any x,y (li.1 and sGSt(x,y) with x + s (1!if there exists t

ESt(x + s,y) such that

x+s+tEi l'. (2.3)

We show some examples of a finite jump system, i.e., a jump system

with a finite Jr'. Let E = {1,•••,n} and Z+ be a set of nonnegative integers.

Example1: Let N E'Z+ and 17i = {x[x(E) = N,xE'ZE}. Then, (E,fi) is

An AIgorithm for Fractional Programming Problems over a Finite Jump System 109

n

RAI : Minimize 2g, (x,)

l=1

n

subject to 2x, :N,

i--1

x,: nonnegative integer i = 1,•••,n.

Let gi (x,) be a convex function. Then problem such as finding the optimal allocation of seats in a federal system is an example which is formulated as RAI. Suppose that there are n states with populations P,. Denote by x, the

number of seats given to state i Let N be the total number of seats to be

allocated, w = N/2r=,P, and i• (x,) = P, (x,/Pi - w)2. Then problem RAI is

well known to as the method of Webster ([14], [15]). O

Example2: Let SiCS2C•••CS. g; E, Ni SIV2 S'''SNm and f2 =

{xlx(Sk) g A[k, le = 1,•••,m, xEiZE}. Then, (E,.T12) is a finitejump system.

n

RA2:Maximize 2i•(x,)

1=:1

n

subject to 2x, = nN,

z=1

n-1

2x, g (n - 1)N,

I=:1

x, + tle g 2N,

x, g N,

x,: nonnegative integer i -- 1,.•.,n.

Let i• (xi) be a concave function. An example which is formulated as RA2 (the production-sales) was provided by A. Tamir [20]. Let the produced items be sold at n given fixed time O=4< ti < •'' < tn where ti - t,-i

110 l*R.im ue ag 290 -Sl•

(i = 1,•••,n) is constant. Suppose that the production rate is constant and the amount of items produced by ti is AX. In RA2, we denote amount of items which are sold at t, by x, and profit which is gained (at t,) by i•(xi). []

Example 3 : Let .XV'.1 be a family satisfying the following property :

If X,YEYV-, then Xg!l Y or YgX or X fi Y =e holds.

Let h : YV' F - Z+ be a function representing an upper bound on the amount

of resource allocated to XENf and f3 = {x1x(X) S h(X), XEArf,

xE'

ZE}. Then, (E,1,) is a finite jump system.

Let g, (xi) be a convex function. Then, problem described as

n

RA3 : Minimize 2g, (x,)

z=1

subj ect to x(X) g h(X) (X E' .Al'-),

x,: nonnegative integer i = 1,•••,n,

was studied by O. Gross [10]. Furthermore, a resource allocation problem

which is formulated as RA3 was provided by P. Brucker [4]. O

Example 4 : Let V and A be finite sets, where V is called a vertex set and A an arc set. Each v E V is called a vertex and each a E' A is called an arc.

Each arc aEA has its initial end-vertex a'a and terminal end-vertex

a-a. We call G = (V,A ; a',a-) a (directed) graPh. We often denote at by

G= (V,A).

Mapplngs 6' : V --> 2A and 6- : V . 2A are, respectively, defined by

6'v={alaEA, v= O'a}, (2.4)

6-v= {alaEA, v= a"a} (2.5)

An Algorithm for Fractional Prograrnming Problems over a Finite Jump System 111

for each v E V.

A network yV' = (G = (V,A),c) is a pair of a graph G = (V,A) and a

nonnegative function c : A . R+ U{+oo} on A. The function c is called a

caPacity fzanction. A function op : A - R+ is called a flow in the network .A/' = (G == (V,A),c) if it satisfies

Va EEA:OK op (a)Sc(a). (2.6)

Let s E V be the source and T l V be the set of sinks. The supply of the source is AI > O. Here, we assume c: A -> Z+.

n

RA4:Minimize 2g,(x,)

z=1

subject to 2 op (a) - 2 q(a) =O (v EI V-T-{s}),

aEcr'v aEe'v

2 op (a) m 2 op (a) sN (v = s),

aEO"v aGcr-v

x. =' 2 q(a) - 2 Åë(a) 2O (vE T),

aE6'v aEe'v

op (a) S c(a) (Va EA),

q(a) : nonnegative integer (Va EA).

Let f4 = {x1x is the feasible solution of RA4}. Then, (E,.TT4) is a finite

Jump system.

An efficient algorithm for problem RA4 was given by N. Megiddo [17] .

Furthermore, a network resource allocation problem which is formulated as

RA4 was studied by A. Federgruen and H. Groenevelt [6]. []

112 %*Rthr.Atue eg290g (pO) p(Åë) =o

(pl) Xg Y gll EOp(X) Kp(Y)

(p2) VX,Y g;E:p(X) +p(Y) 2p(X U Y) +p(X n Y),

we call p a B-function.

(If g : 2E . R satisfies (p2), then we call g a submodular function.) Let

p(.) (p) = {xlxGRe, vX gE:x(X) sp(X) }. (2.7)

We call P{+)(p) a polymatroid. Also, if p : 2E - Z., then

Ip(.) (p) ={xlxEze, vX g;E:x(X) gp(X)} (2.s)

is called an integral polymatroid. A. Bouchet and W. H. Cunningham [3] showed that (E,IP(.) (p)) is a finite jump system (also see M. Nakamura

[18]). The problem that maximize separable concave function over an

integral polymatroid was studied by A. Federgruen and H. Groenevelt [7]. The problem that maximize separable concave function over a polymatroid

was studied by S. Fujishige [8], [9] and H. Groenevelt [11]. []

Above examples are documented in T. Ibaraki and N. Katoh [13], in

N. Katoh [15], and in D. S. Hochbaum and S. Hong [12].

Example6: Denote by Co(f) the convex hull of -. It is known that an

integral polypseudomatroid defined by (2.2) and a finite jump system have

following relations.

Theorem 2.1 ([3]):An integral PolyPseudomatroid satisfies (2-SA). [I]

Theorem 2.2 ([3]) : If .1' satisfies (2-SA), then Co(.1') in RE coincides with

the convex hull of an integral PollJtPsezadomatroid in RE. []

An Algorithm for Fractional Programming Problems over a Finite Jurnp System 113

As shown in [3], the converse of Theorem 2.1 is not true. For example, .1

={O,2}gZ satisfies (2-SA) but not an integral polypseudomatroid.

However, Co(.T') = {xlO S x g 2} is the convex hull of an integral

polyp-seudomatroid.

The problem that maximize separable concave function over an

inte-gral polypseudomatroid was studied by K. Ando, S. Fujishige and T. Naitoh

3. A greedy algorithm for maximizing separable

concave function over a finite jump system

For solving problem SCFP, we will need an algorithm for maximizing

separable concave function over a finite jump system. In this section we

introduce a greedy algorithm in [2].

Let w : RE . R be a separable concave function given by

w(x) =2w. (x (e)), (3.1)

eEE

where for each e E E we is a concave function on R. Consider a discrete optimization problem described as

P: Maximize 2 we (x (e))

eEE

subjectto xEif, (3.2)

where (E,.T') is a finite jump system, i.e., a jump system with a finite f. We

describe a greedy algorithm for solving the above problem P.

A greedy algorithm

/

_{Input : a vector xEf.}

114 escEi.4if ag290e

Step1: If neither of the following two conditions is satisfied, then stop (x is an optimal solution).

(1) There exists a step sES such that x + s (!i .1' and ev (x + s) >

w (x) .

(2) There exist steps s,tES such that x+sEZI1, x+s+ tEjr

and zv (x +s+ t) >w(x).

Step 2: Compute

wi =: max{w(x + s) 1step s satisfying Condition (1) in Step 1},

(3.3)

w2 = max{w(x + s) lsteps s,t satisfying Condition (2) in Step 1},

(3.4)

where the maximum over the empty set is defined to be -oo.

Put nd : = max{wi,w2}.

If we have to = wi, let sA be the step s that attains the maximum of

(3.3), put x: == x + sA and go to Step 1.

If to t wi, let s" and i be the steps s and t that attain the maximum of

(3.4), put x:=x+ sA + t" and go to Step 1.

(End)

It should be noted that in (3.4) w(x+s) but not w(x+s+ t) is

maximized and that each step s in the above algorithm is chosen in a greedy

way.

Denote by xk the current x obtained after the kth execution of Step 2

of the greedy algorithm. During the execution of the greedy algorithm, if the current xh is not an optimal solution, then xh is changed into either xk'i: =

An Algorithm for Fractional Programming Problems over a Finite Jump System 115

Theorem3.1 ([2]):If xh" is changed into xh and further xk into xh'i

successively by the greedy algonthm, then

w(xk-'+sk-') -w(xh-i) >- w(xh+sk) -w(xk). (3.5)

o

Theorem 2.2 implies that for a given finite jump system (E,lr), there

exists a bisubmodular function f such that the convex hull Co(.T') of f is

given by

{xlxERE, V(X,Y) E3E:x(X) -x(Y) gf(X, Y) }, (3.6)

and

-f (Åë,{e}) =minx(e). (3.7)

xEF

f({e},Åë) =maxx(e). (3.8)

xEJr

By the use of such a bisubmodular function f we obtain the following

theorem.

Theorem3.2 ([2]) : The greedy algorithm executes Step2 at most

2{f({e},S) +f(Åë,{e})} (3.9)

eEE

4. Main result

Letf be a separable concave function given byf(x) == 2f.(x(e)) and g be

eEE

a separable convex function given by g(x) :2g,(x(e)). For problem

eEE

SCFP, we assume

116 2iRgi.e,ue

eg290-:l-and

ax Ef:f(x) >O. (4.2)

Note that if each ge is a linear function, then we may assume (4.2) without

loss of generality (see A. Nakayama [18]).

Problem SCFP can be equivalently formulated in the following way :

SCFP2:Minimize 6

subject to f(x) -6g(x) SO,

x E .1'•

Let

h(6) =max{f (x) -6g(x) }. (4.3)

xEf

Since F is finite, it follows from (4.1) that h(6) is convex, monotone

decreasing and piecewise linear function. Furthermore, for a fixed

parame-ter O, h(6) is the maximum of separable concave function over .1,i.e., a

feasible region of a finite jump system.

Let 6' denote an optimal solution of problem SCFP. Then, we have

following properties ([13], [16]).

h(6) >O if and only if 6< 6', (4.4)

h(6) =Oif and only if 6= 6*. (4.5)

In order to solve problem SCFP, we are looking for 6 satisfying h(6)

= O and xEi

.1 . The following Newton's method correctly computes an

optimal solution of problem SCFP.

Newton's method

An Algorithm for Fractional Prograrnming Problems over a Finite Jurnp System

Step2: Compute h(6) and jiEf such that h(6) =f(X) - 6g(X).

Step 3: If h(6) = O, then holt. Otherwise, put

f (x)

6:=

g(j) '

and return to Step 2.

In order to compute r in

117

Step 2, we make use of the greedy algorithm

in section 3. Let 6i be the value of 6 at the beginning of ith iteration of this

Newton's method, and x, be the value of X at this iteration. Moreover, let

Hi -- f(xi) - 6ig(xi) == max{f(xi) - 6ig(x,)} (4.6)

xEX

Bi =g(x,) (4.7)

f(x,)

(Si+i == g(x,)' (4•8)

Then, we have

f(xi)

H,

. (4.9)

6i+1 - 6i =

9(Xi)

B,

Using the similar argument as in the proof of Lemma1 in T. Radzik

[19], we have the following lemma which guarantees fast convergence of

Newton's method.

Lemma4.1 (cf [19]):

Hi+1

H,

Proof : Since x, maximizes f(

f(xi) - 6ig(x,)

Therefore

B,+1

+

< 1.

B,

-x) - 6ig(-x),

2f(x,.,)

-we have

6v (x,+1) . (4.10) (4.11)

118 YliR ETAma ue eg 290 ?

Hi -- f(x,) - 6ig(xi) }) f(xi.i) - 6ig(x,.i)

= (]C(x,.i) - 6i.,g(x,+i)) + (6i.i - (Si)g(xi+i)

H,

B,.,. (4.12)

== Hi+1 +

B,

(Note that if Newton's method excutes at least ktimes, then Hi > O (i <

We should not overlook that we prove Lemma 4.1 without using

prop-erty of (2-SA).

Now, we have following theorem.

Theorem 4.2: If f(x) g ev and g(x) g fi for any x Ef, then Newton's

method terminates in O(log(ev6)) iterations.

Proof: From (4.10) and the property of arithnetic-geometric mean, we

have

Hli+1Bi+1

1

H,B, -<Z-t (4.13)

Since 6ig(x,) > O,

a 2f(xi)

2f(x,) - 6ig(x,)

=H,. (4.14)

Moreover, if Newton's method excutes at least letimes, then Hi > O (i < le) .

Therefore,

Hi --f(x,) - '6ig(xi)

f(Xi-i)

=f(x,)

g(Xz)

g(xi-1)

An Algorithm for Fractional Programming Problems over a Finite Jump System 119

- f(xi)g(x,-i) -f(x,-i)g(x,)

ww g(xi-1)

>l. (4.ls)

-6

Inequality (4.14) and (4.15) implies

1

a2 Hi >- "JGf• (4.16)

While,

62 B,21. (4.17)

Hence, we obtain

a62HiBt2-i}-(2 iB)• (4•18)

It follows from (4.13) and (4.18) that a number of iterations of Newton's

method is O(log(a6)). D

Acknowledgments

The author is grateful to Professor Satoru Fujishige of the Institute of Socio

-Economic Planning, University of Tsukuba for giving useful advices on

this field.

[l]

[2]

[3]

References

K. Ando, S. Fujishige and T. Naitoh: A greedy algorithm for minimizing a

separable convex function over an integral bisubmodular polyhedron. Discussion Paper Series No. 512, Institute of Socio-Economic Planning, University of Tsukuba

(1992), loumal of the C\)erations Research Society of faPan (to appear).

K. Ando, S. Fujishige and T. Naitoh: A greedy algorithm for minimizing a

separable convex function over a finite jump system. Discussion Paper Series No. 554, Institute of Socio-Economic Planning, University of Tsukuba (1993).

120 2ec-itue eg290g

modular polyhedra, Manuscript (1991).

[4] P. Brucker: Networks flows in trees and knapsack problems with nested

straints. In: Proceedings of the8th Conference on Grmph Theoretic Concopts in ComPuter Science (H. J. Schneider and H. Gottler, eds., Hanser, Munich, 1982), pp. 25-35.

[5] R. Chandrasekaran and S. N. Kabadi:Pseudomatroids. Discrete Mathematics 71

(1988) 205-217,

[6] A. Federgruen and H. Groenevelt: Optima! flows in networks with multiple

sources and sinks, with applications to oil and gas lease investment programs.

(iperations Research 34 (1986) 218-225.

[7] A. Federgruen and H. Groenevelt:The greedy procedure for resource allocation

problems : Necessary and sufficient conditions for optimality. Ciperations Research 34

(1986) 909-918.

[8] S. Fujishige: Lexicographically optimal base of a polymatroid with respect to a weight vector. Mathematics of (iperations Research 5 (1980) 186-196.

[9] S, Fujishige: Submodular Functions and ([]iptimization (North-Holland,

darn, 1991),

[10] O. Gross : A class of discrete type minimizaion problems, RM-1644, RAND Corp., 1956.

[11] H. Groenevelt : Two algorithms for maximizing a separable concave function over a polymatroid feasible region. EzaroPean fournal of Ciperational Research 54 (1991) 227-236.

[12] D. S. Hochbaum and S. Hong:About strongly polynomial time algorithrns for

quadratic optimization over submodular constraints. Manuscript (1993). [13] T. Ibaraki and N. Katoh : Resource allocation preblems : A!gorithmic approaches,

MIT Press, Cambridge, MA, 1988.

[14] N. Katoh: Resource allocation problems and applications, Mathematical Science

no. 285 (in Japanese), (Science, Tokyo, l987), pp. 29-34.

[15] N. Katoh: Minimum variance combinatorial problems, In S. Fujishige (eds.)

Discrete stmcture and algonthm I (inJapanese), (Kindai Kagaku, Tokyo, 1992), pp. 111-178.

[16] T. Matsui, Y. Saruwatari and M. Shigeno : An analysis of Dinkelbach's algorithm

for O-1 fractional programming problems, Technical report METR92-14,

ment of Mathematical Engineering and Information Physics, University of Tokyo (1992).

[17] N. Megiddo: Optimal flows in networks with multiple sources and sinks. matical Programming, 7 (1974) 97-107.

[18] M. Nakamura : A-polymatroids and an extension of Edmonds-Giles' TDI scheme. Manuscript (1992).

[19] [20] [21]

An Algorithm for Fractional Programrning Problems over a Finite Jurnp System 121

A. Nakayama : Note on Radzik's Algorithm for fractional combinatorial optim-ization problem. Manuscript (1993).

T. Radzik : Newton's method for fractional combinatorial optimization, Report

No.STAN-CS-92-1406, Department of Cornputer Science, Stanford University

(1992).

A. Tamir : Efficient algorithms for a selection problem with nested constraints and

its application to a production-sales planning model. SIAM Journal on Control and