Microlenses are highly attractive for optical applications such as super resolution and photonic nanojets, but their design is more demanding than the one of larger lenses because resonance effects play an important role, which forces one to perform a full wave analysis. Although mostly spherical microlenses were studied in the past, they may have various shapes and their optimization is highly demanding, especially, when the shape is described with many parameters. We first outline a very powerful mathematical tool: shape optimization based on shape gradient computations. This procedure may be applied with much less numerical cost than traditional optimizers, especially when the number of parameters describing the shape goes to infinity. In order to demonstrate the concept, we optimize microlenses using shape optimization starting from more or less reasonable elliptical and semi-circular shapes. We show that strong increases of the performance of the lenses may be obtained for any reasonable value of the refraction index.