Solutions intermédiaires aux programmes linéaires

Il y a un programme linéaire pour lequel je veux non seulement une solution mais une solution aussi centrale que possible sur la face du polytope qui assume la valeur minimale.

A priori, nous nous attendons à ce que la face minimisante soit de grande dimension pour diverses raisons, notamment que la fonction objectif minimisée soit le maximum de nombreuses contraintes:

Minimisez sous avec linear et pour tout et . $\epsilon$ $f_i(\bar x) \leq \epsilon < 0$ $f_i$ $x_i > 0$ $i$ $\sum_i x_i = 1$

Bien entendu, nous n'obtiendrions jamais de propriété de type centralité dans l'algorithme simplex. Est-ce que certains des algorithmes de point intérieurs habituels présentent de telles propriétés? Y a-t-il même une garantie qu'ils éviteront les sommets ou les faces de dimension inférieure autant que possible?

En fait, je suis probablement satisfait d'un programme quadratique facile qui trouve le milieu de tout le polytope car la centralité importe plus que la minimalité, juste vaguement curieux si d'autres algorithmes de programmation linéaire offrent des propriétés pertinentes.

Mise à jour: j'ai réduit le problème sous-jacent à un simple problème de minimisation contraint résolu avec les multiplicateurs de Lagrange, mais la question ci-dessus reste intéressante de toute façon.

ds.algorithms linear-algebra linear-programming Jeff Burdges
la source

pas exactement votre question mais: calculer le centroïde est # P-difficile; je ne sais pas quelle est la meilleure approximation, mais pour certaines applications, mettre le polytope en position isotrope et prendre la moyenne d'échantillons uniformes polynomialement du polytope (transformé) suffit. voir ces notes, Lemme 15 par exemple: cc.gatech.edu/~vempala/acg/notes.pdf

Sasho Nikolov

est-ce plus une question théorique ou plus pratique? il serait peut-être possible de générer tous les sommets de la face optimale, puis d'utiliser une combinaison convexe appropriée d'entre eux.

anonyme

Réponses:

J'ai quelques observations trop longues pour des commentaires. Voici un résumé.

Tout algorithme pour résoudre exactement votre problème peut être utilisé pour résoudre des programmes linéaires exactement (c.-à-d., "Une programmation linéaire forte", qui est utilisée dans la solution de Sariel, et qui n'a actuellement pas d'algorithme polynomial temporel).
Le suivi naturel est de savoir si des solutions approximatives (c'est-à-dire une "programmation linéaire faible") peuvent fournir une solution. Bien que la réponse soit oui, il semble que la condition d'arrêt de cette procédure nécessite des quantités qui, à ma connaissance, ne peuvent pas être calculées en temps polynomial. (c.-à-d. que l'algorithme trouve quelque chose de bien, mais certifier cela est difficile.) Ma principale suggestion ici est de faire une définition significative d'une « solution optimale » pour votre problème, auquel cas cette approche est traitable. (Cette stratégie jette efficacement les minuscules faces du polyèdre.) $\epsilon$

En général, tout en réfléchissant à votre énoncé actuel de votre problème, j'ai continué à me heurter à des considérations d'efficacité. Mais il y a une intuition raisonnable à cela: les objets que nous jetons autour - sommets, visages, etc. - sont discrets et exponentiellement abondants.

(1.) Supposons que nous ayons un algorithme qui résout exactement votre problème. Notez que tout point exposé d'une face contenant le point milieu fourni sera une solution exacte au programme linéaire d'origine. Procédez comme suit. Ajoutez une nouvelle contrainte linéaire en disant que la valeur d'objectif d'origine doit être égale à la valeur optimale (que nous connaissons maintenant), et définissez un nouvel énoncé d'objectif pour maximiser la première coordonnée de la solution. Répétez cette procédure une fois pour chaque dimension, en ajoutant chaque fois une contrainte et en choisissant une nouvelle coordonnée à maximiser. Ce processus réduira à chaque fois la dimension de la solution; nécessairement, lorsque le processus se termine, nous avons un ensemble affine à 0 dimension, ce qui signifie un seul point. Ainsi avec $\mathcal O(d)$ itérations de votre algorithme de résolution médiane (et en augmentant seulement la description du problème d'un montant polynomial en chaque fois), une forte programmation linéaire est résolue. Cela montre que bien que la solution de Sariel nécessite une programmation linéaire forte, une solution exacte à votre question ne peut pas l'éviter. ( Edit : notez que ma preuve suppose un polyèdre compact (un polytope) en entrée; sinon il faut travailler un peu plus pour trouver des sommets.) $d$

(2.) Voici un schéma itératif, utilisant un solveur convexe complet à chaque itération, dont les solutions convergeront vers une notion légère de solution médiane. Choisissez une séquence positive mais décroissante de paramètres de pénalité ; il est raisonnable de les faire descendre géométriquement, c'est-à-dire . Maintenant, pour chaque , minimisez approximativement la fonction convexe $\{\lambda_i\}_{i=1}^\infty\downarrow 0$ $\lambda_i = 2^{-i}$ $i$

⟨ c, x ⟩ - λ_{i} \sum_{j = 1}^{m} \ln (⟨ a_{j}, x ⟩ - b),

$\langle c,x\rangle - \lambda_i\sum_{j=1}^m \ln(\langle a_j,x\rangle - b),$

$\langle c,x\rangle$ $j$ $m$ $\lambda_i$ $\tau$ $\lambda_i$ diminue, l'objectif linéaire d'origine finira par dominer certaines barrières capricieuses qui vous empêchaient du visage approprié, mais n'affectera pas les barrières vous empêchant d'autres limites, en particulier celles de la face cible.

$\lambda$ $\lambda$

Toutes les conditions d'arrêt que j'ai pu trouver ont eu ce genre de difficultés de calcul. (De plus, beaucoup pourraient à nouveau être utilisés pour en faire un solveur de programmation linéaire puissant.)

$\epsilon$ $\lambda$ $\tau$ $\epsilon$

(Quelques commentaires finaux.) Il semble que la notion de «point médian» soit cruciale; Le commentaire de Sasho souligne que le centroïde (centre de masse?) Est un problème extrêmement difficile, alors que trouver, disons, la plus grande boule inscrite est facile. Les barrières logarithmiques que j'ai suggérées ci-dessus ne seront en général cohérentes avec aucune de ces notions médianes. En revanche, pour les barrières et la balle, vous pouvez dériver une limite inférieure sur la distance de votre centre de gravité à la limite relative du visage; peut-être que cela vous est plus utile?

Enfin, d'après votre description, je pense que vous vouliez dire que le "visage cible" devait avoir une dimension aussi élevée que possible? Ceci est bien défini, mais il existe également des faces de solution pour toutes les petites dimensions possibles. Quoi qu'il en soit, l'approche de Sariel et l'approche barrière ci-dessus fonctionneront avec le visage de la plus grande dimension.

matus
la source

\sum_{i} f_{i} (x)^{2} + \sum_{j} x_{j}^{2}

$\sum_i f_i(x)^2 + \sum_j x_j^2$

\sum_{j} x_{j} = 1

$\sum_j x_j = 1$

x

$x$

ϵ

$\epsilon$

ϵ

$\epsilon$ minimisé pour aider les contraintes à évoluer plus rapidement. Merci quand même! :)

Jeff Burdges

x

$x$

Je ne comprends pas la notion de "programmation linéaire forte" et je n'ai jamais entendu cette expression auparavant. on ne sait pas comment résoudre un LP en temps polynomial fort. mais la résolution d'un LP en polynôme temporel dans la description d'entrée (c'est-à-dire le temps polynomial faible) est bien sûr bien connue. si l'OP veut un algorithme fonctionnant en temps polynomial faible, alors la solution de Sariel + un algorithme de point intérieur poly-temps fera l'affaire, non?

Sasho Nikolov

τ

$\tau$

τ

$\tau$

@SashoNikolov, maintenant que j'y pense, la même notion d'optimalité (avec les mêmes problèmes) peut être intégrée dans la solution de Sariel, par exemple en traitant les contraintes qui sont dans une petite tolérance pour être réellement serrées, et en ajustant cette valeur de manière appropriée. Je mettrai à jour ma solution ce soir.

matus

Trouvez d'abord la solution optimale, puis ajoutez la contrainte linéaire selon laquelle la solution doit avoir une valeur égale à l'optimale souhaitée, et reformulez votre LP comme étant celle qui recherche la plus grosse boule à l'intérieur de la région réalisable. Résolvez ce LP modifié, et vous avez ce que vous voulez.

Pourquoi le deuxième problème peut être résolu en utilisant LP est un problème mignon stnadard en géométrie computationnelle ...

==============

$h \equiv cx = \alpha$ $\min c x$ était la fonction cible LP d'origine). Si est la région réalisable du LP d'origine, nous recherchons la plus grosse boule en . À cette fin, nous devons calculer le plus petit sous-espace affine dimensionnel contenant cet ensemble. Une fois que vous avez trouvé ce sous-espace, changez les variables pour ne considérer que cette sous-surface affine. Maintenant, votre polytope est entièrement dimenisonal, et vous pouvez utiliser le deuxième LP comme je l'ai décrit ci-dessus. $P$ $P \cap h$

Soit donc le sommet calculé par le premier LP. Considérant tous les sommets voisins de . Considérez le sous-espace affine de avec tous ses voisins qui ont la même valeur cible (c'est-à-dire, ). Il n'est pas difficile de voir que ce sous-espace affine est le sous-espace souhaité. $v$ $v$ $v$ $\alpha$

Donc, pour résumer: (A) résoudre LP pour découvrir la valeur optimale. (B) Calculer le plus petit sous-espace dimensionnel contenant la solution réalisable avec la valeur optimale. (C) Réécrivez le LP d'origine dans ce sous-espace affine (c'est-à-dire en supprimant toutes les dimensions non pertinentes), ajoutez une variable et transformez-la en LP pour trouver la plus grosse boule à l'intérieur de ce polytope.

Sariel Har-Peled
la source

Qu'entend-on par "plus grosse boule" dans un polyèdre qui n'est pas de pleine dimension?

Kristoffer Arnsfelt Hansen

@KristofferArnsfeltHansen le polyèdre est sûrement un ensemble convexe situé dans un sous-espace affine d'une certaine dimension.

Sasho Nikolov

pour que cela fonctionne, vous devez spécifier une contrainte vous limitant aux faces que vous avez trouvées à la première étape. Vous devez également savoir que la solution était constante sur ce visage (un relâchement probablement complémentaire le révélerait)

Suresh Venkat

Existe-t-il un moyen de faire les étapes après l'optimisation initiale en temps polynomial? Tel qu'il est écrit, il semble nécessiter la prise en compte de tous les sommets de la face cible, dont il peut y en avoir de manière exponentielle.

matus

d

$d$

v

$v$