Por que a não-convexidade deve ser um problema na otimização?

Fiquei muito surpreso quando comecei a ler algo sobre otimização não convexa em geral e vi declarações como esta: Muitos problemas práticos de importância são não convexos e a maioria dos problemas não convexos são difíceis (se não impossíveis) de resolver exatamente em um tempo razoável. (...