$ d $ is ascent direction iff $ (\nabla\theta(w))^t d > 0 $

20 Views Asked by At

I have a doubt in this exercise.

Let be $ \theta: R^n \rightarrow R $ a concave function differentiable at $w$. $ d $ is a ascent direction of $ \theta $ i.e. exists $ \delta > 0 $ such that \begin{equation} \theta(w+\lambda d) > \theta(w) \quad \forall \lambda \in (0.\delta) \end{equation}

if and only if $ (\nabla\theta(w))^t d > 0 $

This is my try.

As $ \theta $ is differentiable at $ w $ then $$ \theta(w+\lambda d) = \theta(w) + (\nabla\theta(w))^t (\lambda d) + r(\lambda d) $$

where $ \lim_{\lambda \rightarrow 0 } \frac{r(\lambda d)}{|\lambda|} = 0 $

As $ \theta(w+\lambda d) > \theta(w) $ then $$ (\nabla\theta(w))^t (\lambda d) + r(\lambda d) > 0 $$

As $ \lambda \in (0,\delta) $ we can divide by $ \lambda $ the last expression $$ (\nabla\theta(w))^t d + \frac{r(\lambda d)}{\lambda} > 0 $$

Making $ \lambda \downarrow 0 $ we hace $$ (\nabla\theta(w))^t d \geq 0 $$

As you can see I have the option $ (\nabla\theta(w))^t d = 0 $. How can I prove that $ (\nabla\theta(w))^t d > 0 $?

1

There are 1 best solutions below

0
On BEST ANSWER

You haven't used concavity yet. Concavity implies that $$\theta(w+\lambda d)-\theta(w)\le (\nabla \theta(w))^t \lambda d \tag{1}$$ (Geometrically, the graph of function lies below its tangent plane). Since the left hand side of (1) is positive for some $\lambda>0$, the conclusion $(\nabla \theta(w))^t d>0$ follows.

By the way, this is essentially a one-dimensional problem: you could consider the function $\psi(\lambda)=\theta(w+\lambda d)$, which is concave, and argue as above that $\psi'(0)>0$.