Logiciel pour résoudre des programmes semi-définis

marque

Logiciel pour résoudre des programmes semi-définis


Je cherche un logiciel pour résoudre un programme semi-défini particulier.

Les contraintes sont spécifiées comme un ensemble de contraintes linéaires sur les produits par paires des composants d’un vecteur (x i ) i ∈ ℝ n :

Formulaire de programme semi-défini

J’espère trouver un logiciel qui accepte le problème dans ce format. Je sais qu’il existe d’autres façons d’exprimer les SDP, mais j’espère éviter d’écrire un programme pour traduire entre les formats.

Gilles

Pour quel système d’exploitation en avez-vous besoin? Quelle est votre contrainte de prix?

Yuval Filmus

@Gilles Merci d’avoir supprimé ma réponse. Permettez-moi de le résumer. Tout solveur SDP peut résoudre le programme qui intéresse le PO, tel quel. Ce n’est pas un programme semi-défini « particulier », mais plutôt la forme normale standard d’un SDP. La seule différence est que le solveur SDP trouve une matrice PSD, et pour obtenir les vecteurs $ x ^ i $, vous avez besoin d’une étape supplémentaire de décomposition de Cholesky à la fin.

Yuval Filmus

Je ne suis pas sûr non plus que ce soit le bon site pour répondre à la question, étant donné la réponse apparente.

Franck Dernoncourt

Avez-vous regardé les programmes d’optimisation habituels comme CPLEX ou GUROBI?

Réponses


 Yuval Filmus

Votre programme semi-défini est déjà sous forme standard. Ce que vous décrivez est connu sous le nom de programme vectoriel . Les programmes vectoriels sont équivalents aux programmes semi-définis. Si au lieu de x i · x j vous écrivez X i , j et ajoutez la condition que X soit semi-défini positif, alors les deux programmes sont équivalents. Par conséquent, vous pouvez utiliser n’importe quel solveur SDP pour résoudre votre programme. Étant donné la matrice semi-définie positive X , vous pouvez trouver des vecteurs x i tels que x i · x j = X i , j en utilisant la décomposition de Cholesky , qui est facilement disponible dans de nombreuses bibliothèques et logiciels mathématiques, et pourrait même être pris en charge par certains solveurs SDP.

marque

J’ai un gros fichier texte avec des variables $ x ^ i $ comme je l’ai dit. Les contraintes sont écrites sous cette forme. Parfois, ils apparaissent comme ceci $ (x_1 + x_2) x_3 <= 0 $ Ce que je recherche est un programme qui acceptera mon énoncé de problème avec des changements minimes, sinon je devrai réécrire le problème comme vous le dites, en recherchant des instances de $ x_i x_j $ et en remplaçant $ X_ {ij} $

Yuval Filmus

Les solveurs SDP n’acceptent généralement pas les entrées de cette manière, voir par exemple ce format commun: plato.asu.edu/ftp/sdpa_format.txt . Vous auriez donc le même problème même si votre programme était défini en termes de Xij .

 

#pour, des, Logiciel, Programmes, résoudre, semi-définis

 

wiki

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *