Systems opimization methodology. Part II

satisfying the inequality (6.2) is infinite (countable or uncountable). Since the space D, is a topological space, t h e r e exists a system of neighborhoods of the point 57. Denote by On(to) t h e neighborhoods of this system. In each neighborhood On(tJ) there is at least one point u>, satisfying t h e conditions of (6.2). Consider Dn{ul) = On{U) - O n+1 (S7). T h e r e are two possibilities: a) the number of neighborhoods Dn(Uf) containing t h e points CJ,- is finite; then there is a number A^ such t h a t for all n > N 0n(uj) contains infinitely m a n y points U»J; from these points it is possible to construct the sequence w,-n connverging to the point w, i. e. toln —¥ u. By the continuity of t h e function g1 of w, g' —> g1-; > 0, it ' " n—foo

follows t h a t g —g —)■ a1—— ql- and hence, under t h e assumption t h a t the terms of the sequence are smaller than zero, whereas by the relation (6.1) its limit is greater t h a n zero. This contradictioon proves t h e theorem for the case under study; b) the number of neighborhoods Dn(uf) containing t h e points u>, is infinite; this also permits determination of the sequence of points u>,n converging to w. T h e proof can be completed in much the same way as in the preceding case. In the previous chapters, dual problems were investigated for various models of stochastic linear programming problems and in separate cases analytical criteria were formulated for optimality of solutions. Below are given some findings concerning the issues of existence and optimality of solutions in problems of general form.

6.2. OPTIMALITY

6.2

AND EXISTENCE

OF THE SOLUTION

107

Optimality and Existence of t h e Solution in Stochastic Programming Problems

The issues of existence of the solution and its optimality for stochastic programming problems are discussed in Hanson [1]. We will consider some of the results presented in this work. Suppose the vector Y £Y C Em has a scalar distribution ij){Y), that is continuous and twice differentiable. Let X 6 X C En be some vector minimizing the mean value of the scalar function <j>(X, Y) under two types of constraints: 1) the mean value of the function g(X, Y) in nonnegative for g € Er; 2) the function h(X,Y) is nonegative for h G Es. Both types of constraints are important from the point of view of practical appli­ cations. For example, the former constraints can be viewed as long-term contractual requirements where assumption is made for deviations which, however, in the aggre­ gate cannot be vioalated. The latter constraints may reflect some physical constraints of the system which cannot be violated. Let us formulate the following problem min /4>{X,Y)4'{Y)dY

(6.3)

Y

subject to Jg{X,Y)4>{Y)dy>0,h(X,Y)

>0,X

G X c En,

Y

where , g, h are continuous twice differentaible functions given on S = X x Y. For this formulation of the problem, [1] provides formulations of duality theorem and theorems of necessary and sufficient optimality conditions for vector X. We will provide the proof of sufficiency for optimality of the vector. Note that the conditions stated in the theorem are too strong, which substantially restricts the range of problems under study. T h e o r e m 6.2. Let the above-stated function (X,Y) be convex in X and the above-stated g(X,Y) and h(X,Y) concave in X. Fulfilment of the following conditions is sufficient for X to be the minimizing vector of problem (6.3): 1) there exists A < 0; 2) there exists ft(Y) < 0; 3) 4>x{X,Y)^{Y) + \gx(X,Y)iP(Y)+fi(Y)hx(X,Y) = 0; 4) Xg(X,Y) = 0; 5) /i(Y)h(X, Y) = 0, where <j>x = (-§£-;...; j$;),gx,hx are the matrices of rele­ vant dimensions composed of partial derivatives, while \,fi{Y), are the r-dimensional vector and S'-dimensional vector function, respectively. Proof. Let X* and X be some feasible solutions. Since <j>(X,Y) is convex in X, continuous and differentiable, all the conditions (l)-(5) will be utilized for X from

108

CHAPTER 6. EXISTENCE

AND

OPTIMAL1TY

the theorem. Thus we have: j <j>(X*, Y)i>.{Y)dy > j (4>(X, Y) + (X' - X)x(X, Y)) 4>(Y)dY = Y

Y

= j 4>(X,YMY)

- (X* - X){\gx{X,Y)MY)+t±{Y)hx(X,Y)\

dY

Y

which, by the convexity of functions Xg and /j,h, is not less than > j (X, Y)HY)dY Y

- j Xg{X\Y)

- g(X, Y)^{Y)dY

Y

- j n(Y)(h(X\

Y)-

Y

-h(X, Y))dY = j {X, Y)xP(Y)dY - J Xg(X\ Y

Y)4>(Y)dY-

Y

- f n(Y)h{X*,Y)dY

> /

Y

cj>(X,Y)$(Y)dY.

Y

The latter exactly means that X is the optimal solution. The duality theorem below provides a means of establishing lower limits for the objective function values in problem (6.3). Theorem 6.3. TfJ>(X,Y),4>(Y),g(X,Y),h(X,Y) are the functions defined in Theorem (6.2) and if X is the optimal solution in the direct problem (6.2), then X is also the optimal solution in t i e dual problem: max j (4>(X, Y)i>(Y) + Xg(X, Y)i>(Y) + f*(Y)h(X, Y)) dY Y

subject to j (MX,

Y)4>{Y) + \gx(X,Y)il>(Y)

+ n(Y)hx(X,Y))

dY = 0

Y

> < o , K y ) wiere t i e optimal X and ~p(Y) satisfy conditions (l)-(5) from Theorem 6.2 and tie optimal values of objective functions in both problems are equal. We will consider another existence theorem that has been proved by Stoddart [7]. This theorem is applicable to a sufficiently general system from which the problem (6.1) can be derived as a special case. Consider the probability space (A,S,n). Suppose the probability measure fj, is ordinary with respect to some topology over A. Let R be the closed space in En, and U the closed convex set in Em. Consider the fixed measurable mapping r : A —y R. The real-valued function f(r, u) on R x U is linearly bounded below in U if the inequality f(r(u),u(u)) > p(u) + ug(ui)

6.3.

109

INVESTIGATION

holds for some integrable function p and bounded integrable function g on A. Consider a number of real continuous functions • Em such that 1) U(u>) e U for almost every OJ G A; 2) /gi(r(u>),u(u>))dij. < 0 for each i; A

3) ft.,-(r(w), a(w) < 0 for almost every u £ A and for all j . Furthermore, let <j>(r, u) be some real continuous function on R x U. The solution uQ 6 T is then said to be optimal for <j> in T, if/(it) = f d>(r(ui, u(u>))dn has a minimum in the point U0, i.e., the inequality I(u0) < I(u) holds for all u 6 F. Note that we have the system that is equivalent to Jenson's system if A C E„, r(w) = w and ji = J tpdX, where ip is probability distribution toward Lebesgue measure A on En. The proof of the existence theorem for the nonempty F is based on the assumption of closure and compactness under weak convergence in L\ = Li(A,S,fi). That the function I(u) is semicontinuous below under this convergence is sufficient for existence of the optimal solution in F. T h e o r e m 6.4. Let <j>(r,u) be the continuous real function on R x U that is linearly bounded below and convex in U. Suppose f \u(w)\d)j, is bounded on V and A

e-absolutely ofF. Then, if F / 0

I(u) = J (j>(r(u),u(w))d}i A

has a minimum on T. The key condition in this theorem is provided by the boundedness and e-absolute continuity of / \U(u>)\dfi on T. A

In Stoddart [7] two theorems are formulated to meet this requirement under some conditions. This is true when some real function (u) on U is bounded below and is such that f}U> as soon as \U\ -> co on U, and if f ip(u)dn, is bounded on T. \U\—foo

j^

It is also proved that Theorem 6.4 is true even without assuming the key condition if we take p,-(r(w),u) > i>{u), where ip(u) has all the properties stated above.

6.3

Investigation of one Stochastic Programming Problem

Consider the following economic problem. Suppose the production of products has input values X = ( s i , a 2 , . . .,£„) and provides flexible responses to such random factors as demand, weather and failure of equipment. That is, there are plans for production under various conditions whose implementation is random and continuous.

110

CHAPTER 6. EXISTENCE

AND

OPTIMALITY

We need to find the optimal set of input values X by minimizing the mean value of some cost function under the following constraints: 1) average long-term contractual obligations (supply of raw materials, production of products, profit, etc. ) must be generally met, although short-term requirements can be violated; 2) general physical constraints of the system cannot be generally violated and must be satisfied at each random realization of problem conditions. Suppose the functions presented in the problem can be nonlinear. Then we have the problem formulated as in Hanson [1]: min / (X,Y)ip(Y)dy {Y}

subject to (6.4)

j g(X,Y)j>{Y)dy>Q {Y}

(6.5)

h(X,Y)>0,Vy

where <j>{X,Y) is some scalar function of X 6 En and Y £ Em,g(X,Y) and h(X,Y) are the vector functions from Er and Es, respectively, cj>(X,Y) and components of g(X,Y) and h(X,Y) as well as probability distribution ip(Y) are twice continuously differentiable on S = {X} x {Y} C En x Z5m in all their variables. As indicated above, Hanson provides necessary and, under convexity of the func­ tion <j>(X,Y) and concavity of components of vector functions g(X,Y) and h(X,Y) in X, sufficient conditions for optimality of vector X These conditions seem to be too strong, because in the system M~X,yWY)

+ Xgx(X,y)4>(Y)

+Jl(Y)hx(X,y)

= 0,Vy

(6.6)

each summand depends on the vector-parameter y. We will show that these condi­ tions can be weakened without loss of generality by elementing y from some of the summands. By the properties of functions , g and if), problem (6.1) can be rewritten in equivalent form: find vector x which carries minF(i)

(6.7)

subject to G(X)>0,

fc(jf,y)>o,vr,

(6.8)

(6.9)

where the function F(X) and vector function G(X) are computed by the distribution {Y}, integrals / <j>{X, Y)i>{Y)dy and / g(X, Y)^{Y)dy, respectively. F{X),G(X) {V}

(Y)

and h(X, Y) are also twise continuously differentiable. In this problem, the vec­ tor function h alone is dependent on the vector-parameter Y To reduce problem

6.3.

111

INVESTIGATION

(6.7)—(6.9) to a parametric nonlinear programming problem and derive necessary and sufficient optimality conditions for vector X, the following conditions are said to be satisfied: if r + 5 > n, then at most n components of functions G and h can vanish at any point of the set S. The components Gj(j = 1, J) and hp(p = 1, P) vanishing at some point of the set S are such that the matrix dGj_ dGj_ dhy_ dhp_ 5 X ; ; ' " ; dXi' dX^']~dX~, has a maximal rank. Below is given the lemma which permits derivation of necessary optimality con­ ditions for vector X. L e m m a 6.1. Suppose: 1. there is a region gr{X) > 0,r = 1, M, where gr are reaj functions defined over {X} C En ; 2. gr(X) for any r is twice continuously differentiable on {X} C En; 3. there is a vector X such that gr(X) = 0,r = 1, m; m < n (*) gr{X) > 0,r = m + l , M ; 4. ./;x~(l, ■ ■ ■ , m) =£ 0 for m inequalities of the form (*), i. e. the Jacobian has a maximal rank at the point X. Then for any i 6 l , m there is a point X1 such that ft(X') > 0, whiie gr(X') = 0 for any r = T~m, r ^ 1 and gr{X%) > 0, r = m + 1,M. Proof. 1. Since the functions gr are continuous, for any r 6 m+ 1,M and any e r > 0 there is a vector SCr > 0 such that VX 6 \X - X~\ < Ser,\gr{X) - gr(X)\

< er.

Hence, since gT(X) > 0,Vr = m + 1, M, it is possible to choose Str such that for any

xeSSr

_ 0 < gr(X) - e r < gr(X) < gT{X) + er.

If one has to select min<5..1

=

°roi0,

where 5raia is the l-th coordinate of the r-th vector (the coordinates are all strictly greater than zero), and construct the n-dimensional vector whose coordinates are Jr„i0, then for any x from such 5roi0 neighborhood the inequality gr{X) > 0 holds for any r = m + l,M. The reasoning below applies only to vectors X from the neighborhood denoted as 5{X). 2. Consider gr(X),r = l , m on S(X). Fix some i€ l , m and consider the sys­ tem of m — 1 equalities gr(X) = 0 for any r G l , m , r ^ i. For convenience, the functions are enumerated to fix i = m. From the m-th Jacobian (say, the first m columns of the matrix composed of partial derivaties) we delete row m and column,

112

CHAPTER 6. EXISTENCE

AND

OPTIMALITY

in which an element -J^- is such that its cofactor is not equal to zero. This choice is made possible by the nondegeneracy of the m-th Jacobian. The nonzero cofactor of element jf^- is the Jacobian ./jf(l,..., m — 1) of functions gT(X),r = 1, m — 1. Since the functions gr{X) are continuous in the neighborhood S(X), gr{X) = 0,r = l , m — 1 and ^ r ( l , . . . ,m — 1) is a nonsingular matrix, by the implicit function the­ orem there exists an ^^-neighborhood of the point X = (x m , z m + i , . . . , i n ) C ^n-m+i e n t; r e ]y contained in i X of a suitable dimension such that for any point X = (xm, xm-i,.. ., i n ) from i(X) there are unique continuous functions ipi(X),..., ^ m _ i ( J ) , possessing the following properties: a) Z r = fr(X~), r = l , m - 1; b) for any -Y € J(A') the value A' r ,r = l,m — 1 computed from the formula Xr = fr(xm, xm-i,. . . , i „ ) together with the components of vector X form the vector X satisfying the equations gr(X) = 0; c) in £(X) the functions <pr(X),r = l,m — 1 are differentiable and the derivaties -g^-1 for the given /, I = ra,n are the unique solution of the set of linear equations: m l

- dg'dVr

dg, .

S^;^ -^il = 1'm-L =

( }

**

m

m

3. Let us show that for gr(X),r = l,m there is X such that gm(X ) > 0, and all gr(Xm) = 0 for r = l , m — 1. Suppose there is such Xm Let us fix all the coordinates Xm+l

=

x

m + l j -^m+2 — xm+2

i - - -j ^n — ^ m

in the neighborhood i(X). For the coordinate xm = xm there is the neighborhood (x'm,x^) which is entirely contained in the neighborhood £(X). For any xm € ( i ^ , i j and fixed coordinates £m+i i • • ■ > xn there are X\ = fi(Xm,

Xm+i, . . . ,

X-rn — l — ^Pm— 1 \X-m, X

9i{ )

= gi{f>l,¥2,-

£ m + l , ■ ■ • , XnJ

■ ■,fm-l,Xm,Xm

such that i = 1, m — 1. If these coordinates are substituted in gm(X), any xm 6 (x'm,x'^) we get the inequality

Xn)

+ u

. . . ,Xn)

= 0

then under the assumption made for

7 V^m-l i ^ m i 3-771 +15 ■ • ■ ) ^ n ) ^

0.

Since the last n — m coordinates are fixed, the changes in the functions ip% are all dependent on the changes of the xm coordinates only. Hence for any xm 6 (x' , x" )

6.3.

113

INVESTIGATION

there is gm < 0, while gm(X) = 0 is valid_at the point X. In this case, the total derivative with respect to xm at the point X must be zero, i. e. the equality dfi

dxi dxm

,

dg™d
dgm

d^>m^ _

9xm_i dxm

dx2 dxm

dgn

d

(* * * )

must be valid. Comparing the relations (**) with (* * *) yields the set of m equations in m - 1 unknowns. The vector 3x m '

' dxm

is uniquely determined from the set (**). (**) is a solution of (***) only if (***) is a linear combination of equations from the set (**), Since the coefficients form the Jacobian, the relation J y = ( 1 , . . . ,m) = 0 is valid, which is inconsistent with the condition. Hence the above assumption is valid and there is Xm such that for r = l , m — 1, gr(Xm) = 0 and, additionally, gTn(Xm) > 0. Since the function gm was obtained by renumbering, the statement of the lemma holds for any i = l,m. The above lemma can be obtained as a direct result of the implicit function the­ orem by introducing an artificial variable. The following assertion yields the necessary conditions for existence of the solution in Hanson's problem. T h e o r e m 6.5. For the vector X to be the solution of problem (6.4), it is necessary that there be the r-dimensional vector A < 0 and s-dimensional vector function u\(Y) < 0 such that

f,,i,tl0,(wWifl

- "su^wjsaa. o (6,o) \G(X)

u.(Y}h(X,Y)

= 0 = 0>Vy

(6.11) (6.12)

where FX(X) = ^ ^ i s a vector a n d G * W = ^5T^. M X . Y) = ^ x ^ are the matrices of partial derivatives computed at the point X. If in problem (6.4) the function 4>{X ,Y) is convex, while components g}(X,Y) and hi(X,Y),j = l,r,/ = 1,5 are concave in X, then the necessary conditions are also sufficient. Proof. Necessity. Instead of problem (6.4) we will consider the equivalent problem (6.7)—(6.9). Let X be the optimal solution of problem(6.4). Then it is also the optimal solution of problem (6.7)—(6.9). Introducing residuals, the theory of Lagrange multipliers can be utilized to show the necessity of conditions (6.10)—(6.12). The nonpositivity of A and fJ,(Y) can be obtained by the Taylor expansion theorem. Let { = ((1(1 ■ ■ ■, (h f and r,(Y) = {f]f(Y),..., ^(Y))7 be r-dimensional vector and 5-dimensional vector function such that G(X)

- e = o,

114

CHAPTER 6. EXISTENCE h(X,Y)-v(Y)

AND

OPTIMALITY

= 0.

Let us construct the Lagrange function: L (X, A,/*(y),£, ij(y)) = F(Jf) + A (G(X) -0+

fi(Y) (h(X, Y) -

V(Y)).

The extreme points of the objective function in problem (6.7)—(6.9) are among the stationary points of Lagrange function. Partial derivatives are taken with respect to all the variavles vanishing at the point X. Thus we have dLdF(X)+x8G(X)dh(X,Y)^

OX OX

OX OX

OX OX

(6.13)

OX OX

| ££ == Gm Gm -- ee == 0,0, ((*)g * ) g == 2A.6 2A.6==0,* 0,*= =T7rT7r

MX y) vhY) 0l (

= ** } ^) = 2MYMY) = 0'l = zrs-

oik) = ' -

r)T.

Comparing equation (*) with (**) permits elimination of variables £,• and rj\(Y). We get the conditions A,G,(.Y) = 0 and {X\(Y)h,i(X,Y) = 0 or £ A 8 G , ( X ) = A G ( Z ) = 0,

YlMY)hl(X,Y)

= ^(Y}h(X,Y)

= 0.

1=1

The last two expressions and relation (6.13) are the conditions (6.10)—(6.12) from the theorem. We will show the nonpositivity of A and fi(Y). From the conditions (*) and (**) it follows that if Gi(X) > 0, then the corresponding A, = 0 also for hi(X,Y) in a similar manner. If some component of vector constraints (6.8)—(6.9) vanishes at the point X, we consider how the vector X changes to some adjacent feasible point X" Let us employ Taylor theorem to the first order with the residual term of a higher order e(X", x) = e. We have

F(X*) + v(Y)h(X; v(Y)h{x; y)-{F(X) + fi(Y)h(X F{X*) + + XG(X") XG(X') + - (F(X) + + \G(X) XG(X) + ^(Y)h(X, t >Y)) - ) ) == y) : (X* ~ X) d

If,;

= (** -X)( -m Hence

\ \

OX OX

F(X*) - F(X) = -XG(X')

dG

(X)

+

dh(X,Y

Xd-^l+ KYf-^) ' 8x Ox

Ox

- XG(X) - fi{Y)h{X\

= -[XG(X)

+

l

h~ +e

= ,

]

y) + »(Y)h(X,

v{Y)h(X\y)-S\.

We now take the feasible solution X* so close to X that:

y) + e =

6.3.

115

INVESTIGATION

1) £ has no effect on the sign of expression in square brackets and 2) all zero" components of the constraint vector (6.8), except the z-th component, and all zero components of the constraints vector (6.9) keep their values unchanged. This choice of X* is possible, because the conditions in problem (6.7)—(6.9) satisfy the preceding lemma. The signs of expressions [F(X*) - F(X)] and [-X,Gt(X*)} are equivalents. Theorefore, if by choosing X", Gi(X') > 0 and X supplies a minimum to the functional (6.7), that is, F(X") - F(X) > 0, then A < 0. Since any index was taken from zero components, the entire vector A < 0. In a similar manner it can be proved that )J.(Y) < 0. Sufficiency. Suppose there are A < 0 and /i(V) < 0 such that the conditions (6.10)—(6.12) are satisfied. The continuous X-convex function <j>[X,Y) integrates over the region {V} to produce the A'-convex founction F(X). This also applies to the concavity of components of vector function G{X). When the conditions (6.10)— (6.12) are satisfied, by the properties of functions F,G and h, we have the following system of relations:

F(X) > F(X) + (, - I ) M 1

= F(X)

U9^!

-{x-X)

> F(X) - A (G(X) - G(X)) - v(Y) (h(X,y) = F(X) - XG(X) - v(Y)h(X,y)

+

«Y)BJ&*>) >

- h(X,y))

=

> F(X).

Comparing the beginning and the end of the system of relations, where X is any feasible solution, we find that X is the point of minimum. Hence the set of equations (6.10)—(6.12) provides n-\-r-\-s specific, necessary and, in the case of convex programming, sufficient conditions to solve problem (6.4) in terms of problem (6.7)—(6.9). The number of unknown components of vectors X, A and fi(Y) is also n + r + s, in which case the inequalities A < 0 and fi(Y) < 0 for each Y change problem (6.4) to a typical nonlinear programming problem. In contrast to the conditions of Hanson problem, here the augend and addend from the conditions of (6.10) are no longer dependent on Y The vector function /J.(Y) is still dificult to determine. We will give the theorem which, under the conditions stated in problem (6.4), follows from the optimality of vector X and new necessary conditions for optimality. T h e o r e m 6.6. Suppose X is the optimal solution under conditions of problem r (6.4), and let

dF(x) OX dx

! ,dG(X) OX dx

Q

(*)

for some y = Y\ Then /i(Y) = 0 for any Y Proof. Let X be the optimal solution in problem (6.4). Then there are A < 0 and fi{Y) < 0 such that the necessary conditions (6.10)-(6.12) are satisfied. Since the system (*) is independent of Y, there must be

p[Y)—w~— = 0,Vy

116

CHAPTER 6. EXISTENCE

AND

OPTIMALITY

From the necessary conditions of (6.10)—(6.12), and from the nonpositivity of ji{Y) it follows that if h,(X, Y) > 0, then i*(Y) = 0, and if hi(X, Y) = 0, then m{Y) < 0. If for the last i there is at least one component w(Y) < 0 with some Y, this would mean in accordance with (*) that the linear combination of gradients for the functions hi(X,Y) vanishing on ~X must be zero, i.e., the gradients must be linearly indepen­ dent. This assertion seems contrary to the condition. Hence fj,i(Y),i = l , s are all identically zero for any Y Note that the conditions (6.10)—(6.12) permit formulation of the dual problem. It can be shown that for the covexity of F(X) and concavity of components of G(X) and h(X, Y) there is a theorem that is equivalent to the Kuhn-Tucker saddle-point theorem. In this case Slaytor's condition follows from Lemma 6.1, because for nonzero components of constraints (6.8)—(6.9) there is a neighborhood of the point X, at which these components are strictly greater than zero, and for the other components it is always possible to take a linear combination of suitable points X' from Lemma 6.1 to be the interior point for the convex region of admissibility. In applications, however, this approach to solving problem (6.4) involves compu­ tational difficulties and, additionaly, the imposed conditions are very strong. Conditions (6.10)—(6.12) generally provide only stationary points in which case for each stationary point one has to determine (i(Y) for all y 6 V The solution of the system of equations (6.10)—(6.12) depending on the vector Y generally involves serious difficulties. Furthermore, the range of problems becomes narrow if the functions are all re­ quired to be twice continuously differentiable with respect to all variables.

6.4

Definition of the Set of feasible Solutions in Hanson's Problem

Utilizing the specific features of constraints as in (6.9), we may, in some cases, elimi­ nate the dependence on parameter Y from problem (6.4) and define the set of feasible permanent solutions FJ- The set of feasible solutions S for problem (6.4) then is the intersection of the set of feasible X from constraints (6.8) with the set of feasible permanent solutions F] from constraints (6.9), i.e.

S = Uf){X:G(X)>0}. Consider some specific cases, where the analytical character of the functions hi(X,Y) or the economic sense of random values allows one to find the set F] f° r constraints of the form (6.9). Let us consider I I = {X : X € fl {h(X, Y) > 0}} = | A ' : H(X) = r min } h(X,

Y)>o\,

where H(X) and h{X,Y) are ^-dimensional vector functions. If the set \\ is convex, while Gi(X) are all concave, then the nonempty intersection of S also is convex. But

6.4. FEASIBLE SOLUTIONS

IN HANSON'S

PROBLEM

117

in the general case T\ is not convex, and components of H{X) are not continuous functions in X. In all cases the set of feasible solutions S is assumed to be nonempty. Let L be some subset of indices i = l , s uniting the constraints from (6.9) by some common property. In contrast to the constraints in Hanson's problem, the only requirements here are that hi(X, Y) are all continuous for any i — \,s and the condition X > 0 is satisfied at all times. Let \\{L) be the set of feasible permanent solutions for constraints with indices / 6 L and let n(L) be the set of feasible solutions for the other constraints of the form (6.9). 1. Let L be set such that for any / 6 L : hl(X,Y)

=

h'1(X)h'2(Y),

i.e., h'(X,Y) can be represented as the product of two analytic functions, if L = Ly U L 2 U L 3 it follows that: a) if for all l\ g Li the inequality /i2' (V) > 0 holds for any Y, then the relevant constraints hll{X, Y) > 0 can be replaced by constraints hll(X) > 0; b) if for all l2 6 L 2 the inequality h2(Y) < 0 holds for any Y, then the relevant constraints h'2(X,Y) > 0 can be replaced by inequalities h'2(X) < 0; c) if for any I3 € L 3 there are 3/1,3/2 such that h2{y\) > 0 and h2(y2) < 0, then the set of feasible solutions is determined from the condition h^(X) = 0. So we have

Yi(L) = [ x : x e n (Mi(A-)>o)}n n(-Y:A'e n (M 2 po
(6-14)

2. Let L be a set such that for any / G L there is h'(X, Y) = fej(X) + k'z(X) can be represented as the sum of two analytic functions. In this case, the relevant constraints with indicies from (6.9) can be replaced by the following conditions: h[(X)>-mmh'2(Y),Wle-L

J[(L) = L

.Xef]

[h[(X)

> -rmn4(n}|

(6-15)

3. Let L be such that for any / € L there are linear inequalities, i. e., AX — 6 > 0, where A is an I x n matrix and some or all elements of matrix A and vector b are random and finitely distributed, i.e., there are optimistic and pessimistic limits for changes in the values. These random elements form the vector Y Introducing A~ and b+, where random elements are replaced with their pessimistic and optimistic

118

CHAPTER 6. EXISTENCE

AND

0PT1MAL1TY

limits, respectively, the set of feasible permanent solutions LI(L) can be determined for the group of constraints L as follows: Y\(L) = {x '■ AX ^ fe+}> w n i c h follows from the set of inequalities A(u)x > AX > b+ > b(u), where the X satisfying the (•') (•) M inequality (*) satisfies the inequality (**) as well. 4. Let L be such that for any / € L,h'(X,Y) are quadratic in X, i.e., these functions can be represented as h'(X, Y) = XTH,X

+ p,X - b'; I € L

where some or all elements of matrix Hi, vector pi and component b ,1 £ L, are random, finitely distributed values. They determine the components of vector Y So for the constraints I 6 L we have: U(L) = Ix

X : X G fl

X

: X ef]

{minh'(X,Y)>0

min [XTH,X

+ p,X - b, > 0

■■Xtf) l ^ f E E A i i ^ y + E p W - 6 ' ^ 0 ) } }

(6-16)

Since the function between the inner brackets is linearly dependent on the com­ ponents of vector Y, the minimum can be achieved on the boundaries of the feasible region, in which case x,x3 > 0 and

U(L) = \x . x e n (EXX-**; + tp'f*i -*t > o Alternatively, U(L)

= \X

I

:X e n

V(£L

{A'T//"X + P r ^

> 6f}[

(6-17)

J

Ifffj""are all nonpositive definite matrices, then the nonempty set n ( L ) is convex. 5. Let L be such that for any / € L h'{X, Y) is concave in X. Then it immediately follows that the nonempty set Yl(L) is convex because the relation h'(X, Y) > 0 holds for any Y Here the problem is to determine boundaries for t h e convex region of ]1(L). If there exists a boundary or part of it, then it can be determined from the condition h'{X,Y) = 0. Note that in all cases we have n = n ( £ ) n n ( £ ) - If II and subsequently the set S are composed of a number of incoherent sets of feasible X, then problem (6.4), has to be divided into subproblems with the same objective function (6.7) given on these sets Sk(k = 1, K). In problem (6.4), the minimum can be obtained from the relation F(A) = m i n t e T ^ m i n S t F ( A ) .

Chapter 7 Stability of Solutions in Stochastic Programming Problems 7.1

Stability of Solutions in Stochastic Linear Programming Problems

The issues of solution stability in mathematical programming problems are addressed from various points of view and in a variety of ways. The literatures on solution stability choose the conditional extremum as a random point, the optimal basis as a set of vectors, and the optimal value of objective function as a random value. Such a choice determines introduction of different stability concepts. In some literatures, the stability issue is dealt with in stochastic and parametric terms as well as in terms of the error theory. The solution stability is crucial for stochastic programming problems, because here the parameter values are random. We will consider some issues of existence of solution stability regions for stochastic LP problems. Let us introduce the following concepts: 1. Feasibility region. Consider a fixed realization of random event ui0 6 fi. Suppose we have a deterministic LP problem of the form min C(u>o)X.

(7.1)

Let lk(k = 1,2,..., Kwa) denote the extreme points of the convex set S(LO0), each of which is produced by intersection of n cutting planes, where KWa is the total number of extreme points when LO0 € fi random parameters are realized. The region Vj^ C fi is called the feasibility region of the point If. if for any w 6 V^o the intersection of the cutting planes producing this point determines an extreme point of the corresponding set S(ui). 2. Optimality region. Let l^0 be an optimal extreme point of problem (7.1), i.e., for any k / k0 Z* > Z*°, where Z* is the objective function value of problem (7.1) 113

120

CHAPTER

7. STABILITY

OF SOLUTIONS

IN SPP

at the extreme point I}.. The region W** C Vk° is the optimality region of the point lko if for any u G W* Zkw > Zk" (ft = 1,2,... ,ft„;ft = k0). L e m m a 7 . 1 . The function Zk is the continuous function of ui for any extreme point Ik. Proof. The functional value at the extreme point Ij, of the convex set S(u>o) for the fixed realization o>0 G 0 is Zko = c\x\k + c°2x°2k + . . . + c°nx°nk, where xf are coordinates of the extreme point. Denote by xok nonzero values of x° ■ These values are determined from the relation DokXok = 6°, where D0 is the relevant basic matrix. By the nonsingularity of this matrix, the values x?k are continuous functions of a°- and 6°, respectively, Z* is a continuous function of u> G Q. We will prove that for any u0 6 fJ there exists a stability region of Wua such that for all u> G Wwo the corresponding problem (1.1) has the same optimal basis. T h e o r e m 7 . 1 . Let

zt0 > zli (ft = I X : ; k ± k0) at the point w0 E H. Then there exists a neighborhood 0(OJQ) of the point u>0 such that for all u> G 0{ui0) C tt

Zt > ZkJ

(k = I X ; k ± ho)

Proof. At the point u>o E fl Zl - Ztl > 0.

(7.2)

By Lemma 7.1, the functions Zk and Zk° are continuous in w, hence their difference also is a continuous function. From the properties of continuous functions it follows that there exists a neighborhood O(uio) such that for LO G 0(U>Q) the inequality (7.2) is preserved, i.e., Zk > Zk°. [1] shows the ways of obtaining boundaries for parameter variations in LP problems to preserve the optimal basis. [17] and [20] prove the existence of stability regions at any point w € SI.

7.2

e-stability of solutions in t h e mean

Unlike Tintner,N.I.Arbuzova and V.L.Danilov [1], [2] considered one fixed point in space J7, i.e., the point To whose coordinates are expectation for random parameters of problem conditions. The authors obtained conditions under which the optimal basis of problem continues to be optimal for all LO G fi except the subset of a specified measure e < 0. DEFINITION. The solution of stochastic LP problem in the mean is called stochas­ tically stable in module e (e-stable) if the optimal extreme point of problem in the mean continues to be optimal for any realization - of random parameters except the set of measure e.

7.2. e-STABILITY

OF SOLUTIONS

IN THE MEAN

121

N.I.Arbuzova and V. L. Danilov concentrate on a special case of stochastic LP problem, where the vector b(u) alone is random and, additionally, its components are indipendently distributed. Denote by 6; the expectation of a random variable 6j(w), and by of its variance. DEFINITION. The hyperplanes, whose intersection produces the optimal point of problem in the mean, is called labelled. Let the boundary hyperplanes of the con­ vex set 5(57) be all enumerated, and let ki,k2,. . . ,kn be the numbers of the labelled hyperplanes. The extreme point is determined by intersection of the hyperplanes, and its mo­ tions are dependent on realizations of the vector b(uj). The set of n-dimensional Eucledian space, in which the point may fall with probability greater than (1 — (l//2))™, is an ellipsoid with its center at the point corresponding to the optimal solution in the mean. Here / is determined from the inequality (1 — (l// 2 ))* 1 > 1 — e. The axes of this ellipsoid of concentration are obtained in the following way: at the point 57 G f! we consider the intersection of n — 1 hyperplanes from n labelled hyperplanes which is geometrically a straight line. On this line, we separate on either side of the ellipsoid center the value toa^ , where kj is the number of the labelled hyperplane, which does not belong to this intersection, and <7t is the mean square deviation of the random variable on the right-hand side of this hyperplane equation. From the independence of components bj(u) and Chebyshev inequality follows

p {n |6s(u) -l~\ < to} = T[p{\b>(") - £ | < to} >II (l - jj) = (l - £ f (7.3) The value of / can be determined from the inequality

/

1

1,m

I - -P)

>l

~

-e,

(7.4)

where e is a sufflcently small number. DEFINITION. Constraints of the form a,.x < 6, — loi(i = l,ro) are called lower constraints, and those of the form a^X < b, + la, (i = l,m) are called upper con­ straints. Suppose the intersection of lower constraints and a positive hyperoctant is not empty.This means that any realization of vector b(u>) (except the set of measure e) there is at least one feasible solution. Using the above concepts, we formulate without proof the sufficient condition for the stochastic £-stable solution in the mean. T h e o r e m 7.2. For the solution in the mean to be e-stable, it is sufficient that the ellipsoid of concentration does not intersect lower constraints except the labelled ones. For the convex programming problem, the e-stability signifies the constancy (with probability 1 — e) of the basis of labelled normals, by which the vector is decomposed with positive coefficients. Following N.I.Arbuzova, this definition of e-stability is hereinafter referred to as basic.

122

CHAPTER

7. STABILITY

OF SOLUTIONS

IN SPP

DEFINITION. Suppose that for edl wmode the set of optimal solutions H(u) belongs to the &-neighborhood of the set Hip), i. e., for any X°(u), there is X°(U) such that \X°(LJ) - X°{ZJ)\ < S.

It this case, the stochastic programming problem is called solution-stable with char­ acteristics e, S. Suppose the problem is basis-stable mod e and has a unique optimal solution for u = U, Then it is possible to find a distribution of the optimal solution X°(to) = = (I 1 (UI), X2(UJ), . . ., Xk{u>), 0 . . . 0) over the set of measure 1 — e, and a distance dis­ tribution \X°(u>)-X°(uJ)\. For any S there is S\ = p{\X°{u) — X°(ZJ)\ > S}, and the problem becomes solution-stable with characteristics s + E\, 5. In some practical problems, the final criterion for stability is provided by devia­ tions of the optimal value of the objective functional. For this reason we introduce the stochastic stability concept of convex programming problem, in which the issue stability is considered from this point of view. DEFINITION. For any ujmode, let \C{LO)X - C{u)X\ < 5; then the problem is called functionally stable with characteristics e, S. If the problem is e-feasible, 5-stable, then by the continuity of the objective functional in all its independent variables there is S such that the problem is e-functional, S-stable. Following [3], we formulate some propositions. T h e o r e m 7.3. For the solution in the mean X*(U)

= (x*(Z3),x*fi),...

,xl{u),0,...

,0)

to be e-stable, it is sufficient that Y17L\ of < ed2, where d is a minimal distance from the point U to the boundary hyperplanes of stability region W-g C fi. Proof. If DZJ is the k x k basic matrix corresponding to the solution in the mean, then the nonzero components Xj(tj)j = l,k of vector X*(LO) are determined from the relation X"(UJ) = D^ b(ti), where b(iJJ)T = (&i(w),..., bk{ui))T Additionally, in the stability region, the solutions in the mean coordinates of the intersection point of labelled hyperplanes x](u>) are determined from the same relation %{u) = or

m

D^b(u) D

^ » =B-1)'+J^.H,

J = hk,

(7.5)

where A is the determinant of matrix D, and D, ; is the minor of this matrix element d^. The stability region of the solution in the mean W^ coincides with the feasibility region of this solution in space 0. On the other hand, the intersection point of labelled hyperplanes X(OJ) is no longer feasible if it lies on hyperplanes of the form

7.2. e-STABILITY

OF SOLUTIONS

123

IN THE MEAN

di.x = b'(i > k) or x3 = 0(j < k). By the relation (7.5), this is equivalent to the fact that bi(u>) satisfies the inequalities k

k

6 , H A - £ a t J £ ( - l ) ^ ' D , A M = 0, i>k, i=l

(7.6)

e=l

E(-1)' +J .D^,H = 0, ,'
(7.7)

!=1

Hence the stability region Ws of the solution in the mean is determined by the intersection of m hyperplanes of the form (7.6)—(7.7) in the m-dimensional space fi. If the equations (7.6)—(7.7) are normalized and contain b{ instead of 6,-(w), then they provide the distance from the point Xo of space R to the hyperplanes determined by (7.6)—(7.7). Denote these distances by di,d2,. .., dm and define d = min,d\

(7.8)

<e.

Show that 23™-i erf < ed2 implies (8.8). By Chebyshev inequality and properties of expectation, - i i , we have

E['\b{u)-b?\ I1 |2 1 T 1 \b(u))-b\ Pi 'J |6(w)-6 >d\ >d\ < - J d22 1 d

E ( E , (&.-(«) v \ 22

-tf)

d rf

Er =1 E (6,-(W) --5)'.

Em, °

d?

d22

-£'

This completes the proof of the theorem. In [3], the necessary and sufficient condition is derived for the e-stability of the problem ma,xCX,AX 0 with the random first column of matrix, i.e., the problem max CX, Pl(uj)xl + P2x2 + ... + Pnxn < B;

__ Xj > 0,j = l,n.

(7-9)

The elements of column Pi{u>) are random independent variables an(u>),a21(uj),. .. . . . , amj(u>). Suppose problem (7.9) has a unique optimal solution in the mean X*(UJ) with a positive component x\(lo). The proposition is to transform variables Y = 1

xx22

xn <£n

1 / 2 == — ; • ■• •■; ;yn~y\ --== —; — ; --2/2 yn =- — X! Xi X1 Xi X\ X\

124

CHAPTER 7. STABILITY

OF SOLUTIONS

IN SPP

Then (7.9) becomes a fractional programming problem: f m a x Cl + CW + ■ ■ ■ ± C ^ Jl I [ -By, + Pm + ... + Pnyn < - P i H ;

(7.10) y, > 0, j = l,n.

In problem (7.10), the column containing free terms of the set of conditions is random. The solution of (7.10) in the mean exists because X*(UJ) > 0, y" = ip(X*); the e-stability of (7.10) implies the constancy of the set of labelled indices with probability 1 -£.

The equivalence of £ stability is proved for problem (7.9) and (7.10); the necessary and sufficient condition for e-stability is derived for problem (7.10). Let us consider the dual problem to (7.1) with a random vector 6(w) max YTb{u),

(7.11)

where T = {Y : YTA < C{Y < 0)}. It turns out that the e-stability condition we have obtained for the direct problem also ensures the e-stability of the solution in the mean Y for problem (7.11). This assertion follows from the lemma. L e m m a 7.1.Suppose the problems (7.1) and (7.11) have a unique optimal solution for all UJ 6 fi (except for the set of measure e). Additionally, let the solution in the mean X of the direct problem be e stable. Then the solution in the mean X of the dual problem is also e-stable. Proof. Let WZJ C O be the e-stability region of the solution in the mean of problem (7.1). The problems (7.1) and (7.11) have a unique optimal solution on the set WZJ. The point of intersection of the hyperplanes labelled with numbers i j , . . . ,ik,ji,- • ■ ,ji is the optimal extreme point for any n = k -f 1. By the continuity of the solution n = k + l, the duality theory implies that the labelled hyperplanes in the dual problem are the hyperplanes designated with numbers ik+\,. ■ ■, im, ii+i, ■ ■ ■, j n - The set of labelled hyperplanes for any w S W„ in the direct problem is the same, and hence the set of labelled hyperplanes in the dual problem is constant. Since the optimal solution of problem (7.11) corresponds to the intersection of these hyperplanes, the solution in the mean Y is e-stable. We will now consider some special cases of determining solution stability regions for linear programming problems with random data. In problem (7.1), only the vector b is assumed to contain random components. Suppose the problem is solved at the point u>i G $7. Denote the optimal solution

jf(w l ) = (ii(wi),...,*;(«!), o,...,o). In this special case of LP problem, the stability region coincides with the feasibility region. The feasibility region is determined by the set of inequalities 6,HA-^a„X(-ir 3=1

v=\

+ 1

^^H>0,

^>k;

(7.12)

7.3. STABILITY

125

OF SOLUTIONS

B-ir+^&.H > o, j< k. i=i

To ascertain the belonging of the point w2 to the stability region WUI is to find out whether the vector coordinates b(ui2) satisfy system (7.12). But such verification requires substantial computations. One may try to find the subset of stability region (7.12) which allows to ascertain geometrically whether the vector b(u>) belongs to the stability region. Denote by d a minimal distance of the point u from hyperplanes of the form (7.12). Let us solve the equation m

J2(b,(^)-b1(i01) + af = d for a, i. e., we have a = (d/y/m). Then the rectangle [&,-(wi) — i 6 fi the optimal extreme point is the point l0 with (x°,..., i ° ) coordinates. To find out under which realizations of the random vector c(w) this point is optimal, we consider n adjacent extreme points whose coordinates are denoted as (x{,..., x3n), j = 1, n. Then the stability region is specified by the set of inequalities s?ci(w) + . . . + x°nCn(oj) < sici(w) + . . , + x{cn(u).

(7.13)

As before, it is possible to find in this stability region the set which allows to ascertain geometrically whether the vector c(ui) satisfies system (7.13). A more general case is considered. Let o»i € fi be a fixed point; then hyperplanes are of the form at,(ui)X = b^Wj), i = 1, m. Find all the extreme points of the convex set determined by the intersection of these hyperplanes with a positive hyperorthant. Denote the coordinates of these points by {x\{u>\),..., x3n(cji)), j — l , ^ , where kui is the total number of extreme points. Let lB = (x°(u>j),.. ., i°(wi)) denote an optimal extreme point. The stability region then is determined from the system of inequalities: clx<{(u + ... + cnxl(Lo)
j =IX-

(7-14)

This system differs from system (7.13) in that involved here are not only the adjacent points, but all extreme points. Additionally, in (7.13) the coordinates of extreme points are the same for all w G fl, whereas in (7.14) they vary with realization of random data.

7.3

Stability of Solutions to Stochastic Nonlinear Programming Problems

In applied problems of stochastic programming, random parameters have optimistic and pessimistic boundaries for their variations, i.e., random variables are distributed

126

CHAPTER

7. STABILITY

OF SOLUTIONS

IN SPP

in a finite (continuous or discrete) way. In such cases it is possible under certain conditions to determine the range of the objective function and localize the set of optimal solutions for all realizations w € fi. Suppose we have a stochastic programming problem, in which the objective func­ tion f(X,u>) = f(X) is a continuous deterministic function, and the functions defining the problem conditions gi(X,u>), Vz = \,m are quadratic or linear in X with nonpositive definite matrices Hi(cj) for any realization to € fi , i. e., we have the problem min f(X)

)

J \ i subject to XxTHj(u>)X + p,{u>)X - bi(u>) > 0, i = 1, m ( T n subject to Xv H-*i(u)X + pi(ui)X-bi(uj)>0, i = T~^ >

X > 0,

(7.15; (7.15)

J

where all the elements of matrices H,(UJ), vectors p,(oj) and componentsfe;(u;),i = l,m can be random. Let us introduce the following sets: S(u)=

{X :XTH1{LO)X+P,{OJ)X>

S~ = [X ■ XTH~X T

+

S+ = {X : X H,

+ p~X > b+,

X + p+X>b-,

bi{u>), z > 0 , X>0, X>0,

»=T~m},

i = I~^} , i = T~^},

where in fl/, pf, bf, H~, p~, b~, i = 1, m random variables representing realizations of vector LO are replaced by optimistic and pessimistic boundaries, respectively. We have the following statement. T h e o r e m 7.4. If the set of permanent solutions S~ is nonempty, then the fol­ lowing relation holds for the objective function of problem (7.15): min f(X)

< m^fiX)

< mm f(X).

(7.16)

Proof If is sufficient to show that S+ D S(u) D S~, whence it follows that the minimum of continuous function in some set is less than or equal to the minimum of this same function in any part of this set. If X € S~, it follows that for all random realizations u> and with Vi XTH+X+p+X +P," 1

> XTHi{u)X + pi(u))X > XTH~X+ (...) (..) > K > bAu) > b~, X > 0. (.) (,.) (...)

From this it follows that any feasible solution from S~ satisfying inequality (*) also satisfies inequality (**), i. e., 5(w) D S~. Additionally, any feasible solution from the set S(u>) satisfying (**) also satisfies (* * *), i.e., S+ D S(LO). Finally, S+ D S(u) D S~

7.3. STABILITY

127

OF SOLUTIONS

and if S~ ^ 0, then the expression (7.16) from the conditions of the theorem is meaningful. A symmetric theorem can be formulated for the max problem. Corollary. Suppose we have a quadratic programming problem, i. e., in problem (7.15) f(X) = f(X,uj) is a random X-quadratic function with a nonnegative definite matrix H0(UJ) for VCJ

= XTH0(UJ)X

f(X,u)

+poM-Y + 6o(w)

where among the elements of H0, po and b0 are random components with finite dis­ tribution. Then the expression (7.16) from Theorem 7.4 becomes f-(X-)

= mm f-(X)

< mm f{X,u)

< min f+(X) = f+{X+),

where X~ and X+ are optimal solutions for respective sets S+ and S~, while f~(X) and f+(X) are objective functions, in which random data are replaced by their pes­ simistic and optimistic boundaries, respectively Proof. In accordance with the statement of Theorem 7.4 the system of mutual inclusions S+ D S{u) D S~ is valid. If X (w) is the optimal solution of problem (7.15) for realization of u>, then for any ui f-(X-)

= X-TH;X-+P;X-+bv QT

= X {U)H0{U)X°{LO) T


< X+ H+X+

+ bo(w) <

+ p+X+ + 6+ =

f+(X+).

whence comes the required result. Introduce the set S~= [X : XTH~X

+ p~X >bf,X>Q,

i = TTT^}

Theorem 7.5. Let the functions gi(X,u), i — l,m in problem (7.15) be concave or linear, the set of feasible X S~ nonempty, and the set S+ bounded. If the objective function of problem (8.15) is concave and deterministic, then for any to there is an optimal solution X°(u>), which does not belong to S>, and the set of all such optimal solutions satisfies the conditions

{x»}

C A S = S+\ S~

Proof. Since the minimum of the concave function f(X) on the boundary is not less than the minimum of f(X) inside the convex region of feasible solutions, by the continuity of f(X) and by the closedness and boundedness of the region of feasible solutions for each realization of u there exists a boundary point X°(UJ) such that f(X°(uj)) < f(X(u)), \/X(LO) e S(u). This means that for each realization of w at least one of the inequalities gi(X,ui) > 0 or Xj > 0 becomes an equality, i. e. either X0T{io)Ht{uj)X°{u)

+p,(u)X°{u)

= b,(u,)

128

CHAPTER

7. STABILITY

OF SOLUTIONS

IN SPP

for some iu or z°Aui) = 0 for some j w . Such X°(u>) does not belong to S>, because t h e set 5< includes none of the X which could transform some constraint of problem (7.15) into a equality. But 1 " ( C J ) £ S+, because S+ includes all feasibility regions for any realization of w, and hence

{*V)}Vw o s+\ f If in Theorem 7.5 t h e objective function of problem (7.15) is convex, while the absolute m i n i m u m does not belong to any feasibility region S(OJ) for any UJ, then Theorem 7.5 is also valid. T h e proof can be carried out in much t h e same way as above. Theorems 7.4 and 7.5 are generalizations of the findings in [21], where only linear functions in t h e original problem are considered. The s t a t e m e n t below refers to a special case of stochastic programming problem. T h e o r e m 7.6. If in problem (7.15) all the functions are linear in X and only the vector b(u) has random independent components that are finitely and continuously distributed, then the set of optimal solutions {A°(w)} V u / from Theorem 7.5 is convex. Proof. Let S(UJ) be t h e region of feasible solutions for realization of a;. Let X°(LJ\) and X°(u>2) be optimal solutions for any two realizations, u>i and u>2, i- e. /(A'V,))
V A > , ) e 5(Wl),

/ (x0(u2))

VA>2) e

From AX"(ui) > 6(wi), M > A, 0 < A < 1 t h a t

< f (A>2)), 2

)

a

> b{to2), X {ujx)

S(LO2).

> 0, X°{u2)

> 0 it follows for any

A ( A A ' V i ) + (1 - A)X°(«4)) > A6(w,) + (1 - A)6(w 2 ), X° = \Xa{w1)

+ (1 - A)X°(w 2 ) > 0.

The vector X° is a possible realization because of t h e independence and continuous distribution of random variables. This vector is optimal because by t h e linearity of functions in problem (7.15), the objective function gradients and normals to hyperplanes of constraints are constant, and the optimal point X° moving from A°(u'i) to X (w 2 ) continues to be optimal as long as it is feasible, while t h e feasibility for vector X° is proved for any A, 0 < A < 1. Suppose t h e functions of the original problem are all q u a d r a t i c in _Y with nonpositive definite matrices fij(w), i = l,m and nonnegative definite matrix H0(u>) for Vw, i. e., we have the quadratic programming problem for each realization: twnf(X,u>)

= min (xTH0{w)X

+p0(w)X

+ b0{u))

(7.17)

subject to

( XTHt(u)X+Pt(co)X>bt(uJ), \ x>o

t=T^

y7A8>

129

7.3. STABILITY OF SOLUTIONS

wherejhe elements H{{u>), p,(uj) and b,(u), i - 0 , 1 , . . . ,m, can be random variables. Let h'ti, p* and 6; be the mathematical expectations, and let <j\ , ) and b,(w), i = 0 , 1 , . . . ,m, respectively. Introduce the following sets and notations: S H = {.V : XTHt(uj)X

+ Pi{u)X

> bi(u), i = T~fR,

X > 0} ,

S+ = {X : XTH+X

+ p+X >b;,i = T^,

X > 0} ,

S~ = {.Y : XTH-X

+ p~X > b+,i = 17^,

X > o} ,

T

A„iA = {X : X e {S+\ {X : X H~X Jt„ = \ mm h{X)\

+ p~X > bf, il^i,

= mm (xTH+X

fa = I min+ Mx)} = min+ {XTH°X

X > o}}} ,

+ p+X + 6+) ,

+ PoX + 6o) ,

where H+, #7", p+, p~, and 6+, 6," are determined from the following relations for any i = 1, m and /, j = 1, n:

«T = H -- '?%) : fl? = (4 + H ) . p,~ P7

p + == ((pj ^ + Aor}), Aa'), = J/ffj) , p/ = (pj (p$ --- w)), +

6" = = (sr(6:-r = (£+*<*). (£+*<*). ? a t ),6, - Wi) i 6+= 6r Suppose T? and A are strictly greater than zero, S~ ^ 0, while the absolute minimum in problem (7.17)—(7.18) does not belong to S~, and considered for S(ui) are all u> for which there exists at least one feasible solution. Theorem 7.7. The probability that the optimal value of the objective function f(X°(u>)) e [f'xJxJ and the optimal solution of problem (7.17)-(7.18), X°(w), belongs to the region AV]\ is equal at least to Pv>x = P{OJ\H~

< H.(LO) < H+;

p~ < R ( W ) < p+;

K < 6 i H <6, + , Vi = 0 , l , . . . , m } . Proof. It is sufficient to show that the requirement of the theorem holds for the event {u\Hi < Hi(u) < H+; p- < pi(w) < pf; b~ < bt{uj) < bf; Mi = 0 , 1 , . . . ,m}(*). Proceeding in the same manner as in Theorem 7.4, we have S+ D S(ui) D S~ for all us from the event (*), while the set of optimal solutions for these u> is contained in A*,,. According to Corollary of Theorem 7.4 we have then that for all u> from the event (*) the required relations are satisfied for the objective functions: x w fZx = xemir s$ l Ui ) < x™P, jgff /(^> ) -

min

A

xes- -W

') = ft,v

130

CHAPTER 7. STABILITY

OF SOLUTIONS

IN SPP

Now it is easy to show, e.g., by shifting a nonbasic constraint, that depending on the form of objective function and constraint functions there can be realizations such that the optimal solution X°(u>) 6 AVi\ and, respectively, f(X°(uj)j € [/~A; f\iTI\\ but the strict requirement of event (*) is not satisfied for such realizations of u. From this it follows that p,,^ is the lower boundary for the probability that the optimal solution X°(u>) € An,.\, while f(X°(u)) e [f^\, f\
7.4

Feasible Solution and Function Stability with respect to the i-th Constraint

Consider the problem min^ fv(X)

subject to AX > 6(w)

(7.19)

X >0, where fu(X) is a convex function of the n-dimensional vector X = [xi,x2, ■ ■ ■ ,xn), A is an m x n matrix, and b(ui) is a random m-dimensional vector whose coordinates have a finite continuous distribution and the set of feasible solutions S~ is nonempty. The issue of general solution stability amounts to finding a region which bounds the set of optimal solutions inside the n-dimensional parallelepiped. This region is generally difficult to find, because it depends on the form of objective function, the length of interval and distribution of a random variable bt{u>) therein, and the extent to which the random variables bi(u), i = l,ro are dependent. Therefore it seems natural to discuss the issue of solution stability with respect to one random constraint in terms of the optimal solution in the mean. Consider the i-th problem of parametric nonlinear programming derived from problem (7.19):

mmfu(X) rbjectto

= f(X°>(u>))

£ » = 1 airxr = (Ax)j > b^u),

j = l,m;

£?=i a„xT = (Ax)i > 6i(cj),

A' > 0,

j

/

(7.20)

where X°'(LO) is the optimal solution of problem (7.20) for realization b,(uj), and bj(u) is the mean of a random variable 6j(w). Consider an n-dimensional parallelepiped built around the feasible solution X°(LO) of problem (7.19) that is optimal in the mean. So we have [X°(LJ)-8,X°(ID)

+ S};

(7.21)

7.4. FEASIBLE SOLUTION AND FUNCTION STABILITY

131

where 5 is the vector whose components are strictly greater than zero, but can have different values. The problem is to find the probability that in the set of optimal so­ lutions there is the optimal solution of problem (7.20) contained in the parallelepiped only if 6<(CJ) is a random variable and the other random variables b^oj) are equal to their mean values bj(ZJ),j — l,m.,j^i. In other words, we need to find Pi {X°'(LU)

G [XV)

" S, X°(u)

+

6]}.

DEFINITION. Problem (7.19) is said to be solution stable in the sense of the i-th constraint with characteristics e,, 5 if the relation

P, {.Y°'H e [x°(a) - S,x°(u) + s}} > l -ei is valid. To simplify the issue of solution stability in the sense of the i-th constraint, the solution of problem (7.20) is assumed to be unique for each i and any w. Solving this problem may help to reveal which of the constraints for stability of the optimal solution are unessential, i.e. do not produce perceptible changes in the optimal solution when 6;(u>) is changed, and which of the constraints are essential, i.e., carry the optimal solution far away from its mean value when the random variable bt(uj) is changed. The parallelepiped (7.21) can be constructed in a variety of ways. Consider a special case, where the parallelepiped intersects only those constraints of problem (4.1) which become an exact equality on the optimal solution in the mean X°(u>). The vector 6 can be obtained as follows. Let us take the minimal distance d from the point X°(UJ) to the hyperplanes for which (AX°(UJ))j > bj(UJ). Construct the parallelepiped with its center at the point X° and its sides 2 ■ 8j long, in which case ,/^™_1 5j < d. If for X°(p) there is no constraint which becomes an equality, i.e., (AX°(u>)) ■ > b;(u>),j = l,rn, then parallelepiped is constructed in a similar manner by choosing d as the minimal distance from the point X°(UJ) to each of the hyperplanes that are constraints with the mean bj(uj),j = l,m. Note that if the parallelepiped intersects the constraints which become a strict inequality for X (w), then there is a high, but hard to define probability that the optimal solution for all realizations 6,(w) from some interval [bj,6"] drops out of the parallelepiped. This case requires special investigation. In the first place, the distance d may prove to be too small to make meaningful any examination of the feasible solution for stability; secondly, the vector S is often specified on the basis of practical reasons, and the stability parallelepiped may fail to satisfy the requisite conditions. Let /; denote the set of all indices i = l , m for which the constraints with 6;(CJ) in problem (7.19) become an exact equality on X°(uJ), that is, £ " = 1 at]x°(uj) = 6;(w), while I2 is the set of other indices for which

£oy*J(ZD) >&,(*)• 3=1

132

CHAPTER

7. STABILITY

OF SOLUTIONS

IN SPP

Consider t h e i-th problem of parametric nonlinear p r o g r a m m i n g (7.20) for i 6 / j . We solve t h e problem for A,, 0 < A, < 1 in terms of A; for which

bi: = bt(u) = and t h e condition (AX)i

(i-TAb-+T,bt

= bi(u>) becomes (AX)t

= (1 - \t)b7

+ Xtf

= bK.

We obtain a continuous optimal vector function which depends on A^. Transferring &,-(w) = 6,\, from h(u) into b~, we get t h e lower b o u n d a r y for vari­ ations in bi(u>), in which case the optimal solution is necessarily an element of the parallelepiped (7.21). Two cases are possible here. 1. Some coordinate xf(uj) leaves the parallelepiped, i.e., t h e r e exists \\ such that (Axoi{wj)

. > t,-(E7);

(Axoi{us)).

j = l,2,...,m;

= b,(io) = (A - Xl)b- + AJ6+, x°'(u)

x°jp)

-5J<

j ^ i.

> 0

s V ( w ) < x°j(VJ) + Sj]

j = 1, 2 , . .. , n.

and there is at least one x°' such t h a t either X°'(UJ) = X°AUJ)-\-SJ or x^(yj) = X°(LJ) — SJ. 2. Moving from the point 6,(uJ) to t h e point b~ we find t h e b o u n d a r y 6" for which AJ = 0, and the optimal solution x°~ is still contained in t h e parallelepiped (7.21). To find the upper boundary, we transfer bi(uj) from bi(p) to 6; - Two cases are possible here. 1. Some coordinate x°l leaves the parallelepiped (7.21), i.e., t h e r e exists AJ such t h a t similar relations are satisfied in much the same way as for the lower boundary. 2. Transferring 6,-(w) brings us to realization bf, i.e., AJ and t h e optimal solution is an element of the parallelepiped (7.21). This means t h a t either t h e hyperplane (Ax,+ )i = bf passes through the optimal point x'+ from t h e parallelepiped (7.21) or the strict inequality (/lz'°); > 6* is satisfied, i.e., this constraint has already become unnecessary and so is replaced by another constraint. So, by changing 6,(w), we found the lower and the upper b o u n d a r y for variations in the random variable 6,-(w) where the optimal solution of problem (7.20) is necessarily an element of the parallelepiped (7.21). Consider those i g / j , i , e , , constraints, which become a strict inequality for X°(UJ). Then {Ax°(ujj). > b,-(E7), (Ax°(ujj).

> br,

When transferring 6,-(w) from 6;(w) to b~, the i-th hyperplane abandons t h e level line f(x) = f(x°(u))) bounding the convex region and including all the level lines which

7.4. FEASIBLE

SOLUTION AND FUNCTION

133

STABILITY

provide the lower value of function f(x) than f(x°(ui)). Therefore the i-th hyperplane does not intersect these level lines and x°(uj) is also the optimal solution for all A; among the-values b~ and 6,(S7). If the optimal solution of problem (7.20) x'+ = x°(lo) for bf, then the optimal solution x°(to) in the mean is the optimal solution for any realization bi(u>) € [b~,bf]. This is proved for the lower boundary. Since transferring 6,-(w) from bi(uj) to bf may only increase the objective function minimum f(x°(ui)), and f(x0(tJ)) = f(x'+), we have f(x0t(u>)) = f(x°(u>)) for all realizations of &;(OJ) and, by the uniqueness of the solution, x'° = x°(uf) for any 6,-(w). If the optimal solution x'+ =£ x°(uJ) for bf is not an element of the parallelepiped (7.21), then from the solution of the parametric nonlinear programming problem, and based on bt(uJ), we get A2 for which s'-f lies on the boundary of the parallelepiped. For each constraint i we have thus obtained the range of random variables 6;(OJ) in which the optimal solution of problem (7.20) is necessarily an element of the stability parallelepiped. We may now find the lower boundaries for probabilities £, which allow the problem to be solution-stable with respect to suitable constraints in terms of random variables bi(uj), i. e., we have Pi = Pi {x°'(u) e [X-°(U>) - 6, ftA2]|&»

> Pf { 6 , H 6

X°(UJ) + S}}>

= f>j(u)j = 1,2,... ,m, i + i} = 1 - £,-,

2

where b\ and 6 are determined from the following conditions: 1. For i € /: hl - I bl b ' ~ \ (i - \})b~ + \}bf

' lf ,if

X

/ # l - A2)&~ + \]bf

' 'f , if

X+ G

tf

'~ G x'- i

(7 221 {l ll ->

' i'+ e

(7 2V

2. For i e h

fc

. -

fc.+

4 /l

\2U.2 , \2L+

( 1 - - A?)&? + AJ6+

,if ';£

,if

x,+ e , + i„.+ $

rf

(7-24)

Proceeding in this manner makes it possible to examine functional stability in the sense of the i-th constraint. Consider the values 6,(OJ) from problem (7.20) for which |/(i 0 (O)) - /(**{w)| < 6. DEFINITION. Problem (7.19) is said to be functionally stable in the sense of the i-th constraint with characteristics &;, 8 (5 is a number) if P, = P, {|/ (X°(5T)) - / (xDi(u))

\<6}>l-et

To find the probability p,, we solve the parametric nonlinear programming problem (7.20) for the random variable bi(ui). We again find A] and A,2, which determine the

134

CHAPTER 7. STABILITY

OF SOLUTIONS

IN SPP

range of random variable 6,-(u>), to make problem (7.19) functionally stable. But we seek the interval [Af,A?] proceeding not from the solution in the mean, but from optimal solutions X'~ and X'+ such that, in problem (7.20), bt(u) are replaced by b~ and bf, respectively. This is due to the fact that, by the nonuniqueness of the solution in the mean X°(UJ) for problem (7.20), we could obtain a feasible solution X°'(LO), for which

| / ( A - V ) ) - / ( A - 0 , H ) | = <5(*),

and terminate the computation even though there may still be realizations 6,-(u) for which the equality (*) is also valid.

7.5

Investigation of Absolute Solution Stability

In some stochastic programming problems a feasible solution X° is optimal under changes of random parameters. For example, this may occur when the absolute min­ imum of objective function belongs to a set of feasibility regions S(ui), but does not belong to a set of permanent solutions S~ Then it is possible to formulate the prob­ abilistic problem, in which the feasible solution remains optimal for all realizations w 6 O. Here we may investigate without loss of generality only the case, in which the feasible solution belongs to the region S(tJ) that is feasible in the mean. If the abso­ lute minimum belongs to some other feasibility region S(u>), X° £ S(tJ), X° £ S~, then investigation can be carried out in a similar manner. We assume that the range of random variables is always finite. This formulation of the problem makes sense only where the convex program­ ming problem is stochastically constrained or where an extremum of stochastic linear function is to be found on the deterministic polyhedron. We will discuss these two cases. DEFINITION. The stochastic programming problem is called absolutely solutionstable with probability a if the solution in the mean is optimal for all realizations w with probability a. We will consider the direct and the dual problem of stochastic programming by employing usual notations where the conditions of problem form bounded polyhedral regions for each w 6 S7: max CX; min Yb(u);

S{u>) = {X : AX < b(u>),X > 0} , Q = {Y : YA > C, Y > 0} .

(7.25) (7.26)

Since the extremum of linear function of the bounded polyhedron is reached at the extreme point, the question of solution stability in the sense of the above definition can be raised only where not all bi are random and the optimal solution in the mean is generated by deterministic hyperplanes or where we have the trivial case A'0 = 0. The probability a that the feasible solution X° is still optimal is then determined by the set of those realizations w for which A'0 is a feasible point.

7.5. INVESTIGATION

OF ABSOLUTE

SOLUTION

STABILITY

135

The case is different with the dual problem (7.26). Here the polyhedron of the feasible solution region is deterministic, the optimal point X° in the mean is no longer the optimal solution, and for some realization the objective vector leaves the positive cone stretched along the normal of those hyperplanes which generate the optimal solution in the mean. [2] shows that if under some assumptions (uniqueness of solution, etc.) the direct problem (7.25) is basically stable mode, then its dual problem (7.26) is also basically stable with probability 1 — e. Since the solution polyhedron in problem (7.26) is deterministic and the basic stability implies the constancy of basic hyperplanes for some subset of the set of all realizations to, the basic stability of problem (7.26) is equivalent to the absolute solution stability of problem (7.26). So, determining the basic stability region for the direct problem (7.25) we simultaneously determine the probability that the problem (7.26) is absolutely solution-stable [2] provides several ways in which such a probability can be computed. We will present another method of evalution which allows one to determine the probability a that the problem (7.26) is absolutely solution-stable, and hence basically stable. Let us fix all the basic constraints in the mean which become an exact equality. Construct the basic As matrix m x m. Then the probability that the problem is absolutely solution-stable is determined by those realizations for which b = b(uj) £ K/3, where Kp is the cone stretched along the normals with nonnegative coefficients fii,/3 = (/?i, /?2, ■ ■ ■ ,/3m) for which the respective constraints form the basis, and for the solution in the mean we have b = 0A&, where /3i > 0, i = l , m . Hence the probability that b(u) € Kp is the probability P = bT{u)Aj1

=bT{u)A>0,

where A = (a^j) = AJ1 is the inverse to matrix A$, i. e. we have a = P | 0 {aijbi(uj) + a2jb2{uj) + . . . -f a mj 6 m (w) > 0} | In practical problems, however, it is generally possible to determine the boundaries for variations in random variables b»(w), and these boundaries are finite. Then we have: a = P{ n {a!j6i(u>) + a2jb2{uj) + ... + amjbm(tv) > 0} , K < bi(u) < bf,

Vi = I ~ ^ } = P {&M € D} ,

where D is the intersection of the parallelepiped [b~ ,6+] and the feasibility region generated by half-spaces al]b1+a2]b2

+ ... + am]bm>0,

Vj = T^m,

b G Em

Discussion of the absolute solution stability leads to determination of region D. If the joint distribution function of vector components b(u>) is known, then by the linearity of all constraints the probability P{{LO) £ D} can be found by means of

136

CHAPTER 7. STABILITY OF SOLUTIONS IN SPP

complex integration over the polyhedral region of the joint distribution function of random variables bt(u>), i = l , m . Suppose the random variables 6,(w), i = l , m are mutually independent and are all uniformly distributed. Then it follows that / (n) fdbi.. a-

P(b(uj) e D)

.dbm

mAbt-b-)

where the region D is determined from the relation D = {b{uj) :b(u) € {[K,bf],bi

< 6+,V/ = I ^ } n

D{Siib1(uj) + a2]b2{uj) + ... + amjbm{u) > 0,

v» = T7^}} We will now consider the problem for each realization of LO: ' minx F(X) A{LO)X > b(u)

(7.27)

X >0 where F(X) is the deterministic, convex down function, and the conditions of problem form a random polyhedron 5(w). We need to find the probability that some point continues to be optimal for all realizations of w. In the feasible region, the minimum of convex function is reached either at the point of the absolute minimum of this function, if the function exists and belongs to some feasible regions S(u>), or at the boundary of the feasible region. For this reason the issue of absolute solution stability can be discussed in the sense of the above definition only as far as the absolute minimum point of convex function F(X) is concerned, Suppose the absolute minimum is reached by F(x) on x° > 0. Consider the case where x° belongs to the region S(UJ) that is feasible in the mean. Let the parameters of various constraints be all mutually independent. Then we need to make computations under the assumption that the parameters are all continuously distributed:

a = PJf>y(w)*J>&,(w),i = l,2,...,: P | f\lgi(ati,aa,...,ain,bi)

= H*) - X » K

<°

}=

m

= I I f{Si(«ii.««>•■ -,ain,b,) < 0} = ;=i m

= 11

f J

f (" + 1 ) / Pi(Ui,ai2,

...,ain,bi)daiu...,daindbi,

7.5. INVESTIGATION

OF ABSOLUTE

SOLUTION

137

STABILITY

where P ^ a n . a , ^ , . . . , a m , 6,) is the joint distribution density of random vector (an,o.i2, ■ ■ ■ ,a,„b,). Similar relations can be derived when problem (7.27) has constraints of the form 5i( :r > w )) * = 1,2,.. . ,m, where gi(x,u>) are functions that are concave in x, and when random variables are discretely distributed. We will consider a special case and find an explicit expression for the probability a when only the components of vector b = b(u>) in problem (7.27) are random. Suppose that for any i = 1,2,... , m we have n

Y^aijx°j > bi(CJ), x > 0. 3=1

1. Suppose bi(ui), i = l,m assume discrete values y from the set of realizations [fe~, 6^" ]. If we introduce the notation 6° = min \bf J2 aijx°j\, then we need to com­ puter a = P | &,H < X > t J x ° , z = T~^

=

£

...

■■•IZ-y™ e [6~,6+]P {b,(u>) = yi,...,6 m (w) = y m } , which, in the case of independence of vector components bi(u>), is as follows

« = E-we[br,6f]-..

£

f[ P {b,H = y>) = \

£

Pa).

where p,-2 is the probability that bt(ui) = j / l 2 . 2. Let b,(u>) denote independent random variables that are continuously distributed over the intervals [b~,bf]. If p(bi, 6 2 , . . . , bm) is the joint distribution density of a random vector b(u>), then for the same notation of b° we have

r

_

a = P < &j(w) < £ a , j 2 : ° , i = 1,) I ;=i = /

.

Jb,(uj)
/

( m ) /?(&!,& 2 ,...,& m )d& 1 ,dc> 2 ...d& m = J

(m) fp(bub2,...,bm)db,db2,...,dbm

= | ( m ) | Pi(6i)P2(6 2 )... P m (6 m )d6i, d&2, ...,dbm

=

=

138

CHAPTER 7. STABILITY

OF SOLUTIONS

IN SPP

b°

m m

• <

(bt)dbt. = n / Pi(bi)dbi.

K EXAMPLE. Suppose all 6,(CJ) are independently distributed with the mean values b, and variances a,, i = l , m and with probability distributions similar to normal distributions: i

/

C P

a,y2^ " \ Pi(bi) = •

1

..0, o,

-\m

'-U'f)>

6+

{ 67

b,e[b7,bt]

ki[br,ht}, b,{[b-Xl

r a n d o m variable variable t) is normalwhere the random each i there there is aa rrelevant e levant random normalwhere ran dom variable variable t (for (for each ly distributed with characteristics &,■(&,*-
n bf, £ aijX°A, a x° }, < bt) and <Ji. Let 6° = min | bf, E tJ 3

then have then we have

f

n

)

m h°

I

1=1

J

*=i»r

=\ f[fp OL - P k{uj) I bifo) << J2 J2 *j*% &ii2%i i==T >l,m\ a=P{ = IIi(b/ i)db #( W i = = 1

m

a^J

[

=nn — h ,=1

-\(^)h ——■

/ P

K

1

:-my

Replacing variables in the numerator and denominator, we obtain 1i

- = a = 1

1

(2

"

f~^~ e -•-. d* , L-^ Ib~-b% e~~dt J -1 r~ = b -b ,2 L /•-^r- e'^dt _£ +

*(«

?)- * ( ^ ) = n -y.(sa)_,(si).(*7 )- * ( ^ ') m

:

s

where $(s) = - 4 - / e'~dt ^ -oo

is the normal distribution function with characteristics

0 and 1; this function can be computed for any x from the tables.

7.6. STABILITY

IN PROBABILITY

139

MEASURE

If the stochastic programming problem is absolutely solution-stable with proba­ bility a, then, since the optimal solution has the same objective function value for all relevant realizations of CJ, we may say that the problem is absolutely and functionally stable with at least probability a.

7.6

Stability in Probability Measure

The solution stability in probability measure for stochastic problem is discussed in [11]. The optimal solution is considered as the probability distribution function. Their Gateaux derivatives are used to find asymptotic distribution of statistic estimates for the optimal solution. Let SI, B, p be a probability space. Consider the problem associated with functions /,: RK X SI -» R mmtp0(x) ipi(x) = 0,

i £ I,

(fi(x) < 0,

i e J,

where ipt(x) = Ep{fi(x,uj)}

= J ft(x,u>)P(doj). I,J are finite sets of indices. It is n assumed that for any x f{(x,u>) is measurable and integrable with respect to the probability measure under consideration. A large class of stochastic problems can be formulated in terms of (P). The behavior of solutions to problem (P) x(P) is treated depending on the probability measure P Suppose that P is disturbed by some measure Q P := P + Q, where Q is in the same space [SI, B]. Consider Pt = (1 - f)P + t(Q -P),Q 0,

i € I,

tfi, < 0,

i € J}

where f,{x,t) = fQ f,{x,u>)Pt(duj) = ip,(x) + t{rjt(x) - )Q(duj). Let x(Pt) denote the optimal solution of Pt. Consider the Gateaux derivatives in the optimal solution direction dx(P, Q — P) = hm v t-n-o t A s s u m p t i o n 1. Let y?i(x), -qt{x) i € {0} U / U J be continuously differentiable in the neighborhood of point x0. To satisfy Assumption 1, we may require, e.g., that: 1) for all u : f,{x,u>) be continuously differentiable in the neighborhood U(x0) of the point x0; 2) there be the functions gt{u>) : ||V x /,-(a:,w)|| < g,{u), Vx g U(x0), w g 0 that are integrable with respect to P and Q. Then it follows that
140

CHAPTER 7. STABILITY

OF SOLUTIONS

IN SPP

1) gradient vectors V
with (Pj). Denote L0(x,X) = Z/(z, A,0) and L0 as the corresponding set of Lagrange multipliers satisfying the necessary (Kuhn-Tucker) first-order conditions. A £ L0 if V x L 0 (zoA) = 0, A, > OVi 6 J* and A, = OVz € J/J* When M F conditions are satisfied, LQ is nonempty and bounded. Assumption 3. Let ip,(x), Vi £ {0} U III J* be twice continuously differentiable in the neighborhood of x0. Consider the set LUQ) = arg max { £ A,(/3,(xo) : A G L0 \ and the so called crit1 ieiuj ' T ical cone c = ctU : u Vipt(x0) = 0, i G /, uTV 0. When Assumptions MF and 4 are satisfied, x0 becomes an isolated local solution of Po- The conditions of Assumption 4 are generally stronger than standard sufficient conditions (where LQ(Q) is replaced by L0). Assumption 4 is the weakest one and guarantees the existence of the directional derivative. Denote: for A G LQ consider V^ ( L(x 0 , A, 0) = Vn 0 (x 0 ) + J2 ^ V J ; , ( I 0 ) and a pointwise ieiuj maximum /3(u,Q) = max{uTV£,L(:roA0) 4- 1 l2uTVxxLQ(x0\)u A G L*0Q\ quadratic functions corresponding to the quadratic term of Taylor expansion for L(x, A, t). Y1{Q) is the optimal solution set of the problem minu

\7ip0(x0)

uTV^>i(x0) + ^(^o) = 0 i £ I uTVVt(x0)

+ rn{x0) < 0

i € J*

It is apparent that the critical cone C is a recession cone for -={Q) and —(Q) = C ifnt{x0) = 0 , VzG / U J' Theorem 7.8. Let Assumptions 1-4 be satisfied. Then: 1) 3 is a constant K > 0 : ||x(P ( ) - x0\\ < Kt, 2) if, additionally, fl(u,Q) has a unique point of minimum u{Q) with respect to ={Q), then the directional derivative dox(P, Q - P) exists and dox(P, Q — P) = ou(Q). Note that the set of points of minimum (3(u, Q) with respect to —(Q) is nonempty and closed, but is not necessarily a point. To satisfy condition 2), we may require that various forms of sufficient 2nd order conditions (stronger than Assumption 4) be satisfied.

7.6. STABILITY

IN PROBABILITY

141

MEASURE

Consider asymptotic distribution of statistical estimates for the optimal solution of (P). Let Lo-i . . ., u)n be some collection of independent, uniformly distributed obser­ vations with a common probability measure P. Problem Pn\ (P„)minon(x)

S.tipin[x) = 0

iel

ipin(x) < 0

i £ J,

n

where V'm(x) = n _ 1 E / ; ( s . w,). Let xn be the optimal solution of (Pn). This solution ;=i

provides a statisfical estimate for the solution xQ of (P). Here the directional derivative is used as a heuristic means for determining asymptotic distribution of the solution of(P). ^ Consider xn as a function of the empirical measure associated with the collection under study. Consider the measures Qn = n~l E A(ujj), where A(w) is the probability measure 3=1

of mass one at the point u>. Then ipln(x) = F Q „ { / ; ( X , w)} = / fi(x,ui)Qn(dui)

and

xn = x(Qn) can be viewed as the function of Qn. Let x(P) = x0 and dx(P, Qn — P) exist; then W(Qn) = x0 + dx(P, Qn — P)-\-rern(Qn — P) (1). Suppose the residual term on the right-hand side of (1) is asymptotically negligible, which implies (Qn — P) = 0 p ( n - 1 ' 2 ) (2), i.e., n ' ^ r e m tends to 0 in the sense of probability. The asymptotic distribution n 1//2 (x n — x 0 ) is then completely determined by nll2dx(P,Qn — P) So the asymptotics n1^2dox(-, •) can be readily described by employing Theorem 1. (2) is more complicated to derive. A s s u m p t i o n 5. A0 = {A0} is a point. Then fi{u,Q) is the quadratic function (3(u,Q) = u \Vrjo(x0,Q) + E .S/uJ

AoV77,-(z 0) Q)l+i« T ViX(xoA 0 ) J

uTV
i £ / U J;(A 0 ) ieJ;(X0)

where J('(A) = {i £ J* : A, > 0}; J0*(A) = {i € J* : A, = 0}. The following form of sufficient 2nd order conditions is provided to ensure the uniqueness of the point of minimum u{Q). Consider linear space: M = {« : uTV 0. Since M contains the critical cone G, Assumption 6 is stronger than Assumption 4. A s s u m p t i o n 7. Expectation Ep{fi(x0,uj)2} i g /UJ* is Unite. Since rn(x0,Qn) = - E fi(xa,Wj), by the central limit theoremn1/2{rii(xo,Qn)~<{>i{xo)} witi respect to distribution. Consider the Lagrangian functional, A, w) = / 0 (x,w)+ E

i6/uJ

the expectation 1(X,\,LO)

in measure P is L 0 (x, A).

tends to normal

Kf,(x,uj).

Evidently,

142

CHAPTER 7. STABILITY Assumption

OF SOLUTIONS

IN SPP

8.

For almost any ui l(-,X0,u>) are differentiable in XQ: are finite and VL0(x0X0) = Ep{VJ(x0)\0,uj)y Consider random variables, V; i £ /U J* and Z = (zi,. . . ,Zk)T, that are normally distributed with zero expectations and covariances: cov(YtYj) = Ep{f,(x0uj)fj(x0uj)}

cov(Z,Zj) = Ep{...cov(YlZJ)

= uTZ + \uTVlxL0{x0]\0)u;

Define p(u,Z)

= Epj

£ ( V ) = {y ■ uTV
T

i £ / U J*(A0); u \7ipi(x0) + Y, < 0, i £ Jo(A 0 )j and let u(Y, Z) be the set of points of minimum /?(£/, Z) with respect to ^Z(Y). T h e o r e m 7.9. Let Assumptions 1-3, 5-8 and regularity conditions (2) =$■ nll2(xn — x0) —>■ u(Y, Z) be satisfied.

Chapter 8 Methods for Solving Infinite and Semi-infinite Programming Problems Application of mathematical modeling and analysis techniques to economy, techno­ logy, design, and management results in infinite-dimensional systems of inequalities with a finite number of variables [67]. This list may include engineering, design, variational inequalities, theory of moments, continuous linear programming, geometric programming, and theory of fuzzy sets. Formation and development of semi-infinite programming, as a division of mathe­ matical programming, were governed by statement and necessity to solve mathemat­ ical programming problems in finite-dimensional spaces with an infinite number of conditions or with a finite number of conditions but in infinite-dimensional (function) abstract spaces [46, 72, 123). Semi-infinite programming problems can be examined by employing a variety of reductions to a finite case such as finite systems of infinite subsystems or finite probability measures. A natural extension of semi-infinite programming is infinite programming by which are meant statements and methods of solving the programming problems with an infinite number of conditions in function spaces [61, 63, 37, 108, 3, 34, 81]. What are called as large-dimensional problems [153, 132, 54, 56, 67, 68, 71, 72, 115] and decision problems under uncertainty, i.e. stochastic programming problems [146-148] have made a contribution to development of the theory and methods for solving infinite and semi-infinite programming problems. Applications of mathematical programming techniques to planning and control in complex stochastic systems provide an infinite variety of manifestations of random data (where the number of states of nature is infinite), which is reflected in the models with an infinite number of conditions and/or an uncountable set of desired variables. This generates a need for examination of infinite and semi-infinite programming problems. 143

144

8.1

CHAPTER 8. INFINITE AND SEMI-INFINITE

PROGRAMMING

Statement of Semi-infinite Programming Problems

The term "semi-infinite programming" was defined in [14, 29, 103]. Here, we are dealing with constraints on a compact set. Formally, these are finite-dimensional problems with an infinite number of constraints. In the general case, the semi-infinite programming problem (SIPP) can be stated as follows: mf{iP(x):ft(x)
<0- i = T~^}.

(8.2)

x G X is the Hilbert space. In special cases, the problems (8.1), (8.2) can be stated more specifically. Thus, the statement is: 1. The form and properties of the objective functional are: linearity, quadratic form, convexity, and degree of smoothness. 2. Construction of the set for problem (8.1) is: (If T is finite, we have a classical problem of mathematical programming) T — {1, . . . , oo} is countable, T = [0,1]; T = [a,P]; T=fl

.=i

T,; T, = fa,ft], V* = T ^ .

3. We may select, along with constraints of the form ft(x) < 0, a finite number of "ordinary" constraints fi(x) < 0, i = l,m, or x £ X, where X is a compact set in Rn 4. The form and properties of constraint functions are: linearity, quadratic form, convexity, and smoothness. Referring to [109], we have the general statement of problem (8.1) on the as­ sumption that tp(x), ft{x) are convex in Rn For the general statement of (8.2), see [41]. The union of two types of "semi-infinite dimensionality" is exemplified by setting a separably-infinite programming problem [31, 67]: v(A) = inf ex - £ (A)

v

m+i{r)i]{r)\

u(t)x>un+i(t), t e S; Ax+ £ u(r)??(r) = 6;

. [

. '

>-eQ

where S C /?", Q C R',u{-): S - » Rn, un+1(-): S ^ R, c e Rn, b € Rm,v(-):Q^ Rn, : mxn w m +i(') Q ^f R, A e R The first constraints in (8.3) contain an infinite number

8.1. STATEMENT

OF SEMI-INFINITE

PROGRAMMING

145

PROBLEMS

of inequalities with a finite number of variables, whereas the second constrains contain an infinite number of variables, but their number is finite. Referring to [32], we have the problem: (5)

ram{/(i):V,(i,()>0;

Vf € TU

i€l^},

(8.4)

m

which only differs from (8.1) by its special construction, T = Y\ If i-i

The solution of a wide class of the analysis and synthesis problems for discrete dynamical systems in a half-closed interval can be reduced to the solution of the nonlinear programming problem [25-27]: inf{J(u):u 6 Rn, G]t(u) > 0,

Vf 6 l^oo,Vj 6 V m } .

(8.5)

Here J plays the role of ip, G plays the role of / , while T = {1,. . . oo} x {1, . . . m} is the product of the countable set and the finite set. Referring to [110], we have a convex quadratic semi-infinite problem: (Q)

m'm{-xTCx-pTx:g{x,t)<0,

teT,x€X},

(8.6)

where X = {x £ Rn: fj{x) < 0 are convex, j € J = {1, .. .,
in [62]:

I

f ,(F) = inf(c^); \ atx>bt, teT, _ v(Z) = mine x; u(t)x>X(t), VieT;

{

'

(8.8)

Vi 6 I C ff X:{x:a,iX>b, i = l,m}. Here 4>(x):cTx, ft{x):bt - at(x). In the general case (where linear programming problems are extended to cover multiple specification of constraint matrices), such problems are of the form [153]: ma,x{cTx;x > 0; Ax < b VA € G}, (8.9) where x = ( i i , ■■•, xn)T is the column vector of program components, cT = (ci, . .., c„) is the row vector of objective coefficients, A = {an, i 6 l , m , j G l , n } is a constraint matrix, rn < n, b = (bu .. . , bm)T is the column vector on the right-hand side, and G is the matrix set.

146

CHAPTER 8. INFINITE AND SEMI-INFINITE

8.2

PROGRAMMING

Duality of Semi-infinite Problems

Referring to [24], we have that the dual of a semi-infinite problem also is semi-infinite. Thus, the dual of (8.7) becomes [28, 53, 55]:

I

v(D) = sup J2 \{bi = supt/>(A);

EA,* = &><>,

teT.

M

Theorem [28] is given to define the duality of problems (P) and (D). Theorem 8.1. 1) Ifv(P) = — oo, then problem (D) is inconsistent; 2) ifv(D) = +oo, then problem (P) is inconsistent; 3) if problems (P) and (D) are consistent, then v(P) = v(D). The admissible set for A is a convex set in the space of generalized finite se­ quences and retains the properties of convex polyhedral sets in finite-dimensional spaces. These properties provide a framework for interpreting the simplex method geometrically. Referring to [53], we have the duality theorems using Slaiter condition (existence of interior points of an admissible set). Theorem 8.2. [53] Suppose that: 1) the vector set dt = (aJ,bt)T 6 Rn+l is canonically closed; 2) there exists x* 6 Rn such that atx* > bt, Vi 6 T. Now, ifv(P) is finite, then v(P) = v(D) and the problem is solvable. We have general properties of the optimal value function v(P)(c) and v(D)(c). The statement is: v(P) = cl v(D). In particular, consideration is being given to a duality gap and its relation to discrete optimization of semi-infinite problems. Conditions are provided to eliminate a duality gap by introducing a perturbation into the objective function. In terms of the Lagrange function [23, 30, 38, 39], for general convex programming problems MP = inf{f(x):gi(x) < 0, i S / } their Lagrangian dual is: MD = {supinfi(x,A),A > 0, A

x

A € A C {A,: i e I, A,: / 0 is a finite number }};

(8.11)

L{x,\) = f{x) + '£\igi{x). is/

We have that MP — MD if and only if MP = optimal value

lim MP$, where A'fPs is an

J->+o

inf :r (PA I /( )i { s> 1 »(x) < S, i el.

Suppose C is a feasible domain for problem P, Cs is a feasible domain for problem Ps, and 0 + C is a recession cone C. L = {y. f0+(y) = 0 = / 0 + ( - y ) } ;

M = 0 + C A (-0+C) A L.

8.2. DUALITY

OF SEMI-INFINITE

Proposition.

147

PROBLEMS

Let f, gt, Mi be a closed convex C ^ 0, then MPS -¥ MD as

T h e o r e m 8.3. Let C ^ 0 and /0+(j/) > 0, Vy e 0+C n M1, y ^ 0 =» MP = MD and there exists an optimal solution P. Let I0 be a countable subset of / such that {x\g, < 0, i £ I0} = {x\g,(x) < 0, i e I}; then problem P(I0): MP(I0) = {inf f(x)\gt{x) < 0, i £ / 0 } is the equivalent of problem P in terms of the optimal value and feasible solution. Let us construct problems Pn and their dual Dn: (P„) {Dn)

MPn = {inf f(x)\9i(x)

< 0,: = M } ;

MD.n = < sup inf Ln(x, A), A > 0, A £ /T I >■ x

L„(x,A) = f{x) + J2^9i-

Construct C„: C„+i Q C„, Vn, C = HCnI

T h e o r e m 8.4. Let C / 0 and /0 + (y) > 0, Vy £ O + C f l M 1 , y ^ 0, then MP„ = MDn for any sufficiently great n and MPn ->■ M P The dual of problem (Z) (8.8) for a particular specification of the set X be­ comes [62]: v(F) (F)

suP( £ A(%(*) + £ &.•«<); £u(%(<)+ £ .iiV, i>j > 0;

= c;

(8.12)

! £ l,m;

tp(t) > 0 for Vi £ T and (^(t) = 0 for any only finite number t £ T. Referring to [153, 132, 133], we have linear programming problems with the con­ straint matrix (8.9) specified multiply. Duality theorem follows from the assumption of convexity, closure and boundedness of the set G out of which the matrices A are selected. Theorem 8.5. If one of the problems — primal or dual — has a limited solution, then the other problem also has a limited solution, and ex = ipb. If the target functional in one of the problems is not bounded on a suitable set of feasible solutions, then the feasible solution set of the other problem is empty. Here x = argminjez: x £ X} and y = argmax{j/6: y £ Y} are optimal values for the primal and the dual problem on the respective feasible solution sets X and Y generated by constraints on the problems. This theorem immediately follows from the analog of the Minkovski-Farkas theo­ rem for infinite systems of linear inequalities. The dual of problem (8.3) is also a separably-infinite programming problem [31, 67] v(B) = s u p ( £ un+i(t)X(i) - by); tes £ u(t)X[t) - A*y = c; .13) [B) v(r)y > u m + i(r), Vr £ Q; A(-) > 0; AM G fl<s>; y G BP

148

CHAPTER 8. INFINITE AND SEMI-INFINITE

PROGRAMMING

The duality theorem is provided under the following assumptions: Assumption 1. The set Kg = {x £ Rn:u(t)x > un+l(t); Vt £ S} is nonempty and bounded or u„+i(-) = 0. Assumption 2. The set KQ = {y £ Rm: v(r)y > vm+i(r); Vr £ Q} is nonempty and bounded. Assumption 3.. The convex cone Cs C Rn+1 generated by

..A)H u {(: is closed. Theorem 8.6. [31] If problem (A) (8.3) is solvable and has a Unite value, then problem (B) (8.13) is solvable and v(A) = v(B). Furthermore, problem (B) (8.13) admits of its supremum as a maximum. An assertion similar to this theorem can be made under assumptions such as 1-3. Assumption 1*. The set KQ is nonempty and bounded or D m + i() = 0. Assumption 2*. The set K$ is nonempty and bounded. Assumption 3*. The convex cone CQ C Rm+1 generated by

..-^ M H«M(! is closed. Referring to [39, 87, 92], we have the infinite systems defined by convex functions (possibly by adjoining constraints on membership in some set). These functions and sets are generally assumed to be closed, but the Slaiter points are not required to exist. In particular, if there are no constraints on membership in the set, then the constraints are only required to be consistent. Necessary and sufficient conditions are given for the lack of Lagrangian duality gap (8.10) which contains merely a finite number of nonzero multipliers [95]. In particular, the conventional sufficient condition has been derived for a finite number of constraints. For the infinite number of constraints, a compactness condition plays the role of "finiteness'' in the function space. Semiinfinite programming problems can be treated by employing a variety of reductions to a finite case such as finite systems of infinite subsystems or finite probability measures (see, e.g., [88]).

8.3

Optimality Conditions for Semi-infinite Programming Problems

Referring to [140], we have the Farkas theorem for a finite case and, as a result, necessary minimum conditions for problem (8.2). Theorem 8.7. Let F(x), ipi(x), i £ l , n be continuously Frechet differentiable. Suppose the point x0 is a solution to the problem, and weak first-order regularity

8.3. OPTIMALITY

CONDITIONS

FOR SIP

PROBLEMS

11!)

conditions are satisfied at this point. Then n

F'{x0) = ^ c w ' O o ) The constraints {<^} satisfy the weak first-order regularity condition at the point So if any vector z ^ 0: { 0;

i € I(x0) = {i e Y^n:
is slightly tangent to the set A at the point x0. The vector z ^ 0 is slightly tangent to the set A at the point x if there exist the sequences {xn}: xn € A, n 6 1,oo and {An}: A„ £ /? are real numbers such that An(zn — x)T —>• z as n —)• co (weak convergence). Necessary and sufficient minimum conditions [109] are given for problem (8.1) in terms of Lagrangian function. Theorem 8.8. x 6 R is an optimal solution to problem (8.1) if and only if x € 5 s u c n t ia and there exists (X(t))ter(x) £ ^i ^ '

On €
ItSfi(S).

teT(x)

Here the Lagrangian function becomes

*(*, A) =^(A)+ £ > / , ( * ) , /?
A = (A t ), eT e R\ ;

T(x) = {teT:

iGfl"; Vi}; ft(x) = 0}.

The necessary local minimum condition [23, 32] is given for the problems (S) (8.4). Theorem 8.9. [23, 32] Let x" be a local minimum in problem (S) and I, = {t*k g T,.- ipi(x",t*k) = 0; k S 1,A',}; then there exist finite Lagrange multipliers Xlk > 0 m

such that VJ(x')

K,

= E E A ifc V l¥ J,(i*,i^).

A s s u m p t i o n 1. The gradients V # ( i * , t ) for any t S TJ; t £ l , m are linearly independent. Accordingly, the sets /, are necessarily finite and we may write

S = {t»eZi:p.-(*V,\) = 0;

feei.Xi}-

A s s u m p t i o n 2. For any a; there is a finite (possibly empty) set of subsets £lij(x) such that: 1. Hi, GT„- 1 <j <St = S,{x) < o o ; 5,

2. v3,-(x,t) < 0; Vt € n t J and p,-(x,i) > 0; Vi S T, \ U % ( * ) ;

150

CHAPTER 8. INFINITE AND SEMI-INFINITE

PROGRAMMING

3. %(x)nfl;*(z) = { 0 } ; J 7 ^ ; 4. flij(x) is connected and nontrivial, i.e.:

/

dt > 0.

Note that almost all functions will satisfy this assumption. Assumption 3. For any x and any index i there is a nonopen set {/,• that is strictly bounded in T,- and suci thai 73,(3:, t) = 0; Vt € £/;. Denoting A, ; (x) = / dt; $ t J = / tpi(x,t)dt, we may write the penalty n„(x) «,,(*) function as p(x lM) = = /^/(x) -

((*)),

-E(E*. !=1

J=l

3=1

where p is a positive scalar. Assumption 4. Trie functions f(x) are convex and ipi(x,t), t £ l , m are concave in x. Assumption 5. For Vi £ 1, m; j € 1, Si there exists a constant ft > 0 suci that s, 5,

EM*)

s,

< P^{x.

3=1 3=1

,(*) 7=1 i=i

s, for any t g (J n s j ( i ) and any x £ Rn 3=1

Theorem 8.10. [32] Under the assumptions 1-5 the point x* is a global minimum of the function p(x,fi) for any /J. such that 0 < fi < p* for some p' > 0. A series of assumptions and assertions similar to Theorem 8.10 are made for the general case [32]. In [30, 31], for problem (8.7), some generalizations of the Kuhn-Tucker saddle point theorems are examined for arbitrary convex functions, and necessary and suffi­ cient optimality conditions are obtained under some additional conditions. Sufficient optimality conditions for solution in terms of various notions related to the objective function (generalized Lagrangian function, a direction cone, a special duality problem, etc.) are guaranteed by the boundedness of a feasible set [58]. Semi-infinite programs are investigated using penalty functions and Lagrangian methods Necessary optimality conditions are constructed in the form of a system of nonlinear equations. Also, generalization is given to cover a nonconvex case. Referring to [89], we have two sufficient conditions for strict local optimality that do not require strict complementability for the feasible set to be reduced. It is stressed that these sufficient conditions are the natural extension of typical sufficient secondorder conditions to a finite case. Referring to [31], we have necessary optimality conditions for the primal (A) (8.3) and the dual separably-infinite programming problem (B) (8.13). Theorem 8.11. Let x", rf{-) be optimal for problem (A) and let y*, A*() be optimal for problem (B). Then ( u ( 0 s , - u „ + i ( t ) ) A * ( 0 = 0,

V i e S;

8.4. EXISTENCE

AND UNIQUENESS OF SIP

PROBLEMS

(v(r)y*-vn+l{r))ri'(t)=0,

Vr £ Q.

151

Referring to [36], we have a wide class of problems (semi-infinite programming problems, in which the minimized function and the functions defining the inequalitytype constraints are nonsmooth and represented as a maximum of the set of smooth functions on a compact set) for which there is a set of quadratic necessary optimality conditions, where these conditions are interrelated as closely as in classical analysis. Second-order necessary conditions are also given in [121]. As noted in [96], the wellknown second-order necessary conditions for semi-infinite programming problems are valid only where, along with the system of inequalities, the problem incorporates some constraints in the form of inequalities. If there are no equality constraints, then an envelope-like effect occurs. Allowing for this effect results in second-order necessary conditions for the additional summand. Referring to [69], we have new generalizations of the Farkas lemma. These results allow some familiar infinite analogs of the Farkas lemma to be combined within a unified theory. Applications are given resulting in necessary conditions. Referring to [22], we have the marquee method which is generalized in a finite case [19] to an infinite-dimensional situation. The method is also given for the infinitedimensional case. As an application, necessary optimality conditions are provided for the general programming problem. Basically, they include all of the familiar necessary conditions (in theorems such as the Kuhn-Tucker theorem, etc.).

8.4

Existence and Uniqueness of Semi-infinite Programming Problems

Let us consider a linear semi-infinite problem of the form (8.7) [75, 112, 134-136], 1

'

f mines; \ atx
Suppose that T is a compact metric space, B(t), A, T is the set of all continuous mappings B:T -> R and A:T -* Rn for the given parameters a = {c,a,b} G 9, consideration is being given to a suitable (P1). We define the set of feasible points Z = {x G Rn: a,x < bt ,Vi € T} and the solution set P = {x G Z: ex = inf(cy: y e Z)}. For every feasible point x G Z, we define the set of active points N = {t G T: atx = bt}. The vector x0 is called a strictly unique solution of (P1) if there exists a constant K > 0: Vx g Z: cx0 > ex + K\\x - x0\\. Problem (P1) satisfies Slaiter's condition if there exists a vector y g Rn such that aty < bt, Vi g T. Suppose that Q = {a: (P1) satisfies Slaiter's condition }; L = {a: (P1) has a solution }; S = {a: (P') has no more than one solution };

152

CHAPTER 8. INFINITE AND SEMI-INFINITE

PROGRAMMING

conv (A) is a convex hull A C -ft"; cone (A) is the convex cone generated by A. Strict uniqueness is investigated in [75], T h e o r e m 8.12. If a, fixed pair (c,a) satisfies Haar's condition (i.e. there are no points t, g T, i g l , n — 1 such that the vectors c,atl, ..., atn_1 are linearly independent), then for any b G B(t) the optimization problem has a strictly unique solution. Let us select a point to, but not in T, and let ato = c. Theorem 8.13. [75] Let a g Q and x0 G Z. If there exist points ti € T, i G l,n such that - c G cone {{au:i G l,n}) and a(o, a t l , . . ., a(,_,, a ii+1 , . . . , atn are linearly independent, i g Q,n, then x0 is a strictly unique solution of(P'). In practice, the parameter which defines problem (ft') is often known approximate­ ly or it may vary. Complete characterization is provided in [111] for linear problems which have a strongly unique solution and are stable under small variations in the parameter. Consideration is given to the relationship between the unique and the strongly unique solution. Consideration is given to global unicity [112]. Also, characterization is given to the problems which have a unique and a strongly (strictly) unique solution for all constraint functions. Theorem 8.14. [112] For a fixed vector c g ft71; c ^ 0 and a fixed map a g A(T, ft"), o ^ O , the following assertions are equivalent: 1) for any b g B(T) with a = (c, a, b) g L, problem (P1) has a unique solution; 2) for any b g B(T) with a g L problem (ft') has a strictly unique solution; 3) there are no points t, G T, i — l , n — 1 such that —c g cone ({o (l , i £ l,n — 1)}; 4) for any points ti g T, i g l,rz — 1 ' a vector y g ft" such that cy > 0 and a (i y > 0, i g l , n — 1. , Effective characterization of strict un of solutions is obtained for the minimax problem {y{x) = max{a ( i — bt] —> m on the assumption that a = mi{g(x): x € ft"} is finite. Here a wide class of best approximation problems [16] and other problems is covered. Referring to [135], we have generic existence and unicity of the solution to the problem (ft'). For a = (c,a,b), we denote Lz = {a, Z / 0}; K = {x g ft", atx < 0, Vt g T}; K* = {c g ft", ex > 0, Vz g K}\ KT = {c g ft", c = E a,bu, t, g T, a, < 0, i=i

z g l,n}. Theorem 8.15. Let Z be nonempty for some a and cy > 0, and Vy g K, y / 0. Problem (P1) then has a solution. In [98], it is established that, for a compact Hausdorff space there is a dense Gj-set in 6 = {
8.5. METHODS AND ALGORITHMS

FOR SOLVING SIP PROBLEMS

153

T h e o r e m 8.16. The set, S is dense and Gs is a subset of 8. T h e o r e m 8.17. The set L* = {a: (Pr) has only one point } , is dense, and Gs is a subset of L. T h e o r e m 8.18. The set L" contains an open dense subset of L. In [136], generic uniqueness of the solution to problem (/-") is investigated as generic existence and uniqueness of saddle points of Lagrange function. L(x, A) = ex + X(atx — bt), where A £ C*(T), A > 0. Suppose M = {a: L(x,X) has only one saddle point }. T h e o r e m 8.19. If for some point x0 g Rn there is a point A0 € C*(T), A0 > 0 such that (x0,X0) is a saddle point L(x,\) in the region (x G Rn, A G C*(T), A > 0),then x0 is a solution to (P1). Conversely, let x0 G Rn be a solution to (P1) and suppose Slaiter's conditions hold for Z. Then there exists A0 6 C*{T), A0 > 0 such that (x 0 , A0) is a saddle point of the function L(x, A). T h e o r e m 8.20. Let T be a compact space, \T\ > n, then M is dense and Gs is a subset of L.

8.5

Methods and Algorithms for Solving Semi-infinite Programming Problems

Consideration is being given to linear problems of the form (P) (8.7) and their du­ al problems. A review of algorithms for solving linear semi-infinite programming problems [54, 76] includes locally convergent methods [46, 64, 66, 73], discretization methods [56, 57, 74, 75, 77, 94,
.;

the cone of the generalized positive finite sequences of real functions of R The set S C T is called basic if {a,, t G S} is basic in Rn and there exists A G A such that supp A C S. For the given basic set S with the associated A and x, two cases are possible:

(A): irdlatx - bt) = 0; teT

(B): 3u 6 T is such that aux — bu < 0. If S = {ti, ■ ■ ■, tn}, then there are uniquely determined real numbers at, . . . , an such that au = aiai + • • • + anan. For (B), there are two possibilities: (Bl): cti < 0, i € T~n; (B2): fi = min{^-; a, > 0} = -£-. Then we consider a new set

5' = (5\.fe})UWcT.

154

CHAPTER

8.

INFINITE

AND SEMI-INFINITE

PROGRAMMING

T h e o r e m 8 . 2 1 . [54] Suppose the following assertions are true: J. In case (A), x and A are respectively optimal solutions of (P) and (D), and ex = v(P) = v(D) = ip{\); 2. In case (Bl), (P) is unsolvable and lim ip(X + p,p) = + o o , V/i > 0 (here X+p,p is a feasible direction at the point X, p € R^). Furthermore, if au G {at, t g supp A} (e.g., if X is nonsingular), then {X + pp, p > 0} is the unbounded edge of A. 3. In case (B2), S' is the basic set and its respective point X' = X + pp £ A. In addition, if au £ {at, t 6 supp A}, then i/»(A) < ip(X') and [A, A'] is the bounded edge of A. At the r - t h step the simplex procedure either t e r m i n a t e s (A) or (Bl) or we have a new basic set SV+1 ^ Sr. If, however, Ar is singular, t h e n apparently A r + 1 = Ar, and hence we have what is called cycling. The simplex procedure generates in terms of the initial basic set S i , a finite or an infinite sequence of basic sets {Sr}. For the last basic set Sp in this sequence, we either have optimal solutions to (P) and (D), xp and XF, or state the inconsis­ tency of (P) and the unboundness of (D). For a finite sequence, lim ex' = infer and lim ip(Xr) = ip(X). Although the admissible set A is a convex set in the space r—>oo

of generic finite sequences, it retains m a n y properties of convex polyhedral sets in finite-dimensional spaces. These properties provide a framework for interpreting the leading transformation geometrically. Based on t h e dual approach [55], geometric interpretation is given to such notions as boundary points and feasible directions, edges and conjugate directions, etc. This allows the main iterations of the simplex algorithm to be shown geometrically. In [55], the ways of finding the basic solution are examined. T h e optimal solution of linear SIP problems can be computed in a va­ riety of ways. T h e most important of these are exchange algorithms (Dantzig simplex method) and descent algorithms (gradient methods). T h e fundamental exchange algorithm for linear semi-infinite programming prob­ lems is the simplex method. T h e exchange algorithm is a generalization of the simplex procedure which allows introduction into the basis of one or more vectors at an iter­ ation. Execution of exchange algorithms for linear SIP problems is m a d e possible by the solution of linear equations. The solution methods will be numerically stable. T h e pair of dual problems, (P) and (£>), is examined [118] under the following assumptions: 1. (P) and (D) have no duality gap, i.e. the optimal values of (P) and (D) are equal. 2. (D) is solvable or bounded. 3. There are n linearly independent vectors among {at, ( £ T } such that at = (ai(t),...,an(t)T). We call {T„, A} the basic solution (here Tn = {tx, . . . , t n } ) if the vectors a{tx), . . . , a(tn) are linearly independent and A is a solution to t h e dual problem (D), i.e. A{tx,.

..,tn)X

= c,

(8.14)

8.5. METHODS AND ALGORITHMS

FOR SOLVING SIP PROBLEMS

155

where A(tu . .., tn) = (a(ti), . .., a(tn)) is the basic matrix, T'„ is the basic set, and the vectors a(t{), i £ l , n form the basis. Accordingly, the solution of the primal problem (P) is A(tu...,tnfx=(b(tl),...,b(tn))T. (8.15) We now implement each step of the simplex method , i.e. we pass to the basic solution (T„, A), which corresponds to a greater value of the objective function, by changing only one component of the basis (here only one column A(tu ..., tn) varies). Suppose t* £ T enters into the basic set. The linear equations are then solved to obtain representation A(tu...,tn)d=a(t*) (8.16) d = {du ..., dnf We assume that A(6>) = (xi - 0du ..., xn - 9dn, 9)T, \(6) is a solution of equality constraints in problem (D) such that A,-^) > 0 , i £ l,n.

e=^ =

mm{^-!d,>0}.

If there is no d{ > 0, then (D) is unbounded and (P) is unsolvable. If 9 = ^, then the element tr is eliminated from the basic set. The new objective function value for X(8): c(9) = c(0) + 9(b(t*) -

JTar(t')xr). r=l

In this manner three systems of linear equations (8.14), (8.15), (8.16) are solved. Since only one column or row is changed at one step of the simplex method modifying the initial method, the decomposition methods are successful in reducing the number of operations by an order of magnitude as compared to the customary simplex method. The Jordan-Gauss methods of elimination and inverse matrix which are commonly employed to solve linear equations are unsuitable. To ensure stability, use is made of the modification: the Gauss method of elimination with search for the main element in the column, or decomposition methods. Applying to the matrix (AJ.E) the conventional Gauss process of elimination with search for the main element in the column, we obtain (R\F), where R is the upper triangular matrix and F is such that FA = R. On the other hand, given F and R, the linear equations (8.14), (8.15), (8.16) can be readily solved, e.g., for AX = c <£> FAX = Fc or RX = Fc. In this case, laboriousness is proportional to n2 operations. If the basic matrix is fully partitioned at each step, the number of operations is proportional to n3 The method modification: if A = (o(
FA =

0

*

0 0

156

CHAPTER 8. INFINITE AND SEMI-INFINITE

PROGRAMMING

In fact, comparing only two rows yields a new partitioning A: (R\F). Now the number of operations is proportional to n2 To introduce into the basis [118] two or more vectors at once, we need to consider the solution of system (8.16)

A{tu...,tn)d'

= a(t*),

i = Y7k,keN; k

d1 = ( 4 , • • •, < ) T It can easily be shown that X(9) = X(9U . . ., 9n) = (At - £ 9,d\, T

;)

•, A„ — JZ &id%n, di

is the solution of problem (D). The corresponding

value c{9) = c(0) + £ 9,(b(t*) - £ xraT(t])) .= 1

= c(0) + £ A(i*). We require that

r= l

t= l It

all A(£*) > Q, i £ l,n, an increase in the objective function c(0) — c(0) = £ A(t*) i=l

be a maximum and all components X{9) > 0. Then we get an auxiliary problem in standard dual formulation max^>A(t*) subject to - d\

. .

U •

d\-

"1 . . 0 "

' h'

z

l

" Ai '

n

A„

(8.17)

+

4.

_0 . . 1

Jk. >0,iGl,fc,

z, > 0 , i € l , n .

Using the above simplex method, and considering that we have an optimal basic * \T k' < k (any other variables are solution of the form ($i, ^fc'+i, equal to zero), the constraints of the auxiliary problem become:

d\9l + ... + dfOy = Aj <* Ai(0) = A! - d\Qx - ... - df9k, = 0;

di,&l + ... + d£,ek, = \k,^\k,(e)

= \k,-di,el-...-d£,ek,

= 0;

d)0l + ... + dk/9k, + z3 = Xj & X}{9) = zh k' < j < n,

i.e. the first k! components of 9 are located in the basis and correspond to a(i*), . . . , a(t'k,), while the first k1 components of A(#) are zeroed. In this manner we replace ti, ..., tki by t\, ..., t*k,. It can be shown that this method is successful in seeking a new basic solution of (D). We have the primal algorithm for the SIP analog of a linear programming problem of the (P) type, (8.7). a(t) x > b(t), x G Rn,

t G T is a polyhedron in R: a.b are continuous.

(8.19)

8.5. METHODS AND ALGORITHMS

FOR SOLVING SIP PROBLEMS

157

Some results have been obtained for the generalized LP problem. Their applica­ tions can be demonstrated by setting problem (8.19) in equivalent form, where a free variable is introduced cTx —> min; T a{i) x - z(t) = b(t); (8.20)

I

z(t)>0, zgC°°[0,l). Let (£, 0 be a feasible point for (8.20). It is placed in correspondence with the set of active points {t g T: ((t) = 0}. At the active points the free variable (greater than or equal to 0) has a strict local minimum equal to 0. To keep track of zero degrees, we define d(i). If {ii, . . . , tk} is the set of active points, then d(i) is the least integer j which has the property C"+1H*«) 7^ 0. Suppose d(i) is defined on Vi g l,k. We consider the properties of extreme points in the generalized LP problem which are k

transported to problem (8.20). Let m = k + "£, d(i). We construct an (m x n) matrix A-A = (a(f,), a'(ii), . . . , a (d(1 »(«i), ■ • •, a{ik), • ■ • > a^k\{tk))T The point (£, () is extreme for problem (8.20) if and only if the columns of A are linearly independent, which is equivalent to span {a'J>(i;): j = 0, . . . , d(i), i = 1, , . . , k} — Rn. The purification algorithm A is used to obtain from any starting feasible point an extreme point for problem (1.20). The process proceeds at any step so as to retain all previous zeros of the free variable until the new one is obtained. A s s u m p t i o n , {x: cTx < 0 and a(t)Tx > 0, T g [0,1]} = {0} (it is valid, in particular, when the feasible region is bounded). Algorithm A. Step 0: (f\Ci) is a feasible point for (8.20); r = 1. r-th iteration: Step 1. Let (ti, ..., tk) be active points for (£ r , (r); define d{i), i = \,k. Step 2. Define a subspace Tr C R: Tr = Rn if k = 0; otherwise Tr = {x: a^{t,)Tx = 0, j = l,d(i), Vi = 171}. If Tr = {0} — stop; ((r,(T) 's an extreme point. Step 3. g'~ = —Prr(c) (PTT is the orthogonal projection onto Tr); ifg' = 0 select gr ^ 0 arbitrary in Tr. Step 4. 0r = s u p { - [ a ( t ) V / C r W ] , t g [0, 1], t ± t%, . .., h}.

Step 5. C+i = f + U / / W ,

CH-I(')

= a(-) T f +1 " &(■)■

Step 6. r := r + 1, go to Step 1. It has been proved that, under the above assumptions, algorithm A yields an extreme point in at least n iterations, and the objective function value at this point does not exceed the one at the starting point. Algorithm B has been developed for problem (8.20), using a feasible extreme point at each step. The resulting points are taken to be nonsingular, i.e. the corresponding matrix A is invertible. Define n scalars \t]: cTA'1 = (Ai |0 , . . . , ^i,d{i), • • •, )>k,o, ■ ■ ■, ^k,d{k)) = ^ Prove the following optimality property: the nonsingular extreme point ({,() is optimal if and only if for Vz = l,k, A,-,o > 0, Ay = 0 , j = l,d(i), which is utilized in algorithm B.

158

CHAPTER 8. INFINITE AND SEMI-INFINITE

PROGRAMMING

Algorithm B. 1. Select (f°,(o) to be a feasible point. 2. Applying algorithm A to this point, we obtain an extreme point (f 1 ,(\); r := 1. 3. T = (tj, . . ., tk)T are active points for (£ r , ( r ). Find A, A. Here A is taken to be of full rank. 4. If Ajfi < 0 for some j , then g = A~1e2j-i (e2]-\ is the vector with 1 at 2j - 1 and zeros elsewhere), x = £r +ag where a is determined from If a = 0 = sup{ — ayJ, t £ [0,1], t / h, ..., tk}. Let z(t) = a(t)Tx-b(t). Apply algorithm A to (x,z). Obtain (f + 1 , (r+1); k = r + 1. Transition to 3 ; 5. If Ai(] ^ 0 is some j , then h = e,, A(t) = (a(ii)a'(t 1 ), . . . , a(tk)a'(tk))T, l T b(t) = (6(<1)6'( min is feasible subject to x(r + o/i). £ r + 1 ; = X(T + oft); r = r + 1, go to 3. Consideration is being given to the case, where the solution at the extreme point is degenerate, and the general case, where the index sets T are in RF. Even application of the algorithms (A,B) may encounter computational problems which still remain unsolved. Theoretically, however, this method may be of interest in infinite extension of the simplex algorithm. One of the methods of descent is proposed in [100]. The algorithm has been developed for a generalized linear optimization problem in Hilbert space. Let S be any set. W is a function space: S —¥ Rq and U, Z are vector spaces. V = U ®W Here V is taken to be Hilbert space with the scalar product (•, ■). It is necessary that the elements of W have the norm associated with the scalar product or the supremum norm ||W^||oo = sup{||u)(s)||0O, \s 6 S}. Define the convex cone W+ = {w 6 W\ Wi{s) > 0}; W° = {w £ W; Wl{s) > 0, i = IT?}; V+ = U ® W + ; V° = U ® VF°. Introduce the relation ">" into V: f > v <=>({ — v) G V+; 0 is zero in V. Let W° ^ 0, and select some e 6 W°. Any element of the form (u, e) £ V° is taken to be preferable in V General statement of linear problems: ( min((c,d);(u,w));T((u1w)) = b;(u,w)>0; 1 («,ui) G V;

, '

c £ U, d £ W, b £ Z. T: V -> Z is a continuous linear operator. At each step we define V? to be an invariant non-identity endomorphism in V which transfers the current point (x,z) £ V° to the preferable (x, e) 6 Vt that is "far removed" (in the sense of the supremum norm) from the convex cone boundary. In the transformed space, a step is then performed in the direction of steepest descent (in the sense of the minimized functional) and the inverse endomorphism is used to obtain a new current point in the initial space. Endomorphisms Fz, F^ are obtained explicitly for reciprocal linear mappings of V into itself, FZ(V°) C V^, F^(V°) C V°. The generalized algorithm may work well under the following assumptions: 1. V = U®W is Hilbert space with the scalar product (■, •), U is the vector space, W is the functional space S —^ Rq; T: V -¥ Z is the linear mapping;

8.5. METHODS AND ALGORITHMS

FOR SOLVING SIP PROBLEMS

159

2. 3£ G V: ( > 0; 3. V(u,w) G V, {(c,d),(u,w)) = {F2((e,d)),Fz((u,w))); 4. Vz g W the kernel of linear operator T o Fz is Hilbert space in the norm induced by the scalar product (o indicates composition). We have the problem equivalent to (8.21): (SIP)

mm(Fz((c,d)),(u,y)),T

o Fz((u,y))

= b,(u,y) >0,(u,y)

e V,

(8.22)

where y = z~l Q w, and 0 : W x W -> W: (w Q v)i(s) = wt(s)v,(s), \/s G S, i = \,q. For (LP) we have a feasible point (x,z). Iteration: transform V using the endomorphism Fz'. (x,z) —I (x,e). Step is accomplished from (x,e) to obtain in Fz(V) the least SLP functional point. Applying Fz to V yields a new current point in V°. In [101], the step direction is taken to the orthogonal projection of — Fz((c, d)) onto kerTo Fz. Algorithm. Step 0. k := 0. Step 1. Transform the feasible point (x,zy^> > 0 into (x,e) using Fzw, i.e. (x,e) = FzW((x,z)W). Step 2. Project orthogonally — Fz((c,d)) onto kerT o FzW. Accordingly, let Step Step Step Step 1. This

3. Find a: e + azp > 0, z' = e + azp. 4. Invert (x,z)( t + 1 ) = F*m((x + aCp,z')). 5. Check the stopping criterion. If so, then stop; if not so, then k := k + 1, algorithm is applied to LSIP problems (LSIP)

{mmcTx,A(s)x

> 6(s),Vse 5'};

T

(8.23)

n

A{s) = {a,j(s)}; 6(5) = (bi(s), ..., bq{.s)) ; c, x € R ] S = [lt,v,]. The problem can be rewritten as (8.21). Let us introduce free variables Zi(s) G C°°[l„Vi]. Obtain {min cTx, \A(s)x - z(s) = b(s),Vs 6 S},

(8.24)

where z(s) > 0, x G Rn, z € f[ C°°[/;,i>,-]}. Here U = Rn, W = Z = f[ C=°[U,vx\, !=1

T(x,z)

= A(-)x-z(:);

{(c,d)(x,z))

>=1

= cTx+

£ / di(s)zi(s)ds.

Select e, G (7°°ft,Oi]:

•=if,

e;(.s) = 1, Vs 6 [/,, Uj]. It can be readily seen that the direction of steepest descent is

-M). Step 2 requires projection onto kerT 0 F*m, and it is a finite subspace of V Perform the following steps: i. Find the basis {ut; 1 = ~L/n} oiToFzW, since for any (u,w) G k e r T o F | ( M , w = AuQ z~l =>■ Ui = [ki,u), i = V " , h = (0, . . . , 1, 0, 0, . . . , 0), n(s) = ( a « . ( s ) M i ( a ) ) -

ii. Orthonormalize this finite basis using the Gram-Schmidt process.

160

CHAPTER

8. INFINITE

AND SEMI-INFINITE

PROGRAMMING

Step 3 requires a > 0: e + azp > 0. This is accomplished by selecting m i n o r s ) in [0,1]. Let t h e minimum be equal to -z< ml ' n >; then a - ' " i ? ^ . a ( m u , ) is a constant z

p

multiplier in (0,1). Assume z£ m "" < 0. In Step 5, use should be m a d e of t h e criterion of a sufficiently close distance between two adjaced solutions. Suppose t h a t in problem (8.8) c G Rn, c / 0; T is t h e compact and X is the convex compact set in Rm and Rn, respectively; u(-) and A(-) are continuous in T; there exists x such t h a t u(t)x > X(t) for any t € T, and it is not optimal for (8.8). One of t h e first applications of t h e cutting plane m e t h o d (based on t h e Kelley cutting plane method for solving convex programs) is provided by t h e alternative algorithm [86]: SO: Problem (Zo): min{cz:Vx € X C Rn} is examined with k = 1. S i : Let Xk G Rn be a solution to problem (Zk-\). S2: Seek rmn{u(t)xk — X(t)}, t G T, and let tk G T be an element in which a minimum is attained. If u(tk)Xk — X(T — k) > 0, then Xk is optimal lor (8.8) and the algorithm terminates. S3: Eliminate the constraint u(tk)x > \(tk) from problem (Zk) and go to step SI. Referring to [65], we have the limit points of t h e sequence {x^} t h a t are optimal for (1.8) if t h e method is not bounded. If X is a polyhedron, each problem (Zk) is linear and execution of steps SI and S2 is significantly facilitated. In the general case, however, this presents a. complicated mathematical programming problem. As suggested in [62], this alternative algorithm can be modified in such a way that a "sufficiently'' violated constraint is sought instead of t h e constraint most suspectible to violation. Accordingly, the steps 5 0 and 5 1 are replaced by t h e following steps: 5 0 " : For (Z0), specify from step SO a sequence {6k} of nonnegative numbers such that lim Sk = 0. k—>-oo

52*: Let S(xk) = mm(u(t)xk — X(t)) for anyt G T. IfS(xk) > 0, then Xk is optimal for problem (1.8) and the algorithm terminates; otherwise we seek tk G T satisfying u(t)xk

- X(t) < 0;

u(t)xk

- X(t) < S(xk) - Sk.

Referring to [62], we have t h e algorithm based on t h e cutting-plane method [40] for convex programming problems: 5 0 : Let B > v(Z). Select a constant f) G (0,1) and consider problem (SZ0): max
! Select y G Y and let k = 1. 5 1 : Let (xk,<Jk) G Rn x R be a solution terminates.

(8.25)

x G A'. to (SZk-i),

If Ck = 0, then the

algorithm

8.5. METHODS AND ALGORITHMS

FOR SOLVING SIP PROBLEMS

161

52: In accordance with two cutting rules, (Rl) and (R2), we may or may not cut conditions from (SZk-i). S3: (I) If xk is feasible for (Z), i.e. u(t)xk ^ ^(0> V^ G T, then add the condition ex + \\c\\a < cxk to (SZk-i). Let yk = xk. 53: (II) Otherwise we seek tk 6 T such that u(tk)xk - \(tk) < 0. Add the condition u(tk)x - \\u(tk)\\a > \(tk) to (SZk-i). Let yk = yk-iDenote the resulting problem by (SZk). Let k = k + 1 and return to 51. Cutting rule (Rl): Cut off the condition ex + \\c\\ff < B or any other condi­ tion obtained in Step 53(7) on the previous iteration if xk is feasible for (Z), i.e. min(u(t)xkX(t)) > 0. Cutting rule (R2): Cut the condition from (SZk-i) if: (a) this condition was generated in Step S3(II) on the j-th iteration, where j < k; (b)ak<pa3; (c) the condition was not an equality in (SZk-\) in (xk, ak), i.e. u(tj)xk—||u(ij)||cr/t > \(t3). The convergence of algorithm for a convex problem prevails. Theorem 8.22. [62] The failure of the algorithm to terminate generates a se­ quence of feasible points {yk}, and the limit points of this sequence are optimal for (Z). Referring to [84], we have problem (SZk-i) with a polyhedral set X of the form X = {x:a{X > bi] i £ l , m } , i.e. problem max a; ex + |[c||<7 < cyjt_i; u(t3)x - ||ti(ij)|| A ( ^ _ j 6 Jk; d{X > £,-; i £ l , m ,

(8.26)

where Jk is the index set of constraints generated in Step 53(11), but not cut off by Rule (R2) prior to the fc-th iteration. Thus, we have to consider only the last constraint generated in Step 53(1). The dual of problem (8.26) is min(cyt_,Wo -

E Kt,)W3 - £ fcV5); '=1

j£jt rn

(SPk-i)

cW0-

£ u{tj)WjieJk

T,aiV,=0; '=i

(8.27)

||c||Wo+ £ H*f)||^- = 1; W3>Q,je{0}Ujk; Vi>0,ie l,m. Let (xk,ak) be optimal for (SZk-i) and let Wj = Wf, j € {0}(JJk; V, = Vf; i g l , m be optimal for (SPk-i). Then we have the following theorem. Theorem 8.23. [62] If the algorithm fails to end, then among feasible points the algorithm linearly converges in the objective function value.

162

CHAPTER

8.

INFINITE

AND SEMI-INFINITE

PROGRAMMING

In [65], the use of dual relations results in nonlinear equations for primal and dual variables. This system is determined by the set of necessary and sufficient optimality conditions for the primal (Z) (8.8) and the dual (F) (8.12) problem. It is also shown that more than n variables assume nonzero values. We have the s ystem of equations: (

n

m

J2 u{ti)tp{U) + J2 a,vt = c; (N)

\ v{t'~){u(ti)x - A(ii)7= 0 , ! G U v,(a,x — b,) = 0,J 6 l , m .

(8.28)

is system are taken (u(t)x — A(<)) has a local minimum tt if 0. Variables in th to be R: g{x,t) is continuous in X x T; g{-,t) is convex for any t and differentiable in X, and Vxg(x,t) is continuous in X x T; 4. 3x e int X: g[x,t) < 0; Vt 6 T (there exists x =£ x*, with ;* a being optimal); 5. f: Rn -> R; f{x) = \xTCx - pTx; C is positive definite. Let the set X be described by a finite number of constraints: X = {x e Rn: fj(x) < 0;

fj are convex ; j £ J = {1 , . . . , 9 } } .

For clarity, we consider only affine linear constraints, i.e. we have a quadratic problem (Q) (8.6). In order to implement the Kelley cutting-plane method, it is necessary to determine the most violated constraint at each iteration by solving th< s auxiliary problem (Hk)

max{g(x\t):teT},

8.5. METHODS AND ALGORITHMS

FOR SOLVING SIP PROBLEMS

163

which is nonlinear, generally nonconvex, nondifferentiable. The following discretiza­ tion is used, with {Hk) replaced by a sequence of approximating problems: max{g(xk,t):t€Tm},

(fl?)

where {T m } is the set sequence Tm —> T in the sense of Hausdorff metric. These assumptions guarantee the convergence of optimal values and solutions of the sequence {(H™)} to the optimal value and solution of (Hk). Algorithm A. [131]: 50: k = 1; T° ^ 0; z° = X and select Tm for m = 1,2,. . . such that Tm C T; Tm -* T; 51: Compute the solution of the subproblem min{/(;r):zeZ':-1};

(fit-,)

52: Compute the exact solution tm of the auxiliary problem (HI71); 53a: If g(xk,tm) < max{g(xk,t) : t € T}, then go to Step 52 with m = m + 1; otherwise tk = tm; 536: If g(xk,tk) > 0, then go to Step 54; otherwise the algorithm terminates and k x is the approximate solution of(Q); 54: Adjoin the intercept Sk(xk, tk, x) = g(xk, tk) + Vxg(xk,tk)T(x

- xk) < 0

and define Fh = {V g Tk~l: SJ(x3,V,xk) = 0}, where Tk~l is the index set of(Pk-i) k k k k and the sets T = F {J{f }; Z = f) {x: Sj(x>,V,x) < 0}f]X. Go to Step 51 veTk

with k = k + 1.

The auxiliary problem (Hk) in algorithm A is solved by the sequence of associated problems (H™). If in Step 53a the iteration terminates at m = m 0 , then the ap­ proximation th = tmo of the global maximum t of the problem (Hk) is achieved. Let dk be a deviation of the value of the approximately computed and most violated constraint g(x,tk') in (H]*°) at the point Xk(Hk)

g(xk,tk')

=

mzx{g(xk,t):teT};

g(xk,th')-g(xk,tk).

dk =

Theorem 8.24. [110, 131] Let lim 4 = 0 and suppose the sequence {xk} obtained by algorithm A converges to the point x* Then x' is a solution to problem (Q). Theorem 8.25. [110, 131] Let lim dk = 0. Then the sequence {f(xk)}

obtained

fc-+co

by algorithm A increases monotonically. Theorem 8.26. [110, 131] Under the assumptions of Theorem 8.24, the sequence {xk} converges to the unique solution of problem (Q). Let constants M > 0, N > 0 be such that: ||V/(s)]| < M; Vx £ X and ||V.j(a!,*)|| < N\ Vs G X, "it £ T.

164

CHAPTER 8. INFINITE AND SEMI-INFINITE

PROGRAMMING

T h e o r e m 8.27. [131] Under the assumptions of the Theorems 8.24 and 8.25, {xk} and {f(xk)} have the arithmetic convergence rate, i.e. there exist constants ko, ai and a2 such that: 11/* - f{xk)\\ < di/k,Vk where a, = l /

7

( < ^ p ^

> fc0 and ||a* - xk\\ < a2/Vk~,\/k > k0,

a2 =

lMflg^).

For application of the algorithm, it is of interest to consider the case where T = [a, b] C R or T = [a, b] x[c,d]c R2 In the discretization of the problem (/?*), T is replaced by 7\ m C T with the density max min \\i — t II < hm, t€T t'eThm "

i.e. we have the problem

(#£"*)

m&x{g(xk,t):t

£Thm}.

Modifying Steps S2 and 53 of algorithm A, we have Algorithm B . [110, 131]: Select hi; h > 0; e\ > 0; e G (0,1) and replace in algorithm A Steps 52 and 53 by the following ones: 52*; Compute thm which exactly solves problem (Hkm). S3*a: If g(xk,thm) < e 1; then go to Step 53*6, otherwise set tk = thm and go to 54. 53*6: If hm < h, then the algorithm terminates, and xk is an approximate solution of (1.6), otherwise return to Step 52* with hm = hme. We have the discretization network method for the nonlinear problem: min/(x);

X = {x £ Rn\c{x,t)

< 0,

t € T};

(8.30)

c: R71 x R —> R; T is a compact set, T C Rr, f is continuous, A' is bounded. This method does not require optimization over the entire T, while the solution of the original problem is replaced by a subproblem sequence: mmf(x),

XkCX,Xh

= {xeRn\c(x,t)<-ph,teT},

(8.31)

x£Xk

where Tk is a finite subset of T. It is assumed that: c(x,t) is Lipschitzian: |c(x,<) c(x,s)\ < L\\t — s\\; L > 0, Vf, s, c is convex in x, Vf. Slaiter's conditions are satisfied: 3x* e Rn: c{x*,t) < 0 , Vf e T. Special significance is attached to the function a c which yields a neigbourhood, where the constraint inequality is still retained: ac(y,t,f3):c{y,t)<-0,

when \\t-s\\
s£T.

(8.32)

For the generalized algorithm to be operative, we need to specify ac and the way of specifying an arbitrary network in T For two cases the ac is obtained explicitly:

8.5. METHODS AND ALGORITHMS

FOR SOLVING SIP PROBLEMS

165

1. Let c(y,s) be differentiate in 5 on T, and suppose g(y,s) is a gradient c and there exists G(y,t) > 0: \\g(y,t) - g(y, s)\\ < G(y,t)\\t - s\\, s g T, then ac{y,t,0) = l(\\9(y,t)\\2 + 4G(y,t)\c(y,t) + t3\y/i-\\g(y,t)\\}/2G(y,t). 2. Let y g Rn,teT,P> 0, c(y, t) < - / ? , select h > 0. Suppose there exists Q(s) which is a quadratic function with the following properties: | Q[a)>c(v,*)+Pfat\\a-t\\ < h; \ Q(s) = c(y,t) +/3 otherwise. Let Shea, distance from t to 5 = {s g T\Q(S) - 0}, 6 = +oo, if S = 0, then define <*c{y,t,P) = min{h,S}. An algorithm is proposed for generating an arbitrary network for prime sets T. Let T = I\ x • • ■ x Ik, I, = [p,; g,], /i, = (q{ - Pi)/rn.i; the network M3 = {px + fc1/i1/2J,...,pr + fcr/v/2J},fc€ {0,...,2-'m,}, j = ]~F. Algorithm. Select Po > 0: 0 < 0O < mm{-c(x',t), t € T), x' g X. Given L > 0 — Lipschitz constant, function ctc, the rule for generating "/-network in T. Step 0. 70 = Po/L. M0 — 7o-networJc in T. TQ = MQ, k = 0. Step 1. Solve the problem {min/(x); c(x,t) < —Pk, t S Tk} which is a. finite convex programming problem. Let y be its solution; j = 0, EQ = To. Step 2. If j = k, go to 4, otherwise E'j+1 is a point set: {t £ E3\ac(y,t,Pk) < 7y},' £ J + i is a point set in 7 J+ i networic M}+i, such that the distance to E'J+l does not exceed 3~fj/2; j is replaced by j + 1. Step 3. If c{y,t) < —Pk for t g E}, go to Step 2, otherwise c = {t g £j|c(y,<) >

-/?i},ri = rj,uc,gDtostepi

Step 4. xk = y, Tk+l = Tt, Pk+i = Pk/%, lk+\ = 7*/2, fe = k+ 1, go to Step 1. This algorithm generates the sequences {Pk}, {jk}, {Mk}, {xk}. A theorem is given to prove that with Vfc, xk g Xk C A' is a feasible solution to problem (8.30), limit = z — optimal solution (8.30). If / is convex, then there exists k > 0:

f(xk) - f(z) < k1~k The following discretization algorithm was proposed in [18] and developed for quadratic SIP problems. Consideration is being given to QSIP problem (QSIP)

{min F(x) = cTx + -xTCx,

xTa{t) < b(t)},

C is real, positive definite, t g T, T is a compact set, a, b are continuous. The original problem is replaced by the sequence of problems QSIP{Gt)

{min F(x), xTa(t) < b(t),t g G,-},

where Go C G\ C • ■ ■ C T, Gk are finite sets. The following method is designed for constructing Gk: the network T[h] is an intersection of the set T and the set p

{£0_|_ ^2 jih,ei\ji g Z}, hi is a step, t0 is selected in an arbitrary way, e< is the i-th basic i=i

166

CHAPTER 8. INFINITE AND SEMI-INFINITE

PROGRAMMING

vector Rn We may specify {ht} -* 0: T[h°] C ■ ■ ■ C T[hn] ■ ■ ■ C T. Let T[fefc] = Gk. The number of points in the network Gt rapidly increases with increasing i. This generates a need for subtler methods of constructing the sets involved in solution of iteration problems. Referring to [19], we have a new approach. It is essentially aimed at finding a solution to QSIP(G,) not on the entire network T[/t,], but on its specially chosen subset T[h%\ of points, about which the problem constraints are violated, and in terms of the solution of QSIP(G;_i) which has been treated at the preceding stage. Define R(xk) = {t: t G T[hk}\ xja(t) = &(/)}; Xk is a solution to QSlP{T[hk}). Algorithm for selecting f[hk] is proposed in [22]: Step 0. Find a solution x0 to QSIP{[h°]), R = R(x0), f[h°) = T[h0}. Step k. Given: R, f[hk-1}- R C f[hk-1} C T[/ifc->]. xk is a solution to QSIP

(f[h^}).

a) if'Xk-i satisfies the constraint of QSIP (T[hk 1 ]), go to c), otherwise go to b); b) select a new T[hk~1] from the points of R and those points in T[hk~l] ,where the constraints are violated; solve the new problem; the new solution is Xk-i; if R(xk-i) add to R an arbitrary point from f[hk-1} \ R, go to Step k; c) select f[hk}: R C f[hk], find a solution to QSIP(f[hk]); R := R{xk). Transition to Step k-f-1. Referring to [153], for large-scale block problems we have the algorithm for the sequential truncation method. The analog given for the Kornai-Liptack method is based on dual estimations of the linear programming problems specifying the con­ straint matrices multiply. Referring to [80, 144, 145], for the solution of a nonlinear problem of the form (8.29) we have globally convergent methods (a generalization of the Wilson method solving the proposed problem by a sequence of quadratic programming problems). Let X0 C Rn be open, Y C Rm compact , and F: X0 -»• R; f: X0 x Y -> R; g1: m R —> R; j £ J; \J\ < oo three times continuously differentiable functions. We now solve the following problem: mmF(x); x G X = {x 6 A'0 : f(x, y)<0,ye

V};

(8.33)

! Y = {y.g>(y)<0,]£ J}. To ensure convergence, the sufficient condition must hold for local quadratic con­ vergence to the optimal solution So, including the assumption of strict local unicity of x0. We assume that x 0 is a strictly local unique solution to problem (8.29) if for any l e A ' f l U(x0), (U(x0) is some neighborhood) F(x) - F(x0) > Q||.T - x 0 ||; a > 0; ||x|| is some vector norm. Referring to [144], we have the algorithm extending the Wilson method to SIP problem: Algorithm WSI. 50: Given zk = {xk, u'k, yik); i G T~f; let k = 0;

8.5. METHODS AND ALGORITHMS

167

FOR SOLVING SIP PROBLEMS

Sk: For k > 0, we calculate the optimal solution zk+1 for the following approxi­ mation problem: minF(x,zk) = F(xk) + (x xk)Fx(xk)-r k T k + ^(x-x ) Lxx(z )(x~xk); k k { f(x,y,z ) = f(x ,y) + (x- xk)Tfx(xk,y) <0,y (

(POzk)

where L is the Lagrangian L(z) = F(x) + J2 u'f(x,y'),

Je

(8.34) eY,

- problem {PO) is approx-

;=i

imated by the SIP sequence (POzk) whose structure is simpler than that of (PO). T h e o r e m 8.28. [144] Let some second-order sufficient optimality condition hold for the optimal solution x0 of the problem (PO). Then: 1) for any k, the Zj, satisfies this condition for (POzk); 2) the sequence (z<.) is quadratically convergent. To solve SIP problem (POzk), we need to consider the finite optimization problem:

(FPOk

mmF(x,zk) = F(xk) + (x-xk)Fx(xk)+ k T k + \(x - x ) Lxx(z )(x - xk); x £ A'(-Y is a neighborhood of xk+l); / ( * , y'(x), zk) = f(xk,y'(x)) + (x- xk)Tfx(xk, y'(x)) < 0; k I f(x, y', z) = f(x , y') + (x- xk)Tfx(xk,y>) < 0, y> e Y,

(8.35)

where Y is a subset of Y, and L is the previously introduced Lagrangian. T h e o r e m 8.29. [144] xk+l is strictly optimal for (POzk) if and only if xk+1 is strict-locally optimal for (FPOk). The optimal solution xh+1 for the problems (POzk) is computed as follows [80] (Step Sk in algorithm WS1 is replaced by Steps Sk0-Sk3). 510: Start with xs = xk, u" = ulk, i € l , r : s = 0 (for k = 0, x', u" can be chosen arbitrarily). Ski: Maximize the function f(xs,y,zk): y £ Y, specifying y", i G l,r. Sk2: Test for optimality. Go to Step Sk + 1 with zk+1 = z" or set s = s + 1. Sk3: To compute x3, u", solve the finite optimization problem:

(FPO

s-l^ k ,

( min F(x,zs-\zk) = F(xs-1,zk) + (x-xs-1)Fx(xs-\zk) + \(x - x^)TLxx(z3-\zk)(x x^); f(x,y<'°-\zk) = f(xk,yi^1)+_ + (x-xk)Tfxixk,y^-1)<0,iel,r; k k { f(x, y>,z ) = f(x ,y<) + (x- xk)Tfx(xk,y>) <0,y'e

where L is the Lagrangian L(z,zk)

= F(x,zk)

+ £ u'f(x,y'(x),zk); i=i

that Lxx is of the form Lxxiz, zk) = £ ufxyixk,

y')ylix)

+

Lxxizk)

+ (8.36) Y, it can be shown

168

CHAPTER 8. INFINITE AND SEMI-INFINITE

PROGRAMMING

For each i, an (m x n) matrix y'x is computed from the solution of linear equations. Return to Step Ski. is solved in such a way that 'k Fx(x,z°-\zk)

+ YJutfx(x,y''s-\zk)

= Q,

■=i

then for zk, zs is sufficiently close to z0, Step Sk3 is equivalent to an iteration of the Newton method for the system of nonlinear equations: F(x,zk)+£u'fx(x,y'-°-\zk) k

f(x,y'(x),z )

= 0,

= Q; z € V .

Thus the sequence {z3} converges at quadratic rate. For separably-infinite problems (A) (8.3) and (B) (8.13), in addition to Assump­ tions 1-3 (section 8.2) we make the following assumption [31]: Assumption 4. Denote by «,(•) thej-th component ofu(-) and byvi(-) the i-th component ofv(-). Let Uj(-), j € l,n — 1 be continuously differentiate on the open set containing S, and let «»(•), i £ 1, m — 1 be continuously differentiate on the open set containing Q. Theorem 8.30. [31] Let x* 6 Rn; >?*(•) € R[Q) be feasible for problem (A), and suppose that {rt,... ,rq} is contained in »]*(■) and rj* = n*(rt). Also, let y* £ Rm; A*() £ i?' s ) be feasible for problem (B), and let {t 1 ; . . ., tp} be contained in A*(-) and A* = A*(ts). Ifri, i 6 1,9 are interior to Q, and t{, i G l,p are interior to S, then £ Vu^tAx*

- Vu„ +1 (t.) = 0,i e l,p;

771

E Vi)j(r,-)y* - Vvm+1(n)

(8.38)

= 0,i £ l,q.

Given p and q, the unknowns in system (8.38) are x" £ R*, y* £ Rm; t, £ /?*; A* £ R; i £ l,p; r, £ /?' and ry* £ /?; i £ l,g. System (8.38) is composed of p + g + m + n-l-fcp-r'g/ nonlinear equations with the same number of unknowns. Referring to [31], we have one of the most successful methods for solving separablyinfinite programming problems (A) and (B), which is as follows: (1) region 5* in problem (A) is replaced by a subset containing finite points; and definition is given to the solution of the finite linear problem and its dual; (2) using the results of Step (1), the initial point is obtained for iterations of the Newton-Rafson method in the form of the nonlinear equations (8.38) derived from the dual relations between problems (A) and (B). Most of the methods proposed in [46, 54, 72] for solving SIP problems are locally convergent. The global algorithms which guarantee convergence to a stationary point in the problem are given in [33, 52, 144, 145], Referring to [74], we have a comparison of three numerical search methods for solution of SIP problems: discretization, exchange algorithms (e.g., simplex method

8.5. METHODS AND ALGORITHMS

FOR SOLVING SIP PROBLEMS

169

and its modifications), and continuous methods (such as the Newton method) which do not use discretization in the ordinary sense. Theoretical results and examples show that the first of the methods is generally useful only in obtaining some approximations to be further improved by the third type method. The idea of the first discretization method is that the infinite set should be replaced by a finite subset sequence, where­ upon the primal SIP problem should be replaced by a finite subproblem sequence. Computational time substantially increases as the discretized problem increases in dimension. Modifications of the simplex method permit a reduction in the amount of com­ putations by an order of magnitude, but these methods retain the convergence rate that is linear or a little better. The methods based on the Newton method [64, 74, 80, 145] have superlinear quadratic convergence. The penalty function methods which ensure adequate convergence of iteration procedures to a stationary point are important in the construction of global algorithms for nonlinear programming. Referring to [32], we have an exact penalty function for semi-infinite programming which is a generalization of the ^-exact penalty function in nonlinear programming. Such function is constructed for a convex problem, and then necessary existence condi­ tions are provided for a local minimum of the penalty function (Theorem 8.9) subject to the existence assumptions of the global minimum of this function (Theorem 8.10). In the general case, additional assumptions are made and a proposition similar to Theorem 8.10 is formulated. Proofs for the stated theorems are constructive, and the quadratically convergent algorithm is based on these ideas. The results compare favourably with [33]. Referring to [33], we have a projected Lagrangian algorithm for semi-infinite pro­ gramming (SIP). Efforts are made to develop the locally convergent methods on the basis of an exact penalty function. The method of the last type is discussed in [33]. The drawbacks of this method are: each of its iterations calls for solution of a quadrat­ ic programming problem with inequalities, while the high rate of convergence calls for conditions that are not necessarily satisfied. The modification of this method proposed in [33] permits obviation of such drawbacks. We have the algorithm for SIP problems using the quadratic sequential program­ ming methods together with an exact penalty function of class L^. Its global con­ vergence is proved. The proof does not require that the implicit function theorem be applied to SIP constraints; it suffices to impose a weaker condition on the finiteness of points transferring a global maximum to any SIP constraint. We have the minimization method for locally Lipschitzian functions using approx­ imate values of the functions. This method yields the SIP minimization algorithm for exact penalty functions which is similar to the method of confidence regions employed in nondifferentiable optimization. A finite method is constructed for SIP approxima­ tion of an exact penalty function. In [91] proposes alternative penalty methods. As suggested in [913], the proce-

170

CHAPTER 8. INFINITE AND SEMI-INFINITE

PROGRAMMING

dures of discretization, regularization and those of the penalty method are harmonized in such a way that for each discretized problem there is a fixed unconditional mini­ mization problem which is to be solved before the results of two adjacent iterations are brought into a certain proximity. Provision is made for the adaptive method of constructing the next discretized problem using the approximate solution of the two preceding problems. Consideration is given to the problem mm{/(u) : u G K0}; K0 = {u g Rn : g(u,t) < 0,Vi <= M};

(8.39)

f,gt are convex and differentiable in Rn M is a compact subset in a normed space Y Denote u* = arg min /(«); / m ; n = min f(u); Sr = {u g Rn: \\u\\ < r } , || • |j is the Euclidean norm. We assume that u* ^ 0 and the constraints satisfy Slaiter's condition for arbitrary r > 0, u £ Sr, t,t' €. M with some L = L(r) < oo: \g(u,t)-g(u,t')\
(8.40)

Let u be Slaiter's fixed point with Mi as a finite /i;-network on M. K, = {u g Rn;g(u,t) c

< 0;V< G M t }:

i M = min{/(u) + -||u|| 2 },a = - m a x g ( « , f ) ; C (r)

= a- 1 [/(S) + ( P | | + r ) 2 - C l ( r ) ] .

Suppose that {/*,}, {£;}, {£ t }, {T,} are the given sequences of positive numbers ap­ proaching zero. Let us fix r so that u'r]Sr/8^0;

u x ' 0 e A'ifl 5 r/4i

K M ^ E b K ' l + ^ t J + nft !£M,

^,5(u) = /(u) + v;(u) + ||u-u^- 1 || 2 , where c(r). To find a solution to this problem, we construct a sequence {ti 1,s }; s = 0,. .. ,s(i); i — 1,2,... ,s(i) are determined during iteration. Algorithm, i — 1, s = 0, s(i) > 0. Step 1. If s = s(i), then u'+h° = u*'sW; i := j + 1; s := 1; if, however, s < s(i), then s := s + 1. Step 2. Determine the point u ,,s from the condition ||VV'i,su''s|| < e\. Step 3. For ||u;'3 - u'^-l\\ > e, we set s{i) = s + 1; go to Step 1. Step 4. If ||u ; ' s - u^-'H < e, then s(t) = s; go to Step 1. Denote q(r) =2rLa~',£, = ^- + (j(i|Mi|)5r, 4 , where |M,| is the number of elements in the set Mt. is(r) = sup ||V/(u)||. u6S r

8.5. METHODS AND ALGORITHMS

FOR SOLVING SIP PROBLEMS

171

T h e o r e m 8.31. Let hi+1 < ht, Vz, h, < aL'1; let condition (1.40) hold, and -[2u{r)q{r)h, - (e,- - e,)2} + e, < 0 for any i; oo

EiiMr)q(r)h^

+ E, + 2q(r)ht} < r/2.

!=1

For the algorithm we then have s(i) < oo with any i, \\u^'\\ < r, Vi, s and the sequence {u*,s} converges to some u* 6 U". Moreover, /(u*'*W) - inf f(u) < 4re, + (4r + v(r))e,; p(u'^\

K2) < £,;

p(v,Q)=

inf | | t ; - H I -

An estimate is made of the method convergence rate. Denoting IM,O = /(«''°) /mm + t/(r)(ff('")^« + £,-)) a n < i adjusting the zero tendency of the sequences {hi}, {e^}, {e,-}, {r,} in a special way, we guarantee the estimates: ||«" s -«*||<3[ / i ! ,o/6] 1 / V / 3 ' + 3 ) / 2 , t-I

6 is a constant > 0, q is a constant: 0 < q < 1; /?; = 2 s(£). In the case s(«) = 1 for Jt=i

any i we get:

||u" s - U *||<3[ W ,o/&] 1/ V i - 1)/2 Referring to [26], we have the iterative algorithms for nonlinear semi-infinite prob­ lems with recurrent constraints (systems of associated optimization problems with or without recurrent constraints). For the convex problem (8.5), [27], however, there is an iterative algorithm of the gradient form using the penalty function method. m

ut+1 = ut-

S, fin1)

+ Y, ^fl,«(u')GJ,{u'); J=l

t

H]t(u ) J

=

a]t-b]lG]t(ut)\\G'}t(ut)\\-2;

{ 0, if G}t(uf) < 0,j e I7m,i e I~5o~; ~ \ 1, if G J( (u') > 0 , j 6 l,m,f € l,oo;

Proof is also provided for the theorem which determines convergence conditions for iterative algorithms of this form. In [68], semi-infinite problems are investigated using penalty functions and Lagrangian methods. A review is provided for relationship between SIP and optimiza­ tion problems with a finite number of variables and constraints, and two classes of convex SIP problems are introduced. One of these classes is based on the fact that the convex set can be represented as closed subspaces; the other class is defined by rep­ resenting the elements of the convex set as a combination of "points and directions"

172

CHAPTER 8. INFINITE AND SEMI-INFINITE

PROGRAMMING

A generalization is given to the nonconvex case. To solve SIP problems, necessary optimality conditions are generally taken to be a system of nonlinear equations. In the proposed method, such a system is constructed from a discretized version of the SIP problem under discussion, i.e. the problem with a finite number of variables and constraints. It is standard practice to solve this system by the linearization method. Finiteness is also the subject matter of [67]. SIP problems can be investigated by employing a variety of reductions to the finite case such as finite systems of infinite subsystems or finite probability measures. In [60], one of the general abstract methods for solving extremal problems (mar­ quee method) is generalized to the semi-infinite case.

8.6

Statement of the Infinite Programming Problem

The first statements of linear infinite programming problems probably refer to [100]. In accordance with [6, 7, 8, 10, 11], we define Eoo = {x = (xi,... ,Xk, ■ ■.)} to be a numerical sequence space with componentwise addition and multiplication by scalar. For x = (xj,. . ., zj.,. . .,) £ £«, we define the set J(x) = {k: x ^ 0}. Let E'^ = {x £ Ex: J(x) < oo} be a subspace of finitely defined elements. For a = ( o i , . . . ,ak, ■ ■ ■) G £«>, on the subspace E'^ we define the functional (a, x) = J2 a<x' i'SJ(i)

which is obviously linear in E'^. Let a0 = (a0\,. . .) £ E^,, b = (blt. . .) 6 Em. The infinite matrix is On . . . a\j .. . an

. . . a,ij

Denote a,. = (o,-j,...) € E^, ( a;, is the i-th row of the matrix A); a.3 = ( a ^ , . . .) 6 Ex (a.j is the j - t h column of the matrix A). The linear infinite programming problem then becomes: L oooo :inf{(a 0 ,x) : (a,.,x) < bhi - 1,2,..., x £ E'x} =

Vx>00.

(8.41)

Let 3 be the vector space of all vectors a;;, i 6 J , where J is an arbitrary index set of any power which is determined over the ordered basis Y with many, but only finite nonzero values, and let T = Yn be a finite-dimensional vector space over Y, while A0, {A,: i G ,/} is a collection of vectors therein. State the problem [100, 28] mint/'Ao; j/'A; > a,, i £ J,y where the vector af i g J, a, G Y.

eYn

(8.42)

8.6. STATEMENT

OF THE INFINITE PROGRAMMING

PROBLEM

173

Referring to [1], we have the linear problem min(a:, c); subject to Ax = b;

( 8 - 43 )

x e P,

where b £ Z, c £ Y; Z, Y, X are topological vector spaces. Problem (8.43) can now be represented as min(x, c); Ax-beQ; (8.44)

|

x £ P, where Q, P are positive definite cones in spaces Z and X, respectively. Referring to [108], we have an infinite-dimensional analog of the programming problem f{x) -» min; subject to (8.45)

I

Ax > j/o, where X, Y are locally convex spaces, A: X —> Y is a continuous linear operator , the functional is linear and continuous in X, and inequalities in Y are interpreted in terms of a partial ordering which is generated by a closed convex cone Ky. Consideration is being given to problem (8.45) with the additional condition x > 0 which is interpreted in terms of the partial ordering generated by a closed convex cone K~x in X [63], viz.:

I

maxci; x > 0 in X;

(8.46)

Ax < b in Z, where c £ X* is the X-adjacent space, b £ Z and A is the linear transformation from X into Z: A: X -> Z. Referring to [43], we have a linear problem with a finite number of inequality constraints and an infinite number of variables

I

c(x) —¥ max; A(x) =_d1_

(8.47)

Pj(x) >bhj £l,n,x£ V. Here V, U are vector spaces over the field R; A: V -> U is a linear operator from V into U; 0j, j € l,n, C are linear forms on V with values in R; &_,, j £ l,n are real numbers, d £ U. According to [27], (X, X') and (Y, Y') are two dual linear space pairs, A is a liner, weakly continuous operator mapping X into Y; A* is its associated operator; P(Q) is a weakly closed nonnegative cone in X(Y); P+(Q+) is the P{Q)-adjacent cone of

174

CHAPTER 8. INFINITE AND SEMI-INFINITE

PROGRAMMING

nonnegative elements in X'(Y'); b g Y, c 6 X' The partial ordering is induced by the respective cones in the spaces X, Y, X', Y' The problem is stated as follows: (TT) :

> b,x > 0} = F

mf{cx:Ax

(8.48)

or [122, 124, 125] x —> inf;

Ax > b.

(8.49)

The convex infinite programming problem is investigated in [100] minp(y); subject to G{y) > 0,

.

l

'

where G(y) = (gi{y),... ,gr{y),...) is the vector of concave functions given in the region which is defined by a convex set S of conditions on y, and ip(y) is convex. A more general problem is studied in [63]

I

max/(a:); x > 0 in X;

(8.51)

g(x) > 0 in Z, where X is also the set of all n-dimensional functions defined on T = { 1 , 2 , . . . } , while Z is the set of all Z: g(x) = b — z(x). Referring to [61], we have the general programming problem in function spaces [

(

/(a:)-+sup; $ ( x ) > 0 (G,);

(8.52)

xeG.

If G is convex, the functional f(x) is convex up on G, the operator $(x) is convex up on G (with respect to a positive cone Gi), then we have a convex programming problem in function spaces. Referring to [61] and [37], we have a functional analog of the LP problems. Suppose f(x) = ex is a linear functional, $(z) = b — A{x) is a linear operator of (6 6 E\), and G is a convex cone. Then we have

I

ex —> sup; Ax
(8.53)

z > 0 (G), i.e. the problem which is similar to (8.46). Referring to [141], we have the problem in Banach spaces (_ g(x) < 0,

x € G,

v

where / : X —> R is Frechet differentiable, the operator g: X —¥ Z is continuously Frechet differentiable; C S X, C is convex and closed.

8.7. DUALITY

OF INFINITE PROGRAMMING

175

PROBLEMS

Referring to [138], we have a quasiconcave problem with affine constraints

I

F(x) -> sup; G(x) = 0;

(8.55)

x € D, where F(x) = F2(F1(x)); F: D -4 W and G: X -4 Y are affine operators; F 2 : B —>■ y is a quasiconcave operator, i.e. the set {at 6 S: F 2 (x) > b} is convex V6 G F, and D C X, Fl(D) C B C VK; X, y , Z, and W are linear topological spaces.

8.7

Duality of Infinite Programming Problems

Let us define a series of problems that are the duals of the infinite programming problems stated in section 8.6. The dual of (8.41) becomes [6, 7, 8, 10]: (£««,)

sup{(-6,y) : (a.^y) = -a0j,j

= 1,2,. . . , y > 0, y £ &„} = v*^,

(8.56)

the dual of (8.42) [100, 28] is max Yl aixi] E K'x, = Ao; x € H,

(8.57)

x > 0.

In [1], the dual of (8.43) is max(6, w); -A"w + ce P*]

(8.58)

! w e W or that of (8.44) is max(fc, w); -A*w + ce P*;

(8.59)

|

weQ' Here the P- and Q-conjugate cones are P' = {yeY:{x,y)>0yx£ P};Q' = {w € W: (z,w) >0,VzG<3} and A* is the /1-conjugate operator. Referring to [127], we have the dual of problem (8.48): (O :

sup{y*fe : A*y = c, y* > 0} = G*

(8.60)

or the dual of (8.49): [122, 124, 125]

I

y'b —>• sup; A*y' = c;

y*>o,

(8.61)

176

CHAPTER 8. INFINITE AND SEMI-INFINITE

PROGRAMMING

the dual of (8.52): [61] \f(A) -» sup f o r A > 0 (G*),

(8 62)

-

where f (A) = sup F(x, A) = sup[/(as) + A$(r)] as well as the dual of (8.53): [61, 37] xeG xeG ( Xb -> inf; | c
I

(8.63)

A > 0 (G?)

and the dual of (8.46): [63] [ min(6,z*); I z*>0,z*EZ*; ( A*z* >c,c£ X".

(8.64)

The early investigations in finite linear programming made it apparent that the primal and the dual problem must be treated jointly. The duality theory, generalizing the classical Lagrange method, allows for extremality criteria and provides the basis for many computational algorithms. In the infinite case, the duality theory provides a principal means of studying extremal problems, but the situation here seems to be significantly complicated. In the finite case, dual problems (subject to fmiteness of extreme values) are always in duality. For infinite-dimensional spaces, however, this is generally not the case [100]. For this reason, it is standard practice either to consider a weaker relationship between problems (a week duality) [61, 37] or to prove duality under additional conditions on spaces, cones, etc. (solid properties of a cone, compactness of a feasible solution set, Slaiter's conditions, etc.) which are guaranteed by the validity of the required separability theorem [100, 127, 128, 105]. For linear infinite programming problems, the basic result is stated as a duality theorem [100, 28]. Theorem 8.32. If the system of inequalities yA, > at, i £ J has the MinkovskiFarkas property and is consistent, then we have one of the following results: 1. problem (8.42) is inconsistent, sup^Za.x, = oo or sup J2aixi 's finite; %

i

2. problem (8.57) is inconsistent, inf y'Ao = —oo; 3. problems (8.42) and (8.57) are inconsistent; 4. both problems are consistent and infy'Ao = sup J2 a;£; = JZ cnx* holds for a set of feasible solutions. In [1], the fundamental results of duality theory in linear infinite programming are treated systematically, and much thought is given to the strong duality theorem which ensures equality of the functional optimal values in the primal and dual problems. For the equality-constrained problem (8.43), the strong duality condition is stated as a closure condition for some sets constructed in terms of the problem parameters. For the inequality-constrained problem (8.44), the strong duality is guaranteed if there exists an inner point (Slaiter type regularity).

8.7. DUALITY

OF INFINITE PROGRAMMING

PROBLEMS

177

Referring to [61], we have a generalized duality theorem for convex programming problems in function spaces under assumptions of the form (8.52), (8.62). Theorem 8.33. If the objective functional f(x) and the constraint operator $(x) determined on the convex set G are convex upwards and the closure of the feasible solution set is nonempty, then the upper bound value is in the dual problem (8.62). As a special case, a generalized duality theorem is obtained for linear problems in function spaces (8.53),(8.63), as in [28]. Referring to [61], we have classes of convex and convex-fractional programming problems for which the generalized duality theorem changes to the conventional dual­ ity theorem of the extreme-value equality in the primal and the dual problem. In par­ ticular, some theorems establish the duality relationships without any requirements similar to Slaiter's familiar condition. Theorem 8.34. Let f(x) be a functional which is convex upwards and continuous in the convex set G, and let $(x) be an operator which is convex upwards (in a convex cone G\) and continuous in G. If lim fiJf,G)

= -co,

p—»oo

where h,[f,G)=

( { {

sup f(x), if GC\C,±% C\c" - c o , if Gf[Cp = Q\

xeG

(8-65)

C„ = {x : |as| = / ) , ! £ E}, G and Gi are closed sets, each bounded subset of G is weakly compact (which is guaranteed by the reSexivity of E D G), then the dual problems are related by duality relations. The functional 0} is weakly closed for the functional
178

CHAPTER

8.

INFINITE

AND SEMI-INFINITE

PROGRAMMING

In [37], duality theorems for linear programming in abstract spaces (infinite pro­ grams) are stated subject to conditions which are similar to Slaiter's condition. In [127, 128], such theorems are formulated on the assumption of solid properties of the cone U = {(Ax - y,cx - v) x > 0,1/ > 0 } . T h e o r e m 8 . 3 7 . Let n and v' be dual LP problems (8.48) and (8.60), with 7r solvable. Moreover, let 1. cone U be solid in Mackey topology; 2. b E int(AP - Q) in Mackey topology. Suppose then that TT and IT' are in duality and problem n* has a solution. T h e assumptions of the theorem can be readily verified if cone Q is solid, specifi­ cally if Y is t h e function space with a homogeneous norm. A similar theorem can be proved if the closure of V is taken instead of solid property. Bourbaki-Alaoglu theorem relates the solid property of a convex set to the weak (local) compactness of its polar. T h e duality theorem [128] is also provided. T h e o r e m 8 . 3 8 . Suppose that U, = {A*y*+x", y*b*-v*) : y* > 0, x* > 0, v* > 0}, its conjugate cone is 11+ = {(x,v)

:Ax + vb>Q,x>Q,v>

0},

t i e pair of dual problems ix and IT' (8.48), (8.60) are in duality, and TX has a solution if: 1. U* is T-solid, and subject to one of the following conditions: 2. TX is feasible, c g int(A*Q+ + P + ) ; 3. TX is feasible, (c,v0) g intU* for some v0; 4.a) ix is feasible; 4.b) x > 0, Ax > 0, ex > F implies x = 0; 5. the e-optimal set Dc is nonempty and weakly bounded for some e. Under assumption (1), the conditions (2)-(5) are equivalent to each other. Solv­ ability of 7r* (8.60) can be assumed instead of admissibility of TT (8.48). We have a uniform continuous-time programming problem. Using the convex infinite analysis constructs and the corresponding Kuhn-Tucker variational theorem, a dual problem is constructed and t h e strong and weak duality relations are derived. Here the uniformity assumption allows a special convenient representation of the dual problem for analysis. Linear and quadratic programming problems are treated as special cases. In [41], duality is studied for convex programming problems with operator con­ straints. In [137, 139], an abstract duality theory is developed for general vector optimization problems. This theory is applied to quasiconcave programming prob­ lems with linear convex constraints in the ordered topological spaces [138]. Duality relations are obtained for marginal functional values in t h e primal and dual problems. Strong and weak duality relations are provided for problems in which constraints are specified by convex operators.

8.8. OPTIMALITY

CONDITIONS

FOR IP

PROBLEMS

179

For nondifferentiable programming problems in [86], a duality theory is construct­ ed from application of the alternative theorem. Similar issues receive sufficient at­ tention in vector problems with a convex structure [143]. Issues of duality theory in vector optimization are treated in [34, 85] for nonconvex vector optimization problems [50, 51].

8.8

Optimality Conditions for Infinite Programming Problems

In [43], for problem (8.47) there are necessary and sufficient optimality conditions (the previously obtained results can also be used for problems with infinite inequality constraints). Theorem 8.39. Let x0 g W. In order that the functional C attain a maximum on W at the point x0 ■& the form C must admit of representation such as

c=

(8-67)

Y, W& + «, jeJ(x0)

where W = {x : Ax = d, 0j(x) >bj,j£l,...,n,x£ V} is a constraint polyhedron; J(x0) = {j g l , . . . , n : Pj(z0) = bj}, fij > 0, j g J(x0), a g (ker A)T (if x g Y, then x g {a g V* : a(v) = 0 Va; g X}; V is the set of linear forms on V). Similar necessary and sufficient optimality conditions are provided for convex and, specifically, quadratic problems [42-44], A special feature of the optimality criterion (8.67) is that there are no topological constraints or regularity conditions which are common for the infinite case. The fulfilment of condition (8.67) means that in problem (8.47) the Lagrangian has a saddle point. In [63], the results of the Kuhn-Tucker theorems are extended to cover the infinite case. Under a certain constraint (the weak closure of a special cone) on the form of the constraint operator, the conjugate cone and the cone of feasible directions, the necessary and sufficient conditions for extremum are provided as the existence of a nonnegative saddle point for the Lagrange function. In connection with prob­ lem (8.51) the Lagrange function is defined as ip(x, z') = f(x) + (z', g(x)), x eX,z*

g Z'.

Then the nonnegative saddle point (x,z*) of the function ip(x,z*) is defined by the following relations: x > 0 in X, z* > 0 in Z*] tp(x,z*) < tp(x,z*) < 0 from X and z* > 0 from Z* The Kuhn-Tucker theorem is proved for convex programming in linear spaces, but this requires no differentiability. Theorem 8.40. Let X and Z be linear spaces, and suppose that Px and Pz are closed convex cones in X and Z, respectively; f is the convex functional specified in Px; g is the convex function in Px with values in Z. And let 3 a point x° such that

180

CHAPTER 8. INFINITE AND SEMI-INFINITE

PROGRAMMING

x° > 0 in X, with g(x°) lying in Pz- Then the point x 6 X is an optimal solution of problem (1.66) <=> if there is another point z* 6 Z* such that (x,z*) is a nonnegative saddle point of the Lagrange function ip(x,z*). In addition to Theorem 8.40 the following theorem may be formulated for prob­ lem (8.46). Theorem 8.41. Let X and Z be local convex linear spaces and let some closure conditions be fulfilled. Then x is an optimal solution of problem (8.46) <=> 3 z* 6 Z* such that (x,z') is a nonnegative saddle point of the Lagrange function ip(x,z*). The Kuhn-Tucker Theorem is generalized to linear spaces. The way to do this is through consideration of programming in Banach and other spaces, where differenti­ ation is determined. The assumption of Theorem 8.40 that the cone Pz must contain a region substantially narrows the field of application of this theorem. The theorem can be formulated under substantially weakened assumptions. Theorem 8.42. Theorem 8.40 continues to hold for Z if the requirement that g{x°) be inside Pz for some x° > 0 is replaced by the following conditions: (A') for any nonidentically zero nonnegative continuous linear functional z* there exists xz- 6 X such that z*(g(xz>)) > 0; (A") the set A = {(t/, z) : y < f(x), z < g(x) for x > 0} has a nonempty kernel; (B) any element from Z can be replaced as the difference of two elements, each belonging to PzHere the kernel of cone Pz is composed of all elements such that for any direction in space Z there is a segment containing the point z and lying entirely in P%. The saddle points of the Lagrange function are considered where there is no dif­ ferentiability. Theorem 8.43. Let S be a, linear system and let Y and Z be linear topological spaces. Suppose that Py, Pz are convex cones in Y and Z with nonempty interiors; X is a (fixed) convex set in H; / is a concave function mapping X into Y; g is a concave function mapping X into Z. Let 3 the point x* £ X : g(x*) > 0 (i.e. g(xt) belongs to the interior of Pz). If x0 maximizes f(x) subject to g(x) > 0 then there exist linear continuous functionals y* > 0 and z* > 0 such that for the Lagrange function

*(*.*') = y'l/(*)] + **[s(*)] the saddle point inequalities ®(x,4)


<

${x0,z*)

hold for all x 6 X and z* > 0. Note that, in applications, X is a convex cone, namely a nonnegative orthant of system S. The following theorems were obtained for the case of differentiability (differen­ tiability is taken to be Frechet differentiability, spaces are Banach spaces, cones are closed). Theorem 8.44. (A) Let f be differentiable in X and let g be a differentiable function mapping X into Z. The cones Px = {x : x > 0} and Pz = {z : z > 0} are

8.8. OPTIMALITY

CONDITIONS

FOR IP

PROBLEMS

181

closed. Let x0 maximize f(x) subject to x > 0, g(x) > 0, and let g(x) be regular in x0. (B) From the relations x > 0 and 5g(x0, £)—g(x0) > 0 (( = x- x0) it then follows that -6f(x0;£) > 0. Theorem 8.45. (A) Let all of the assumptions (A) in Theorem 8.44 be fulfilled. Further, suppose the set W is regular and convex, while U and a are such that U(x) = 6g(x0; x),\/x £ X; a = Sg(xQ;x) - g(x0); x*(x)

e X;

= -Sf(x0,x)yx 13 =

-8f(x0;x0).

(B) Then there exists zj > 0 such that the Lagrange function $(x,z*) = f(x) + 3*[5(x)] has a nonnegative quasisaddle point in (XO,ZOJ!/O)> VO = ^ ,',e- satisfies the conditions Sx$((x0;z'0);() < 0 , V i >Q,x = x0 + (; &x${(xo;zo);x0) 5*9{{x0]4);Q

= 0;

= ([g(x0)] > 0 , W > 0,C = z* - z*Q;

Sz.^({xo;z;);z"})

= z'a[g(xo)] = 0.

Theorem 8.46. (Generalized necessary condition). (A) Let all the assumptions in (A) of Theorem 8.45 be fulfilled, and let the functions f and g be concave. Then the function $(x, z*) has a nonnegative saddle point in (xo, ZQ), where x0 is the maximal element. Theorem 8.47. Let X, Z, Px, Pz and g have the same meaning as in The­ orem 8.45 (including the regular convexity assumption for Wf and the regularity assumption for g). Let Y be such that, in the normed linear space Y there exists the bounded linear functional which is strictly positive on a closed convex cone K. Let us further assume that f is a differentiable function mapping X into Z so that x0 is the maximal element proper. (B) Then for some yj > 0 the function 4i(*,**) = !£[/(*)]+ *o[0(*)] has a nonnegative quasisaddle point in (x0,Zg,i/g). Here Wj = {w* 6 W*: w* = T*(v*), v* > 0, v' e V*}. For problem (8.45) there are regularity conditions [34] under which the minimum point is a saddle point of the Lagrange function. In a sense these regularity conditions were demonstrated to be necessary. In [122, 124, 125], necessary optimality conditions are given for the linear prob­ lem (8.48).

182

CHAPTER 8. INFINITE AND SEMI-INFINITE

PROGRAMMING

T h e o r e m 1.47. Problem (8.49) has an optimal solution such that 1. cx0 = F = G; 2. y'0(Ax0 - b) = 0; 3. y'Q + Ax - b = 0.

Theorem 8.47 corresponds to the complementary slackness theorem for finite LP problems. The formulated problem (8.48) fails to meet the nonnegativity require­ ments for variables. For the quasiconvex programming problem (8.55) with finitely many convex in­ equality constraints [138], necessary and sufficient optimality conditions are obtained in subdifferentiable form. The generalized Kuhn-Tucker conditions are provided for abstract problems of concave vector optimization in topological vector spaces[139]. In [126], optimality conditions are given in the form of Kuhn-Tucker theorem for problems in complex spaces. In [86], the generalized Farkas theorem is provided and necessary optimality condi­ tions are obtained as applications for general problems of nondifferentiable optimiza­ tion in infinite-dimensional spaces. Moreover, the alternative theorem is provided, the optimality and Kuhn-Tucker conditions are obtained as applications for mathematical programming problems. In [141], the necessary optimality conditions of the Lagrange multiplier rule type are provided under some assumptions of regularity. In [116], the problem of minimization on a subset of the topological vector space is studied from the point of view of the computational algorithms inducing specified minimizing sequences. Namely, the problem is defined to be an optimization problem on a sequence set in the generalized normed space. First- and second-order necessary optimality conditions are provided for the smooth and nonsmooth cases.

8.9

Existence and Uniqueness of a Solution to Infinite Programming Problems

Consideration is being given to a pair of dual problems such as (8.48) and (8.60) [38]. Some of the duality theorems, in particular, Theorems 8.37 and 8.38 are presented in [128]. The first assertion of Theorem 8.38 is provided in [105] on the assumption of solvability of w" (which can be assumed instead of admissibility of IT) and existence of the element (co,t><>) € Tint{{A*y* + x*,y*b) : y* > 0,.r* > 0} and fits in the general scheme of proving duality [120]. The use of the BourbakiAlaoglu theorem makes possible the proof of not only the equivalence of condition 3) in Theorem 8.38 and more convenient conditions 2), 4) and 5), but also the existence of a solution to the primal problem and the weak compactness of an £-optimal solution. Referring to [128], we have the theorem which provides a framework for link­ ing the duality, the compactness of a feasible set and the existence of a solution to

S.JO. METHODS AND ALGORITHMS

FOR SOLVING IP PROBLEMS

183

problem IT. Theorem 8.48. [128] Let: 1. n and IT* be a pair of dual problems, with n feasible, and let 2. p+ be solid; 3. x > 0, Ax = 0 => x = 0. Then: 1. w and n~ are in duality; 2. the feasible set n is weakly compact; 3. TV has a solution. The linkage between duality and existence of a solution for linear and convex infinite programming problems is also observed in other literatures, e.g. in [100]. Existence of solutions is proved for the class of parametric linear programming problems [100] where linear problems are studied in metric spaces. Just as the existence and uniqueness theorems for SIP problems (section 8.4), compact metric spaces are examined [98] and the uniqueness theorem is formulated for compact Hausdorff spaces X. Theorem 1.49. [98] There exists a compact Gs-set in 6 = 2X x cx such that any problem {f(x) ->• min, x e A, (A, / ) 6 0} has a unique solution. As suggested in [98], Theorem 8.49 is also valid for some classes of nonmetrizable compact spaces, specifically for weak compact subsets of Banach spaces or spaces which are homeomorphic with respect to weakly compact subsets of the dual Banach space possessing the Radon-Nikodim property.

8.10

Methods and Algorithms for Solving Infinite Programming Problems

For problems like (8.47), the procedure of simplex method [44] is generalized and proves to be finite-step even in the finite-dimensional case. The point xQ <E W is called an .E-point of W if (kerA)nt

fl

kerft) = ff; H = (ker A) f)(f)

ker ft).

The E-point of the polyhedron W is called nonsingular if \J(x)\ = diam{keiA \ H); the polyhedron W is nonsingular if any one of its E-points is nonsingular. Theorem 8.50. (On improvement of a basic solution). Let W ^ 0 and be nonsingular, H C kerc, and let x0 be an E-point ofW. Then, in ker A, there exists a collection of vectors e3, j £ J{x0) such that Pj(ek) = 5]k, j,k 6 J{x0), with Sjk as Kronecker delta. (I) If c(e1) < 0, Vj 6 J(x0), then x0 is the point of maximum of the functional c on W

184

CHAPTER

8.

INFINITE

AND SEMI-INFINITE

PROGRAMMING

(II) Ifc(eM) > 0 for some j 0 £ J(x0) and f3j(ek) > 0 Vj £ 1 , . . . , n \ J ( x 0 ) , then the functional c is not bounded above on W (III) If c ( e , J > 0 a n d t h e set I(x0) = {j £ l , . . . , n \ J ( s 0 ) : & ( e i o ) < 0} is nonempty, then: 1) there exists a unique j \ £ /(xo) such t h a t e = \bn - Pn{x0)\l\Pn(eK\

= m m 16,- - 0 i ( x o ) | / | A - ( e * ) | ;

2) the point y = x0 + eeJ0 belongs to W and is an 3) c(y) > c(x); 4)J(y) = (J(x)[j{j1})\iJ0}; 5) the vector collection gj, j £ J(y), where

E-point;

(8-68)

9h = e3o/0jAeio); g, = e, - {fih{ej)l0h{ek)^,j

£ J(y) \ {ji}

(8.69)

satisfies the conditions g} G k e r A , j € >/(y), 0}{gk) = Sjk, k G J(j/)- If H <(_ kerc, then c is not bounded on W below or above. T h e o r e m 1 . 5 1 . [43] (simplex method). Let W satisfy the conditions of Theo­ rem 8.50. Starting with any E-point of the polyhedron W, in a finite number of steps (one step is described in Theorem 8.50) it is possible either to reach the E-point in which a maximum of the form c is attained or to establish that c is not bounded above on W. In particular, any linear form either attains a maximum in one of the E-points or is not bounded above on W Note t h a t t h e number of steps in t h e simplex procedure does n o t exceed c™ = n\/m\(n — m)\, where n is t h e number of inequality constraints in problem (8.47), rn = 0, 3 e 0 > 0, h, i £ 1 , . . . , n in R such that \b{ — bf\ < £, j £ 1 , . . . ,n and for 6,-, i € 1 , . . . ,n such that \b, — B,| < e, i € 1 , . . . , n, the polyhedron W defined by the conditions A(x) = d, (33(x) > b3, j £ \,...,n, is nonempty and nonsingular. In [107], some numerical properties of the simplex are examined for t h e infinite case, specifically a new definition is given to the infinite simplex with a countable set of extreme points. Consideration is being given t o t h e question as t o which of the simplexes from this class allow approximation by their finite subsimplexes. In [44], t h e dual simplex method is extended t o cover convex infinite problems with linear constraints like (8.47). T h e theorems given here a r e largely similar to Theorems 8.50 and 8.51. For quadratic infinite problems [42] there is the Wolf algorithm, which is as follows: firstly, one has t o solve the problem in which some of t h e inequality constraints are

8.10. METHODS AND ALGORITHMS

FOR SOLVING IP PROBLEMS

185

omitted, while the other are replaced by equalities; secondly, the resulting solution is "improved" by a finite-step procedure over a finite-dimensional space. Namely, imple­ mentation of the algorithm calls for solution of the corresponding infinite-dimensional problem, which, in a sense, governs the choice of a function space. If, however, one is successful in solving the infinite-dimensional problem, then implementation of the second part of this algorithm is automatic. The infinite-dimensional part of the algo­ rithm is implemented by solving a differentiable matrix equation of Riccati's form. Referring to [11], we have an extremal problem with infinitely many criteria and constraints for the smooth and nonsmooth cases. Lagrange multiplier rule is stated for deriving necessary extremum conditions. Referring to [18-22], we have conditions for application of the marquee method developed in the finite case to extremal problems in infinite-dimensional spaces. The separability theorem for the system of convex cones with the common vertex at zero is generalized to the infinite case. T h e o r e m 8.53. Let E be a locally convex topological space and let K\,..., Ki be a system of I convex cones in E with vertices at zero such that 1) ViK, ^ 0, i = 1 , . . . , / ; 2) if L\, Li C E are subspaces of E each of which is represented by an intersection of some subspaces from the system aff A' 1 ,...,aff Ki, then L\ and Li are in the common position. This cone system then has the separability property if and only if there exists o,i G A'j*,... ,aj G K*, a, = 0 for any i, i = 1 , . . . , / such that ai + .. - + ai = 0. As in the case of finite-dimensional spaces, no assumption is made about sol­ id properties of the sets and their approximating cones, wherein lies a distinction between the known results and those obtained from the marquee theory.

Chapter 9 Optimization on Fuzzy Sets In large and complex systems, the optimization problem is difficult to state formally. Furthermore, in a number of cases the main system variables are fuzzy and given approximely, and their stochastic characteristics are sometimes impossible to define. When functioning, the model experiences uncontrollatle perturbations such that its structure mat substantially change, i.e., the model initially regarded as a linear one can be transformed into a nonlinear problem, etc. Then it seems wise to ensure stability of the model for the entire period of its functioning. Note that this is crucial for long-term planning models. In the general case, the model stability will be interpreted to mean the property that the optimal solution obtained from utilization of the optimization model is invariant under model modifications such as changes in parameters or structure. If the model stability conditions are not satisfied, e. g., when perturbations produce changes in the model parameters, and the previously obtained optimal solution is not preserved, then one has to define the limit solution set (a solution cone) for this level of perturbations. This section deals with a theoretic background and applied aspects of the solu­ tion of nonuniquely formulated optimization problems which formed the basis for development of the estimation algorithms for stability of optimization models under uncontrollable perturbations. Consideration is given to the main features of inad­ equately fomalized optimization models, the techniques designed to synthesize the solution algorithms for such a class of optimization problems, the methods for esti­ mating the stability of optimization models under uncontrollable perturbations, and the issues of development of applied program packages for solving inadequately for­ malized optimization problems.

9.1

Optimization problems in Large and Complex Systems

The modern framework of solution for optimization problems suggests that the stat­ ed problem is unconditionally formalized, i.e., there are a uniquely defined criterion, 187

188

CHAPTER 9. OPTIMIZATION

ON FUZZY SETS

an objective function or functional, or a set of criteria, a uniquely defined system of constraints. If the proposed problem is not formalized, i.e., when the system of constraints and criteria is not uniquely defined, then it is considered to be mathemat­ ically incorrect or its solution is inappropriate, or additional information is required to make this problem correct and solve it by employing traditional methods. Note that the absence of uniqueness is the general case of problem statement and a special case of incorrect problems. This class of problems is mentioned here because very efficient algorithms are provided for solving some types of incorrect problems, and if general conditions of uncertainty allow a problem to be reduced to this type of problems, then it can be solved in an exact or approximate way. In the general case, optimization problems can be classified as the deterministic, the stochastic and the problems to be solved under uncertainty. The deterministic problems employ completely determined information. The me­ thods for solving these problems are the most diversified ones. In the stochastic optimization problems, provision is made to express the conditions of model perfor­ mance and its variables in the form of probability relations, i. e., the distribution laws for random variables or random functions. The difficulties in solving this class of problems are as follows: firstly, the distribution laws derived for a restricted amount of statistical data are not necessarily reliable or stable, because a slight increase or decrease in the amount of initial a priori data may completely alter the design law of distribution; secondly, multidimensional distributions are very difficult to compute; thirdly, the distribution law is not necessarily derived. A special feature of the optimization problems to be solved under uncertainty (or under incomplete information) is that the stochastic characteristics of the sys­ tem (object) under study cannot be obtained. Although these problems are the least developed and there are no universal algorithms for their solution, certain recommen­ dations can be given here. Basically, such problems must be solved by employing a comprehensive approach, i.e., applying various methods or their combinations. The comprehensive approach includes the following phases [3]: — definition of the set of conditions to characterize the model and generation on their basis of the set of optimization problems to provide an adequate (to some extent) description of the object; — solution of the formulated optimization problems and identification of the un­ certainty zone for each of the obtained solutions; — adaptation of every solution to various combinations of initial data; — finding solutions in the uncertainty zone. Although this approach seems to be comprehensive, it does not allow one to syn­ thesize constructive solution algorithms for optimization problems under uncertainty. This is due to the following facts. If, e.g., the linear form is given as intervals Cf'n < d < Cf^, Vi, then in order to form the set of problems which reflect the set of conditions characterizing the object (alternatives), one has to take into account 2" linear forms, where n is the dimension of the vector of unknowns, i.e., one has to

9.1. OPTIMIZATION

PROBLEMS

IN LARGE AND COMPLEX SYSTEMS

189

solve 2 n linear programming problems. It is easy to see that even for comparatively small n the number of problems to be solved is sufficiently large. So it is essential to form the minimal set of problems (alternatives) which can adequately reflect the actual performance conditions of the object. The existing methods of solving optimization problems under uncertainty, as a rule, take into account only sufficiently small changes in the objective function co­ efficients and model constraint system. Actually, such methods do not allow for variations in the model structure. In the general case, the solution of the optimization problem under uncertainty must be taken to be some set of vectors. The principles of selecting "coordinated" decisions have not been investigated and are largely dependendent on the intuitive prerequisites of a decision maker. Investigations show that under actual performance conditions of various control systems one has no opportunity to rely on initial chance-constrained information, and the optimization problem has to be formulated with due regard for this characteristic property. In these conditions, one has to ascertain whether the model is adequate and whether it can be successfully utilized for specific (nonuniquely defined) performance condi­ tions of the system (object). Note that an attempt to solve a nonuniquely formulated problem is necessarily associated with an attempt to formalize this problem. Then care should be taken to prevent the substance of the problem from being corrupt­ ed by formalization. One may often observe situations, where formalization of the problem amounts to "fitting" an actual model to a programming model such that its solution becomes accessible to a specific executive. Such a "universal" model is often represented by a linear programming problem. In view of the diversity of nonuniquely formulated problems and because of the necessity to solve such problems, some methods were proposed for formal description of qualitative relations. These methods are based on fuzzy sets as in L. Zade [22]. To solve approximate decision problems in the nonuniquely defined setting, one may utilize fuzzy F-sets which can be viewed as models for problems of some classes whose parameters have no clear-cut boundaries. According to [22], the fuzzy F-set is defined as follows. Let X be a universal (ordinary) set of elements. Suppose the F-set A C A' is defined as a collection of pairs (HA{X),X;X e X), where \iA is the belonging function of x -> [0,1], while HA{X) is interpreted as a degree to which the element X belongs to the F-set A. Among operations on F-sets (see [22, 16]) we select only those — inclusions, intersection and union which are necessary for further discussion: a) A C B & pA(x)

< HB{X), (Va); x G A';

6) C = A U B •£> pc[x) = min {nA{x)} ; x £ X; X

B) C = A n f i H / i c ( i ) = max {/J.A(X), ^B( )}

(9.1)

;x e X.

Of special interest are optimization problems whose solutions are based on fuzzy sets. Let m a x / ( i ) ; x 6 X be a uniquely defined traditional optimization problems,

190

CHAPTER 9. OPTIMIZATION

ON FUZZY SETS

and X" a solution vector. In the informal setting, the optimization problem can be represented as follows. There are a set of objectives (which contains only one element for the uniquely defined problem) and a set of choices whose intersection allows one to define an optimal solution of the original problem (as is evident from the foregoing, the intersection of these sets may generally contain more than element, in which case the problem does not have a unique solution, or it may be empty, in which case the problem has no solution). The problem of achievement of the objective described by the fuzzy set with the belonging function \ic '■ B! —^ [0,1],

f Mc =

lj{x)
(9.2)

\ 0,/( S ) > / ( ! ' )

can be described by incorporating the method of execution of nonuniquely defined instructions into the formulation of the problem. We obtain the optimization problem fi(x) = min {/ip(x), HN(X)}

—> Extr(max),x g X,

(9.3)

where pip(x) is the belonging function which characterizes the pre-image of the F-set B C X for / : p.p{x) : x —*• [0,1]; JJ,N(X) is the belonging function which characterizes the F-set of N feasible choices for HN(X) : x —> [0, 1], . .

f 0,/(x) < /(**); >/(x* v

W(z) = |

^W

:*), , = ]f 01,31,,i1 6g /AT;VN;;

r Thee solution so lution of this problem is the fuzzy set wwhich hich is the intersection of the fuzzy sets of objectives and choices [16]. The optimization problem [9.3] does not allow one to obtain a unique solution, although such a solution may actually exist. This is a serious handicap to the use of F-sets for solving optimization problems where no adequate description is provided. Despite its apparent universality, the proposed approach to optimization problems as a way of realizing nonuniquely defined instructions for achievement of a nonunique­ ly defined objective does not allow one to synthesize constructive applied algorithms for solving actual nonuniquely formulated optimization problems. This is mostly due to the fact that the problem of constructing a feasible choice set is essentially the prob­ lem of determining feasible solutions for the original optimization problem, which is highly conjectural. So, without rejecting Zade's approach in the general case, one has to accept its nonconstructivity, which in turn necessitates classification of nonunique­ ly formulated optimization problems and development of applied algorithms for their solution. Investigations show that in the actual solutions of optimization problems for large and complex systems the system parameters are often represented by nonuniquely defined variables. The nonuniquely defined variable can be interpreted as follows. It is well known that the fuzzy set A C V is characterized by the belonging function

9.1.

OPTIMIZATION

PROBLEMS IN LARGE AND COMPLEX SYSTEMS

191

H'A{X) which assigns some number x 6 A (the belonging function) to each element HA ~~^ [0,1]. In a first approximation, the element of the fuzzy set is regarded as a nonuniquely defined variable. The definition of the nonuniquely defined variable which is based on the concept of assignment equations [22, 16] is more rigorous, and hence more extensively applicable. To describe the variable as an element of algorithmic language, one has to indicate the name of the variable (identifier) and the range of values assumed to be this variable. Formally, these requirements can be satisfied if the variable is described as a group (triple) of parameters (A', U, R(X; u)) each of which can be interpreted as follows: X is the name of the variable (identifier); U is a universal set to which the variable may belong. The range of values A' — R(X;u) or, for simplicity, R(X) can be viewed as a constraint which is imposed on u £ U and specified by the variable X; if x — u, u £ -R(A'), this is equivalent to the existence of the assignment equation for the variable x = u : R(X). In other words, the assignment equation reflects the fact that the variable cannot assume other values than those which belong to the range of its values. If the variable is nonuniquely defined, this means that the assignment equation for the nonuniquely defined variable x = u : R{X) is nonuniquely defined and reflects the fact that the element x is assigned the value u under constraint R(X). The degree to which this equality (assignment of the value x to the u) is satisfied is called the consistency of the value u with R(X). This reasoning can be written as c(u)

= HR{X){U);

U£

U,

where HRIX){U) >S the degree to which the u belongs to the constraint R(X). Note that for the uniquely defined variables (J.R(X)(U) — 1 if the assignment equation is satisfied and HR(X){U) = 0 otherwise. The belonging function and the belonging degree are actually equivalent concepts. Application of fuzzy sets will be illustrated for formalization of the nonuniquely formulated optimization problem. Technical propositions often call for minimization of the functions referred to as posinominal:

max/(i) = 2J

n x.

,;

x £ X

(9.4)

Here ambiguity of mathematical description manifests itself in: — the indeterminate functional structure (because the parameter — the exponent k — can assume various values); — the nonuniqueness of the parameter (the components of vector c = {c,}; j = l,m can assume different values belonging to fuzzy sets); — that the constraint set X determining the system performance conditions may belong to fuzzy sets.

192

CHAPTER 9. OPTIMIZATION

ON FUZZY SETS

When problem [5] is inadequately described at the level of nonuniquely defined variables, it can be represented as max (U(c)), xu^)

;

x 6 U(X),

where parameters c, k "approximately" belong to a fuzzy set and can be represented as (V?)(ci = c,4 approximately c, = 1/cJ + fi]/c} ± Ac] + /i 2 /c 2 ± Ac,2 + . . . = (9.5) k = /cA

approximately

=U/ii/fe ± AJ.

k = 1/fc, + ^i/fci ± A^ + id2/k2 ± Af + . . . =

(9 6)

'

i 3

where fi t, fit are the functions of belonging of the elements c;, k to the sets U(C), U(/c), respectively. The sign A_ means "by definition is" The notation (9.5)-(9.6) means that the parameters c and k can assume any values from a given set, in which case for every assumed value there is a particular value of the belonging function. Note that, unlike probabilities, the belonging functions form a complete set of events, i.e., Yl^k / 1. k

Problem (9.4) is rather difficult to solve even in the uniquely defined setting. The difficulties encountered in the solution of problem (9.4) with due regard for nonunique definition of model variables are much greater than those in the unique formulation of the problem, because the construction of the feasible choice set is the feasible solution set for the original problem (9.4). As noted before, such solutions are sometimes difficult to obtain. [6] proves the validity of the extension principle which makes it possible to extend the basic theorems and concepts of uniquely defined sets to fuzzy sets. The possibility to solve problems (9.4)-(9.6) allows one to determine the boundaries for applicability of the theorems of necessary extremum conditions in convex optimization problems under nonuniquely defined conditions for model performance which, in turn, allows one to make the decisions more adequate. One cannot claim that the solution methods of traditional (uniquely formulated) optimization problems can be extended to problems with nonuniquely defined vari­ ables. The resolution of this issue is of fundamental importance. Mathematics is now equipped with numerous algorithms and methods for solving optimization problems. So there is no need to develop new methods for solving special classes of problems without examining the potential of the familiar methods.

9.2

Optimization of Problems with Nonuniquely Defined Parameters

General recommendations on the solution of nonuniquely formulated optimization problems are given in L. Zade [22] and include implementation of procedures for con-

9.2. OPTIMIZATION

OF PROBLEMS

WITH NDP

193

structing fuzzy sets of objectives and choices and the domain (set) of their inter­ section. Mathematically, these recommendations may often involve insurmountable difficulties, and provide no means for synthesizing constructive algorithms intended to solve actual applied optimization problems in the nonunique setting. One of the special, but important issues is the estimation of optimal solution invariance in nonuniquely formulated programming problems where the model param­ eters are nonuniquely specified. The general formulation of the algorithm synthesis problem for determining invariant solutions as a prerequisite for synthesis of solution algorithms of the convex programming problem is very complicated when mathemat­ ical description is inadequate. So it may be wise to distinguish special classes of problems, where such a formulation is not only possible and permits machine real­ ization, but also provides the openings for solving the general problem. The most suitable for this purpose are linear programming problems whose general formulation for nonuniquely defined model parameters is given below. Application of traditional methods for solving linear programming problems, where the coefficients of a linear form are nonuniquely specified, requires solution of 2™ lin­ ear programming problems (n is the dimension of the vector of variables). For the cases of moderate dimension, the number of problems is rather large, which is not only wasteful of machine time, but also involves perceptive disturbances in accuracy (because of the iterative nature of procedures). Computational procedures become more complicated where variations in constraint parameters have to be allowed for. This emphasizes the advisability of applying special algorithms which are not required to solve the optimization problems with nonuniquely defined parameters by reducing it to a particular set of correct prob­ lems. The stability (or invariance) algorithm of the optimal solution is to ascertain whether the functional gradient vector belongs to the cone of allowable variations for all the functionals from a specified set of the optimization problems. When synthesizing the estimation algorithm for the solution stability under vari­ ations, the main tasks in determining the structure of the algorithm are to find an advantageous (from the point of view of machine realization) way of specifying the allowable variations cone and the functional cone, and the ways of determining the set of solvable problems and selecting the design optimization problem. Additionally, it is very important to examine the efficiency of the developed algorithm from the point of view of its machine implementation and from the point of view of isolation of those classes of problems which can be effectively solved by the developed algorithms. Note that one of the classes of such problems includes the estimation problems of the optimal solution stability under perturbations.

194

9.3

CHAPTER 9. OPTIMIZATION

ON FUZZY SETS

Basic Notions

We will consider the design problem as a linear programming problem such that its linear coefficients are nonuniquely defined variables max ([/(c), x) ;

X = {x\Ax
i £ l ;

x > 0} ,

where U(c) is a fuzzy set of coefficients each of which belongs to a fuzzy subset ''approximately Ci" Ci^

approximately

Z\ = n\\c\ + fJ."\c'( + . . . + p.\\c\\

c2A

approximately

c2 = p.'2\d2 + /4'lc2 + ■ ■ ■ + A^kli

c„4

approximately

cn = fi'n\c'n + ^'|c'„' + . . . + n'n\c'n.

The notation (9.7) implies that the coefficient ci can assume values c\,c'(,... ,c\, and the quantity JJ,\ shows for the coefficient c\ the degree of its belonging to the universal set of coefficients {c[, c",. . ., c\}, that is, C\ = c\ with the belonging function Hi. So the coefficient can assume any value from the universal set {c[,.. ., c\} with a suitable belonging function. In what follows the notation (9.7) will be used in a more compact form: c,A

approximately

ct =U f4 |c; , Vi,

j = 1,2,. . .

It may be wise to solve the linear programming problem with nonuniquely defined coefficients of a linear form in two stages: 1) solve a simpler problem, i.e., the linear programming problem with the coeffi­ cients given at intervals, and then 2) solve the general problem. Suppose that in the problem max(c, x);

x £ X;

X = {x\Ax
x>0}

the coefficients of a linear form are given at intervals c™ln < c, < c f ^ V t . Define the conditions under which the solution of this problem is unique. If the solution is not unique for a given interval of variations in the coefficients of a linear form, then define the limit solution set which allows one to find a. coordinated solution. The limit solution set is the set which can be obtained when all LP problems are generated on the basis of the condition cfln < c; < cf'^jVi. The coordinated solution is that solution £' for which f = m a x | s - i * w | -> min,;r* w £ RX)RX

= {.T*1''} ,i = 1,2,. . . ,

9.3. BASIC

195

NOTIONS

x* w is the solution of the LP-problem max(c ( 'l,i); x G X. Let us form the matrices C\ and C-i where each row is constructed on the model: one element is maximal, while the other elements are minimal, and vice versa. We have diagC 1 {c; nin ), diagC2 = ax

{c }>

/^min

/"'max

o2

/~>max

/Tnax

o2

Ci fmax

(9.8)

/^raax

fmax

/~<min /^min

^2

/~*min

r>max

/"•mill

(9.9)

C2 /~<min

/^min

/^max

The number of rows in the matrices (9.8), (9.9) is In. Note that the number of vectors whose components assume only two values cf ax ,c™ m , Vi is 2" Here (9.8), (9.9) are the limiting matrices. T h e o r e m 9.1. Let the vector c = {c,}; i = 1,», be given by the upper and the lower values of its components cfm < c, < c| nax ,Vi. Here a) the matrices C\ and C2 (9.8), (9.9) are such that

diagCi = {Cr}

diagC2 = { c r x } ;

,

l,n;

b) the circular solid cones A'+ and A' are such that K+ is circumscribed about Ci, A"~ is inscribed in C2 and the center of cones A'+ and A"~ is defined as follows

£

C;=

!.<> (9.10)

i = 1,2n

2n

Then any vector S $ C = C, U C 2 , for whose components Cfn has the property of indlusion ck 6 A*+ x A'~

< Cf1 <

Cf^.Mi,

Proof. Let us enumerate the vectors c(j> G d U C2 = C; c ' = c « / | | c W | | , | | c ( i ) | | = (c' ',c' J ') 1 / ' 2 ; j = l,2n and calculate the direction cosines a' J ' between the vectors c' J ' S Ci U C2 = C; j = 1, 2n and the normalized vector c: J

o^=(c,c(;) o a

2

o(j)

c,c

oU)

c o(j)

c

_

e Ci; ,-,

€ C3;

l,2n.

196

CHAPTER 9. OPTIMIZATION

ON FUZZY SETS

In the arrays < a\ > and < cq \, we define respectively the maximal and the min­ imal element, a^ = m a x j o ' | , a'"' = m i n j a j } a n c ' t n e vectors c^K &v' forming the angles area' 1 ' and area'"' with respect to C. Take the generatrices to be the circular cones A'+ and K~, respectively. We will consider the scalar products (c,c), (c,c), where the vectors c, c are such that among their components there are at least two or more components c™ax (or c™111). If we compare ( c , c J with f c, cj, where c'A' is any row vector dk> f C, then we may see that o{k)min

c T •. .T

o( )rnm Cn

0

0 (A:)min

■ cx + c2 „ -a C „ ^ Cj

0(t)max

0

■ c2+...

+ cf

o

o(^) min

o

■ cj + c / + 1

„ , -min ° , i -max ° ,;mii ° Cj -t-C 2 ■ Cj -f- . . . -f- Cy • Cy -|-Cy_|_j • C j +

c/+1 + 1

. . ° -min ■+■ . . . -f- C„ -C„

because the number of maximal components is larger in the product (c, c) (note that all £, > 0, c] are normalized). Hence the angle between the vectors c and c is always smaller than a' z ', i.e., the condition c £ A'+ is necessarily satisfied. For the vectors c, whose components include two (or more) c™m, one may show that there is always {c,c) < (c^,c) which means that a'"' > (cA"',c), i.e., c f K~ Hence the assertion c G K+\K~ is true. The theorem we have now proved makes it possible to state the existence condi­ tions for the unique solution in the LP problem with the coefficients of a linear form specified at intervals. It has been known that the solution of the LP problem is regu­ lar, i.e., it is placed at the node of the polyhedral set X\x\Y^o,ijXt < bjX > Of; j = l,m, which forms a constraint system. Let x" be a solution of problem max(c'*',i); x 6 X = \Y,aijXi < bj, x > 0J; j = l,m where c'*1' is the fc-th row of matrices (9.8), (9.9) which is selected in an arbitrary way. We may distinguish a subset of constraints M C X, M = lx\ ^ a . j i ; < bj,x > 0J; j = l,u which form the roof at the pont x'\

(v,-) ( E «<»*• = &*) i

j — i,f.

By the theorem of necessary and sufficient extremum conditions [22], we have the proposition if c[k] 6 D (M(k)), then x* = max (c[fc], a;); Vc^; h)

xeX,

it = 1,2,...,

where D(M ) is the dual cone which is constructed at the point x* and formed by the normals of hyperplanes J2 aijx] = bf, j — 1, v, forming the roof at x~ So, in order to establish the fact that the solution is unique in the LP problem (9.7) with the coefficients of a linear form specified at intervals, it is necessary (and

9.3. BASIC

197

NOTIONS

sufficient) to run 2n tests for inclusions of vectors c(k] 6 C = C\ U C2 in the cone D(MW), or, what amounts to the same thing, for inclusion of the cone A'+ in the cone D(M). To define the limit solution set (cone), it is advisable to utilize the following algo­ rithm. Assuming the limit matrices (9.8), (9.9) are constructed, the computational algorithm scheme can be represented as follows: Al:l. Formulate the original problem. max (c' 1 ', xj ; X = {x\Ax
x 6 X; .T>0},

1

where C' = {C, }; i = ~L/n is the first row of matrix C\. 2. Solve the original problem in 1, and fix the solution vector A'*(1). 3. In the constraint set X = lx\ J^a^x, < bly x > 0}, find those constraints which form the roof at the point A'*(1). 4. Construct a polyhedral cone D(M'-1') whose edges are the vectors atJ of the roof hyperplane normals j = l,v; i = l,n, 5. For all row vectors of matrices (9.8), (9.9) starting with the second, the se­ quential test is run for inclusion of the vector c'", k = 2 , 3 , . . . in the cone D(M^). The vector designated with number / , whose direction does not belong to D{M^1'), is taken to be the estimated one. State the problem max f c ( / ) , x) ;

x € X = {x\Ax < 6, x > 0} .

6. Problem in 5 is taken to be the original, and transition is made to para 2. Implementation of the algorithm will yield a solution set x*'1', i*' 2 ',...,, which can be ordered or an acceptable solution can be selected as a vector x determined as r r = max \x — x"^'\ —¥ min;

r*'1' G A',

or a vector x= {x,y. 0

s !. ==i1

•W/5;

i = 1 ,n.

, i + ir»n ct»t .^karl about - k ^l-,o solution The solid cone Rx circumscribed the set a;*'1', x*' 2 ',. . ., has the condition that the solution of any LP problem which can be based on interval speci­ fication of model coefficients belongs to the cone Rx. The validity of this inclusion follows from the fact that any vector c- > ^ C which can be based on the condition cfm < c, < c™ax, Vj is included in the cone A' + , i.e., c<*> G A'+. It should be noted that, in the general case, replacement of the set 2 n vectors with the matrix C = C\ U C2 containing 2n vectors may give rise to errors in the definition of an acceptable solution, but such errors may not affect the result in the general case.

198

CHAPTER 9. OPTIMIZATION

ON FUZZY SETS

Since the procedure for testing vector inclusions in the polyhedral cone D(M) (the cone of allowable variations) is rather complicated (from the point of view of machine implementation), it is advisable to introduce two types of tests: approximate and accurate. The approximate testing covers the inclusion of vector C' ' in the allowable variations cone which is a circular solid cone Qx inscribed in the allowable variations cone. We well describe the operator scheme for testing the belonging of vector directions c'fc' to the polyhedral convex cone Qx(c^ € Qxj- This scheme is implemented in the "accurate" version of algorithm and includes the following procedures: A 1': {AiAiAzAtAsAeA-rPs} , where A\ — definition of the center of gravity for the vectors of normals a tJ of hyperplanes J2aijxi — bj] j = l,o, which form the bundle for x", i V

Ci= ^ a , j / n ;

i = l,n;

3=1

A2 — formation of a vector collection {ot,3}; i = l,n; j = l,v, whose norms are respectively fj =c /ctf, a3 —the direction cone between vectors c and cM>] A3 — calculation of the direction cosine j3k between vector c' ', c and generation of vector c'" with norm rc =c ff}k; Ai — definition of the "zone", where the vector c'" lies; A$ — formation of an equation for a straight line passing through the points c and o mk

°c,

X

i~

O C

l

_

_ c < * > -■■■-

x

n~

j

O c

n ik)'

A6 — definition of the intersection point a;'" for the straight line m\ and the straight line q(k> closing the zone; A7 — calculation of a distance from c° to c- ' ans x'fc' — r^ck\ r^ respectively; Ps — testing: r<*> < r<*>. Fullfilment of condition P 8 shows that the direction of vector c'fc) belongs to the cone Q. The zone, where the vector c'*' lies, is determined by the algorithm whose operator scheme is represented as the relation AI" : {A,A2P3}

,

where At — definition of the collection of direction cosines j3j, j = T~u between vectors mk and bj (the direction vector Cj coincides with the straight line passing through the points c and a,-); A2 —definition in the collection {ft}; j = l,t> of the maximal element ft C {ft} and the corresponding vector 62;

9.3.

BASIC

199

NOTIONS

P 3 — t e s t i n g : ft+1 > & _ , ? Suppose t h e vectors {a,.,} are ordered, i.e., the sequence of vectors 0,1,0,2,. ■ ■ ,a,v; i = l , n is defined to be such t h a t the straight lines passing through the points a,k -T- a,fc+i; 2 = l . n ; fc = l , v form a closed convex planar polyhedron. T h e "zone" is a triangle whose sides are straight lines passing through t h e points c and gt, (c;a,t), (ajfcjajt+i), respectively. T h e straight line passing through t h e points (ajjort+i) is referred to as closed. If condition P3 is satisfied, the "zone" is formed by t h e straight lines passing through t h e points Cc;c*z), ( C , Q 2 + 1 ) , (az;az+i); otherwise {c;a2), ( c ; a , . i ) , ( g ° ; a , _ i ) . Note t h a t t h e solution set £*(*>, A; = 1 , 2 , . . . is t h e limit one in t h a t t h e solution vector of any LP problem, whose linear coefficients satisfy t h e condition c™m < c, < c™ ax ,V,, has t h e property t h a t its direction belongs to t h e solution cone a;*'", k = 1 , 2 , . . . This fact has escaped t h e attention of investigators. W h e n compared to t h e algorithm of t h e LP problem which has t h e coefficients of a linear form specified at intervals, t h e nonunique definition of coefficients is allowed for in t h e following way. T h e belonging function can b e assigned to each row of ma­ trix C. Since t h e matrix row is taken as a linear vector and vector components are noninteracting variables, t h e belonging function of t h e row (vector) must be taken, according to (9.6), as t h e maximal value of all belonging functions of separate com­ ponents. Consequently, t h e matrices C i , C2 can be complemented by the columns of the belonging functions. So t h e belonging value corresponding to t h e row is assigned to t h e solution of each LP problem whose linear form represents t h e row of matrix C. T h e proposed algorithm can be used most efficiently where there is no need to ran­ domize solutions (indicate t h e belonging functions of each of t h e solutions obtained) or where t h e solution is invariant with respect to nonuniquely defined coefficients. Solutions can be randomized in t h e following way. Formulate t h e LP problem whose linear coefficients are selected at t h e a-level 1 t h a t is equal or close to 1. Suppose t h e problem is max(cw,i);

x 6 X;

X = {x\Ax
x > 0}

(a)

and vector x* is its solution. As in (9.8), (9.9), we formulate t h e limit set of linear vectors by taking t h e lower b o u n d a r y of t h e a-level is a specific value aA < a 2 . After constructing t h e allowable variations cone D(M) on t h e solution x*a and testing t h e vectors directions for belonging to t h e cone D{M), one m a y establish t h e optimal 'The a-level of a fuzzy set A is an ordinary set Aa of all the elements of a universal set U such that the degree to which they belong to the fuzzy set A is greater than or equal to a : Aa = |u|/j/i(") > a \. The fuzzy set A can be decomposed in terms of the sets of levels: A = U1 a-A a=a

CHAPTER 9. OPTIMIZATION

200

ON FUZZY SETS

solution invariance with respect to nonuniquely defined coefficients or determine the value of the a-level ji = aD for which the invariance conditions are preserved. Formulating a new LP problem with the coefficients selected at a new a-level D a a{P) < a( ) yields a new solution x*' ' which can be associated with the belonging p function value fip = a' '. The solution with the maximal belonging function value, i. e., i*' 1 ' can be taken as an acceptable solution of the LP problem with nonuniqiely defined linear coefficients.

9.4

Solution Optimization Algorithms for Linear Programming Problems with Variations in Constraint Coefficients

The principle of duality in mathematical programming problems implies that the correct (uniquely defined) LP problem maxfc, x)\

(P):

x 6 X;

X = {x\Ax
x>0}

can be placed in correspondence with the dual (9.9). We will suppose that in the primal problem the constraint system is given ap­ proximately, which can be generally represented as interval definition of the vector of right-hand sides b e U(S);

bfn
6;max;

Vj;

j = I~^.

As noted before, with the linear coefficients defined nonuniquely at intervals, cf™ < c, < c™ax, Vi, i = l,n the optimal solution invariance condition can be represented as cU)eQx;

V/;

f = T^H,

where Qx is the cone of allowable variations and c"' is a row vector from the limit matrix C — C\ U C 2 . This provides a way of constructing the estimation algorithm for the optimal solution invariance under variations in constraints: 1. Set up the correct (uniquely defined) LP problem, where the components of column vector b are arbitrarily selected from the interval [6fax;6™m]. We have the problem max(c, ;r); x € A'; A = [x\Ax < b{s\

x>0}.

2. Set up and solve the dual problem min (6 ( i ) ,y) ;

I E A';

ye V;

9.4. SOLUTION

OPTIMIZATION

201

ALGORITHMS

Y = {y\Ay>C,

y>0};

and fix the solution vector. 3. Based on (9.8), (9.9), set up the limit matrices Bu B2\ diagBj = {b™x}, diag£ 2 = {b™}; i = l,n. 4. With the solution y* for the problem in para 2, construct the allowable variations cone Qx. 5. Test the vectors 6<J' £ B = B, U fi2 for bel onging to the allowable variations cone Qz. 6. If the condition in para 5 holds for all the rows (vectors) forming the limit matrices By and B2, this is a necessary and sufficient condition for the optimal solution to remain stable in the given range of constraint variations. 7. If the condition in para 5 is not satisfied, then the first vector 6"', whose direction does not belong to Qx, is used for setting up a new problem min(6(/),y);

y £ Y,

whose solution y*'1' is employed to construct a new cone of allowable variations and to test sequentially the directions of the other vectors for belonging to the cone of allowable variations. Here, as in Algorithm (A 1), one can obtain a limit set of solutions y*' ', k = 1,2 ... Note that G. Dantzig was the first to consider the definition of the range of linear coefficient variations, for which the optimal solution is not violated, as applied to the continuous LP problem [4]. Dantzig shows that in solving the continuous LP problem by the simplex method for determining the maximal and the minimal values of linear coefficients, for which the optimal solution is preserved, it is possible to use the analytic relations [4] max c.'i = c° + min I —

\anl

min Cij = c°, + max

,

— I,

atJ > 0;

atJ < 0,

where i is the index of the z-th basis process, and j is the nonbasic index; Cj — Cj

/

j

&ijCji.

This method has the following limitations: 1. The proposed estimations can be used only if the problem is solved by the simplex method, i.e., there are simplex tables at each step. If the continuous LP problem is solved by such methods as the penalty function method or the gradient method, the proposed analytic relations are basically inapplicable. 2. As noted above, application of Dantzig relations requires computer-storage of all the arrays obtained at each step. The result of such nonrational utilization of

202

CHAPTER

9.

OPTIMIZATION

ON FUZZY

SETS

computer storage is t h a t t h e values [c™ax; c™m] can be determined by Dantzig relations only for the problems of a fairly low dimension. 3. Basically, Dantzig relations cannot be used for estimating t h e optimal solution invariance in t h e integer and nonlinear programming problems. 4. As noted in the formulation of the problem, some cases require not only esti­ mation of the optimal solution stability for a specified range of variations, but also determination of an acceptable solution for t h e entire range of variations. In such cases, Dantzig relations fail to hold. So development of t h e estimation algorithm and m e t h o d for optimal solution in­ variance, as based on the separability properties of convex cones, is not only necessary, but also permits a significant increase in t h e efficiency of computational procedures.

9.5

Optimization of Integer LP Problems

Integer and diserete linear programming is one of t h e most actively developing spheres in m a t h e m a t i c a l programming which is due to the demands of numerous engineer­ ing applications. W i t h o u t touching upon all possible fields of application of integer and discrete programming (see [11]), one has to emphasize high efficiency of integer optimization models in solving the problems of computer system adaptation. At the same time it is to be admitted t h a t the integer and discrete linear pro­ gramming problems represent one of the underinvestigated classes of mathematical programming problems, and the existing algorithms for their solution cannot be con­ sidered as efficient, and in some cases they prove to be inadequate. T h e formal meth­ ods for solving LP problems t h a t have enjoyed t h e widest application are Gimiry's methods and branch-and-bound m e t h o d [10]. W i t h o u t touching upon t h e efficiency of these m e t h o d s , we note t h a t t h e necessity, e.g., in Gomory's method, to effect the n-multiple (n being the dimension of the vector of variables) solution of the LPproblem presents obstacles such t h a t even an approximate solution of /LP-problems cannot be obtained. After careful analysis of the formal solution methods for ILP problems F. Gill and W. Murrey concluded t h a t ". . . no significant progress is currently observed in the integer linear p r o g r a m m i n g . . . one can hope to be successful only where heuristic methods are developed" [5, pp. 269, 273]. T h e approximate methods t h a t have enjoyed the widest application for solving ILP problems are the methods of barrier functions and r a n d o m search [5, p. 171]. In some cases, however, these methods are not very effective in applications. Note that the existing solution algorithms (formal and heuristic) of ILP problems do not allow for t h e fact t h a t the control problems reduced to the integer optimization problems can be solved on multiple machine systems, and in t h e process, the solution may require multiple corrections for adapting the system. Since none of the existing methods of solving ILP problems can be used to solve nonuniquely formulated ILP problems, one has to consider t h e possibility of synthesiz­ ing a unified algorithm which can be utilized for solving t h e uniquely and nonuniquely

9.5. OPTIMIZATION

OF INTEGER LP

PROBLEMS

203

formulated problems. As before, in the solution of nonuniquely formulated continuous LP problems, we shall observe the following procedure. First we consider the solution algorithm of the uniquely formulated ILP problem, then turn to the problem with interval-defined parameters and finally go to the original problem, that is, the ILP problem, where the nonuniquely defined variables are regarded in terms of a linear form and constraints. The proposed solution algorithm of the uniquely formulated ILP problem is based on the heuristic self-organization principle, It is as effective as the simplex method and admits a very simple machine implementation. The heuristic self-organization principle [7] allows for the following procedures: — selection of elementary algorithms for generation of inputs; — selection of heuristic sampling criterions; — selection of a law for generation of combinations. A special feature of the heuristic self-organization principle, which is responsible for its high efficiency, is that the gradient methods, the method of random search, and other methods for solving optimization problems can be used at the elementary algorithm selection stage. Let us formulate the main algorithm heuristics. Suppose max(c, x), x € X = {x\Ax < b,x > 0} ,

x = integer

(9-11)

is the original integer LP problem. Based on (9.11), we formulate a pair of equivalent LP problems without integer requirements: the primal problem m a x ( i . i ) ; x e X = {x\Ax < 6, x > 0} ,

(9.12)

the inverse problem min(c, x); x 6 X = {x\Ax < 6, x > 0}

(9.13) (1

Suppose the solutions of problems (9.12), (9.13) are the vectors x* ' and x*(2', respectively. Bisect the line segment passing through the points x*(1), x*(2). In the direction of x*'1' we obtain a vector set X = {£'*'} ,fc= 1,2,..., ,(1)

if) = - 3

«(*-l)

~X>

+ xf-x); Vz; i = ! > ; x<°> = x*<2)

in the direction of x*(2) we obtain a vector set X = {x ( -' ) |, j = 1,2,... f»'l v

.(j-ll i ~

x

x > = —■

*(2)

x

i

-(j-l)

x-

w

'

1

- (0)

»(1)

; Vz;z = l , n i ' ' = x * '.

2 Bisection is effected until |x*(1) - xf'| < Ax or |x*(2) - x\k)\ < Ax„ where Ax is a descreteness interval, k = 1,2,. . .

CHAPTER 9. OPTIMIZATION

204

ON FUZZY SETS

From the collections X = {i{k)}, k = 1,2,...; X = { i b ) } ; j = 1,2,... we form the collections of integers X I , X2, X3, X4 in which Xl<*> = Entier(z<*)), X2{3) = Entier(iW), X3(i> = Okrugl(xW), X4<3> = Okrugl(i<J>), where Entier(x) is the procedure of forming an integer by dropping its mantissas; Okrugl(s) is the rounding of the number x to the nearest integer. From the collections XI, X2, X3, X4 we eliminate those integer vectors which do not belong to the original set of constraints, i.e., for which we do not separate the condition AX{LO) < b, where w = 1,2,3,4; xl 6 X I , x2 62 X2, x3 € X3, x4 € X4. Then the integer vectors we have obtained can be viewed as feasible solutions of the original ILP problem. We will suppose that implementation of stage II of the heuristic self-organization o(') o(«+i)

principle resulted in selection of vectors x ,x , . . . , that are used for generating combinations (stage III of the heuristic self-organization principle). Let us form twodimensional arrays: o((+l)

>(')

o (0

X =

x

fo(*+l

l,n,

=U.

where each row represents the vector x or x whose components are changed to an integer kp such that the following inclusion holds °(0 o(0

3(0

o(0

V

p> xp+l<

o(01 ■ .*»

eA;

X = {x\Ax < 6, x > 0} The array X

is of the form: ,

o(0

xx X

+Ai

o(0

°(0

>(0

>(0 o(0

e.Y

»(0

+/c2

SA­ o(0

o(0

(9.14)

,

Xn

GA' •>(0 The number of arrays X , t = 1,2,... corresponds to the number of vectors 3(0

xK~'eX selected by the criterion r<'> > ( 0 , 7 - 0,8)r* For each row of the arrays (9.14), calculate the values of a linear form of the At) . . , , r . o ( 0 , o(0 original ILP problem (11): L(x{ ),L(i 2 ) i M^n )' x i £ A , i is the number ot a (0, {t) o(() (r/° A i u ■. , row. The maximal element Lm(x m a x | L ( i t ) j and its associated row z m are determined in the array of linear forms we have obtained. The computational algorithm scheme for the maximization problem (9.11) is of the form [15]:

9.5. OPTIMIZATION

OF INTEGER

LP

205

PROBLEMS

A2:l. Form the inverse problem which, in our case (with respect to (9.11)), is the continuous LP problem min(c,a;);

x G A' = {x\Ax < b,x > 0}

2. Solve the primal and the inverse LP problem without integer requirements, and fix the solution vectors a;*'1',a;*'2'. 3. Perform the bisection procedure and form the arrays X I , A'2, A3, A4. If A1UA2UA3U A4 / 0 for |a;*(1) - a-*(2)| > 5, the original /LPproblem has an integer solution which can be obtained by the proposed algorithm; otherwise one has to alter the objective function vector c ± w. Go to para 1. 4. Calculate the vector norm x*(1), r* = (V(1>, a**1') ,

oft)

the vectors x

, select from the array .{'

o(*+l)

,x

,. . ., whose norms exceed (0, 7 — 0, 8)r". oft)

o('+l

,

o (0

o(t+l)

oft)

5. 1 he vectors x , a . . . are used to form the arrays X , X , ■ • • |diag X = {x\ ±k,} e A = {x\Ax 0}, where i is the number of a row, and k, is an integer. o ft)

6. In the arrays A

o (t+1

,X

0(()

„((+l)

, ■ ■ ■, determine the rows xm , xm

, . . . , , where the

values of a linear form of the ILP problem are the largest. The vector x m £ o(t + l )

,xm

lxm

1

, . . . , > , which ensures the largest value of a linear form among the vectors

of) o('+i)

x

m i xm

i ■ ■ ■ ii fakes an exact solution of the original ILP problem to be o(a)

xm — max(c, x);

x € X = {x\Ax < b} , where xt are integers. In the meaningful treatment, the algorithm can be integrally represented as fol­ lows. The solution of the integer LP problem is taken to be an integer vector whose Euclidean norm (length) is as close to that of the solution of a suitable continuous LP problem as possible. The integer vector, whose norm has the least departure from the optimal solution norm of the continuous LP problem, is sought by exhaustion of some finite set of the feasible solutions of the original ILP problem obtained from bisection of the line segment connecting the points x*''),x*' 2 ' that are the solution vectors of the LP problem generated in terms of the original problem. Investigations and machine experiments lend support to the high efficiency of the algorithm and advisability of its application for solving applied problems in a wide range. Based on the solution algorithm of the ILP problem, the invariance conditions for optimal solution can be formulated as follows. The basic algorithm operations, which make it possible to obtain solutions close to the optimal, are calculations of optimal solutions for the primal and the inverse problem of continuous linear programmingmaximization and minimization of a given linear form. The solution of the continuous linear programming problem is regular, i.e., it is located at the node of a polyhedral

206

CHAPTER

9.

OPTIMIZATION

ON FUZZY

SETS

set formed by a constraint system. For this case (regularity of solutions) t h e necessary conditions for an e x t r e m u m in any of the existing forms (Kuhn-Tucker, DubovitskyMilyutin, Boltiansky) are also sufficient. For t h e regular solution, it is possible to determine a dual cone (the cone of allowable variations) t h a t is a convex polyhedral cone whose components are gradients to hyperplanes the intersection of which forms the point of solution. Since t h e necessary e x t r e m u m conditions are satisfied, the inclusion of the vector of a linear form in t h e dual cone of suitable LP problems is valid. Introduce the definitions. D E F I N I T I O N 3. The sequence of vectors X= XI U X2 U X3 U X4 with X± 0 is called the support sequence. D E F I N I T I O N 4. T h e solution of the ILP problem is called invariant in the small if, irrespective of t h e value u in the ILP problem max(c ± w, x);

x € X = {x\Ax

< 6, x > 0}

the support sequence is kept invariant. D E F I N I T I O N 5. T h e solution of the ILP problem max(c ± ID, x);

x £ X = {x\Ax

< b,x > 0}

is called invariant if, irrespective of the value w, in t h e ILP problem there is a unique optimal solution x * ' s \ T h e following theorem is valid. T h e o r e m 9 . 2 . Let max(c, x);

x € A' = {x|Ax < b, x > 0}

be the original ILP problem whose solution is the vector x*' s '. Suppose the following conditions are satisfied: a) the linear form (c, x), is bounded above on the set X; b) there exist the solutions x*' 1 ' and x*' 2 ' of the continuous LP problems max(c, x);

x g X = {x\Ax

< b, x > 0} ;

min(c, x);

x e X = {x\Ax

< b,x > 0} ,

respectively; c) the dual cones D(M{1)) and D(M< 2 ) ) are defined for the solutions x* (1) and x*' 2 ' respectively. In order for the integer solution x*' s ' to exist in the integer linear programming (ILP) problem max(c±iy,x); x G X = {x\Ax < b, x > 0} it is necessary to satisfy the condition for inclusion of t h e vector c±wm QI =

D(Af"')n(-D(M<2')),

the cone

9.5- OPTIMIZATION i.e., c±w

OF INTEGER

IP

PROBLEMS

207

e Qx.

Proof. The solutions of the LP problems a) max(c,i),

x £ X = {x|i4x < b, x > 0}

6) min(c,x),

i £ A ' = {x|Ax < b,x > 0}

are regular. Based on the necessary and sufficient extremum conditions (9.6), this allows one to claim that the fulfillment of the inclusion condition c ± w G Z)(M (1) ), c±w e (--D(A-f(2))j is necessary and sufficient for the continuous LP problems max(c ± w, c),

x € X = {x\Ax < b, x > 0}

min(c±u;,x),

x G A' = {x|/lx < 6, x > 0}

to have the solutions which identically coincide with the solutions of LP problems in a) and b). In the solution vectors of LP problems a) and b) are respectively x*'1' and x*'2', then the fulfillment of the inclusion c ± w £ D(M^) and c±w e (-D(M)W)) or (2 c±w e D(M^ n (-£>(M >)) ensures that in the ILP problem max(c±ui,x);

x G A' = {x\Ax < b, x > 0}

the support sequence X obtained from bisection of the line passing through the points x*'1' and x*'2' is the same as in the ILP problem max(c, x);

x 6 X = {x|i4x < b, x > 0} .

This completes the proof of the theorem. Based on the theorem, one can claim that the fulfillment of the inclusion condition c ± w 6 Qx is necessary and sufficient to ensure that in the ILP problem max(c ± w, x);

x G X = {x\Ax < b, x > 0} ;

the optimal solution is invariant in the small and necessary for the optimal solution to be invariant. Investigations show that the estimation algorithm for invariance of optimal solu­ tions in the ILP problem is highly effective where the conclusions of Theorem 9.2 are used. Note that the proposed algorithm does not guarantee that the solutions will be obtained for all cases. On the assumption 1 for \x* — x* ' < Ax, V? the algorithm does not work. o

But the algorithm can be complemented and modified. If the support sequence X is o empty, X^- 0 (which do not preclude the solution of the ILP problem), then taking

208

CHAPTER 9. OPTIMIZATION

ON FUZZY SETS

the design vector to be some vector c' 1 ', whose direction does not belong to Qx, allows one to form a pair of LP problems without integer requirements: max(c (1) ,x);

x G X = {x\Ax < b, x > 0} ;

min(c (1) ,:r);

x € X = {x\Ax < b, x > 0} ,

whose solution makes it possible to determine vectors c 0 ' 1 ' and xoi-2\ for which x°l

-

x° \ > Ax,Vi, and thus obtain a new support sequence X which may contain integer vectors. In what follows the basic algorithm is implemented (para 2), the matrix (b) is constructed, and the maximal element is determined (with respect to the linear form of the original problem). Note that such a case is "diagnosed", i.e., revealed with the use of this algorithm. There are other "abnormal" cases. Firstly, the solution of the continuous LP problem max(c, x), x g X = j:r|/l;r < b,x > 0 | is the vector a:*'1' with integer components, and the bisection procedure is inadvisable here. The solution vector of the ILP problem max(c, x), x 6 X = <x\Ax < b,x > 0 | can be determined by rounding off to the nearest integer and dropping mantissas only for solving a suitable continuous LP problem. Secondly, the dual cone D(M' 2 ') represents only one vector, and hence the cone Qx must represent here this vector alone. Although the solution of the ILP problem max(c±u), c), x £ X = \x\Ax Q\ is also the vector x*'1', the solutions of the continuous LP problems m a x ( c ± i » , i ) ; i £ A ' = | X | A T 0[; min(c ± IO, x); x € X = | x | / l x < 6, x > 0 \ yield an empty support sequence. This form of "abnormality" is revealed by the algorithm, because the symptoms of the "abnormality" x* — x*1 < AxjV^x*' 1 ' being an integer vector) are obvious. The following estimation system is introduced to estimate the efficiency of the pro­ posed algorithms: 1) time required for solving the problems of invariance estimation in terms of the proposed algorithms; 2) accuracy of problem solution; 3) convergence of algorithms; 4) cycling probability. The estimation algorithms for invariance of optimal solutions in LP problems with variations in functional parameters and constraints are highly efficient and ap­ propriate for estimation of the invariance stability of optimal solutions with respect to perturbations. In the existing solution methods of ILP problems, provision is made for unique specification of model parameters (coefficients of a linear form and constraints). When the parameters are nonuniquely specified (e. g., at intervals), the existing methods al­ low one to solve the problem by significantly enlarging its dimension. The proposed algorithm makes it possible to estimate the optimal solution invariance without en­ larging the problem dimension, hence its efficiency is by an order of magnitude higher than that of the familiar algorithms.

Chapter 10 Optimization of Nonlinear Programming Problems with Nonuniquely Defined Variables As discussed earlier, the problems of optimal control in a large (or complex) system, as a rule, are inadequately formalized and must be viewed as an inadequately described model. In what follows, the term "optimal control" is interpreted to mean the optimal control itself and the finite-dimensional optimization problems. This is due to the fact that the problem of optimal control in a continuous system can be thought of as an infinite-dimensional programming problem in an infinite-dimensional space [20]. The Kuhn-Tucker theorem is central in the mathematical programming theory and can be extended to the problems in infinite-dimensional spaces. The design model of the inadequately described nonlinear optimization problem is taken to be the nonlinear programming problem with nonuniquely defined variables. The existing methods of solving the optimization problems with nonuniquely defined variables are very complicated and allow for construction of the fuzzy sets of objective and feasible choices and their intersection. These features do not preclude uncertainty in selecting a solution even though the solution can only be unique by the physical properties of the model. So it is essential to determine those conditions which, when satisfied, allow the nonlinear programming problem with nonuniquely defined variables to have a unique solution, whence follows the optimal solution invariance with respect to nonuniquely defined model parameters. Note that this approach is not necessarily advisable because estimations of appropriateness are decisive in all cases. Investigations show that solving the optimization problems with nonuniquely defined variables yields a class of conditionally ill-defined problems, i.e., the problems can be ill-defined according to Hadamard-Kolmogorov and well-defined according to Tikhonov.1 To solve the ill-defined (unstable) optimization problems, one may use the 'According to Hadamard-Kolmogorov, the problem is ill-defined if a particular concept of the solution x = R(U) in the initial data U makes it possible to satisfy the following conditions: a) for 209

210

CHAPTER

10.

OPTIMIZATION

OF NONLINEAR

PP

efficcient algorithms t h a t are based on the Tikhonov's principle of regularization and make it possible to obtain a solution for a wide class of m a t h e m a t i c a l programming problems. A special feature of regularization algorithms — determination of the normal and the approximate optimal solution — is t h a t t h e optimization procedures must be ef­ fected m a n y times (or at least reiterated). T h e approximate n a t u r e of iterative pro­ cedures, which can hardly guarantee the required accuracy for calculations in the medium-dimensional optimization problems, may preclude estimation of the optimal solution invariance when the parameters of the optimization problem are subject to variations. Investigations show t h a t in the convex programming problem there are invariant solutions (/^-solutions) t h a t are independent (to a certain extent) of variations in the functional or constraints. When inadequately described, the estimation problem of the optimal solution invariance amounts to solving one well-defined optimization problem, which permits a significant increase in the efficiency of the algorithm: ac­ curacy, speed, convergence, etc. Investigations also show t h a t the theorems of Kuhn-Tucker, Dubovitsky-Miliutin, Boltiansky hold t r u e for the problems with nonuniquely defined variables. Theoretical propositions make it possible to offer the m e t h o d s for synthesizing the solution algorithms of the optimal control problems t h a t are inadequately described.

10.1

Optimization of Problems with Nonuniquely Defined Variables and their Solution Methods

As noted before, the posinominal function optimization problem max/i(u>) = £ cx [rijwf'-'] ; w eW

= {w\g(w)

< 0,

(10.1)

w > 0, c > 0}

may have extensive engineering applications. In actual conditions, the coefficients of c, and index ki3 are nonuniquely defined and can be viewed as the nonuniquely defined variables (coefficients) belonging to the fuzzy sets U(C) and U(K), respectively. So, in the general case, we need to consider the optimization problem with nonuniquely defined variables. F-sets provide a means of obtaining the solution of t h e control problem with nonuniquely variables as some F-set of solutions. To this end, one has to determine any element u € U there is a solution x from the space F; b) the solution is uniquely defined; c) the solution is stable. According to Tikhonov, the problem is well-defined if: a) for some class of data. U G m there is a solution x which belongs to a given set M, a; £ M; b) the solution is unique in the class of functions belonging to M\ c) the solution is stable [21].

10.1. OPTIMIZATION

OF PROBLEMS

211

WITH NDV

the existence conditions for the unique solution when the coefficients of the objective function and constraints are nonuniquely specified in the problem maxh(l/(w)j, wG U{W). The conventional optimization problem can be represented in terms of F-sets as a special optimization problem (9.4). When stated traditionally and in terms of F-sets, the optimization problem allows one to determine the conditions under which the identity of solutions can be estimated for both cases. These conditions are usually associated with the F-set support in the original problem. L. Zade [22] investigated the control issue in large systems to show that the mathematic tools, which are based on the generalization principle and are designed for solving traditional optimization problems, can be applied for solving control problems under uncertainty (with nonuniquely defined variables). The direct application of the generalization principle sometimes involves substan­ tial difficulties. For this reason, one has to make significant preparations which actu­ ally amount to developing the solution algorithms and methods for ill-defined control problems with due regard for inadiquate description. We shall show that the optimization problem with nonuniquely defined variables (10.1) can be solved by the traditional methods. Additionally, we shall estimate their efficiency. Turning to the optimization problem in the traditional setting and its analog stated in terms of F-sets [16] Z', :

max/(z);

x € X;

Z'J :

m(x) = min{mp(i),mjv(i)} —> Extr

(max);

x £ X,

we note that the main criterion for adequacy of the problems Z' and Z" is taken to be the coincidence of the F-set support m(x) (the set x 6 X\m(x) > 0) with the solution x" of problem Z' This allows one to consider the solutions of problem Z" as determination of the conditions under which the F-set of solutions to this problem will coincide with the support of the set. In addition to operations on F-sets, as defined in Ch. 9, we define for the solution of the formulated problem the following concepts: 1. The support of the fuzzy set {u,} C U, i = 1,2,..., is such that (yu,(rnA(u)) > 0], A C U. The height of the fuzzy set h = supm^(u). 2. We adopt the following notation of a fuzzy subset of A C U n

A = /Ii\ul + . . . + /in|u„ = X ^ ' l " ' = V WKl i= l

where the plus sign denotes the union operation (U). 3. The set of the a-level of the fuzzy subset A is defined as A = U\fj.A(u);

A=

a- A.

212

CHAPTER 10. OPTIMIZATION

OF NONLINEAR

PP

4. The fuzziness increment operator FH is utilized for transforming the ordinary (nonfuzzy) set to the fuzzy set. Let A C U be a fuzzy subset and suppose the operator F acts to produce a fuzzy subset F(A;K)=UiiA(u)-K(u), where K(u) is a set, i. e., the core of the operator FH:

K(u) = F(l/u;K) 5. The nonuniquely defined belonging function is that belonging function for which HA{U), ^B(U) a r e intervals in [0,1], i.e. for a fixed u HA = {aua2}

-» [0,1];

I* = {biM-*

[0,1].

6. The complement to the fuzzy set

A = A' = j

(l-^A\u).

7. The union of the fuzzy sets A and B A + B = A U B = I (JIA{U) A /ifl(u)) \u.

8. The intersection of the fuzzy sets AC\B=

[ (fiA{u)\J

nB(u))\u.

Here (AAmax), (VAmin). 9. The product of the fuzzy sets A, B A B = j fj,A(u) ■ fiB(u)\u. 10. The convex combination of fuzzy subsets {A;}; i = 1, n is the fuzzy set A with the belonging function: A = Ui^.4, + . . . + UnPA„-

11. The generalization principle. Let / be given as the map A" —> V and let Z be a fuzzy subset: Z = Hx\xx +/*2|a;a + . . . + /j n |z n . Based on the generalization principle,

f(Z) =f(Pl\x}+...+

p„|s n ) = /Kil/C*!) + . . . + ^ n | / ( x n ) .

10.1.

OPTIMIZATION

OF PROBLEMS

WITH NDV

213

We will show that problem (10.1) can be reduced to a finite set of traditional op­ timization problems. To do this, we utilize the Zade-Bellman generalization principle and mathematical induction principle. We will actually consider the cases of interval (nonunique) definition of the vari­ ables c = {c,}; i = l , n and k and then unite both cases. Suppose there exists a universal set c, € C of the functional coefficients of U(C) in the problem m a x / ( a ) , x € X where accordingly there is a fuzzy subset CM; C^

= j/jt\Cl; c

i=T~^

and the support of the subset has the power of continuum

C(A) = I fj.C{A)\C, c where /i, is the function of belonging of the component C, to the fuzzy subset C ^ ' f 1, Ci — Ac, < c, < c, + Ac,-:

(v»)(/4e>) = ( 0, c, > c, -+- Ac,, c, < c, — Ac,. Note that the belonging function y.\ be represented as

can be nonuniquely defined, while Hc{A) c a n rs

(c)

pew = r>; In view of the last relations, the belonging function fj,p(x), which characterizes the pre-image of the F-set of objectives C for the map / : X —> Y, becomes the function UP and, according to [16], takes the form: fj.p(x,c) = (J.p{x) PI no[Ay, ,

v_ /

l,f(x)>f(x*),ccU(C);

>"p[X'C)-\0,f(x)
and is nonuniquely defined. In view of the above relations, the optimization problem Z", which is an analog of the uniquely defined problem Z', at the level of fuzzy sets (variables), becomes fl(x) = mm{fip(x),iJ.N(x)}

-4 Extr(max).

xeX We shall define the form and structure of the fuzzy set support, fj.{x), and formu­ late the auxiliary problem of determining the conditions under which the supports of fuzzy sets, fi(x) and fi(x), coincide (this is equivalent to the fact that the solutions of the problems (f(x), U(C) j —>• max, x g X with nonuniquely defined and ordinary variables coincide).

214

CHAPTER 10. OPTIMIZATION

OF NONLINEAR

PP

We shall consider the cases in which the functional coefficients are normalized < co < £»(n»K)) V J : c° = c,-/||c||, where ||c|| is the functional norm, ||c|| = (c^) / Here the belonging function values p.(x) are fuzzy subsets in the interval [0,1], (Vi).

co(min) 1 2

Let us isolate a-levels in fj.p(x,c), fip(x,c) = / / j p (z,c), where /^p is the value o of the belonging function fJ.p{x) at the a-level; (x,c)^{c\v(c) > a } , where v(c) is the degree to which the vector c = {c,}; i = l , n belongs to the fuzzy subset fip(x,c). If the number of a-levels is equal to w, then it is possible to generate a finite set of special problems of the form: /i(a> = min \jj,p (x,c),fj.iv(x)\ i6l,

—> Extr(max),

a = l,w;

1, xeNJ(x)>f(x),

(10.2)

cCU (&">);

/i(z)

0,xeN,f(x) 0\ coincides with the solution of the problem f(x) —> max, x g A'. Consequently, if the support of the F-set p,(a'(x) coincides with the solutions on all o-levels, this is a necessary (and sufficient) condition for existence of the general unique solution in problem (10.1) when k is a uniquely defined variable. The assumption that k belongs to the class of nonuniquely defined variables is of no importance. In this case the belonging function fj,p (x,c) in problem (10.2) must be regarded as jiSp (x, c, k) = fip '(x, c) fl fip(k).

10.2

Generalization in Nonuniquely Defined Functional Optimization Problems

Let m a x / ( C , x); x € .V be the original (well-defined) optimization problem. Suppose the objective function is given explicitly. The set of coefficients C is universal, i. e., all the coefficients are uniquely defined variables. We introduce the following definitions. DEFINITION 1. The functional f{C,x) is nonuniquely defined if at least one of the coefficient sets c, £ C is a nonuniquely defined variable or a nonuniquely defined number which can be characterized by the. triple of parameters C, U, R(C, U), where C is the name of the variable; U is the universal set; u € U is the common name of elements of the set U; R(C,U) is a fuzzy subset of the set {/ that is a nonuniquely defined constraint on the value of the variable U specified by C. The assignment equation for c is of the form c = u : R(C).

10.2.

GENERALIZATION

IN NONUNIQUELY

DEFINED PROBLEMS

215

The degree to which this equality is satisfied is called the consistency of the value u with R(C) and is denoted as fi(u) --= VR(C){u),

where HR(C)(U) is the degree to which it belongs to the constraint R(C). EXAMPLE. The nonuniquely defined coefficient c, can be represented as a nonuniquely defined number APPROXIMATELY c and written as c,4

APPROXIMATELY

c ; = 1 / 4 " + U ^]/c\j),

j = 1,2,...,

3

where fj,[3' is the function of belonging of the value cp' to the universal set C = \C{k}V k = 1,2,... We shall consider the formation of a "fuzzy" functional as a result of the action of uncontrolled perturbations. In this case it may be wise to represent the "fuzzy" functional as a result of the action of the fuzziness increment operator on the uniquely defined functional f(x,C). The fuzziness increment operator can be defined according to [3] as follows. DEFINITION 2. Let U = {uk}; k = 1,2,... be a universal set; A C U—a fuzzy subset for whose elements there are the belonging functions /i/i(u,); K(u) — a fuzzy set that is obtained through the action of some operator on a singleton 1/u : K{u) = F(l/u; A'). Then the action of the fuzziness increment operator on the fuzzy subset A C V may result in a. fuzzy subset F(A; K) that is defined as F(A; K) = HA{U) ■ A"(u), where (J,A(U) • K(u) is the product of the number (J.A{U) and the fuzzy set K(u) for which A = [ a ■ fi^(u)\u holds when \a\a ■ s u p / ^ a ) < 1, Va\. Suppose the result of the action of the fuzziness increment operator is that the set of functional coefficients f(x,C) (or at least one of the coefficients) becomes the set of nonuniquely defined numbers APPROXIMATELY C. We obtain the nonuniquely defined functional optimization problem max/(r,C4

APPROXIMATELY

c) ;

x £ X.

(10.3)

The presence of the functional as in (10.3) necessitates the solution of two prob­ lems: — definition of the conditions under which the solutions of the original and the perturbed problem (10.3) coincide; invariance of the optimization problem with re­ spect to perturbation; — development of the general solution method for problems of the form (10.3). We shall examine the possibility of solving problem (10.3) by the traditional me­ thod. In [3], the generalization principle is formulated to transfer the main properties of the universal (uniquely defined) mappings or relations on some universal region U(C) to the nonuniquely defined mappings or relations whose domain of definition can be nonuniquely defined, U(/J,,\U,). For the mapping problems, the generalization principle can be represented as follows. Let / be the map u -* v, A a fuzzy subset, and A = U(/J.,\ut). According to [3], f(A) = U(ni\f(ui)). The last relation is called the generalization principle.

216

CHAPTER

10.

OPTIMIZATION

OF NONLINEAR

PP

For the optimization problems, t h e generalization principle can be t r e a t e d at the level of mappings as prescribed by the procedure in [16]. But the efficiency of this approach is not very high. This is due to the fact t h a t in some cases the tradition­ al optimization problem treated in terms of F-sets does not allow one to obtain a unique solution even though it exists. Since the solution m e t h o d s for traditional op­ timization problems are adequately developed, it is advisable to determine at least those conditions under which the traditional methods can be applied to solving the problems with nonuniquely defined variables. By analogy, t h e possibility of solving the nonuniquely defined functional optimization problem with t h e use of traditional methods will be called the generalization principle. In the solution of the LP problems with the coefficients of a linear form specified at intervals ( C h . 9 ) , it was shown t h a t in order to e s t i m a t e t h e optimal solution invariance or construct the limit solution set (if the solution is not invariant) it suffices to run In tests for inclusions of vectors (rows of matrix C = C\ U C2) in the allowable variations cone Qx. Using t h e concept of near-gradient, 2 one m a y obtain another form (condition) of t h e optimal solution invariance in the LP problem with nonuniquely defined (interval-defined) coefficients of a linear form. In order to define near-gradients in the LP problem with nonuniquely defined coefficients of a linear form, one has to take into account t h e fact t h a t t h e rows of matrix C = C\ U C2 are. gradients of a linear form. We shall determine the limit — maximal and minimal — elements of the vector set generated by the method given above. Let us normalize t h e vectors c: ^=CW/(cW,CW)1/! and define the direction array of cosines between the normalized vector c of the center of gravity of t h e vector set C = C\ U C 2 and t h e vector c' 3 ' S C; j = l , 2 n : 6;=(c,c(i));

i=3T25T

(10.4)

In the array {bj}; j = l,2n, we define the maximal and t h e minimal elements, bz = max{6j}, bv = min(&,), and their associated vectors c C C, c C C. Each of the vectors c' J ' C C; j = l , 2 n has the property CWgA'J,

bv>k\

CWeAp,

k>bf,

(10.5)

where KQ, KQ are circular cones whose generatrices form the respective angles arc6„, arc&z with the vector c. 2 The near-gradient of function f[%) at the point x is the vector that is the limit point of some gradient sequence V / ( n ) , V / ( s j ) , . . . , V/(x ft ), where {xk}f=l is a sequence of points converging to x such that f(x) is differentiable at all points of this sequence [15].

10.2. GENERALIZATION

IN NONUNIQUELY

217

DEFINED PROBLEMS

Since the vectors c? C C are taken to mean the gradients, then by the definition of the near-gradient [15], the vectors c and c are the limit points of the gradient sequence, and hence near-gradients. So the nonunique definition of the functional leads to a nonuniquely defined near-gradient and, accordingly, to the optimization problem m a x { ( c J , i ) , ( c v , i ) } ; x G A"; X = {x\Ax0}

[

>3)

If x* is a solution of the problem max(x' z ', x); x € X, then the condition that any one of the problems max(c' J ', x); x G A'; j = 1,2,. . .; X = {x\Ax < b, x > 0} will have a solution as the vector x* can be written in terms of Kuhn-Tucker theorem as follows: if c[v}eD(M) then max(c[j],i) = i". (10.7) Vj; j = 1,2T where D(M) is the dual cone which is made up by the vectors of hyperplane normals generating at x* a bundle (roof). If this proposition is not satisfied, then the basic algorithm can be utilized for solving the problem of determining the limit solution set. After solving the problem and constructing the cone D(M)1, each of the vectors c?G C; j' = 1, 2n is successively tested for belonging to the cone D(M)1 The first vector c"', whose direction does not belong to the cone D(M), is utilized for formulating the problem max(c,x); x G A; X = {x\Ax < b, x > 0}

(10.8)

After solving problem (10.8), determining the solution vector x' 1 ' and construct­ ing the cone D(M)2, one continues testing the vector directions c " + 1 ' , c^t+2\ . . . for belonging to the cone D(M)2 This procedure is carried out until all the vectors c' j) G C\ j = l,2n are surveyed. Suppose the total number of problems arising from the solution of the LP problem with nonuniquely defined coefficients is equal to w, i.e., there exist vectors x*' 1 ',. . ., a:*'"'. The vector x, for which r — \x — x*'!M —> min; ! = l,w can be taken as a solution of the original LP problem. In the general case, one can state that the solution cone Rx = (x* ( ''|; i = l,u includes all possible solutions x**c), x*(c' G Rx of the original LP problem which could not occur under various combinations of components c (j) that did not appear in C = Cx U C2. Note that suitable belonging functions can be defined for the components of the solution cone Rx. We shall exam­ ine the ways of constructing near-gradients for the nonlinear objective function which contains nonuniquely defined coefficients. On the assumption that the functional / ( x , C) is well-defined and convex, we con­ struct its linear approximation at the point x (s) : / ( s ) ( x , C ) = / ( x ( s ) , C ) + + V / ( x ' 5 ' , C)(x — x^'); x' 5 ' G X. The fuzziness increment operator is forced to act

218

CHAPTER 10. OPTIMIZATION

upon the functional ps\x,C).

PP

Similarly to (10.3), obtain the optimization problem

s

max/< >(x,[/(C)) = / ( x < s ) , C 4 C +V/(x's>,CA

OF NONLINEAR

APPROXIMATELY

APPROXIMATELY x a

( i )

C)(x-x^);

C) + (10.9)

,

where C is a fuzzy set of coefficients which is distinguished from the set C by the scale coefficient (c, = c, ■ M, M being the scale determined by differentiation, c, G C, c, e C ) . Problem (10.9) is a linear programming problem, where the objective function coefficients are nonuniquely defined. Similarly to (10.4)—(10.6), one may define neargradients V/j 2 '(a:, C), V / | ^ ( s , C). If the numeric of iterations is equal to p, then it is possible to construct the cone of near-gradients:

K» =u {v/((;»(x, o,v/((;»(x,o];

S = YTP.

Assumption 10.1. Suppose there exists a convex optimization problem max f(x); x £ A'. The action of the fuzziness increment operator, under which at least one of the functional coefficients becomes a nonuniquely defined number or a nonuniquely defined variable, transfers the original problem to the class of vector optimization problems of almost differentiable functions. The methods of generalized gradient descent (GGD methods) are widely used to solve the optimization problems of almost differentiable functions. But here they are very difficult to use. This is due to the fact that the GGD methods require unique specification of the generalized gradient; otherwise there is no algorithm which provides a means of constructing a vector V / | ( x , C) [15] such that for any e > 0

min|V£-V/,(*,C)|<e; v/.(*,C)e A'f. If the problem is approximately solved, one may construct a vector V/ X (x, C) for which, with the positive e specified, there exists a point x belonging to the neighbor­ hood of X, x 6 U(X) such that min|V/;(x,C)-V/.s(x,C)|<e;

V/,(x,C)e A'f Additionally, we require the conditions to be satisfied in such a way that these relations would hold for Vf$(x,C) = V/s(~">, V/ S (.r, C) = V / s \ Then we assume that this is a necessary (and sufficient) condition for x to be a solution of the nonuniquely defined functional optimization problem. If Vf°(x,c) cannot be constructed, then solve a pair of problems by taking V/ S (x, c) to be the functionals whose gradients are respectively V / j 1 ' , V/}">. So the proposed formulation of the optimization problems with nonuniquely de­ fined variables allows for the solution by traditional methods.

10.3. OPTIMIZATION

10.3

OF NONLINEAR

CONVEX FUNCTIONS

219

Optimization of Nonlinear Convex Functions with Nonuniquely Denned Coefficients

We shall consider the "original" convex optimization problem min/(A',C4C

APPROXIMATELY

x 6 X = {x\gi(x) > 0,

C) ;

x>0},

where the objective function (functional) is explicitly given and the coefficients are nonuniquely defined variables: Cij)A

APPROXIMATELY

CU) = U

(nU)\Cij))

We shall define the conditions under which the solution of the original problem is invariant with respect to the fuzzy set of coefficients t/[/i' J ''|C' J 'J. If the invariance conditions do not hold for the given fuzzy set of coefficients, then one has to define some fuzzy subset [/(/j' J '|Cj for which the invariance conditions hold. The statement of the problem can be modified as follows. We have the convex optimization problem with nonuniquely defined variables: Z_:

min/i(z);

x £ X.

The influence of perturbations leads to the problem: Z:

mmh(x,K{X;W));

x e X,

where K(x\ w) is the fuzziness increment operator. What kind of structure must the operator K(x;w) have to make these solutions coincide? The reverse statement of the problem seems natural, i. e., we have the nonuniquely defined functional optimixation problem. Then one has to estimate the existence of a fuzziness reduction operator such that its action will transfer the otiginal problem to the class of problems with uniquely defined variables, where the solution of the latter coincides with that of the original problem. Suppose the solution x' = {x*}; i = L/ri of the problem min/(x); x 6 A' = {x\gt(x) > 0,x > 0}; j = l,m is regular, i.e., it is located at the node of the convex polyhedral set X, (f(x),gj(x)) are convex differentiable functionals. On the set X it is possible to select a subset M C X of constraints g,(x) < 0; j = l,t> which form a bundle (roof) at the point a-': (Vj)ff,(x-) = 0 j = M -

(10.10)

Based on the Kuhn-Tucker theorem, the dual cone D(M) is defined as D(M) = {V(7,-(x*)}; j = l,v and has the property that the set of problems | m i n / ( p , ( x ) ; x € X\ has the general (regular) solution if the vector directions V/' p '(x*) belong to the

CHAPTER 10. OPTIMIZATION

220

OF NONLINEAR

PP

dual cone D(M). This condition can be written in terms of ALGOL operators as follows if V / W ( / ) £ D(M) then min/<">(*); x € X;

(V/M(«)),

(1

p = l,2,...

°'n)

If the set of vectors V/' p '(a:) is viewed, e. g., as a result of action of the fuzziness in­ crement operator, and if a subset of near-gradients < V/'"'(x*), V / ' J ' ( . T * ) | is selected, then the fulfillment of the condition A"™ C -D(Af), where Kf = = { V/'"'(x*), V/W(x*)j, is a necessary (and sufficient) condition for the nonuniquely defined functional optimization problem to have a unique solution. The fulfillment of the condition for inclusion of the near-gradient cone A'™ in the cone D(M) (the allowable variations cone) makes it possible to select in the fuzzy set of generalized gradients their fuzzy subset which has a unique solution if for the original fuzzy subset of gradients there is no unique solution. We will consider the estimation algorithms for existence of a unique solution in the nonuniquely functional optimization problem. Suppose the original problem can be solved by linear approximating programming methods [6]. Then we have the set of problems min / « (x, U(C)) = f (xW) + V / (xW>) (x - xW) ; XW = [x\g3 (jW) =

9i

x 6 X^

:

(*(/)) + V f t (*W) (x - i W ) > 0} ,

(10 12)

where z'^' is the vector in the neighborhood of which the original problem is linearized: / = 0,1, 2 , . . . If in order to select a vector x^+1' one may utilize the relation x " + 1 ' = where / is the number of a step, /'■" is the step whose value lies within x(f) _|_ lU)S''\ 0 —/max, and S^> is the vector of a feasible direction, then problem (10.12) transforms to the problem / (*<") + Z(»V/ (xW) 5 ( / ) -> Extr(min); S{!) = {*\gj {xu)) the sequence -jx^H

x, s G S<»;

+ / ( / ) V 5 t (*(/>) S<" > 0} ,

is convergent and forms the solution x*, j z ' ^ ' }

(10.13) —> s*,

/ = 0 , 1 , 2 , . . . The solution S*^\ f = 1,2,... of problem (10.13) is regular, which offers a means of constructing the cone of allowable variations Qx = n£*(M'- f '), / = 1,2,...,, where D(M^) = {Vg,{x^)], j C // is a special cone of allowable variation which is determined at each step; Ij is the number of hyperplanes which form a bundle at the /-th step. Since (10.13) is the convex optimization problem, then for each vector Su> it is possible to construct a special cone of near-gradients A'f = {V/W(x^)),V/M(a:W)} and a common cone: Kr = UfK»,

/=1,2,...

(10.14)

Test the condition K* £ Qx

(10.15)

10.3.

OPTIMIZATION

OF NONLINEAR

CONVEX

FUNCTIONS

221

for t h e entire fuzzy set of coefficients. T h e fulfillment of (10.15) shows t h a t in the nonuniquely defined functional optimization problem t h e r e exists a unique solution. Otherwise one has to reduce the fuzzy set of coefficients and restrict oneself to some value of t h e a-level for which a unique solution can be ensured (the a-level is a fuzzy subset for which t h e belonging functions /i(x) > ad). For t h e fuzzy set, which contains the belonging functions /J, > ad, one may define the original problem and t h e cones Qx and Kx for which the above algorithm can be utilized sequentially. So we have the vector optimization problem of functionals. Note t h a t in some cases it is advisable to verify the condition (10.6) at each step of the regular solution. Justification of the algorithm. As noted before, linearization of t h e original math­ ematical programming problem, where a regular solution is required at each step, leads to a set of problems (10.12), (10.13). T h e algorithm will be implemented in compliance with the operator scheme t h a t follows: A1A2A3P^ | ASA6A* t As, (10.16) where A\—the procedure of defining a feasible point x ' p ' in the original problem m i n / ( a : ) ; x£ X(p = 0); A2 — generation of t h e approximating LP problem (10.13) for determining a fea­ sible direction s'p' at t h e point x ' p ' ; A3 — solution of problem (10.13) and definition of vector 5 ' p ) P 4 —verification: V/(a- (p >)S (p > < 0; A5 — determination of the maximal step length / = maxj/|z' p > + / ■ S^l

£ A'

(P 4 = t r u e ) ; A6 — determination of t h e designed step line 0 < / ( p ' < / for which / ( z ( p ) ) + / (p) (p) 5 -► min;

A7~p

= p + 1;

A8—termination of the optimization search, storage of vectors x^\ S ' p ' , compu­ p tation of values / ( x ' ' ) ( P 4 = false). This scheme allows one to examine t h e definition of 5 ' p ' t h a t is a feasible direction at the point i ( p ) . By the regularity of the solution 5 ( p ) , a special cone D(NM) can be constructed as follows: D (M< p )) = {v9l(xM)}

;

j = TT^,

where vp is t h e n u m b e r of hyperplanes forming a bundle at the p-th step. T h e following proposition holds for t h e cone J D ( M ' P ' ) : if

V/< a >(z ( p ) ) € £>(M