Symmetric duality for nonlinear mixed integer programs with a square root term

SYMMETRIC DUALITY FOR NONLINEAR MIXED INTEGER PROGRAMS

WITH A SQUARE ROOT TERM

Do

ABSTRACT. We formulate a pair of symmetric dual mixed integer programs with a square root term and establish the weak, strong and converse duality theorems under suitable invexity conditions.

Moreover, the self duality theorem for our pair is obtained by as- suming the kernel function to be skew symmetric.

1.

Introduction

The study of symmetric duality in nonlinear programs was initiated by Dantzig et al. [3]. Balas [1] considered the symmetric duality results of Dantzig et al. [3] for the case that some primal and dual variables were constrained to belong to some arbitrary set; for example, the set of integers. While Balas [1] used concave j convex functions and nonnegative orthants as the cone, Mishra and Das [9] generalized this to any arbitrary cone. And then Kim et al. [5] established the symmetric duality theorems for multiobjective nonlinear programs with arbitrary cones. The duality results 'of Balas [1] of the problems with convex cone domains and the pseudo-convex jpseudo-concave kernel function were extended by Mishra et al.[8]. Recently Kumar et al. [6] presented a modified pair of symmetric dual minimax integer programs which was in the spirit of Mond and Weir [11,12] and did not require any of several assumptions of the type given by Mishra et al. [8].

On the other hand, Mond et al.[7,10] gave symmetric duality theo- rems for certain nondifferentiable programs with square roots of qua- dratic forms in the objective functions. Since then Chandra and Husain

2000 Mathematics Subject Classification: 90Cll, 90C30.

Key words and phrases: mixed integer programs, symmetric duality, invexity.

This research was supported by the Research Grant of Pukyong National Uni- versity, 1998

[2J gave symmetric and self duality theorems for nondifferentiable pro- grams with the convexity/concavity conditions of kernel function. The following pair of programs was considered by Chandra and Husain [2]:

(P) Min

subject to

(D) Max

subject to

F(x,y,w)

f(x,y) - yT"Vyf(x,y) + (xTBx)t - "Vyf(x,y) +Cw

0,

wTCw

1, x

0,

0,

G(u,v, z) = f(u, v) - UT "Vxf(u, v) - (vTCv)t - "Vx2 f(u,v) - Bz

^0,

zTBz

1, u

0, v

0.

In this paper, we formulate a pair of symmetric dual mixed integer programs with a square root term and establish the weak, strong and converse duality theorems under the condition that f(x, y) +

TBz is invex in

for each

and -f(x,y) +

T

_{invex in}

for each (x,

where (x, y)

Moreover, the self du- ality theorem for our pair is obtained by assuming f(x, y) to be skew symmetric.

2. Preliminaries and notations

We constrain some of the components of

and

to arbitrary sets of integers. Suppose the first

components of

and the first ml components of

(0

°

^ml

^m) are arbitrarily constrained to be integers and the following notations are introduced:

where n = ^{nl +n2, m} = ^{ml +m2. Let U and V} be two arbitrary sets of integers in

and

respectively. Let f :

lR be a twice differentiable function. Let "VX2 f (x, y) denote the gradient of

f (x, y) with respect to

and "VY21 (x, y) be defined similarly. Also let

"VX2 X2f(x, y) denote the Hessian matrix of f(x, y) with respect to

"Vy2y2 f(x,y), "Vy2x2 f(x,y) ^and "VX2y2 f(x,y) are defined similarly.

DEFINITION

1 [2]. A differentiable function F :

is said to be invex with respect to the 17 :

iffor all (x, u) E

F(x) - F(u)

17(X, u)T\7F(u).

DEFINITION

2. Let

be elements of an arbitrary vector space. A real valued function

is said to be separable with respect to

if there exist real valued functions

and

such that

We shall make use of the following generalized Schwarz inequality:

where x,

and A

is symmetric and positive semidefinite.

Now we consider the following minimization problem with a square root term:

(P) minimize j(x) + (xTBx)t

subject to g(x)

0,

where j :

9 :

and B is symmetric positive semidef- inite n

n matrix.

In order to obtain the symmetric duality results, we introduce Fritz John type necessary optimality theorem for

LEMMA 1 [4]. If x ^is optimal to (P), then there exist r E

P E

and z

such that

pTg(X) = ^0,

r(\7j(x) +Bz)

\7pT g (x), zTBz

1,

(x

^BX)t

x

Bz,

(r, p)

0,

(r,p)

0.

We formulate the following symmetric dual mixed integer problems with a square root term:

Primal (BP) Max

Min

,y (1) subject to (2)

Dual (BD)

Miilyl

Max

,Y2 (3) subject to (4)

T T 1.

F(x, y, w) = f(x, y) - Y2 \7Y2f(x, y) + _{(x2 BX2)}

- \7Y2f(x, y) + Cw

0, wTCw

1,

Xl E

U,

V,

T T 1.

G(u, v, z)

f(u, v) - u2 \7x2 f(u, v) - (V2 CV2)

- \7

f(u, v) - Bz

0,

zTBz

1, UI

U, VI

where (i) B

2

and C

are symmetric positive semi- definite, (ii) z and ware vectors

and

respectively, (iii)

f :

is twice differentiable in X2 and. Y2 and separa- ble with respect to XI( or

and (iv) 171(X2,U2) + U2

° ^and

172(V2,Y2) + Y2

o.

For notational convenience, the sets of feasible solutions of primal X and dual Y are denoted by

X

{(x,y,W)/XI

U,YI

~-\7yd(x,y)+Cw ~ O,wTCw _~ I},

Y

{(u,V,Z)IUI E U, VI E V, -\7 x2f(u, V) - Bz ~ 0, zT Bz ~ I}.

3. Synunetric duality

In this section, we establish weak, strong, converse and self duality theorems between (SP) and (BD).

THEOREM

1 (Weak Duality). Let f(x, y) + xr Bz be invex in X2 for every (XI,Y) with respect to

and -f(x,y) +y'[Cw. be invex in Y2 for every (x,

with respect to

Then, for any (x, Y, w)

X and (u,v,z)

Y,

F(x,y,w)

G(u,v,z).

Proof. Denote

Z

maxmin{F(x,y,w)l(x,y,w) E X}, and

Xl

X2,Y

W

minmax{G(u,v,z)l(u,v,z)

Y}.

Yl

X,Y2

We give the proof only for the case f(x, y)

separable with respect to Xl. (The case f(x, y) is separable with respect to Yl can be handled in a similar way.) Since f(x, y)

separable with respect to XI, it follows that f(x,y)

h(Xl) + h(X2,Y)· Therefore V y2 !(x,y)

V y2 h(X2,y) and Z can be written as

Z = maxmin{h(xl) + h(X2,Y) - y'fvy2 h(X2,Y) + (Xr BX2)!1 Xl

U,

Xl

X2,Y

Yl E V, -Vy2 !(x,y) +Cw

0, wTCw

I}.

or Z

max

min

{h (Xl) + t/J(Yl) : Xl E U, Yl E V}, where (5) t/J(Yl) = min{h(X2,Y) - y'fVy2 h(X2,Y) + (Xr BX2)!

. X2,Y2

1- V y2 h(X2,Y) + Cw _~ 0, wTCw _~ I}.

Similarly, W

min

max

[h (Ul) + 1/J(VI) : Ul E U VI E V], where (6) 1/J(Vl) = max{h(u2, v) - urV x2h(U2, v) - (v'f CV2)!

X2,Y2

1- V x2 h(U2,V) - Bz

0, zTBz

I}.

Let (x,y,w) E X and (u,v,z) E Y. In order to prove the theorem, it is sufficient to show that t/J(YI)

1/J(Vl).

t/J(YI) -1/J(Vl)

T T ¹

~

h(X2,Y) - Y2 V y2 h(X2,Y) + (X2 Bx2)2

T T ¹

- h(U2, v) + u2 V x2h(U2, v) + (V2 CV2)2

~ h(X2,Y) - y'fvy2h(X2,Y) + (XrBX2)~(zTBz)!

- h(U2,V) + urVx2 h(U2, v) + (V'fCV2)~ ^(wTCw)!

(by (4), (2) and (i))

~ h(X2, y) - y'fVy2 h(X2, y) + xr Bz - h(U2, v) + urV

^{2f2(U2, v)}

+ v'fCw (by the generalized Schwarz inequality)

~

(X2, U2)T(Vx2!2(U2, v) + Bz) - 'rJ2(V2, Y2f(V y2 !2(X2, y) - Cw) + yiCw + uiBz - yiVy2 !2(X2,Y) + ufvX2 !2(U2,V)

(by the invexity of f(x,y) + X2TBz,and - f(x,y) + Y2TCw)

= {'rJl(X2,U2) +U2}T(Vx2 !2(U2,V) +Bz) - {'rJ2(V2, Y2) + Y2}T(VY2!2(X2,Y) - Cw)

~O

(by (1), (3) and (iv)).

Therefore F(x, Y, w)

G(u, v, z). 0

Using the Lemma

we can prove the following strong duality the- orem.

THEOREM

2 (Strong Duality). H (x, y, w)

X solves (SP) and the. matrix V Y2Y2 h (X2, y) is positive or negative definite, then there exists z

such that (x, y, z)

Y with F(x, y, w)

G(x, y, z). H,

in

addition, f(x,y)+xf Bz beinvex

X2 for every (Xl, y) with respect

to

and - f(x, y) +y'fCw be·invex

Y2 for every (x,

with respect to'rJ2, then (x, y,z) is optimal for (SD) and objective value of the dual is equal to that of the primal.

Fri, y, w)

G(x, y, z).

Proof. For given

=

=

(5) and (6) are a pair of symmet- ric dual nondifferentiable programs. Since (x, y, w) solves (SP), by Lemma 1 there exist r

JR., a:

2

and /3

such that

(7) a:V

!2(X2,fj) = ^aTCW,

(8) jj(1 - w

CW)

0,

(9) rVx2 h(x2,y) + (a - rIh)TVX2Y2!2(X2,y) + rBz

0,

(10) (a - rY2fVY2Y2h(X2, y)

0,

(11) Ca

2jjCW,

(12) zTBz

1,

(13) (

_X2.vX2 o-::::).!

=

2 =

x2 .oZ,

(14) (r, a, jj)

0,

(15) (r, a, jj) i- 0.

Now multiplying (10) by (0: - rlh), we have

(0: - rlh)TV

!2(x2, fj)(o: - rfh)

O.

Since V

h ^{(X2' y)}

positive or negative definite, we obtain

(16) 0:

rfh.

Now multiplying (11) by

we get (17)

It

is to be observed here that r > 0, for otherwise 0: = ^rY2 = 0, and (17) together with (8) imply f3 = 0, a contradiction to (15). Now equation (11) with the aid of (16) and the fact r > 0, gives

(18) - T Y2

(-T Y2

TC-) 1.

Also from (8), either f3 = 0, and hence CY2 - 2(f3/r)Cw = 0 or w

CW

In either case (18) give

(19) -T Y2

= (-TC-)1. ^{Y2 Y2}

From (9) and (16) together with

> 0 we get (20)

and from (12) and (20), (X2' Y, z) is feasible for (BD). Multiplying (20) by X2, we get

(21) Hence

F(x,y,w) =h(Xl) + h(x2,fj) - YIV

h(x,fj) + (xIBx2)~

= h (xI) + ^h(x2, fj) - yI CW + ^{(xI BZ)}

(using (7), (16) with

> 0 and then (13))

=!(x,fj) -xIV

!(x,fj) - (yICY2)~

(using (19), (20), !

h + h,and V

!

^V

h)

=G(x,y,z).

o

Thus (x, y, z) is optimal for (SD) by Theorem 1.

A converse duality theorem may be stated as follows:

THEOREM 3 (Converse Duality). If (x, y, z)

Y solves (SD) and the matrix "\1 X2 X2h(X2, y) is positive ^or negative definite, then there exists w

such that (x, y, w)

X with F(x,y,w)

G(x,y,z).

If, in addition, f(x, y) + x'fBz be invex in X2 for every (Xl, y) with respect to

and - f(x, y) +y'fCw be invex in Y2 for every (X,Yl) with respect to

then (x,

w) is optimal for (SP) and the objective value of the primal is equal to that of the dual.

G(x, y, z)

F(x, y, w).

We now establish the self duality of (SP).

Assume that nl = ml, n2 = m2, C = B, z = wand f(x, y)

-f(y, x).

It

follows that (SD) may be rewritten as follows:

(SD') Max

Min

subject to

T T ¹

f(v,u) - U2 V y2 f(v,u) + (V2 CV2)'2 - "\1y2 f(v,u) +Bz

zTBz

1,

Ul E

U,

V.

(SD') is formally identical to (SP); that is, the objective and con- straint functions of (SP) and (SD') are identical. This problem is said to be self dual.

It is easily seen that whenever (x, Y, z) is feasible for (SP), then (Y, x, z) is feasible for (SD), and vice versa.

THEOREM

(Self Duality). Assume that (SP) is self dual and that the invexity conditions of Theorem 1 are satisfied. If (x, y, z) is an optimal solution for (SP), and the matrix "\1Y2Y2h(X2, y) is positive or negative definite, then (y, x, z)is an optimal solution for both (SP) and (SD), and the common optimal value is o.

Proof By Theorem 2, (x, y, z) is an optimal solution for (SD), and

the optimal values of (SP) and (SD) are equal to F(x, y, z). From the

self duality, (y, X, z) is feasible for both (BP) and (BD). So Theorem 1 and Theorem 2 give optimality in both problems, and thus objective values of F(y, x, z). Now it remains to show that F(x, y, z)

o.

F(x,y,z) =!(x,y) - Y2TVyJ(X,Y) + (xIBX2)!

= !(x, y) - yIBw + _{(xI BX2)~}

(using (7), (16) and r > 0)

= !(x, y) - (yI Bfi2) ~ + (xI BX2) ~ ^. (by (19))

Hence,

F(x,y,z) =!(x,y) - (yIHfh)~ + _(XIBx2)~

=F(y,x,z)

=!(y,x) - (xIBx2)~ + _(yrBfh)~

= -

!(x,y) - (xIBx2)~ + (yIBy2)~

(by the skew symmetry of ! (x, Y) ) and therefore F(x, y, z)

o.

References

o

[1] E. Balas, Minimax and duality for linear and nonlinear mixed-integer program- ming, in:J. Abadie (ed.), Integer and Nonlinear Programming, North-Holland,

Amsterdam, 1970. .

[2] S. Chandra andI. Husain, Symmetric dual nondifferentiable programs, Bull.

Austral. Math. Soc. 24 (1981), 259-307.

[3] G. B. Dantzig, E. Eisenberg, and R. W. Cottle, Symmetric dual nonlinear programs,Pacific J. Math. 15 (1965), 809-812.

[4] Hanson, On sufficiency of the Kuhn-Tucker conditions, J. Math. Anal. Appl.

12 (1981),545-550.

[5] D. S. Kim, Y. B. Yun, and W. J. Lee, Multiobjective symmetric duality with cone constraints, Euro. J. Oper. Res. 101 (1998), 686-691.

[6] V. Kumar,I.Husain, and S. Chandra, Symmetric duality for minimax nonlin- ear mixed integer programming, Euro. J. Oper. Res. 80 (1995), 425-430.

[7] S. L. Mehndiratta, Symmetric and self duality in nonlinear programming, Nu- mer. Math. 10 (1967), 103-109.

[8J M. S. Mishra, D. Acharya, and S. Nanda, Ona pair of nonlinear mixed integer programming problem, Optimization 28 (1993), 9-16.

[9J B.K. Mishra and C. Das, On minimax and symmetric duality for a nonlinear mixed integer programming problem, Opsearch 17 (1980), no. 1, 1-11.

[lOJB.Mond, A class of nondifferentiable mathematical programming problems, J.

Math. Anal. Appl. 46 (1974), 169-174.

[11] , Symmetric duality for nonlinear programming, Opsearch 13 (1976), 1-10.

[12] B. Mond and T. Weir, Generalized concavity and duality in: S. Schaible and W.T. Ziemba (eds.), Generalized Concavity in Optimization and Economics, Academic Press, New York, 1981.

Department of Applied Mathematics Pukyong National University

Pusan 608-737, Korea