Separably-infinite programs

Zeitschrift fiir Operations Research, Volume 24, 1980, page 33-45. 9

Wiirzburg.

Separably-Infinite Programs B y A . Charnes, Austin 1 )3), P.R. Gribik, Pittsburgh2), and K.O. Kortanek, Pittsburgh 2)4)

Received May 1979

Summary: Separably-infinite programs are a class of linear infinite programs that are related to semi-infinite programs and which have applications in economics and statistics. These programs have an infinite number of variables and an infinite number of constraints. However, only a finite number of variables appear in an infinite number of constraints, and only a finite number of constraints have an infinite number of variables. Duality in this class of programs is studied and used to develop a system of nonlinear equations satisfied by optimal solutions of the primal and dual programs. This nonlinear system has uses in numerical techniques for solving separably-infinite programs.

Zusammenfassung: Bei den in diesem Beitrag untersuchten separabel-infiniten Programmen handelt es sich um lineare Programme mit unendlich vielen Variablen und unendlich vielen Nebenbedingungen, wobei nur endlich viete Variablen in unendlich vielen Nebenbedingungen vorkommen und nur endlich viele Nebenbedingungen unendlich viele Variablen haben. Fiir diese Programme, die in einem engen Zusammenhang zu semi-infiniten Programmen stehen, wird eine Dualit/itstheorie entwickelt, die Grundlage Ftir numerische Verfahren zur L6sung yon separabel-infiniten Programmen ist.

1. Introduction In some recent applications o f m a t h e m a t i c a l p r o g r a m m i n g in statistics and e c o n o m ics, a n e w class o f linear programs can be defined. These f o r m u l a t i o n s have an infinite n u m b e r o f variables and an infinite n u m b e r o f constraints. As such, t h e y are in the class o f infinite programs [Duffin];however, t h e y possess additional structure. O n l y a

1YA. Charnes, Director, Center for Cybernetic Studies, The University of Texas at Austin, Austin, Texas 78712, USA. 2) P.R. Gribik, and K.O. Kortanek, Department of Mathematics, Carnegie-Mellon University, Pittsburgh, Pennsylvania 15213, USA. a) Research partially supported by the Office of Naval Research, Contract No. N00014-75-C0569. 4) Research partially supported by National Science Foundation, Grant NSF ENG76-05191.

34

A. Charnes, P.R. Gribik, and K.O. Kortanek

finite number of variables appear in an infinite number of constraints and only a finite number of constraints have an infinite number of variables. These programs are closely related to semi-infinite programs [Charnes/Cooper/Kortanek, 1962] which can be considered to be a subclass of this formulation. This class of programs is of use.in the study of the optimal experimental design problem. In this problem, one wishes to allocate measurement resources to points in a given region so that the measurements obtained can be used to make "good" estimates of some unknown constants in a linear regression problem. In Gribik/Kortanek [ 1977, Section 6], this allocation problem is formulated as a linear program in which the Fisher information matrix related to the allocation must satisfy an infinite number of linear inequalities. The information matrix depends upon the allocation via a finite number of linear equalities. If the points at which measurements are possible are infinite in number, the allocation has an infinite number of variables. Thus this linear program is of the class we will examine. There are also applications of this class of programs in economic equilibrium problems.

2. An Expansion of a Semi-inf'mite Program In order to introduce the programs we study in this paper we first consider a semiinfinite program. Program 1: Let S be a set in R k and let u (.): S -+ R n, u n + 1 ('): S ~ R and c E R n . Find V I = i n f c r x

from among x E R n which satisfy u T ( t ) x >1 Un+l(t) for all t ES.

//

The dual we give for Program I uses the concept of a generalized finite sequence space [Charnes/Cooper/Kortanek, 1962]. Denote by R (S) the set of all ?~(-): S -+ R which assume non-zero values at finitely many points only; that is all X (-) with finite support. The vector space R (S) is termed a generalized finite sequence space. If the set S contains an infinite number of points, R (s) is obviously infinite dimensional. The following program is a dual forProgram I.. Program 11." Find VII = sup tEsUn+l(t) X (t) from among X (.) E R (s) which satisfy tES

u (t) X (t) = c

x(.)~>0.

//

The duality of Programs I and II has been studied extensively, [Charnes/Cooper/Kortanek, 1962, 1969; Glashoff]

Separably-InfinitePrograms

35

The programs we consider have characteristics in common with both of the above programs.

ProgramP: Let SC__Rk, QC_.Rl andlet u ( . ) : S - > R n, Un+l('):S ~ R v (-): Q -+R m, Vm+l('): Q ~ R , c E R a, b E R m and A E R mxn Find V e = inf c r x -

~

r~Q

Vm+l(r) ~ (r)

from among x E R n and r/(.) E R (Q) which satisfy ur(t) x >>,Un+l(t) for all t @S Ax+ Z v(r)rl(r)=b rEQ and r~(-)~> O.

(la) (lb)

//

(lc)

If the sets S and Q contain an infinite number of points, Program P has an infinite number of constraints and an infinite number of variables. Therefore, it is an infinite program. However, the constraints (1 a) which are infinite in number contain only a finite number of variables, while the constraints (lb) which contain an infinite number of variables are finite in number. Because of this property, Program P is closely related to Programs I and II and we call it a separably-infinite program. 3. Duality in Separably-inf'mite Programming Proceeding in a formal manner, the following program is obtained as the dual for Program P.

Program D: Find VD = sup ~ Un+l(t ) 2~( t ) - - b T y tES from among )~ (.) E R (s) and y E R m which satisfy ~, u (t) • (t) " A Ty = c tES vr(r) Y >1Vm+1(r) for all r ~ a

(2a) (2b)

and

x (.)/> 0

//

(2c)

Program D is also separably infinite.

Lemma 1: Programs P and D are in duality in that for x, r/(-) feasible for Program P and y, ), (.) feasible for Program D, cTx -- ~, Vm+l (r) rl (r) >~t~S Un+l (t) X (t) -- bTy. rEQ

A. Charnes,P.R. Gribik, and K.O. Kortanek

36

Proof: Using (la), (lb), and (2c), Z Un+l(t ) ~ (t) -- bTy tES ~Un+l(t)

forall t E S ) ,

KQ = (yERmlvT(r)y>~Vrn+l(r)

forall r E O ) ,

CS C__Rn+l is the convex cone generated by

CQ C__Rm+l

1 It,s/u/(1)/ 'rO/u/(it/" is the convex cone generated by

CS and CQ are often called moment cones. The following assumptions are made throughout the remainder of the paper. (A1) Either the set K S is non-empty and bounded, or Un+l(- ) = 0. (A2) The set KQ is non-empty and bounded. (A3) The cone CS is closed.

Lemma2: L e t g E R n a n d h E R . Then(gh) E C s i f a n d o n l y i f xTg>~h forall x E K S.

Separably-InfinitePrograms

37

Proof: Consider the polar cone of CS C~= {( wwn+1 ) W E R n ' w n + I E R I w T d q - w n + I e>~O

t.

Since CS is assumed to be closed, we have (C~)* = CS [Rockafellar, Theorem 14.1 or Stoer/I~itzgal, Lemma 2.7.6]. Thus ( _ ~ ) E C

s if and only if

wTg--Wn+lh>/O

for all

Wn+l E C ~ .

Now CS is generated by

Thus

C~ =

l( wWn+l)

wTu (t)-- Wn+1 Un+l(t) >i 0 for all t E S and wTO+Wn+ll >/0 }

Therefore, we have that ( _ ~ ) E CS if and only if for w ER n and Wn+1 @R,

wTg--Wn+l h >~O

(3a)

whenever

wTu (t) -- Wn+1 Un+l(t ) >10

for all t E S

Wn+1 >i 0

(3b) (3c)

Case1: Un+l(') r 0. Let w ER n and Wn+1 E R satisfy (3b) with Wn+1 = 0. That is wTu (t) >~0

for all t E S.

If w r 0, it is a direction of infinity [Stoer/Witzgal] (or recession direction Rockafellar [1970]) of the set K S which contradicts the assumption that K S is bounded if Un+l(" ) r 0. Therefore, we may divide (3a) and (3b) by Wn+1 to obtain the desired result.

Case2: Un+l(- ) = 0.

A. Charnes, P.R. Gribik, and K.O. Kortanek

38

In this case (3a), (3b) and (3c) become

wTg--Wn+l h ~ O whenever

wTu (t) >I 0

for all t E S

Wn+1 >>-O. These conditions are equivalent to

wig >>-0

(4a)

--h i> 0

(4b)

whenever

wTu (t) >10

for all t E S.

(4c)

If (4a), (4b) and (4c) hold, then obviously

w r g - h f> 0

(Sa)

whenever

(Sb)

wru (t) >i o.

Now suppose that (5a) and (5b) are satisfied by w. Then for any a > 0, otw satisfies (Sb) and so

o~Tg--h>>-O

for all a > 0

or

;rg >0. If we set w = 0, we get --h~>0. Thus (5a) and (5b) imply (4a), (4b) and (4c).

//

Lemma 2 is used in showing that a duality equality exists between Programs P and D under our assumptions.

Theorem 1: If Program P is feasible and finite valued, then Program D is feasible and Vp = VD. Moreover, Program D assumes its supremum as a maximum.

Proof: Program P can be written in the following form: Find Vp = inf z

39

Separably-InfinitePrograms

from among x ER n , ,1 (') ER (Q), z ER, w ER which satisfy uT(t)x>/Un+l(t)

forall tES

(AX)cTx +r~Q \-Vm+l(r)(V(r) ) rl (r) + ( i )

W =

(:/

and 77(-)i>o, w~>0.

//

This is equivalent to the following form.

Find Vp = inf z from among x ER n, z ER which satisfy x EK S z __ c T x ] E CQ .

//

Let us define the set g C__Rn+l

g=

I xEKs

and

7. - - C T X

z