Les matheux sont dans la place - pt=prout

[Anonyme20240202]

Ca me rappelle le programme de L3 en maths ça, ou alors un pauvre financier en master qui découvre les joies des maths

X* = argmin(J) s.t J(X) = c.T X

s.t -> subject to

et c^T pas c.T j'imagine non? C'est écrit bizarrement là

Chaque méthode à ses avantages et inconvénients, faut choisir selon la forme du problème. Faut également préférer des algos stables (stabilité numérique), genre: https://en.wikipedia.org/wiki/QR_algorithm

Généralement si tes matrices sont pas diagonal dominant (https://en.wikipedia.org/wiki/Diagon...ominant_matrix) t'auras des trucs instables

Les problèmes de stabilité pour la méthode de points intérieurs c'est un truc bien connu:


https://www.scopus.com/record/displa...&origin=inward
https://www.scopus.com/record/displa...&origin=inward
https://www.scopus.com/record/displa...&origin=inward
https://www.scopus.com/record/displa...&origin=inward

Faudrait voir dans quel contexte tu fais ça, t'es obligé d'utiliser cette méthode? Sinon y'a d'autres approches pour optimiser ça (edit: grillé par Laya)

https://en.wikipedia.org/wiki/Quasi-Newton_method
https://link.springer.com/referencew...06-48332-7_248
https://en.wikipedia.org/wiki/Low-rank_approximation
https://web.stanford.edu/class/ee364...seq_slides.pdf
https://www.cs.cornell.edu/~sridharan/convex.pdf

Sinon la stabilité numérique c'est tout un domaine, ne serait ce que à quoi ton code ressemble dans tes calculs intermédiaires, si tu respectes pas les bonnes pratiques de bases tu vas accumuler les erreurs. Est ce que tu normalises avant de faire les calculs, se souvenir que l'addition n'est pas associative si tu fais du calcul flottant, comparer le déterminant de la matrice avec la norme au carré pour voir si le problème est bien conditionné (http://www.ece.northwestern.edu/loca.../relcomp2.html), etc.

[BentheXIII]

Merci à vous deux. Je suis aussi intéressé par la mise en oeuvre de préconditionnement pour essayer d'améliorer les choses, mais ne suis marié à aucune méthode à priori. Mon seul souhait est d'avoir quelque chose d'implémentable sans trop de prise de tête en C, je me raccroche à l'apparente simplicité de la structure du problème pour me dire que j'ai une chance.

Outre les liens que vous partagez, j'ai aussi espoir de trouver de l'inspiration dans la doc du package python CVXOPT, dont je souhaite en quelque sorte réimplémenter sa fonction conelp en C . Celle-ci répond à mon besoin, mais quelque chose de plus simple m'irait aussi.

@Kamikaze : les liens Scopus que tu partage ont l'air cassé. Et

c.TX

est un mix honteux de syntaxe python.

[Anonyme20240202]

Ah 'tain ces salauds de Scopus ont mis une protection bidon sur les liens, attends je corrige ça

- - - Mise à jour - - -

On Numerical Issues of Interior Point Methods

The cholesky factorization in interior point methods

Stability of Augmented System Factorizations in Interior-Point Methods

Modified Cholesky Factorizations in Interior-Point Algorithms for Linear Programming

- - - Mise à jour - - -

Mais c'tait plus a titre informatif pour parler des problèmes de stabilités, y'a des solutions proposées mais je suis pas sûr que ce soit forcément digeste ou adapté à ce que tu veux faire. Faut voir la taille de n, la forme des problèmes etc.

[Anonyme20240202]

Au pire tu peux copier coller

https://github.com/cvxopt/cvxopt/blo...on/coneprog.py

[BentheXIII]

j'ai regardé la structure du problème et je pense que la méthode primal/dual peut profiter de la structure du problème pour se réduire à l'inversion d'un système 6x6 symmétrique Merci l'absence de terme quadratiqu dans la fonction de coût. Pas trop compris comment faire pop un terme de préconditionnement mais je verrai à l'usage

[Anonyme20240202]

[Shosuro Phil]

P..., rien qu'avec les 25 qu'il cite y'en a pour un mois d'insomnies...

[Anonyme20240202]

Y'a un truc qui me turlupine en ce moment, j'ai vu plusieurs personne avec la même question online ce qui est rassurant mais les réponses ne me satisfont pas.
https://www.quora.com/If-R-3-and-R-h...ensional-space
https://socratic.org/questions/what-...-example-for-r

J'essaye de trouver une explication au besoin qu'on a d'introduire le concept de dimension.

Est ce que les dimensions sont un pur outil "graphique" parce que c'est plus lisible pour nous, ou est ce qu'il y a une différence fondamentale (a priori y'a une différence fondamentale mais j'aimerais trouve un argument convaincant).

Plus formellement, par exemple R et R² ont a la même cardinalité, mais R c'est dimension 1 et R² c'est dimension 2.

Je vois rien qui m'empêche de reproduire n'importe quelle opération de R² dans R, calcul vectoriel ou autre. Car j'ai vu l'argument de dire qu'avec un seul vecteur tu ne peux pas span (famille génératrice/sous espace vectoriel engendré) R².

Mais y'a rien qui m'empêche de faire un mapping d'un élément de R pour représenter 2 vecteurs

C'est pas ce que fait justement la courbe de Lebesgue (Z-Order Curve)? https://fr.wikipedia.org/wiki/Courbe_de_Lebesgue

Je pense que y'a un truc qui m'échappe, l'intuition me dit que R² ou R^n est plus """grand""" que R d'une manière qui force la notion de dimension.

La réponse qui me convainc le plus c'est celle là: https://qr.ae/pKHfEF

You could map every point in R^3 to one in R. But the distance metric in R^3 doesn't become a distance metric in R. We know this because there are no continuous maps from R^3 to R.

On peut aussi dire que R et R² ne sont pas homéomorphiques

Mais j'aimerais bien une intuition en terme de "cardinalité" ou de "quantité d'information", qu'est ce qui fait la différence fondamentalement? Je prends les intuitions

[Arthropode]

Alors tu peux considérer que ce qui change c'est le nombre de voisins (ou de manière équivalente le volume d'une boule de rayon unité). Bêtement, si tu considères une grille cartésienne à coordonnées entières un point donné à 6 voisins en 3D, et seulement 4 en 2D. Ça change beaucoup de chose en fait. Donc déjà le calcul des distances (il y a « plus de chemins possibles » pour relier deux points, donc des distances plus courtes).
Et puis derrière ce nombre de voisins a des effets directs assez surprenants. Par exemple les marches aléatoires où là en 1 ou 2D il y a une probabilité de 1 de passer à un point donné, en 3D et plus elle est de 0. Ou en physique statistique où le résultat d'un modèle dépend de la dimensionnalité du système. L'exemple phase c'est le modèle d'Ising de ferromagnétisme qui ne présente pas d'ordre en 1D, mais peut en présenter en 2D ou plus.

[Shosuro Phil]

La notion de dimension et celle de cardinalité n'ont juste pas grand chose à voir, elles ne cherchent pas à capturer la même chose.

La cardinalité c'est juste une question de "avoir le même nombre d'éléments" (pour les cardinaux finis) ou "pouvoir être mis en correspondance" (pour les cardinaux infinis). La nature de la correspondance n'est pas prise en compte, notamment la (bi)continuité n'est pas au programme. Et oui, c'est assez facile de voir que R et R^n (pour un entier n>0 quelconque) sont en bijection. Le plus simple pour le toucher du doigt (même si ce n'est pas 100% correct) c'est la façon suivante: un nombre réel c'est une suite infinie de chiffres, en découpant la suite infinie tu peux alimenter n suites infinies de chiffres (le 1er va dans la première suite, le 2e va dans la 2e suite, .. le n-ème dans la n-ème suite, le n+1-ème dans la première suite, etc) et donc reconstituier n nombres réels.

La dimension, ça parle du nombre de coordonnées qu'il faut pour définir un point de manière affine, donc en particulier bicontinue. Ou, dans un espace pas nécessairement vectoriel, de manière suffisamment régulière (mes cours de géo diff sont vieux). Et oui, il y a une grosse différence.

Dans la vie de tous les jours, ce qui compte, c'est la dimension.

- - - Mise à jour - - -

Mais j'aimerais bien une intuition en terme de "cardinalité" ou de "quantité d'information", qu'est ce qui fait la différence fondamentalement? Je prends les intuitions

La quantité d'information contenue dans un nombre réel, comme dans deux, est de toute manière infinie. Ce n'est plus, à ce niveau, une mesure pertinente.

[Anonyme20240202]

Merci, en gros si je reformule de manière informatique, j'aimerais comprendre la différence entre la machine minimale capable de représenter des opérations dans R et celle qui travaille dans R².

Vu que tous les points de R² sont représentables dans R (même cardinalité) ça veut dire que forcément la différence vient des opérations qu'on peut faire sur ces points et non des points en eux-même. C'est ce que j'aimerais mettre en évidence par une différence précise entre les deux machines avec un contre exemple d'opération impossible pour la machine qui travaille avec R.

L'exemple d'Arthropode donne une bonne intuition mais je vais essayer de trouver un truc formel précis avec un impact direct sur la conception des 2 machines.

[Shosuro Phil]

Je ne suis pas sûr que parler de machines soit une très bonne idée - d'ordinaire on parle de machines pour des objets qui manipulent des données finies, or si on "voit" les réels comme des suites de chiffres (avantage: il n'y a qu'un nombre fini de chiffres différents), ce sont par nature des suites infinies de chiffres.

[Anonyme20240202]

Ouais une autre manière de formuler c'est si j'ai un canal de communication entre 2 entités.

Si ce canal de communication ne permet de transmettre que des éléments de R, est ce que je ne peux pas quand même faire de la géométrie dans R² en créant certaines opérations arbitraires?

La cardinalité est la même donc tout point de R² est représentable dans R, c'est un début

Mais bon il faut que j'y réfléchisse plus, j'ai des lacunes en topologie. Et toutes les discussions sur le sujets sont du point de vue topologique. Que je comprends je pense mais j'aimerais avoir l'angle informatique/constructif (dans le sens construction), qui fait émerger naturellement la notion de dimension comme un besoin

Je viens de découvrir la notion de module (https://fr.wikipedia.org/wiki/Module_sur_un_anneau) par exemple qui a l'air d'être dans la lignée du système arbitraire que je décris

- - - Mise à jour - - -

Much of the theory of modules consists of extending as many of the desirable properties of vector spaces as possible to the realm of modules over a "well-behaved" ring, such as a principal ideal domain. However, modules can be quite a bit more complicated than vector spaces; for instance, not all modules have a basis, and even those that do, free modules, need not have a unique rank if the underlying ring does not satisfy the invariant basis number condition, unlike vector spaces, which always have a (possibly infinite) basis whose cardinality is then unique. (These last two assertions require the axiom of choice in general, but not in the case of finite-dimensional spaces, or certain well-behaved infinite-dimensional spaces such as Lp spaces.)

[Vautour]

Si X et Y sont deux ensembles en bijection et que tu mets une structure algébrique (= opération(s) avec propriété(s)) sur X, alors tu peux transférer via la bijection la structure sur Y.

Mais "faire de la géométrie", c'est probablement des choses où la notion de voisinage va importer. Donc de la topologie, donc besoin d'homéo et pas juste de bijection.
Tes points proches dans R^2 n'auront pas des images proches dans R, ce qui fait que tu vas perdre tes propriétés topologiques sur les opérations dans R.

- - - Mise à jour - - -

Non, la notion de module n'a pas de rapport avec ce que tu décris ici.
Les espaces vectoriels sont un cas particulier de modules sur un anneau. Certes la notion de dimension pour les ev doit être remplacée par la notion plus faible de rang pour les modules, mais ça n'a aucun rapport avec la cardinalité / bijection.


et je reviens sur "faire de la géométrie". Tout matheux te dira (depuis le programme d'Erlangen) que c'est étudier des actions de groupes. Et rien n'impose à une action d'être continue.

[Anonyme20240202]

Ouais je venais tout juste de tomber là dessus: https://en.wikipedia.org/wiki/Transport_of_structure

Via: Can set of integers form a vector space over field of rationals?

Une des réponses reprend ce que tu dis

If instead we allow an arbitrary addition operation on Z, then yes, we can make it a Q-vector space, by "transport of structure" (Wikipedia link) via a bijection, e.g., a bijection φ:Z→Q.

Faut que je prenne le temps de digérer

En tout cas merci pour les réponses

[Anonyme20240202]

WTF, révélation du jour



https://fr.wikipedia.org/wiki/Carr%C3%A9_unit%C3%A9

J'étais en train de bosser là dessus en me disant que la démonstration doit pas être si compliquée et j'y arrivais pas, tu m'étonnes

[Aghora]

C'est quoi une "distance rationnelle" ?

[Souly]

C'est quoi une "distance rationnelle" ?

Bah un nombre rationnel ?

[Aghora]

Donc pas un nombre réel.

En y réfléchissant, effectivement "ça fait sens"...

[Vautour]

C'est quoi une "distance rationnelle" ?

La question est la suivante :
$\exists x \in \mathbbR^2 \setminus (\bigcup_j C_j), \forall i \in \{1,2,3,4\}, d (x,A_i) \in \mathbb Q$ ?
où $(C_i)_{i \in \{1,2,3,4\}}$ désigne les 4 côtés du carré unité et
$(A_i)_{i \in \{1,2,3,4\}}$ désigne les 4 sommets du carré unité
PS : Pour la norme 1 et la norme infini, je sais répondre. Et comme toutes les normes sont équivalentes ...

EDIT : Bordel, j'ai dû m'y reprendre à 3 fois pour bien le taper. C'était plus simple d'écrire un poly de L2 cet aprem.

[Souly]

La question est la suivante :
$\exists x \in \mathbbR^2 \setminus (\bigcup_j C_j), \forall i \in \{1,2,3,4\}, d (x,C_i) \in \mathbb Q$ ?
où $(C_i)_{i \in \{1,2,3,4\}}$ désigne les 4 côtés du carré unité.

PS : Pour la norme 1 et la norme infini, je sais répondre. Et comme toutes les normes sont équivalentes ...

EDIT : Bordel, j'ai dû m'y reprendre à 3 fois pour bien le taper. C'était plus simple d'écrire un poly de L2 cet aprem.

Tente une dernière fois pour voir, avec les 4 sommets du carré et pas les côtés

[Aghora]

La question est la suivante :
$\exists x \in \mathbbR^2 \setminus (\bigcup_j C_j), \forall i \in \{1,2,3,4\}, d (x,C_i) \in \mathbb Q$ ?
où $(C_i)_{i \in \{1,2,3,4\}}$ désigne les 4 côtés du carré unité.

PS : Pour la norme 1 et la norme infini, je sais répondre. Et comme toutes les normes sont équivalentes ...

EDIT : Bordel, j'ai dû m'y reprendre à 3 fois pour bien le taper. C'était plus simple d'écrire un poly de L2 cet aprem.

Le code latex passe pas :/.

[Vautour]

Tente une dernière fois pour voir, avec les 4 sommets du carré et pas les côtés

Rah, tu as raison !

[Shosuro Phil]

Je traduis: des distances (euclidiennes) aux 4 coins du carré qui soient des nombres rationnels (donc des nombres réels, mais des nombres réels particuliers).

PS : Pour la norme 1 et la norme infini, je sais répondre. Et comme toutes les normes sont équivalentes ...

Note pour les lecteurs un peu hâtifs: sur le coup, il bluffe le charognard.

C'est clairement équivalent, si on autorise à changer le côté du carré pour être n'importe quel entier à la place de 1, à demander l'existence d'un point avec des distances entières aux coins d'un carré. Et vu sous cet angle, ça devient un problème de théorie des nombres plus que de géométrie. Mais c'est pas plus facile pour autant, je soupçonne.

D'ailleurs même en autorisant les points à être sur les côtés du carré, je trouve pas.

[Anonyme20240202]

Ah je crois que j'avais oublié de poster ça

[Shosuro Phil]

Ah oui j'ai déjà vu ce modèle, il y a une vidéo récente de Mathologer où il parle de calculs autour de la sphère (et où il parle des modèles de Henry Segerman).

J'ai le bouquin de Segerman sur les modèles 3D, mais j'étais pas allé très loin dans les impressions. C'est pas des modèles super simples à sortir en fait.

[OMar92]

Le Français Michel Talagrand reçoit le prix Abel.

J'aime bien son look

[Shosuro Phil]

Toi t'as jamais vu des photos d'Adrien Douady

Talagrand, je ne connaissais de lui que des "inégalités de Talagrand" (et c'était il y a 25 ans), mais je ne savais même pas s'il était encore vivant ou quoi.

Bref, il a sans doute pas mal participé au développement en France des probas comme partie légitime des maths. Merci monsieur. (Je me souviens encore d'avoir, il y a une petite vingtaine d'années, entendu un matheux réputé dans son domaine, quasiment se vanter de ne pas savoir ce qu'est une variable aléatoire; deux décennies et quelques médailles Fields et autres prix plus tard, les mêmes auraient au moins la décence de s'en excuser)

[Eloso]

Le truc, c'est qu'avec tous ces mathématiciens au look affirmé, je m'imagine Shosuro Phil en avoir un du même acabit.
Et maintenant j'ai trop peur d'être déçu

[Shosuro Phil]

Nan j'avoue je suis pas aussi classe. D'ailleurs 1/ je suis (officiellement) pas mathématicien mais informaticien et 2/ j'ai pas de prix prestigieux.