optimisation en nombres entiers

Soit $x_1\geq ...\geq x_n\geq 0$ tels que $x_1+\cdots+x_N=K$ entier $<N$. J'ai besoin de minimiser
$$(n_1,\ldots,n_N)\mapsto (x_1-n_1)^2+\cdots+(x_N-n_N)^2$$ quand $(n_1,\ldots,n_N)$ est une suite d'entiers $\geq 0$ de somme $K.$ Est ce que quelqu'un du forum sait comment faire? M\^eme une solution approchée serait utile. Merci.

Réponses

  • Bonjour.

    La solution est évidente : $x_i=n_i$.

    Ou alors tu t'es trompé dans l'énoncé.

    Cordialement.
  • Non non pas d'erreur mon cher Gérard. Les $x_i$ sont fixés, les $n_i$ sont des entiers variables, d'o\`u le titre. On peut imaginer un b\^aton de longueur $K$ cassé en N segments $x_1\geq \ldots\geq x_N$ et un diagramme de Young correspondant \`a la partition de $K$ qui approche bien les segments...
  • Bonjour,

    Un des algorithmes possibles est par exemple l'algorithme "branch and bound".
    J'en connaissais un autre mais je n'arrive pas à m'en souvenir, n'étant pas spécialiste de la question.

    Amicalement,
  • J'ai posé la question suivante en Analyse hier et cela a fait un flop. Avec la permission des modérateurs je la repose ici: peut-\^etre les arithméticiens s'y intéresseront-ils.

    Soit $x_1\geq ...\geq x_n\geq 0$ tels que $x_1+\cdots+x_N=K$ entier. J'ai besoin de minimiser
    $$(n_1,\ldots,n_N)\mapsto (x_1-n_1)^2+\cdots+(x_N-n_N)^2$$ quand $(n_1,\ldots,n_N)$ décrit les suites d'entiers $\geq 0$ de somme $K.$ Est ce que quelqu'un du forum sait comment faire? On peut voir les $x_i$ comme les restes d'un b\^aton de longueur $K$ brisé en $N$ morceaux, et $(n_1,\ldots,n_N)$ comme une partition de l'entier $K$. Pas inintéressant de représenter cette partition optimisante comme un tableau de Young.

    [Restons dans la discussion initiale. Il suffisait de demander le transfert en "Arithmétique". AD]
  • Hello,

    Deja je commencerais par prendre les parties entière des $x_i$. La somme fera $K'$, ensuite
    je cherche parmis les parties de $1..N$ contenant $K-K'$ éléments et pour ces
    indexes $i$ au lieu de prendre la partie entiere de $x_i$ je prend la partie entiere $+1$. Cette fois
    pour chaque combinaison la somme fera bien $K$. Ca fait encore beaucoup de combinaisons a tester, mais
    en cherchant en priorité ces combinaisons parmis les indexes pour lesquels $[x_i]+1 -x_i$ soit le plus petit
    possible on devrait limiter les combinaisons a tester...

    a+

    eric
  • Ok,

    j'ai compris. Il faut dire que tu ne précises pas ce que" sont les $x_i$ et comme tu parlais d'entiers, je les ai considérés comme entiers eux aussi.

    Bonne chance.
  • Merci Kuja pour m'aiguiller vers Branch and Bound, qui semble un monde. Merci Eric pour ton algorithme débrouillard que je vais proposer \`a mes clients. Amicalement.
Connectez-vous ou Inscrivez-vous pour répondre.