I have found that Carthage does little to develop her navy, but the military yards at Qart-hadast are well developed - so there is your chance. After quickly taking it and defending it with a solid garrison, start building ships and blockade their ports, every other one, all the way to Iberia. Make sure you follow those trade routes on the map to get the right ones to maximize the efficiency rather than hitting every port - this also means you have adequate ships for defense in case any enemy fleet is around that you missed.

Due to unit upkeep costs such as elephants, Elite African Infantry, etc. after a few years of blockade, Carthage's finances are in the negative and their possession of the Sahara only hurts them, which means no retraining of beat-up units. With time and troop cycling you can beat them down or better yet, grab Ippone and start training elephants to smash them.