EQUATIONS APPROACH

(1)

SENSITIVITY ANALYSIS FOR PARAMETRIC VECTOR OPTIMIZATION PROBLEMS USING DIFFERENTIAL

EQUATIONS APPROACH

FATMA M. ALI (Received 11 September 1998)

Abstract.A new method for obtaining sensitivity information for parametric vector optimization problems(VOP)v is presented, where the parameters in the objective functions and anywhere in the constraints. This method depends on using differential equations technique for solving multiobjective nonlinear programing problems which is very effec- tive in finding many local Pareto optimal solutions. The behavior of the local solutions for slight perturbation of the parameters in the neighborhood of their chosen initial values is presented by using the technique of trajectory continuation. Finally some examples are given to show the efficiency of the proposed method.

2000 Mathematics Subject Classiﬁcation. Primary 90C29, 90C30, 90C31.

1. Introduction. A differential equations approach is presented as a new method for solving equality constrained nonlinear programing problems in [7]. This technique was extended in [1] to be applicable for solving multiobjective nonlinear convex or nonconvex programing with equality or inequality constrained problems. The multiobjective nonlinear programing problem is transformed also to a nonlinear autonomous system of differential equations. In fact, the asymptotically stable critical points of the differential system are constrained local Pareto optimal of the original optimization problem. Recently, other results on equality or inequality constrained nonlinear programing problems with fuzzy parameters by using this approach in [2].

In this paper, sensitivity information is obtained by using the idea of the autonomous system of diﬀerential equations corresponding to the vector optimization problem (VOP) (see [1]). These information coincide with the explicit representation of the ﬁrst order partial derivatives of the local solution point and associated Lagrange multi- pliers tothe parametric problem [4]. The problem under consideration is a parametric vector optimization problem, where the parameters in the objective functions and anywhere in the constraints. The fundamental equation corresponding to the problem is described inSection 2. By using the technique of trajectory continuation, [5,6,8], the behavior of the local solution for slight perturbation of the parameters in the neighborhood of their chosen initial values is discussed inSection 3. Finally twoillustrative examples are given inSection 4.

2. Problem formulation. A mathematical programing problem with general perturbation in the objective functions and anywhere in the constraints has the form

(2)

(VOP)v: min

f1(x,v),f2(x,v),...,fm(x,v)

, x∈Rⁿ (2.1)

subject toG(x,v)≤0, whereRⁿis ann-dimensional Euclidean space, fj(x,v), j=1,2,...,m, G(x,v)=

g1(x,v),g2(x,v),...,gr(x,v)T (2.2) possess continuous ﬁrst and second derivatives.

The corresponding problem with scalar objective and equality constrainted [3], can be written in the form

Pk(ε): minfk(x,v) (2.3)

subject to

F(x)∈R^m−1:fj(x,v)+s_j²−εj=0, j=1,2,...,k−1,k+1,...,m,

G(x)∈R^r:gj(x,v)+ξ_i²=0, i=1,2,...,r , (2.4) where

x=

x1,x2,...,xn,s1,s2,...,sk−1,sk+1,...,sm,ξ1,ξ2,...,ξr , ε=

ε1,ε2,...,εk−1,εk+1,...,εm

. (2.5)

Assume that the matricesA1= ∇xF(x)andA2= ∇xG(x)are of full ranks.

From [3], it is well known that the optimal solutionx^∗ofPk(ε)is an eﬃcient solution for the vector optimization problem if one of the following conditions is valid:

(i) x^∗solvesPk(ε)for everyk=1,2,...,m, (ii) x^∗is the unique optimal solution ofPk(ε).

Recently, in [1] problem (2.4) was solved by using diﬀerential equations approach for ﬁxedv=0 and the fundamental equations was

Bx˙+

A^T₁ A^T₂γ1

γ2

= −∇xf_k^T, A1x˙= −F, A2x˙= −G,

(2.6)

whereBis a symmetric nonsingular matrix of order(n+m+r−1)×(n+m+r−1).

From the above autonomous system (2.6), we obtain

˙

x=φ(x)= −PB⁻¹∇f_k^T−P˜ F

G

, (2.7a)

γ1

γ2

=D⁻¹



 F

G

− A1

A2

B⁻¹∇fk



, (2.7b)

whereP=I−P1,

P1=B⁻¹

A^T₁ A^T₂ D⁻¹

A1

A2

, (2.7c)

P˜=B⁻¹ A^T1 A^T2

D⁻¹, (2.7d)

D(x)=

A1B⁻¹A^T₁ A1B⁻¹A^T₂ A2B⁻¹A^T₁ A2B⁻¹A^T₂

(2.7e) is a nonsingular matrix.

(3)

In [1], it was proved that the matrixP(x)is a projection operator which projects any vector inR^n+m−1ontoM(x), where Mis the tangent of the system of constraints atxwhere,

M(x) =

Y∈R^n+m+r−1: A1

A2

y=0

. (2.8)

Alsoit was proved that if

(a) x^∗is a regular point of the constraints,

(b) the second order suﬃciency conditions are satisﬁed atx^∗, (c) there are nodegenerate constraint atx^∗,

then any trajectory starting from a point within some neighborhood of the local minimal pointx^∗converges tox^∗att→ ∞.

3. Sensitivity information. By using the technique of trajectory continuation [5,6, 8], we will discuss the behavior of the local solutionx^∗for slight perturbation of the parameters in the neighborhood of their chosen initial values.

The following existence theorem, which is based on the implicit function theorem [4], holds.

Theoem3.1. Letx^∗be a unique local solution of(VOP)v=0satisfying the assump- tions (a)–(c). Then there exists a continuously diﬀerentiable vector valued functionx(·) deﬁned in some neighborhoodN(v)so thatx(v)=x^∗, wherex(v)is a unique local solution for the problem(VOP)v for anyv∈N(v)satisfying the assumptions (a)–(c).

For anyv∈N(v) the fundamental equations corresponding to(VOP)v have the following form:

Bx˙(v)+

A^T₁ A^T₂γ1

γ2

= −∇xf_k^T, A1x˙(v)= −F, A2x˙(v)= −G,

(3.1)

and consequently,

φ x(v)

=x˙(v)= −B⁻¹

A^T₁ A^T₂γ1

γ2

+∇xf_k^T

. (3.2)

From equation (2.7a) nearx^∗, one can write

φ x(v)

=dx(v) dt ∂φ

x^∗

∂x

x(v)−x^∗

. (3.3)

Proposition 3.2. IfB(x)= ∇²f_k^T+

γ^T₁ γ^T₂_∇²_F(x₎

∇²G(x)

, then ∂φ(x^∗)/∂(x)= −I, that is, the local minimal pointx^∗is asymptotically stable.

(4)

Proof. In fact

∂φ x^∗

∂(x) = ∂

∂x

−B⁻¹ A^T1 A^T2

γ1

γ2

−B⁻¹∇f_k^T

= ∂

∂x

−B⁻¹

A^T₁γ1+A^T₂

−B⁻¹∇f_k^T

= −∂B⁻¹

∂x A^T₁γ1B⁻¹

∇²F_T

γ1−B⁻¹A^T₁∂γ1

∂x−∂B⁻¹

∂x A^T₂γ2

−B⁻¹

∇²G_T

γ2−B⁻¹A^T₂∂γ2

∂x−B⁻¹∇²f_k^T−∂B⁻¹

∂x ∇f_k^T

= −B⁻¹

∇²f_k^T+

γ₁^T γ₂^T∇²F

∇²G

−∂B⁻¹

∂x

∇f_k^T+

A^T₁ A^T₂γ1

γ2

−B⁻¹ A^T1 A^T2







∂γ1

∂x

∂γ2

∂x





.

(3.4)

Diﬀerentiating (2.7b) with respect tox, we get







∂γ1

∂x

∂γ2

∂x





= −D⁻¹







∂

A1B⁻¹A^T₁

∂x γ1+∂

A1B⁻¹A^T₂

∂x γ2

∂

A2B⁻¹A^T₁

∂x γ1+∂

A2B⁻¹A^T₂

∂x γ2





− ∇²F

∇²G

B⁻¹∇fk

− A1

A2

∂B⁻¹

∂x ∇fk+ A1

A2

B⁻¹∇²fk+ ∇F

∇G

= −D⁻¹ γ1 γ2





 ∇²F

∇²G

B⁻¹A^T₁+ A1

A2

∂B⁻¹

∂x A^T₁+ A1

A2

B⁻¹∇²F ∇²F

∇²G

B⁻¹A^T₂+ A1

A2

∂B⁻¹

∂x A^T₂+ A1

A2

B⁻¹∇²G







× ∇²F

∇²G

B⁻¹∇fk− A1

A2

∂B⁻¹

∂x fk+ A1

A2

B⁻¹∇²fk+ ∇F

∇G

= −D⁻¹ A1

A2

B⁻¹

γ1 γ2

∇²F

∇²G

+∇²fk

+D⁻¹

∇²F

∇²G

.

(3.5)

From (3.4) and (3.5), we obtain

∂φ x^∗

∂x =−B⁻¹

∇²f_k^T+

∇²G

−B⁻¹ A^T1 A^T2

−D⁻¹ A1

A2

B⁻¹

γ1 γ2

∇²F

∇²G

+∇²fk

+D⁻¹ ∇F

∇G

(5)

=−B⁻¹

∇²f_k^T+ γ1 γ2

∇²F

∇²G

−

A^T₁ A^T₂ D⁻¹

A1

A2

B⁻¹

∇²G

+∇²fk−B

=−I,

(3.6)

that is,

t→∞limx(t)=x^∗, (3.7)

where the solution nearx^∗ becomesx(t)x^∗+(x(0)−x^∗)e^−t asymptotically stable.

For obtaining sensitivity information for the ﬁrst order estimation of solutions of a parametric optimization problem, we introduce the following system of diﬀerential equations:

Bdx dv +∇v

A^T₁ A^T₂γ1

γ2

= −∇v

∇xf_k^T

, (3.8)

A1

A2

dx dv = −∇v

F G

. (3.9)

Then, one can easily obtain dx(v)

dv = −PB⁻¹

∇v

A^T₁ A^T₂γ1

γ2

+∇v

∇f_k^T

−P∇˜ v

F G

, (3.10)

∇v

γ1

γ2

=D⁻¹

∇v

F G

− A1

A2

B⁻¹

∇v

∇xf_k^T +∇v

A^T₁ A^T₂

γ1

γ2

, (3.11) whereP,B,P˜andDas in (3.4).

After solving(VOP)v, we may wish to answer the following question: if the problem (VOP)v is replaced by(VOP)v, v ∈N(v) what is the new eﬃcient solution of the problem(VOP)v, v∈N(v)without solving it again.

With(x,γ1,γ2)=(x(v),γ1(v),γ2(v))is identically forvnear zerounder the as- sumption of Theorem 3.1 and Proposition 3.2 a ﬁrst order approximation of x(v),γ1(v),γ2(v)

in the neighborhood ofv=0 is given by





 x(v) γ1(v) γ2(v)





=





 x^∗ γ₁^∗ γ₂^∗





+







dx(v) dv

∇v

γ1(v) γ2(v)







∗

v+O v

. (3.12)

Sensitivity information (3.10) and (3.11) minimize the computation efforts needed for finding many efficient solutions for parametric problem(VOP)v, v∈N(v).

4. Illustrative examples. In this section we provide numerical examples to clarify the theory developed in the paper.

(6)

Example4.1(see [4]).

P(v): minimizef (x,v)=x1+v2x2

subject tog(x,v)=x²1+x2²−v1²≤0. (4.1) To illustrate the application of the general equations (3.10) and (3.11) for obtaining sensitivity information for the ﬁrst order estimation of the solution of the parametric optimization problem, we write the following.

ReformulateP(v)with equality constraints in the form P1(v): minimizef (x,v)=x1+v2x2

subject tog(x,v)=x²1+x2²−v1²+s²=0. (4.2) Formulate (3.10) and (3.11) withB= ∇²f^T+γ∇²g, then

B⁻¹= 1 γ





 1

2 0 0

0 1

2 0

0 0 1

2





, D⁻¹= γ 2

x₁²+x₂²+s²,

P∇˜ vg= 1 2

x²₁+x₂²+s²







−2x1v1 0

−2x2v1 0

−2sv1 0





,

−P= 1 v₁²







x²₁−v₁² x1x2 sx1

x1x2 x₂²−v₁² sx2

sx1 sx2 s²−v₁²





,

−PB⁻¹

∇v

∇xf_k^T

=







0 x1x2

2γv1²

0 −x²₁−s² 2γv₁² 0 sx2

2γv₁²





 .

(4.3)

Consequently, we obtain

dx dv





 x1

v1

x1x2

2γv₁² x2

v1 −x²₁−s² 2γv₁² s

v1

sx2

2γv₁²







, (4.4)

dγ dv

−γ

v1 − x2

2v₁²

. (4.5)

Sensitivity information which we obtained in (4.5) coincide completely with the Fiacco’s results in [4, page 106].

(7)

Example4.2.

P(v): minimize(f1(X,v),f2(X,v)) subject toG(X)= (x,y)∈R²:x+y≤1!

,

wheref1(X,v)=x²+y²−v1, f2(X,v)=x²−y²−v2.

(4.6)

Consequently,

P1(ε): minimizef1(X,v)

subject tox+y−v1≤1, x²−y²−v2≤ε2. (4.7)

Start with ﬁrst choiceε=ε2=1 as in [3] and formulateP1(ε)with equality constraints in the form

P1(ε): minimizex²+y²−v1

subject toF(X,v)=f2(X,v)=x²−y²−v2+s²−1=0, G(X)=x+y+ξ²−1=0,

(4.8)

whereX=(x,y,x,ξ). SolveP1(ε)toﬁnd the unperturbed point atv1=0, v2=0. To formulate (3.10) and (3.11), we obtain

B⁻¹=





 1

2(1+γ1) 0 0 0

0 1

2(1+γ1) 0 0

0 0 1

2γ1 0

0 0 0 1

2γ2





 ,

D⁻¹= 1

|D|





 1

1+γ1+2ξ²

γ2 −(x+y) (1+γ1)

−(x+y) (1+γ1)

2

x²+y² (1+γ1) +2s²

γ1





,

P˜= 1

|D|





 1 2(1+γ1)

(x−y) (1+γ1)+4xξ

γ2

1 (1+γ1)

2y(y−x) (1+γ1) +2s²

γ1

1 2(1+γ1)

(y−x) (1+γ1)+4xξ²

γ2

1 2(1+γ1)

2x(x−y) (1+γ1) +2s²

γ1

1 2γ1

2s

(1+γ1)+4sξ² γ²

1

2γ1

−2s(x+y) (1+γ1)

1 2γ2

−2ξ(x+y) (1+γ1)

1

2γ2

4ξ

x²+y² (1+γ1) +4s²ξ

γ1





 .

(4.9)

(8)

Thus, we get

dx dv = −1

|D|







0 − v2

(1+γ1)

y(y−x) (1+γ1) +s²

γ1

0 − v2

(1+γ1)

(x−y) (1+γ1)+s²

γ1

0 − v2

2γ1

−2s(x+y) (1+γ1)

0 −v2

γ2

2ξ

x²+y² 1+γ1 +2s²ξ

γ1







. (4.10)

References

[1] F. M. Ali,Technique for solving multiobjective nonlinear programming using diﬀerential equations approach, J. Inform. Optim. Sci.18(1997), no. 3, 351–357.MR 99a:90167.

Zbl 919.90130.

[2] ,A diﬀerential equation approach to fuzzy non-linear programming problems, Fuzzy Sets and Systems93(1998), no. 1, 57–61.MR 99b:90157. Zbl 919.90143.

[3] V. Chankong and Y. Y. Haimes,Multiobjective Decision Making. [Theory and methodology], North-Holland Series in System Science and Engineering, vol. 8, North-Holland Pub- lishing Co., Amsterdam, 1983.MR 86k:90002. Zbl 622.90002.

[4] A. V. Fiacco,Introduction to Sensitivity and Stability Analysis in Nonlinear Programming, Mathematics in Science and Engineering, vol. 165, Academic Press, Florida, 1983.

MR 85b:90072. Zbl 543.90075.

[5] W. Hahn,Stability of Motion, Translated from the German manuscript by Arne P. Baartz. Die Grundlehren der mathematischen Wissenschaften, vol. 138, Springer-Verlag, New York, 1967.MR 36#6716. Zbl 189.38503.

[6] J. LaSalle and S. Lefschetz, Stability by Liapunov’s Direct Method, with Applications, Mathematics in Science and Engineering, vol. 4, Academic Press, New York, 1961.

MR 24#A2712. Zbl 098.06102.

[7] H. Yamashita,A diﬀerential equation approach to nonlinear programming, Math. Program- ming18(1980), no. 2, 155–168.MR 81k:90090. Zbl 436.90094.

[8] T. Yoshizawa,Stability Theory by Liapunov’s Second Method, Publications of the Mathe- matical Society of Japan, no. 9, The Mathematical Society of Japan, Tokyo, 1966.

MR 34#7896. Zbl 144.10802.

Fatma M. Ali: Department of Mathematics, Faculty of Education, Ain Shams Univer- sity, Roxy, Cairo, Egypt

(9)

Special Issue on Space Dynamics

Call for Papers

Space dynamics is a very general title that can accommodate a long list of activities. This kind of research started with the study of the motion of the stars and the planets back to the origin of astronomy, and nowadays it has a large list of topics. It is possible to make a division in two main categories: astronomy and astrodynamics. By astronomy, we can relate topics that deal with the motion of the planets, natural satellites, comets, and so forth. Many important topics of research nowadays are related to those subjects.

By astrodynamics, we mean topics related to spaceflight dynamics.

It means topics where a satellite, a rocket, or any kind of man-made object is travelling in space governed by the grav- itational forces of celestial bodies and/or forces generated by propulsion systems that are available in those objects. Many topics are related to orbit determination, propagation, and orbital maneuvers related to those spacecrafts. Several other topics that are related to this subject are numerical methods, nonlinear dynamics, chaos, and control.

The main objective of this Special Issue is to publish topics that are under study in one of those lines. The idea is to get the most recent researches and published them in a very short time, so we can give a step in order to help scientists and engineers that work in this field to be aware of actual research. All the published papers have to be peer reviewed, but in a fast and accurate way so that the topics are not outdated by the large speed that the information flows nowadays.

Before submission authors should carefully read over the journal’s Author Guidelines, which are located at http://www .hindawi.com/journals/mpe/guidelines.html. Prospective au- thors should submit an electronic copy of their complete manuscript through the journal Manuscript Tracking Sy- stem at http://mts.hindawi.com/ according to the following timetable:

Manuscript Due July 1, 2009 First Round of Reviews October 1, 2009 Publication Date January 1, 2010

Lead Guest Editor

Antonio F. Bertachini A. Prado,

Instituto Nacional de Pesquisas Espaciais (INPE), São José dos Campos, 12227-010 São Paulo, Brazil; [email protected]

Guest Editors

Maria Cecilia Zanardi,

São Paulo State University (UNESP), Guaratinguetá, 12516-410 São Paulo, Brazil;

[email protected]

Tadashi Yokoyama,

Universidade Estadual Paulista (UNESP), Rio Claro, 13506-900 São Paulo, Brazil;

[email protected]

Silvia Maria Giuliatti Winter,

São Paulo State University (UNESP), Guaratinguetá, 12516-410 São Paulo, Brazil;

[email protected]

Hindawi Publishing Corporation http://www.hindawi.com