This paper considers the problem of optimizing robot navigation with respect to a time-varying objective encoded into a navigation density function. We are interested in designing state feedback control laws that lead to an almost everywhere stabilization of the closed-loop system to an equilibrium point while navigating a region optimally and safely (that is, the transient leading to the final equilibrium point is optimal and satisfies safety constraints). Though this problem has been studied in literature within many different communities, it still remains a challenging non-convex control problem. In our approach, under certain assumptions on the time-varying navigation density, we use Koopman and Perron-Frobenius Operator theoretic tools to transform the problem into a convex one in infinite dimensional decision variables. In particular, the cost function and the safety constraints in the transformed formulation become linear in these functional variables. Finally, we present some numerical examples to illustrate our approach, as well as discuss the current limitations and future extensions of our framework to accommodate a wider range of robotics applications.