Dans cet exposé, on s’intéresse à l’adaptation d’algorithmes classiques pour la programmation linéaire à des formulations plus complexes. Dans une première partie, on montrera comment les algorithmes de type Newton, une brique de base des algorithmes de points intérieurs, s’adapte aux problèmes non convexes dont le paysage d’optimisation est dit “bénin”. Ce genre de formulation apparaît notamment dans les problèmes de reconstruction de phase, et plus globalement dans les formulations factorisées, dont on donnera divers exemples. Dans une seconde partie, on s’intéressera aux programmes linéaires en transport optimal, et à leurs variantes déséquilibrées. Afin de résoudre efficacement et exactement ces problèmes, on proposera une méthode inspirée de l’algorithme du simplexe réseau, possédant à la fois des garanties théoriques et une performance encourageante en pratique.