More and more businesses are deploying their application(s) with different cloud providers which are close to their customers in order to provide better Quality of Service (QoS) to their end customers. In this work, an optimized and secure software-defined overlay network is proposed as an efficient mechanism to interconnect these geographically-dispersed applications compared to using only plain IP routing. A logically centralized Cognitive Routing Engine (CRE), based on Random Neural Networks with Reinforcement Learning, was developed to find with minimal monitoring overhead the optimal overlay paths when the public Internet is used as the communication means between the overlay nodes. CRE was evaluated by using an overlay network composed of hosts from 5 different public clouds where it was shown that the latency of CRE paths is most of the time within 5% of the latency of the optimal IP paths. Furthermore, it was also demonstrated that CRE is able to do asymmetric path optimization where the forward path is different from the reverse path for a given data centre pair in order to further improve QoS.