Comment implémenter un package d'optimisation convexe?

Question

Je réalise entièrement que les paquets d'optimisation convexe, comme les paquets d'algèbre linéaire, devraient être des choses que vous utilisez, et non pas implémentées. Cependant, à des fins purement éducatives - y at-il une bonne ressource - lien/livre sur la façon de mettre en œuvre un paquet d'optimisation convexe? (comme pour les programmes quadratiques avec des contraintes quadratiques?)

Merci!

Answer 1

Tout bon manuel sur l'optimisation convexe aurait des choses que vous recherchez. Une telle ressource gratuite, mais géniale est ici: CO Book. Notez que, comme vous le mentionnez correctement, la mise en œuvre des algorithmes mentionnés dans ce livre nécessitera certainement des bibliothèques d'algèbre linéaire, que vous pouvez ou non choisir de mettre en œuvre.

Answer 2

Il ya un article pertinent dans Optima, un bulletin d'information du mathematical optimization society appelé "Développement rapide d'un solveur Minlp open-source avec COIN-OU". Il décrit la construction d'un solveur non linéaire en utilisant certains des paquets coin-or. La plupart des pièces ou des choses sont écrites en C++.

Pour python, vous pouvez utiliser la structure de données d'algèbre linéaire et les algorithmes disponibles dans numpy. Le package scipy associé a des optimiseurs non linéaires mais rien de spécifique pour l'optimisation convexe. Et enfin, vous pouvez regarder l'optimiseur convexe basé sur python de la GPL de Boyd cvxopt pour avoir une idée du genre de tâche que vous avez devant vous.

Answer 3

Cela dépend de ce que vous allez, mais vous devriez aller au prof. en optimisation des mathématiques dans votre université dans laquelle vous êtes en ce moment ou que vous avez obtenu un diplôme et vous devriez lui demander directement.

J'ai implémenté des solveurs pour plusieurs problèmes réduits à l'optimisation convexe (http://cs229.stanford.edu/proj2017/) - cvx4ml qui fonctionne plus vite qu'une solution similaire de SkLearn, et j'ai passé un examen de 24 heures à Stephen Boyd, donc je peux donner ce que tu peux faire et décrire votre plan très rude:

Alors vous allez créer votre propre paquet que je vais écrire étape par étape instruction:

1. vous devez créer la bibliothèque pour travailler avec matrice dense/vecteurs
2. vous devriez créer une bibliothèque pour travailler avec des matrices/vecteurs clairsemés
3. Mettre en oeuvre environ 20 algorithmes différents pour résoudre le système d'équations linéaires (car dépend de la situation dont vous aurez besoin différents d'entre eux)
4. introduisent des concepts comment décrire les contraintes, le domaine de la fonction, etc dans votre langage de programmation ou votre système que vous avez créé.
5. Mettre en œuvre plusieurs normes et évaluation de deux normes, certaines techniques de factorisation comme LU, Cholesky.

6. Mettre en œuvre un solveur conique simple personnalisé pour un cône orthont négatif. Et cela dépend de ce que vous allez faire. 6.a - résolveur d'écriture basé sur la méthode du point intérieur. 6.b - résolveur d'écriture avec support optimisation répartie 6.c - solveur d'écriture basé sur une méthode de sous-gradient projetée.

7. améliorer pour soutenir d'autres cônes

8. solveur vous amélioré à l'étape "5"

Et si vous voulez être au niveau de CVXPY puis

9. Implémenter l'analyse de description de programme comme CVXPY et transformer le problème en forme conique.

p.s. Si vous vous sentez négligé avec certains de ces sujets, alors:

• Lecture algébrique linéaire livre qui a écrit prof. de votre université

• Regardez dans le youtube dans EE263 avec S.Boyd, EE364A avec S.Boyd, EE364B avec S.Boyd.