Trois ou quatre phrases

Les humains s’attachent souvent à quelques idées qu’ils énoncent en trois ou quatre phrases comme sonne un slogan. Trois ou quatre phrases qui résumeraient le plus souvent une situation complexe, à plusieurs variables en une situation dont on ne retiendrai plus qu’un schéma simple si loin de la réalité.
Certains écrivent des livres et d’autres les résument en trois ou quatre phrases sonnantes et trébuchantes.
La nuance n’est pas vraiment l’apanage des humains. Le plus souvent ils ne voient qu’une face d’une seule pièce et ignorent tous les possibles réels. Cela me rappelle une nouvelle de Philip K. Dick dans laquelle suite à un accident nucléaire dans une centrale, les visiteurs de cette centrale étaient tous plongés successivement dans des réalités où chacun d’entre eux successivement devenait le maître ce cette réalité. Et bien sûr rien ne tournait bien rond dans aucune de ses nouvelles réalités.

Pour finir je vous rappellerai ce grand penseur Krishnamurti qui disait que tant que l’on est gouverné par la pensée, l’harmonie, le sacré ne peut exister.

C’est pourquoi j’ai cette idée qu’il faut mais le faut il… remettre du hasard dans notre société occidentale gouverné uniquement par l’idée que le profit individuel bénéficie à tous, notre société qui ne va que dans un sens possible et ignore tous les autres possibles

Chapitre 1 : dérivation et convexité

1. Dérivation

soit f : {\mathbb R}^n \mapsto {\mathbb R} une fonction

On dit que f est différentiable en a s’il existe un vecteur \nabla f(a)

appelé gradient de f en a vérifiant

f(a+h)=f(a) + <\nabla f(a),h> + \|h\|\epsilon(h)

\lim_{\|h\| \mapsto 0} \epsilon(h) = 0

On dit qu’elle est deux fois différentiable en a s’il existe aussi une matrice symétrique

notée \nabla^2 f(a) appelée matrice hessienne de f en a vérifiant

f(a+h)=f(a) + <\nabla f(a),h> + \frac{1}{2}<\nabla^2 f(a)h,h> \|h\|^2\epsilon(h)

PROPOSITION

Si f est différentiable en a

\nabla f(a) =\begin{pmatrix} \frac{\partial f}{\partial x_1}\\ \vdots \\ \frac{\partial f}{\partial x_n}\end{pmatrix}

Si f est 2 fois différentiable en a

\nabla^2 f(a)_{ij} = \frac{\partial^2 f}{\partial x_i\partial x_j}

2. Convexité

Soit C \subset {\mathbb R}^n

Définition

On dit que C est convexe si

\forall x,y \in {\mathbb R}^n \forall t \in [0;1]\text{ on a } tx+(1-t)y \in C

PROPRIETES

– l’intersection d’ensembles convexes est convexe

– la multiplication d’un convexe par un scalaire est convexe

– l’addition ou la différence d’un convexe avec un élément {\mathbb R}^nde est convexe

– Attention l’union de deux ensembles convexes n’est pas un convexe

PROPOSITION

Soit C \subset {\mathbb R}^n

C est convexe ssi

\forall \lambda_{1},\cdots,\lambda_{k} \geqslant 0 \text{ tq } \Sigma{\lambda_{k}} = 1 \text{ on a } \forall x_1,\cdots,x_k \in C\text{ } \Sigma{\lambda_{k}x_k} \in C

Démonstration simple par récurrence.

Définition

soit C \subset {\mathbb R}^n on appelle enveloppe convexe de C notée coC le plus petit ensemble convexe contenant C. C’est aussi l’intersection de tous les convexes contenant C.

PROPOSITION

Soit C \subset {\mathbb R}^n et C \neq \varnothing

Si C est un ouvert alors coC est un ouvert.

THEOREME DE CARATHÉODORY

Soit C \subset {\mathbb R}^n et C \neq \varnothing

alors

\forall x \in CoC \text{ } \exists \lambda_1,\cdots,\lambda_{n+1} \geqslant 0 \text{ tq } \sum_{i=1}^{n+1}{\lambda_{1}} = 1 \text{ } \exists x_1,\cdots,x_{n+1} \in C\text{ tq } x= \sum_{i=1}^{n+1}{\lambda_{i}x_i}

Démonstration :

A mettre

COROLLAIRE

Soit C \subset {\mathbb R}^n et C \neq \varnothing

Si C est un compact alors coC est un compact

Démonstration :

On a \phi : C\text{x}C\text{x}\cdots\text{x}C\text{x}\Delta \mapsto \text{coC}
\phi : (x_1,\cdots,x_{n+1}),(\lambda_1,\cdots,\lambda_{n+1}) \mapsto \sum_{i=1}^{n+1}\lambda_{i}x_i

avec \Delta=\{((\lambda_1,\cdots,\lambda_{n+1}); \sum_{i=1}^{n+1}\lambda_{i}=1\}

Cette fonction est bien définie, elle est surjective d’après Carathéodory, elle est continue. CxC…..CxDelta est un compact comme produit de compact.
Or l’image d’un compact est un compact dans ces conditions. CQFD

Ceci n’est plus vrai en dimension infinie.

3. Fonctions convexes

{\mathbb R}^n est muni du produit scalaire usuel et de la norme associée

Soit K \subset {\mathbb R}^n et et K \neq \varnothing
F de K dans {\mathbb R}^n une fonction et K convexe.

Définitions

L’épigraphe de f noté epi f = \{(x,r) \in K\text{x}{\mathbb R}^n; f(x) \leqslant r\}

La section inférieur de niveau lambda est

S_f(\lambda)=\{x \in K; f(x) \leqslant \lambda\}

On appelle courbe de f de niveau lambda

S_f(\lambda)=\{x \in K; f(x) = \lambda\}

Définition d’une fonction convexe :

On dit que f est convexe si :

\forall x,y \in K \text{ }\forall t \in [0;1]\text{ } f(tx+(1-t)y) \leqslant tf(x) + (1-t)f(y)

On dit que f est strictement convexe si :

\forall x,y \in K \text{ }x \neq y\text{ }\forall t \in ]0;1[\text{ } f(tx+(1-t)y) < tf(x) + (1-t)f(y)[/latex]  On dit que f est fortement convexe si :  [latex]\exists c>0\text{ }\forall x,y \in K \text{ }\forall t \in [0;1]\text{ } f(tx+(1-t)y) \leqslant tf(x) + (1-t)f(y) - ct(1-t)\|x-y\|^2

On dit que f est quasi convexe si :

\forall x,y \in K \text{ }x \neq y\text{ }\forall t \in ]0;1[\text{ } f(tx+(1-t)y) \leqslant max(f(x),f(y))

PROPOSITION

f est convexe ssi epi(f) est un ensemble convexe

Fortement convexe implique strictement implique convexe, implique quasi convexe

Exemple :

f(x) = x^2 fortement convexe
f(x) = -ln(x) est strictement convexe
Fonction affine par morceau est convexe

Une fonction strictement convexe est est enveloppable par une fonction quadratique.

PROPOSITION

f est convexe ssi :

\forall \lambda_1,\cdots,\lambda_{k} \geqslant 0 ; \sum_{i=1}^{k}\lambda_{i}=1

\forall x_1,\cdots,x_{k} \in K \text{ } f(\sum_{i=1}^{k}\lambda_{i}x_i) \leqslant \sum_{i=1}^{k}\lambda_{i}f(x_i)

f strictement convexe ssi :

\forall \lambda_1,\cdots,\lambda_{k} \geqslant 0 ; \sum_{i=1}^{k}\lambda_{i}=1

\forall x_1,\cdots,x_{k} \in K \text{ } f(\sum_{i=1}^{k}\lambda_{i}x_i) < \sum_{i=1}^{k}\lambda_{i}f(x_i) [/latex]  f affine ssi égalité à la place des inégalités ci dessus  <strong>PROPOSITION</strong></p> <p>Caractérisation des fonctions fortement convexe.</p> <p>f fortement convexe ssi il existe c>0 tel que g définie par<br /> [latex]g(x) = f(x) -c\|x\|^2 est convexe

ceci n'est vrai que si la norme est issue d'un produit scalaire.

Introduction à l’optimisation

Chapitre 0 : Introduction à l’optimisation

C’est une branche de l’analyse qui joue un rôle important en ingénierie. Il s’agit de déterminer les extrema de fonctions de plusieurs variables avec ou sans contraintes.

Un problème d’optimisation est de la forme (en minimisation)

(P) min f(x) x élément de C
f : {\mathbb R}^n \mapsto {\mathbb R}
et C un sous ensemble {\mathbb R}^{n}

– f est l’objectif
– C est la contrainte
{\mathbb R}^{n} est l’espace de décision (espace de Banach)

Rq : max f(x) = – min (-f(x)) pour x élément de C
donc on ne parlera que de minimisation

L’ensemble C est généralement de la forme :

C=\{x \in {\mathbb R}^{n}\text{ ou } x \in D : g_{i}(x) \leqslant  0 i = 1,\cdots,m , h(x) = 0\}

g_{i} : {\mathbb R}^{n} \mapsto {\mathbb R} fonctions
h : {\mathbb R}^{n} \mapsto {\mathbb R}^p une application
où D un fermé de {\mathbb R}^{n}

On obtient la classification suivante :

1. le problème (P) est dit convexe :
Si
– f et g_{i} sont convexes
– D convexe
– h affine

2. le problème (P) est dit quadratique :
Si
– f est quadratique (on considérera que le cas convexe)
g_{i} et h sont affines
D = {\mathbb R}^{n}

3. le problème (P) est dit linéaire :
Si
– Toutes sont affines
D = {\mathbb R}^{n}_+

Dans le cas 3 ce sont des problèmes de programmation linéaire.

4. Problème non convexes

idées (22) à ses débuts

Vous connaissez cette maison que l’on trace en passant par chaque segment une seule fois.

chemin

Quelles sont les figures de ce type ? Et n’est ce pas ce qui gouverne les particules

nombre premiers jumeaux et matrice

Screenshot from 2014-08-16 16:08:38

Observez bien cette image : les deux premières colonne donnent les nombres premiers jumeaux, la troisième leurs multiplications, la quatrième donne (p+1)(p’-1), la cinquième la division de la quatrième par neuf, puis la sixième colonne la racine carré de la cinquième colonne.

Et qu’observe-t-on sur les matrice 4×4 à droite si on les multiplie par le vecteur colonne (2, 4 , 6 , 10) on obtient les chiffres de la sixième colonne.

Ce qui est intéressant à mon avis c’est de voir que chaque ligne de chaque matrice a une somme qui s’incrémente de 1 à chaque fois.

Je vais continuer mes investigations et je vous tiens au courant

Un petit programme en prolog qui résoud le solitaire à alvéoles

Sous le prolog ciao-prolog  : la source du programme sol6

% Solution of 45-peg solitaire
%                      76 77 78
%                      67 68 69
%                      58 59 60
% 46 47 48 49 50 51 52 53 54
% 37 38 39 40 41 42 43 44 45
% 28 29 30 31 32 33 34 35 36
%                      22 23 24
%                      13 14 15
%                         4 5 6

:- use_module(library(lists)).
:- use_module(library(numlists)).
:- use_module(library(aggregates)).
:- use_module(library(sort)).
:- use_module(library(random)).

initial_state(sol,sol([4,5,6,13,14,15,22,23,24,
28,29,30,31,32,33,34,35,36,
37,38,39,40,41,42,43,44,45,
46,47,48,49,50,51,52,53,54,
58,59,60,67,68,69,76,77],[78])).
final_state(sol([_,_,_,_,_,_,_,_,_,_,_,_,_],[_,_,_,_,_,_,_,_,_,
_,_,_,_,_,_,_,_,_,
_,_,_,_,_,_,_,_,_,
_,_,_,_,_])).
deplacement(3,X,Y,Z):-
Z=\=46,
Z=\=47,
Z=\=37,
Z=\=38,
Y is Z – 1,
X is Z – 2.
deplacement(1,X,Y,Z):-
Y is Z – 9,
X is Z – 18.
deplacement(2,X,Y,Z):-
Y is Z + 9,
X is Z + 18.
deplacement(4,X,Y,Z):-
Z=\=45,
Z=\=44,
Z=\=36,
Z=\=35,
Y is Z + 1,
X is Z + 2.

move(sol(V,W),deplacement(_,X,Y,Z)):-
member(Z,W),
deplacement(_,X,Y,Z),
member(X,V),
member(Y,V).

update(sol(V,W),deplacement(_,X,Y,Z),sol(V1,W1)):-
delete(V,X,V2),
delete(V2,Y,V3),
V4 = [Z|V3],
sort(V4,V1),
delete(W,Z,W2),
W3=[X,Y|W2],
sort(W3,W1).
value(4,1).
value(5,1).
value(32,1).
value(40,1).
value(58,1).
value(13,2).
value(14,2).
value(31,2).
value(34,2).
value(39,2).
value(50,3).
value(59,3).
value(78,3).
value(22,4).
value(42,4).
value(45,4).
value(47,4).
value(77,4).
value(29,5).
value(30,5).
value(35,5).
value(51,5).
value(54,5).
value(67,5).
value(6,6).
value(15,6).
value(24,6).
value(37,6).
value(49,7).
value(76,7).
value(33,8).
value(36,8).
value(44,8).
value(48,8).
value(23,9).
value(38,9).
value(43,9).
value(60,9).
value(69,9).
value(28,10).
value(41,10).
value(46,10).
value(52,10).
value(53,10).
value(68,10).

produce_value(X):-
random(1,4,Value),
assertz(value(X,Value)).
produce_all_values([]).
produce_all_values([X|Xs]):-
produce_value(X),
produce_all_values(Xs).

evaluate([],[]).
evaluate([Boule|Board],[V|Value]):-
value(Boule,V),
evaluate(Board,Value).
evaluate_board(sol(Board,_),Value):-
evaluate(Board,ListValue),
sum_list(ListValue,Value).
inserts([Value|Values],Frontier,Frontier1):-
insert(Value,Frontier,Frontier0),
inserts(Values,Frontier0,Frontier1).
inserts([],Frontier,Frontier).

insert(State,[],[State]).
insert(State,[State1|States],[State,State1|States]):-
lesseq_value(State,State1).
insert(State,[State1|States],[State|States]):-
equals(State,State1).
insert(State,[State1|States],[State1|States1]):-
greater_value(State,State1),
insert(State,States,States1).

equals(state(S,_,V),state(S,_,V)).
lesseq_value(state(S1,_,V1),state(S2,_,V2)):- nocontainsx([S2],S1),V2>=V1.
greater_value(state(_,_,V1),state(_,_,V2)):-V1>V2.

update_frontier([M|Ms],State,Path,History,F,F1):-
update(State,M,State1),
evaluate_board(State1,Value),
\+ member(State1,History),
insert(state(State1,[M|Path],Value),F,F0),
update_frontier(Ms,State,Path,History,F0,F1).
update_frontier([],_,_,_,F,F).

solve_best([state(State,Path,_)|_],_,Moves):-
final_state(State),
reverse(Path,[],Moves).
solve_best([state(State,Path,_)|Frontier],History,FinalPath):-
findall(M,move(State,M),Moves),
update_frontier(Moves,State,Path,History,Frontier,Frontier1),
solve_best(Frontier1,[State|History],FinalPath).

test_bfs(Problem,Moves):-
initial_state(Problem,State),
solve_best([state(State,[],[])],[State],Moves).

board(Xs,Ynew):-
board10([deplacement(_,X1,X2,X3)|Xs],Y),!,
delete(Y,X1,Y1),
delete(Y1,X2,Y2),
Y3 = [X3|Y2],
sort(Y3,Ynew).
board(Xs,Ynew):-
board([deplacement(_,X1,X2,X3)|Xs],Y),
delete(Y,X1,Y1),
delete(Y1,X2,Y2),
Y3 = [X3|Y2],
sort(Y3,Ynew).

jeu(Y,Z,[Move]):-
member(X3,Z),
deplacement(_,X1,X2,X3),
member(X1,Y),
member(X2,Y),
delete(Y,X1,Y1),
delete(Y1,X2,Y2),
Y3 = [X3|Y2],
length(Y3,1),
Move = deplacement(_,X1,X2,X3).

jeu(Y,Z,[Move|Moves]):-
member(X3,Z),
deplacement(_,X1,X2,X3),
member(X1,Y),
member(X2,Y),
delete(Y,X1,Y1),
delete(Y1,X2,Y2),
Y3 = [X3|Y2],
sort(Y3,Y4),
delete(Z,X3,Z1),
Z2 = [X1,X2|Z1],
sort(Z2,Z3),
Move = deplacement(_,X1,X2,X3),
jeu(Y4,Z3,Moves).

 

main(S):-
test_bfs(sol,X),
retractall(board10(_,_)),
assertz(board10(X,[4,5,6,13,14,15,22,23,24,
28,29,30,31,32,33,34,35,36,
37,38,39,40,41,42,43,44,45,
46,47,48,49,50,51,52,53,54,
58,59,60,67,68,69,76,77])),
board([],Y),
difference([4,5,6,13,14,15,22,23,24,
28,29,30,31,32,33,34,35,36,
37,38,39,40,41,42,43,44,45,
46,47,48,49,50,51,52,53,54,
58,59,60,67,68,69,76,77,78],Y,Z),
jeu(Y,Z,Moves),
append(X,Moves,S).