Information Technology Reference
In-Depth Information
Gradient descent is a popular optimization method that finds a local minimum
of a function by successively taking steps proportional to the negative of the gradi-
ent of the cost function. Gradient descent is also known as steepest descent, or the
method of steepest descent. Gradient descent is based on the observation that if the
real-valued function
f
(
x
) is defined and differentiable in a neighborhood of a point
a
,then
f
(
x
) decreases fastest if one goes from
a
in the direction of the negative gra-
dient of
f
at
a
, it follows that, if
b
=
a
−
α∇
f
(
a
) for
α
>
0 a small enough number,
then
f
(
a
)
f
(
b
). The algorithm starts with a guess
x
0
for a local minimum of
f
,
and constructs the sequence
x
0
,
x
1
,
x
2
,... such that
≥
x
k
+1
=
x
k
−
α
k
∇
f
(
x
k
)
,
k
≥
0
.
(14.16)
We h ave
f
(
x
0
)
≥
f
(
x
1
)
≥
f
(
x
2
)
≥...
(14.17)
According to the Armijo rule, the sequence converges to the desired local minimum
if the cost improvement obtained at each iteration is sufficiently large. The value of
the step size
is allowed to change at every iteration.
For constrained optimization problems, gradient descent may not yield a feasible
point at each iteration (
i.e.
,
x
k
+1
is not guaranteed to satisfy the constraints). In this
case, the gradient projection method can be used to ensure that each
x
k
is feasible.
The simplest gradient projection method determines a feasible direction method of
the form
α
x
k
+1
=
x
k
+
α
k
(
x
k
−
x
k
)
,
(14.18)
where
f
(
x
k
)]
+
x
k
=[
x
k
−
.
s
k
∇
(14.19)
]
+
.
α
k
∈
,
Here, [
1] is a step size, and
s
k
is a
positive scalar. Thus, to obtain the vector
x
k
, we take a step
denotes projection on the set
X
,
(0
f
(
x
k
) along the
negative gradient, as in steepest descent. We then project the result
x
k
−
−
s
k
∇
f
(
x
k
) on
X
, thereby obtaining the feasible vector
x
k
. Finally, we take a step along the feasible
direction
x
k
−
s
k
∇
α
k
.
The gradient projection method can be applied to the control of redundant robots
(see,
e.g.
, [15]). In this case, constraints on robot motion are described by a cost
function. The gradient of the cost function can be considered as an artificial force,
pushing the robot away from the undesirable configurations. At each iteration, an
artificial force
g
(
q
) is induced by the cost function at the current position. The gra-
dient of this function, projected onto the null space of the main task Jacobian, is
used to produce the motion necessary to minimize the specified cost function as far
as possible.
The main advantage of this method is that the constraint avoidance process has no
effect on the main task. This can be understood as follows [12]. A square matrix
M
is
called an orthogonal projection if its mapping
Mx
of
x
is perpendicular to
x
x
k
using the step size
−
Mx
for
any
x
. It is noteworthy that
JJ
+
,
J
+
J
,
I
JJ
+
,
I
J
+
J
are all orthogonal projections.
−
−
We denote the range space of
J
+
by
(
J
+
), and the range space of
I
J
+
J
by
R
−
R
(
I
−
J
+
J
). We denote the null space of
J
by
N
(
J
), and the orthogonal complements of
Search WWH ::
Custom Search