To complement Christian Clason's comment: there is usually no need to compute geodesics to optimize over manifolds directly. The usual replacement used for optimization purposes is called a retraction. A retraction is an approximation of the exponential map (which generates geodesics), accurate up to first order. For various manifolds of practical interest, computationally inexpensive retractions are known. For example, for the sphere, retracting the tangent vector $u$ at $x$ is often done as $R_x(u) = \frac{x+u}{\|x+u\|_2}$. For $u$ small, this agrees with the exponential of $u$ at $x$ up to first order.

To complement Christian Clason's comment: there is usually no need to compute geodesics to optimize over manifolds directly. The usual replacement used for optimization purposes is called a retraction. A retraction is an approximation of the exponential map (which generates geodesics), accurate up to first order. For various manifolds of practical interest, computationally inexpensive retractions are known. For example, for the sphere, retracting the tangent vector $u$ at $x$ is often done as $R_x(u) = \frac{x+u}{\|x+u\|_2}$. For $u$ small, this agrees with the exponential of $u$ at $x$ up to first order.

Edit: in addition to Absil et al.'s excellent book, you may also find my introduction to optimization on manifolds helpful: http://www.nicolasboumal.net/book.