OF AN ITERATIVE PROCEDURE FOR SOLVING THE
OPTIMIZATION PROBLEM INTO AN ELLIPSOID Liljana Stefanovska
Faculty
of Technology and Metallurgy, P.O. Box 580, Skopje, Macedonia Beti
Andonovic
Faculty
of Technology and Metallurgy, P.O. Box 580, Skopje, Macedonia Sonja
GegovskaZajkova
Faculty
of Electrical Engineering, P.O. Box 574, Skopje, Macedonia szajkova@cerera.etf.ukim.edu.mk ABSTRACT.
For solving the problem of optimization in a space limited by an
ellipsoid and a linear goal function, for which the maximum is searched, there
is an iterative procedure suggested. The procedure starts from an interior point
of the ellipsoid and by moving into its interior there is a generated sequence
of points of the contour of the ellipsoid that converges to the optimal solution
(point), where the goal function is of greatest value. 1.
PRELIMINARY OBSERVATION
Let R^{n} is Euclidean ndimensional space where the vector xÎR^{n} is denoted by ^{ }
where
x_{i} (i = 1, ..., n) are scalars. The
inner product of two vectors x,
y Î R^{n} is defined by
and the norm of an arbitrary vector xÎR^{n} is defined by
For
any vector x¹0, there is its unit vector
that can be determined by the
relation
where
. 2. SETTING OF THE OPTIMIZATION PROBLEM We observe the optimization problem of the following type max{c^{T}x
 xÎE} E = {xÎR^{n } x^{T}Ax £ 1} (1) where
c,
xÎR^{n } are vectors, A is a
diagonal matrix of positive elements of an order n´n, that is
where
a_{i} (i = 1, ..., n) are
scalars. Such a defined feasible space determines the interior of an
ndimensional ellipsoid. Not getting more specific, instead of problem (1), we observe the problem of the following type
max{
^{T}x
 xÎE}
E = {xÎR^{n } x^{T}Ax ³
1}
(2) where
is the unit vector and the
inequality x^{T}Ax ³ 1
enables the normal vectors of the tangent plane to ellipsoid to be oriented to
the interior of the ellipsoid (feasible space). The values
of the goal function of the problem (2) and z
= c^{T}x
of the goal function of the problem (1) are connected by the following
relation
3. AN ALGORITHM OF THE METHOD To
solve the optimization problem (2), there is an iterative procedure suggested
for constructing a sequence of feasible solutions {x^{(k)}}
obtained by the
recurrence formula
x^{(k+1)
}= x^{(k)}
+ t^{(k)} d^{(k)},
( k = 0, 1, 2, ... ).
(3) The vector d^{(k)}¹0 determines the feasible movement direction
into the interior of the ellipsoid, and the scalar t^{(k)}¹0
determines the length of the step which is chosen such that the following
solution is on the contour of the feasible area and thereat a real improvement
in the goal function is achieved. That means that the following inequality is
satisfied
^{T}x^{(k+1)}
>
^{T}x^{(k)}.
(4) 3.1.
THE STARTING STEP The
method starts from an interior feasible solution x^{(0)},
i.e.
 x
^{(0)T}Ax^{(0)}
> 1. A starting movement direction is the vector
d^{(0)}
=
,
(5) and
the length of the step t^{(0)}
is chosen by the condition that the next solution x^{(1)
}obtained by
x^{(1)}
= x^{(0)}
+ t^{(0)} d^{(0)}
(6) satisfies the
following equality
x^{(1)
T}Ax^{(1)} = 1, i.e., to be a boundary feasible solution. The graphic review of this coming out on the contour of the feasible space in R^{2} is shown on Figure 1. Figure
1. Indeed,
by choosing the starting movement
direction (5), there is always some small length of the step t^{(0)} >
0, provided by the condition x^{(0)} to be an
interior solution, where for the next solution
x^{(1)}
= x^{(0)}
+ t^{(0)}
the value of the
goal function will be
^{(1)} =
^{T}x^{(1)}
=
^{T} (x^{(0)}
+ t^{(0)}
) =
^{T}x^{(0)
}+ t^{(0)}
^{T}
=
^{T}x^{(0)}
+ t^{(0) } >
^{T}x^{(0)}
=
^{(0)}. Thus, for the next solution x^{(1)} the value of the goal function will increase, which means that a better feasible solution is obtained. 3.2. AN ARBITRARY STEP The further determining of the boundary feasible sequence of solutions x^{(i+1) }= x^{(i)} + t^{(i)} d^{(i)} (i = 1, 2, ... ) (7) continues by choosing an upper movement direction and determining the step length. At any feasible solution x^{(i)} determined by (7) and for which holds
x
^{(i)T}Ax^{(i)} = 1 there
is the vector n^{(i)}ÎR^{n}, that is perpendicular to the
tangent plane of the ellipsoid at the vector x^{(i)} and
directed to the interior of the ellipsoid. Thus,
and
and

^{ (i)} = 1. We give the following Lemma:
The direction
d^{(i)}
=
+
^{(i)}
(9) is a feasible movement direction (Figure 2.), by which the goal function increases its value. Figure 2 Proof: For a length that is small enough t > 0, the next feasible solution is x^{(i+1) }= x^{(i)} + t d^{(i)} = x^{(i)} + t ( + ^{ (i)}) for which it is true x^{(i+1)T}Ax^{(i+1)} = 1 and the value of the goal function
^{(i+1)} =
^{T}x^{(i+1)}
=
^{T}(x^{(i)}
+ t (
+
^{(i)})) =
=
^{T}x^{(i)
}+ t (
^{T}
+
^{T}
^{(i)})
=
^{(i) }+ t (1+
^{T}
^{(i)}) >
^{(i)} achieves a real increasement because

 = 
^{(i)} = 1. To
the sequence of boundary solutions there
is a corresponding sequence of the goal function values { z^{(i)}
}, (i = 0, 1, 2, …) for which it is true z^{(i+1)}
> z^{(i)}. The method ends when the following condition is satisfied
 z^{(i+1) }  z^{(i) }
< e .
(10) for
an arbitrary e > 0. 4. EXAMPLE In R^{2}, let the goal function vector be and the
ellipsoid is defined by the diagonal matrix where e =0.001 is given. Table 1. Results for the initial solution
Table 2. Results for the initial solution
Table 3. Results for the initial solution
The
results presented above show that the optimal solution is
for which the goal function reaches the maximum in the fourth iterative step (i
= 4), and z_{max} = 54.23. REFERENCES [1]
Bandi, B.,
Metodì optimizacii, Vvodnìi
kurs,
Izd. Radio i svyazy, Moskva, 1988 [2]
Chang, Y. S., The Steepest Descent Gravitational Method for Linear Programming,
Discrete Applied Mathematics 25, (1989) 211239 [3]
Garvin, W. W., Introduction to Linear Programming, Mc GrawHill Book Company, Inc,
1960 [4] Karcicka,
L. D., Teorija i metodi na linearnoto
programirane, Univerzitet ”Kiril i Metodij”,
Skopje, 1987 [5]
Zlobec, S., Petric, J., Nelinearno programiranje, Naucna knjiga, Beograd, 1989 [6]
Vujcic, V., Asic;, M., Milicic, N., Matematicko
programiranje, Matematicki institut, Beograd, Savremena racunska
tehnika i njena primena, Knjiga 7, 1980
