Search-09b : Minima fallacieux — le paysage de la relaxation SDP factorisée

Navigation : << Search-2c (QuikGraph) | ↑ Série Search | Partie 2 : CSP →

Question centrale. Search-9 a relaxé un problème combinatoire vers un programme linéaire — relaxation convexe, résolue exactement. Ici on fait un pas de plus, et un pas de côté : la relaxation semidéfinie de MaxCut est convexe, mais les solveurs à grande échelle ne la résolvent pas telle quelle — ils la factorisent \(Y = XX^T\) en une variable \(X \in \mathbb{R}^{n \times r}\) de rang borné, et le problème devient non convexe. La question de ce notebook : quand ce paysage non convexe piège-t-il la recherche locale dans des minima fallacieux — des points stationnaires sous-optimaux — et quand est-il prouvablement sûr ?

C’est le point d’arrivée « certification » du fil paysages : MGS-15 (série .NET de la Partie 4) mesurait les paysages de fonctions par corrélation fitness-distance ; ici on interroge un paysage dont la théorie garantit — au-dessus d’un seuil de rang — qu’il ne possède aucun piège. Pilote « calculatoire borné » de l’EPIC #13106 (digestion et canonicalisation des mathématiques assistées) : chaque affirmation est mesurée sur des instances exhaustivement énumérables, avec référence exacte par vrai solveur conique.

A. Le problème et sa relaxation

Soit \(W\) une matrice de poids symétrique à diagonale nulle (un graphe pondéré). MaxCut cherche la bipartition \(s \in \{\pm 1\}^n\) maximisant

\[\mathrm{cut}(s) = \frac{1}{2} \sum_{i<j} W_{ij}\,(1 - s_i s_j).\]

La relaxation de Goemans–Williamson remplace chaque \(s_i s_j\) par un produit scalaire \(\langle y_i, y_j \rangle\) de vecteurs unité — c’est-à-dire \(Y = XX^T\) avec \(\mathrm{diag}(Y) = 1\) — et lève l’exigence de rang :

\[\text{(SDP)} \quad \max_Y \ \tfrac{1}{2}\sum_{i<j} W_{ij}(1 - Y_{ij}) \quad \text{s.c.} \quad \mathrm{diag}(Y)=1, \ Y \succeq 0.\]

Le problème (SDP) est convexe : sa valeur \(p^*\) est calculable exactement (cône semidéfini, solveur conique). C’est la référence de tout ce qui suit.

import itertools
import numpy as np
import cvxpy as cp

def instance_cycle6():
    n = 6
    W = np.zeros((n, n))
    for i in range(n):
        W[i, (i + 1) % n] = W[(i + 1) % n, i] = 1.0
    return "C6 (cycle pair, biparti)", W

def instance_k8():
    n = 8
    rng = np.random.default_rng(42)
    Wr = rng.uniform(0.1, 1.0, (n, n))
    W = np.triu(Wr, 1) + np.triu(Wr, 1).T
    return "K8 poids uniformes seed 42", W

def instance_g10():
    n = 10
    rng = np.random.default_rng(7)
    A = (rng.random((n, n)) < 0.5).astype(float)
    W = np.triu(A, 1) + np.triu(A, 1).T
    return "G(10, 0.5) seed 7", W

INSTANCES = [instance_cycle6(), instance_k8(), instance_g10()]
for name, W in INSTANCES:
    aretes = int(np.count_nonzero(np.triu(W)))
    print(f"{name:32s} n={len(W):2d}  aretes={aretes:2d}  poids total={np.triu(W).sum():7.3f}")
C6 (cycle pair, biparti)         n= 6  aretes= 6  poids total=  6.000
K8 poids uniformes seed 42       n= 8  aretes=28  poids total= 18.130
G(10, 0.5) seed 7                n=10  aretes=19  poids total= 19.000
def maxcut_brut(W):
    n = len(W)
    meilleur = -np.inf
    for bits in itertools.product([-1, 1], repeat=n - 1):
        s = np.array([1] + list(bits))
        v = 0.5 * sum(W[i, j] * (1 - s[i] * s[j])
                      for i in range(n) for j in range(i + 1, n))
        if v > meilleur:
            meilleur = v
    return meilleur

def sdp_maxcut(W):
    n = len(W)
    Y = cp.Variable((n, n), PSD=True)
    obj = cp.Maximize(0.25 * cp.sum(cp.multiply(W, 1 - Y)))
    prob = cp.Problem(obj, [cp.diag(Y) == 1])
    prob.solve(solver=cp.CLARABEL)
    return prob.value

print(f"{'instance':32s} {'cut optimal (brute)':>20s} {'SDP (CLARABEL)':>15s} {'ecart':>8s}")
for name, W in INSTANCES:
    b, s = maxcut_brut(W), sdp_maxcut(W)
    print(f"{name:32s} {b:20.4f} {s:15.4f} {s - b:8.4f}")
instance                          cut optimal (brute)  SDP (CLARABEL)    ecart
C6 (cycle pair, biparti)                       6.0000          6.0000  -0.0000
K8 poids uniformes seed 42                    11.8581         11.8584   0.0003
G(10, 0.5) seed 7                             14.0000         14.3249   0.3249

Lecture. Sur le cycle pair \(C_6\), la relaxation est exacte : \(\mathrm{SDP} = \mathrm{cut} = 6\) (un graphe biparti a une coupe qui traverse toutes les arêtes, et \(Y = ss^T\) l’atteint). Sur \(K_8\) pondéré elle est exacte aussi, à \(3\times10^{-4}\) près. Sur \(G(10,\,0.5)\) en revanche l’écart vaut \(0{,}3249\) : la valeur semidéfinie \(14{,}3249\) est inatteignable par toute coupe entière (la meilleure coupe vaut \(14\)). C’est l’écart intégralité de la relaxation — et la raison pour laquelle la suite distingue soigneusement valeur SDP (la cible du paysage factorisé) et coupe (ce qu’on en arrondit).

B. La factorisation de Burer–Monteiro

Résoudre (SDP) en variable matricielle \(n \times n\) coûte cher en grande dimension : \(O(n^2)\) inconnues et un cône de taille \(n\). L’idée de Burer–Monteiro : paramétrer \(Y = XX^T\) avec \(X \in \mathbb{R}^{n \times r}\), \(r \ll n\). La contrainte \(Y \succeq 0\) devient automatique, la contrainte \(\mathrm{diag}(Y)=1\) force chaque ligne \(x_i\) sur la sphère \(S^{r-1}\), et le problème devient

\[\text{(BM}_r\text{)} \quad \max_{X \in (S^{r-1})^n} \ f(X) = \tfrac{1}{2}\sum_{i<j} W_{ij}\,(1 - \langle x_i, x_j\rangle).\]

Non convexe en \(X\) — et c’est ainsi que tournent les solveurs SDP à grande échelle. Le prix : des minima locaux fallacieux deviennent possibles. La théorie encadre exactement ce prix :

  • Barvinok (1995) – Pataki (1998) : un SDP à \(m\) contraintes affines admet une solution optimale de rang \(r\) avec \(r(r+1)/2 \le m\). Le rang optimal n’est jamais « grand ».
  • Burer–Monteiro (2005) (Local minima and convergence in low-rank semidefinite programming, Math. Program. 103(3), 427–444) : si \(r(r+1)/2 > m\) et sous une condition de non-dégénérescence, tout minimum local de (BM\(_r\)) est globalement optimal — le paysage est sans piège.
  • Pont moderne vers les sommes de carrés : Low-Rank Univariate Sum of Squares Has No Spurious Local Minima (SIAM J. Optim., 2023) montre la même phénoménologie pour les programmes SOS factorisés en rang borné.

Pour MaxCut, \(m = n\) (les \(n\) contraintes diagonales), d’où le seuil \(r^* = \min\{r : r(r+1)/2 > n\}\). La prédiction falsifiable de ce notebook : fallacieux présents sous \(r^*\), absents à \(r^*\) et au-dessus.

def r_star(m):
    r = 1
    while r * (r + 1) // 2 <= m:
        r += 1
    return r

print(f"{'instance':32s} {'n (= m)':>7s} {'r*':>3s}   justification du seuil")
for name, W in INSTANCES:
    n = len(W)
    rs = r_star(n)
    print(f"{name:32s} {n:7d} {rs:3d}   r={rs-1}: {r_star(n)-1}*{r_star(n)}/2 = {(rs-1)*rs//2} <= {n} ; "
          f"r={rs}: {rs}*{rs+1}/2 = {rs*(rs+1)//2} > {n}")
instance                         n (= m)  r*   justification du seuil
C6 (cycle pair, biparti)               6   4   r=3: 3*4/2 = 6 <= 6 ; r=4: 4*5/2 = 10 > 6
K8 poids uniformes seed 42             8   4   r=3: 3*4/2 = 6 <= 8 ; r=4: 4*5/2 = 10 > 8
G(10, 0.5) seed 7                     10   5   r=4: 4*5/2 = 10 <= 10 ; r=5: 5*6/2 = 15 > 10

C. La méthode de recensement

Pour chaque instance et chaque rang \(r\), on tire 40 départs \(X_0\) d’une loi normale standard à graines fixes (une graine par départ, reproductibles), et on suit l’ascension de gradient projetée : le gradient euclidien \(\nabla_{x_i} f = -\tfrac{1}{2}\sum_j W_{ij} x_j\) est projeté sur l’espace tangent de la sphère en \(x_i\) (gradient riemannien), puis chaque ligne est renormalisée. Un départ est convergé quand la norme du gradient riemannien tombe sous \(2 \times 10^{-4}\).

Un point convergé est classé fallacieux s’il satisfait les trois conditions : (i) valeur \(< p^* - 10^{-3}\max(1,|p^*|)\) — strictement sous l’optimum SDP ; (ii) c’est bien un point stationnaire (gradient riemannien ~ nul) ; (iii) c’est un maximum local empirique : 20 perturbations aléatoires de norme \(\varepsilon = 0{,}02\) sur la variété n’en augmentent aucune la valeur. La condition (iii) est un contrôle du second ordre approché — elle distingue un vrai piège local d’un simple arrêt prématuré de l’ascension.

def bm_f(W, X):
    n = len(W)
    iu = np.triu_indices(n, 1)
    G = X @ X.T
    return 0.5 * np.sum(W[iu] * (1 - G[iu]))

def bm_ascent(W, r, seed, iters=1500, eta=0.2, tol=1e-7):
    n = len(W)
    rng = np.random.default_rng(seed)
    X = rng.standard_normal((n, r))
    X /= np.linalg.norm(X, axis=1, keepdims=True)
    for t in range(iters):
        grad = -0.5 * (W @ X)
        gT = grad - np.sum(X * grad, axis=1, keepdims=True) * X
        if np.linalg.norm(gT) < tol:
            break
        X = X + eta * gT
        X /= np.linalg.norm(X, axis=1, keepdims=True)
    grad = -0.5 * (W @ X)
    gT = grad - np.sum(X * grad, axis=1, keepdims=True) * X
    return X, bm_f(W, X), float(np.linalg.norm(gT)), t + 1

def est_max_local_empirique(W, X, K=20, eps=0.02, seed=123):
    rng = np.random.default_rng(seed)
    f0 = bm_f(W, X)
    for _ in range(K):
        D = rng.standard_normal(X.shape)
        D -= np.sum(X * D, axis=1, keepdims=True) * X
        nrm = np.linalg.norm(D, axis=1, keepdims=True)
        if np.all(nrm < 1e-12):
            continue  # tangent trivial (r=1 : S^0 est discret), aucune perturbation possible
        D /= nrm
        Xp = X + eps * D
        Xp /= np.linalg.norm(Xp, axis=1, keepdims=True)
        if bm_f(W, Xp) > f0 + 1e-9:
            return False
    return True

print("Outils prets : bm_f (objectif), bm_ascent (gradient projete, renvoie X), est_max_local_empirique (controle 2e ordre approche)")
Outils prets : bm_f (objectif), bm_ascent (gradient projete, renvoie X), est_max_local_empirique (controle 2e ordre approche)
STARTS = 40

def recensement(W, rmax):
    n = len(W)
    p_star = sdp_maxcut(W)
    lignes = []
    for r in range(1, rmax + 1):
        fallacieux, converges, vals = 0, 0, []
        for s in range(STARTS):
            X, val, gnorm, _ = bm_ascent(W, r, seed=1000 + s)
            vals.append(val)
            if gnorm < 2e-4:
                converges += 1
                if val < p_star - 1e-3 * max(1.0, abs(p_star)) and est_max_local_empirique(W, X, seed=9000 + s):
                    fallacieux += 1
        lignes.append((r, converges, fallacieux, max(vals), min(vals)))
    return p_star, lignes

print(f"{'instance':32s} {'r':>2s} {'seuil':>6s} {'conv.':>9s} {'fallacieux':>10s} {'meilleur':>9s} {'pire':>9s}")
RESULTATS = {}
for name, W in INSTANCES:
    n = len(W)
    rs = r_star(n)
    p_star, lignes = recensement(W, rs + 1)
    RESULTATS[name] = (p_star, lignes)
    for r, conv, fal, vmax, vmin in lignes:
        print(f"{name:32s} {r:2d} {'>= r*' if r >= rs else '<  r*':>6s} {conv:5d}/{STARTS:<3d} {fal:10d} {vmax:9.4f} {vmin:9.4f}")
instance                          r  seuil     conv. fallacieux  meilleur      pire
C6 (cycle pair, biparti)          1  <  r*    40/40          39    6.0000    2.0000
C6 (cycle pair, biparti)          2  <  r*    40/40           5    6.0000    4.5000
C6 (cycle pair, biparti)          3  <  r*    40/40           0    6.0000    6.0000
C6 (cycle pair, biparti)          4  >= r*    40/40           0    6.0000    6.0000
C6 (cycle pair, biparti)          5  >= r*    40/40           0    6.0000    6.0000
K8 poids uniformes seed 42        1  <  r*    40/40          40   11.1461    5.0249
K8 poids uniformes seed 42        2  <  r*    40/40           0   11.8584   11.8584
K8 poids uniformes seed 42        3  <  r*    40/40           0   11.8584   11.8584
K8 poids uniformes seed 42        4  >= r*    40/40           0   11.8584   11.8584
K8 poids uniformes seed 42        5  >= r*    40/40           0   11.8584   11.8584
G(10, 0.5) seed 7                 1  <  r*    40/40          40   13.0000    5.0000
G(10, 0.5) seed 7                 2  <  r*    40/40          12   14.3249   13.7699
G(10, 0.5) seed 7                 3  <  r*    40/40           0   14.3249   14.3249
G(10, 0.5) seed 7                 4  <  r*    40/40           0   14.3249   14.3249
G(10, 0.5) seed 7                 5  >= r*    40/40           0   14.3249   14.3249
G(10, 0.5) seed 7                 6  >= r*    40/40           0   14.3249   14.3249

Lecture du recensement. Trois régimes se lisent sur le tableau, identiques sur les trois instances :

  • \(r = 1\) : universellement fallacieux. Les lignes vivent sur \(S^0 = \{\pm 1\}\) : le problème factorisé est MaxCut discret, et presque chaque départ s’arrête sur une coupe sous-optimale — 39/40 sur \(C_6\) (pire : 2,0 sur un optimum de 6), 40/40 sur \(K_8\) (meilleure des 40 : 11,1461, en dessous même de la coupe optimale 11,8581 — 40 départs n’ont jamais trouvé la meilleure coupe), 40/40 sur \(G(10,0.5)\) (pire 5,0 pour un optimum SDP de 14,3249).
  • Rangs intermédiaires : la décroissance. À \(r=2\), \(C_6\) garde 5/40 fallacieux (plateau à 4,5) et \(G(10,0.5)\) en garde 12/40 (valeurs autour de 13,77 contre \(p^*=14,3249\)) ; \(K_8\) est déjà propre. Les pièges ne disparaissent pas d’un coup — ils se raréfient.
  • À partir de \(r^*\) : zéro. Aucun départ, sur aucune instance, ne converge vers un maximum local sous-optimal à \(r \ge r^*\). La prédiction de Burer–Monteiro est confirmée empiriquement sur ces instances.

Une nuance honnête s’impose : la propreté commence avant \(r^*\) sur les trois instances (\(C_6\) et \(G(10,0.5)\) sont propres dès \(r=3 < r^*\) ; \(K_8\) dès \(r=2\)). Le seuil \(r(r+1)/2 > m\) est une garantie suffisante, pas un coude de transition de phase : la théorie dit où l’on est sûr, pas où les pièges s’arrêtent exactement. Un recensement qui observerait un fallacieux à \(r \ge r^*\) sur une instance non dégénérée réfuterait le théorème — aucun ne l’a fait.

# Contre-exemple positif : exhiber UN maximum local fallacieux concret (G(10,0.5), r=2)
name_g10, W_g10 = INSTANCES[2]
p_star = RESULTATS[name_g10][0]

candidats = []
for s in range(STARTS):
    X, val, gnorm, _ = bm_ascent(W_g10, 2, seed=1000 + s)
    if gnorm < 2e-4 and val < p_star - 1e-3 and est_max_local_empirique(W_g10, X, seed=9000 + s):
        candidats.append((val, s, X))
val, s_chosen, X_chosen = min(candidats)   # le pire des fallacieux confirmes

rng = np.random.default_rng(31415)
ameliorations = []
for _ in range(200):
    D = rng.standard_normal(X_chosen.shape)
    D -= np.sum(X_chosen * D, axis=1, keepdims=True) * X_chosen
    D /= np.linalg.norm(D, axis=1, keepdims=True)
    Xp = X_chosen + 0.02 * D
    Xp /= np.linalg.norm(Xp, axis=1, keepdims=True)
    ameliorations.append(bm_f(W_g10, Xp) - bm_f(W_g10, X_chosen))
ameliorations = np.array(ameliorations)

print(f"Depart seed={1000 + s_chosen} (r=2) : valeur {val:.4f} contre p* SDP {p_star:.4f} (deficit {p_star - val:.4f})")
print(f"Gradient riemannien au point : {np.linalg.norm(-0.5 * (W_g10 @ X_chosen) - np.sum(X_chosen * (-0.5 * (W_g10 @ X_chosen)), axis=1, keepdims=True) * X_chosen):.2e} (stationnaire)")
print(f"Sur 200 perturbations (eps=0.02) : max de l'amelioration = {ameliorations.max():.2e}, positives = {(ameliorations > 1e-9).sum()}")
print("=> maximum local SOUS-OPTIMAL certifie empiriquement : stationnaire, aucun voisin meilleur, deficit clair.")
Depart seed=1032 (r=2) : valeur 13.7699 contre p* SDP 14.3249 (deficit 0.5551)
Gradient riemannien au point : 9.91e-08 (stationnaire)
Sur 200 perturbations (eps=0.02) : max de l'amelioration = -3.01e-04, positives = 0
=> maximum local SOUS-OPTIMAL certifie empiriquement : stationnaire, aucun voisin meilleur, deficit clair.

Lecture du zoom. Le point exhibé a toutes les cartes d’un vrai piège : déficit de \(0{,}5551\) par rapport à \(p^*\), gradient riemannien de l’ordre de \(10^{-8}\) (stationnaire), et aucune des 200 perturbations de norme \(0{,}02\) n’améliore la valeur — c’est bien un maximum local, pas un simple arrêt de l’algorithme. C’est exactement l’objet pathologique que toute méthode de recherche locale (cf. Search-4) redoute : le gradient ne dit plus rien, seul le déficit de valeur trahit le piège.

D. Friction et essais ratés (chemin de découverte)

Trois défauts ont été rencontrés et corrigés en cours de route — ils sont conservés parce qu’ils font partie du résultat :

  1. Double comptage de la référence SDP. La première implémentation sommait \(\langle W, 1-Y \rangle\) sur les \(n^2\) entrées : chaque paire comptée deux fois, référence \(p^*\) gonflée d’un facteur 2 — et tous les points convergés semblaient fallacieux, à tout rang. Un recensement n’est bon que sa référence : le symptôme (100 % de fallacieux, y compris au-dessus du seuil) contredisait le théorème, et c’est cette contradiction qui a révélé le bug.
  2. Critère de convergence trop strict. Avec 600 itérations et un seuil \(10^{-5}\), une partie des départs était classée non convergée alors qu’ils avaient atteint la valeur optimale — la convergence sur la variété est lente en fin de course. Passage à 1500 itérations et seuil \(2\times10^{-4}\) : tous les départs convergent.
  3. \(r=1\) n’est pas lisse. À \(r=1\) la « sphère » \(S^0\) est finie : l’ascension opère des bascules de signes, et la notion même de gradient projeté dégénère. Les nombres de \(r=1\) se lisent comme une recherche locale discrète, pas comme de l’optimisation continue — c’est un enseignement, pas un artefact.

E. Limites et réserves

  • Taille. \(n \le 10\) : l’énumération exhaustive des coupes (\(2^{n-1}\)) reste la référence. Rien ne prouve que la phénoménologie (propreté commençant avant \(r^*\)) persiste à grande échelle.
  • Recensement n’est pas preuve. Zéro fallacieux observé à \(r \ge r^*\) sur 3 instances × 40 départs ne remplace pas le théorème : l’absence observée n’est pas l’absence démontrée. Réciproquement, le théorème exige la non-dégénérescence — condition non vérifiée ici ; une instance dégénérée pourrait montrer des fallacieux au-dessus du seuil sans le réfuter.
  • Le pont SOS est cité, pas reproduit. Le résultat SIAM 2023 (SOS univarié sans minima fallacieux) ouvre la lecture « paysage low-rank SOS » de l’EPIC ; ce notebook mesure MaxCut, le pont reste bibliographique.
  • Rounding non traité. Passer de l’optimum SDP \(Y^*\) à une coupe (arrondi hyperplan de Goemans–Williamson) est un autre sujet — ici la cible du paysage est la valeur SDP, pas la coupe.

Raccord au corpus

Search-9 (programmation linéaire) → ici la relaxation monte d’un cran (cône semidéfini) puis se défait : convexité exacte contre efficacité non convexe. Search-4 (recherche locale) : les minima fallacieux sont l’ennemi générique de toute méthode locale. MGS-15 (Partie 4, série .NET) : la même question de paysage, posée sur des fonctions de test et mesurée par corrélation fitness-distance — l’autre famille, l’autre méthode. Ce notebook est le pilote « calculatoire borné » de l’EPIC #13106 : mesurer sur instances énumérables ce que la théorie garantit au seuil du rang.

Exercices

Les exercices s’exécutent de bout en bout (cellules stubs valides, rien à décommenter).

Exercice 1 — Le graphe de Petersen

Construisez \(W\) du graphe de Petersen (\(n=10\), 3-régulier, arêtes \(\{i, i+1\}\) et \(\{i, i+5\}\) mod 10 pour \(i < 5\)), calculez coupe optimale, \(p^*\) SDP, puis recensement \(r = 1..6\). Le seuil \(r^*\) vaut 5 : la propreté commence-t-elle avant, comme sur les trois instances du cours ?

Exercice 2 — Synchronisation Z2 bruitée

Remplacez \(W\) par une instance de synchronisation : \(W = s_0 s_0^T + \sigma \cdot N\) avec \(s_0 \in \{\pm1\}^{10}\) fixé, \(N\) symétrique à diagonale nulle (graine fixée), \(\sigma = 0{,}3\). Recensez \(r=1..5\) : le bruit crée-t-il des fallacieux au-dessus du seuil ?

Exercice 3 — Fiabilité du test de max local

Faites varier \(\varepsilon \in \{0{,}005, 0{,}02, 0{,}05, 0{,}1\}\) dans est_max_local_empirique sur le point fallacieux du zoom : à partir de quel rayon une perturbation trouve-t-elle une amélioration ? Cela mesure le bassin local du piège — et les limites d’un certificat de second ordre approché.

# Exercice 1 : graphe de Petersen — recensement au seuil r* = 5.
# Indice : W[i,(i+1)%5] pour le cycle exterieur, W[i%5, 5+(i+2)%5] pour l'etoile interieure,
#          W[i, i+5] pour les rayons. Puis reutiliser maxcut_brut, sdp_maxcut, recensement.
def petersen_W():
    # TODO etudiant : construire et retourner la matrice (10, 10) symetrique a diagonale nulle.
    return None  # TODO etudiant

# Exercice 2 : synchronisation Z2 bruitee.
def W_sync_bruitee(sigma=0.3, seed=99):
    # TODO etudiant : s0 uniforme +/-1 fixe par seed, N symetrique diag nulle, retourner W.
    return None  # TODO etudiant

# Exercice 3 : rayon de Bassin du piege.
def rayon_bassin(X, W, eps_list=(0.005, 0.02, 0.05, 0.1), K=100, seed=2718):
    # TODO etudiant : pour chaque eps, retourner la meilleure amelioration trouvee sur K perturbations.
    return None  # TODO etudiant

print("Exercices a completer : petersen_W, W_sync_bruitee, rayon_bassin.")
Exercices a completer : petersen_W, W_sync_bruitee, rayon_bassin.

Conclusion

Le paysage factorisé de Burer–Monteiro se comporte exactement comme la théorie le promet sur ces petites instances : piégé universellement au rang 1 (où il dégénère en le problème combinatoire lui-même), piégé partiellement aux rangs intermédiaires, et sans aucun piège observable au-dessus du seuil \(r(r+1)/2 > m\). La garantie n’est pas un coude observable — la propreté commence avant — mais elle délimite la zone où la recherche locale est certifiée sûre.

C’est la réponse à la question du fil : MGS-15 mesurait des paysages subis ; ici le rang est un levier qui achète un paysage sûr. Et c’est la leçon de méthode de l’EPIC #13106 : le théorème dit où regarder, le recensement mesure si le réel obéit — ni l’un sans l’autre. Un tableau de zéros n’est pas une preuve ; c’est l’absence de réfutation, la plus honnête des confirmations empiriques.

Références. S. Burer, R. D. C. Monteiro, Local Minima and Convergence in Low-Rank Semidefinite Programming, Mathematical Programming 103(3), 427–444 (2005) — DOI 10.1007/s10107-004-0564-1 · G. Blekherman et al. pour le contexte Barvinok–Pataki (1995/1998) · Low-Rank Univariate Sum of Squares Has No Spurious Local Minima, SIAM J. Optim. 33(2) (2023) — DOI 10.1137/22M1516208 · M. Yurtsever et al., Scalable Semidefinite Programming (l’usage pratique de la factorisation). Pilote #13194 / EPIC #13106.

Retour au sommet