Propriétés probabilistes dans les algorithmes d

Propriétés probabilistes dans les algorithmesd'optimisation sans et avec dérivées

Clément Royer - University of Wisconsin-Madison

Séminaire SPOC

Institut de Mathématiques de Bourgogne

12 avril 2017

Propriétés probabilistes en optimisation sans et avec dérivées 1

Introduction: Aléatoire et optimisation

L'aléatoire est de plus en plus présent en optimisation numérique.

Pour de multiples raisons :

Problèmes de grande taille : Méthodes classiques trop coûteuses.

Calcul distribué : Données stockées sur plusieursmachines/processeurs.

Applications : Problèmes d'apprentissage.

Questions sur l'aléatoire

Comment l'analyse des méthodes est-elle a�ectée ?

Améliore-t-on les variantes déterministes ?

Aléatoire en optimisation sans dérivées ?


Introduction: Aléatoire et optimisation

L'aléatoire est de plus en plus présent en optimisation numérique.

Pour de multiples raisons :

Problèmes de grande taille : Méthodes classiques trop coûteuses.

Calcul distribué : Données stockées sur plusieursmachines/processeurs.

Applications : Problèmes d'apprentissage.

Questions sur l'aléatoire

Comment l'analyse des méthodes est-elle a�ectée ?

Améliore-t-on les variantes déterministes ?

Aléatoire en optimisation sans dérivées ?


Complexité des algorithmes d'optimisation

Analyse de Complexité

Etudier le taux de convergence d'un critère donné.

Borner le comportement d'une méthode au pire cas.

Avec aléatoire : résultats en espérance/probabilité.

Utilité de la complexité

Quelles indications données par la complexité ?

Quel lien avec la pratique ?

Importance pour les méthodes sans dérivées ?


Objectifs du séminaire

Trame

1 Introduire des aspects aléatoires dans des algorithmes sans dérivées.

2 Fournir des garanties théoriques (ex : complexité).

3 Comparer la complexité et le comportement numérique.

Dans cet exposé : méthodes de recherche directe;

Les résultats s'appliquent à d'autre méthodes, comme les régions decon�ance.


Objectifs du séminaire

Trame

1 Introduire des aspects aléatoires dans des algorithmes sans dérivées.

2 Fournir des garanties théoriques (ex : complexité).

3 Comparer la complexité et le comportement numérique.

Dans cet exposé : méthodes de recherche directe;

Les résultats s'appliquent à d'autre méthodes, comme les régions decon�ance.


Outline

1 Recherche directe déterministe

2 Recherche directe à base de descente probabiliste

3 Extension aux problèmes avec contraintes linéaires

4 Propriétés probabilistes en optimisation avec dérivées


Outline

1 Recherche directe déterministeOptimisation sans dérivéesRecherche directe





Problème et hypothèses

Soit le problème suivant :minx∈Rn

f (x).

Hypothèses sur f

f minorée, a priori non convexe.

f de classe C1, ∇f fonction lipschitzienne.

Optimisation di�érentiable

Depuis x ∈ Rn, on peut décroître f dans la direction de −∇f (x) !Principe de base des méthodes de premier ordre/gradient.

Objectif : converger vers un point stationnaire d'ordre 1:

lim infk→∞

‖∇f (xk)‖ = 0.


Problème et hypothèses

Soit le problème suivant :minx∈Rn

f (x).

Hypothèses sur f

f minorée, a priori non convexe.

f de classe C1, ∇f fonction lipschitzienne.

Optimisation di�érentiable

Depuis x ∈ Rn, on peut décroître f dans la direction de −∇f (x) !Principe de base des méthodes de premier ordre/gradient.

Objectif : converger vers un point stationnaire d'ordre 1:

lim infk→∞

‖∇f (xk)‖ = 0.


Le contexte sans dérivées

Le gradient de f existe mais ne peut pas être utilisé en pratique.

Code de simulation : le gradient est trop coûteux.

Fonction f disponible sous forme de boîte noire : pas de code pour ladérivée.

Di�érentiation automatique inapplicable.

Examples : météorologie, industrie pétrolière, médecine...

Mesure de performance : Nombre d'évaluations de l'objectif.


Le contexte sans dérivées

Le gradient de f existe mais ne peut pas être utilisé en pratique.

Code de simulation : le gradient est trop coûteux.

Fonction f disponible sous forme de boîte noire : pas de code pour ladérivée.

Di�érentiation automatique inapplicable.

Examples : météorologie, industrie pétrolière, médecine...

Mesure de performance : Nombre d'évaluations de l'objectif.


Algorithmes d'Optimisation sans Dérivées (DFO)

Méthodes sans dérivées déterministes

Méthodes à modèles, comme les régions de con�ance.

Méthodes directionnelles, comme la recherche directe.

Introduction to Derivative-Free Optimization

A.R. Conn, K. Scheinberg, L.N. Vicente. (2009)

Théorie de convergence (vers des optima locaux).

Bornes de complexité/Vitesses de convergence activement étudiées.


Algorithmes d'Optimisation Sans Dérivées (2)

Méthodes �DFO" stochastiques

Ont pour but de trouver des optima globaux:

Ex) Stratégies Evolutionnaires, Algorithmes Génétiques.

Souvent sans analogues déterministes.

Cet exposé ne concerne pas les méthodes stochastiques;

Nos algorithmes sont basés sur des éléments probabilistes.

Méthodes �DFO" avec propriétés probabilistes

Développées à partir d'algorithmes déterministes.

Béné�cient de garanties théoriques grâce à cela.

Le côté aléatoire améliore la performance.


Outline

1 Recherche directe déterministeOptimisation sans dérivéesRecherche directe





Algorithmes de recherche directe

Variantes sans dérivées des méthodes de gradient.

Introduites vers 1960, théorie de convergence vers 1990.

Simples à implémenter, fort potentiel de parallélisme.

Optimization by direct search: new perspectives on some

classical and modern methods.

Kolda, Lewis and Torczon (SIAM Review, 2003).


Un algorithme basique de recherche directe

1 Initialisation: x0 ∈ Rn, α0 > 0, 0 < θ < 1 ≤ γ.2 Pour k = 0, 1, 2, ...

Choisir un ensemble Dk de r vecteurs.Si il existe dk ∈ Dk tel que

f (xk + αk dk) < f (xk)− α2k ,

alors (k réussie) poser xk+1 := xk + αk dk et αk+1 := γ αk .Sinon (k non réussie) poser xk+1 := xk et αk+1 := θ αk .


Un algorithme basique de recherche directe


Choisir un ensemble Dk de r vecteurs.Si il existe dk ∈ Dk tel que




Choisir les directions de sondage

On cherche à choisir les ensembles des directions/de sondage Dk pourgarantir la convergene de l'algorithme.

Une mesure de qualité

Pour un ensemble de vecteurs D, la mesure cosinus de D est donnée par

cm(D) = minv∈Rn\{0}

maxd∈D

d> v

‖d‖ ‖v‖.

Si cm(D) > 0, pour tout v il existe d ∈ D tel que (d , v) est un angleaigu.

Avec v = −∇f (x) 6= 0, D contient une direction de descente pour fen x .







maxd∈D

d> v

‖d‖ ‖v‖.









maxd∈D

d> v

‖d‖ ‖v‖.




Génération positive

Comment garantir cm(D) > 0 ?

Ensemble de générateurs positifs (PSS)

D est un PSS s'il génère Rn par combinaisons linéaires à coe�cientspositifs ou nuls.

D est un PSS ⇔ cm(D) > 0.

Un PSS contient au moins n + 1 vecteurs.

Exemple

D⊕ = {e1, . . . , en, -e1, . . . , -en} est un PSS avec

cm (D⊕) =1√n.


Génération positive

Comment garantir cm(D) > 0 ?

Ensemble de générateurs positifs (PSS)

D est un PSS s'il génère Rn par combinaisons linéaires à coe�cientspositifs ou nuls.

D est un PSS ⇔ cm(D) > 0.

Un PSS contient au moins n + 1 vecteurs.

Exemple

D⊕ = {e1, . . . , en, -e1, . . . , -en} est un PSS avec

cm (D⊕) =1√n.


Convergence de la recherche directe déterministe

Lemma

Si l'itération k n'est pas réussie et cm(Dk) ≥ κ > 0,

κ ‖∇f (xk)‖ ≤ O (αk) .

Lemma

Indépendamment de {Dk},

limk→∞

αk = 0.

Théorème de convergence

Si ∀k , cm(Dk) ≥ κ,lim infk→∞

‖∇f (xk)‖ = 0.


Convergence de la recherche directe déterministe

Lemma

Si l'itération k n'est pas réussie et cm(Dk) ≥ κ > 0,

κ ‖∇f (xk)‖ ≤ O (αk) .

Lemma

Indépendamment de {Dk},

limk→∞

αk = 0.

Théorème de convergence

Si ∀k , cm(Dk) ≥ κ,lim infk→∞

‖∇f (xk)‖ = 0.


Worst-case complexity in deterministic direct search

Théorème de complexité

Soient ε ∈ (0, 1) et Nε le nombre d'appels à f nécessaires pour satisfaireinf0≤l≤k ‖∇f (xl )‖ < ε. On a

Nε ≤ O(r (κ ε)−2

).

En choisissant Dk = D⊕, on a κ = 1/√n, r = 2n, la borne devient

Nε ≤ O(n2 ε−2

).


Outline


2 Recherche directe à base de descente probabilisteDescente probabilisteConvergence et complexitéDescente probabiliste en pratique




Introduction d'aléatoire

Idée (Gratton et Vicente, 2013)

Utiliser des vecteurs tirés aléatoirement et indépendamment, typiquementmoins que n + 1 !

From PSS...

...to random sets





From PSS...

...to random sets





From PSS...

...to random sets


Motivation numérique

Test de convergence: f (xk) < flow + 10−3 (f (x0)− flow);

Budget: 2000 n appels à f max.

Problème D⊕ Q D⊕ 2 n n + 1 n/2 2 1

Déterministe Probabiliste

arglina 3.42 16.67 10.30 6.01 3.21 1.00 �

arglinb 20.50 11.38 7.38 2.81 2.35 1.00 2.04

broydn3d 4.33 11.22 6.54 3.59 2.04 1.00 �

dqrtic 7.16 19.50 9.10 4.56 2.77 1.00 �

engval1 10.53 23.96 11.90 6.48 3.55 1.00 2.08

freuroth 56.00 1.33 1.00 1.67 1.33 1.00 4.00

integreq 16.04 18.85 12.44 6.76 3.52 1.00 �

nondquar 6.90 17.36 7.56 4.23 2.76 1.00 �

sinquad � 2.12 1.31 1.00 1.60 1.23 �

vardim 1.00 3.30 1.80 2.40 2.30 1.80 4.30

Table: Ratio du nombre d'appels à f (moyenne sur 10 réalisations, taille n = 40)


Algorithme de recherche directe probabiliste

Notations probabilistes

Ensembles/Directions de sondage : Dk = Dk(ω), dk = dk(ω);

Itérés : xk = Xk(ω);

Longueurs de pas : αk = Ak(ω).


Choisir un ensemble Dk de r vecteurs tirés indépendamment au

hasard.

Si il existe dk ∈ Dk tel que

f (Xk +_k dk) < f (Xk)− A2

k,

alors (k réussie) poser Xk+1 := Xk + Ak dk et Ak+1 := γ Ak .Sinon (k non réussie) poser Xk+1 := Xk et Ak+1 := θAk .


Outline






Qu'est-ce qu'un bon ensemble de sondage ?

D

D n'est pas un PSS...

...D⊕ si...

D⊕

-∇f (x)

...-∇f (x) plus proche de D !

Etre proche de l'opposé du gradient : un gage de qualité ?



D

D n'est pas un PSS... ...D⊕ si...

D⊕

-∇f (x)





D

D n'est pas un PSS... ...D⊕ si...

D⊕

-∇f (x)




Une nouvelle mesure de qualité

Propriétés dans le cas déterministe

On a requis

cm(Dk) = minv 6=0

maxd∈Dk

d> v

‖d‖ ‖v‖≥ κ.

Il su�rait d'avoir

cm (Dk ,−∇f (xk)) = maxd∈Dk

d>[−∇f (xk)]‖d‖‖∇f (xk)‖

≥ κ.

Avec de l'aléatoire, la seconde propriété peut être vraie en probabilité.

Quels sont les bons outils probabilistes pour exprimer cela ?


Analyse probabiliste

Plusieurs types de résultats

Déterministe/Pour toute réalisation⇓

Avec probabilité 1/Presque sûr⇓

Avec une certaine probabilité

Sous-martingale

Une sous-martingale est une suite de variables aléatoires {Vk} telle queE [|Vk |] <∞ et

E (Vk |V0,V1, . . . ,Vk−1) ≥ Vk−1.


Ensembles de directions et descente (p, κ)

On cherche à étudier

P (cm (Dk ,−∇f (Xk)) ≥ κ) .

où Xk dépend de D0, . . . ,Dk−1 mais pas de Dk .

On va utiliser les probabilités conditionnelles/le conditionnement aupassé.

Propriété de descente probabiliste

Une suite d'ensembles aléatoires {Dk} est dite à descente (p, κ) si:

P (cm (D0,−∇f (x0)) ≥ κ) ≥ p

∀k ≥ 1, P (cm (Dk ,−∇f (Xk)) ≥ κ | D0, . . . ,Dk−1) ≥ p,


Ensembles de directions et descente (p, κ)

On cherche à étudier

P (cm (Dk ,−∇f (Xk)) ≥ κ) .

où Xk dépend de D0, . . . ,Dk−1 mais pas de Dk .

On va utiliser les probabilités conditionnelles/le conditionnement aupassé.

Propriété de descente probabiliste

Une suite d'ensembles aléatoires {Dk} est dite à descente (p, κ) si:

P (cm (D0,−∇f (x0)) ≥ κ) ≥ p

∀k ≥ 1, P (cm (Dk ,−∇f (Xk)) ≥ κ | D0, . . . ,Dk−1) ≥ p,


Résultats de convergence

Lemma

Pour toute réalisation {αk} de {Ak}, indépendamment de {Dk},

limk→∞

αk = 0.

Lemma

Si l'itération k n'est pas réussie,

{cm (Dk ,−∇f (Xk)) ≥ κ} ⊂ {κ ‖∇f (Xk)‖ ≤ O (Ak)} .

Il s'agit de prouver que {cm (Dk ,−∇f (Xk)) ≥ κ} se produit su�sammentsouvent.


Résultats de convergence (2)

Soit {Dk} à descente (p, κ) et Zk = 1 (cm (Dk ,−∇f (Xk)) ≥ κ).

Proposition

Soit

Sk =k−1∑i=0

[Zi − p0] , p0 =ln θ

ln(θ/γ).

1 {lim infk ‖∇f (Xk)‖ > 0} ⊂ {Sk → −∞}.2 Si p > p0, {Sk} est une sous-martingale avec P (lim sup Sk =∞) = 1.

Théorème : convergence presque sûre

Si {Dk} est à descente (p, κ) avec p > p0, on a

P(

lim infk→∞

‖∇f (Xk)‖ = 0

)= 1.


Résultats de convergence (2)

Soit {Dk} à descente (p, κ) et Zk = 1 (cm (Dk ,−∇f (Xk)) ≥ κ).

Proposition

Soit

Sk =k−1∑i=0

[Zi − p0] , p0 =ln θ

ln(θ/γ).

1 {lim infk ‖∇f (Xk)‖ > 0} ⊂ {Sk → −∞}.2 Si p > p0, {Sk} est une sous-martingale avec P (lim sup Sk =∞) = 1.

Théorème : convergence presque sûre

Si {Dk} est à descente (p, κ) avec p > p0, on a

P(

lim infk→∞

‖∇f (Xk)‖ = 0

)= 1.


Complexité et descente probabiliste

Idée intuitive

Soient Gk = ∇f (Xk) et Zk = 1 (cm(Dk ,−Gk) ≥ κ).Si Zk = 1 et k réussie, on a κ ‖Gk‖ < O(Ak)...

...Ak tend vers 0...

...donc si inf0≤l≤k ‖Gl‖ est grand,∑

k

l=0 Zl doit être faible.

Une borne utile

Pour chaque réalisation de l'algorithme,

k∑l=0

zl ≤ O(

1

κ2 ‖g̃k‖2

)+ p0 k ,

où ‖g̃k‖ = inf0≤l≤k ‖gl‖.



Idée intuitive




k


Une borne utile


k∑l=0

zl ≤ O(

1

κ2 ‖g̃k‖2

)+ p0 k ,




Idée intuitive




k


Une borne utile


k∑l=0

zl ≤ O(

1

κ2 ‖g̃k‖2

)+ p0 k ,



Complexité et descente probabiliste (2)

Rappel : Zl = 1 (cm(Dl ,−∇f (Xl ) ≥ κ).

Argument d'inclusion{inf

0≤l≤k‖∇f (Xk)‖ ≥ ε

}⊂

{k∑

l=0

Zl ≤ λ k

}avec λ = O

(1

k κ2 ε−2

)+ p0.

Borne de type Cherno�

Pour tout λ ∈ (0, p),

P

(k−1∑l=0

Zl ≤ λ k

)≤ exp

[−(p − λ)2

2 pk

].


Complexité et descent probabiliste (3)

Théorème : Complexité probabiliste

Soient {Dk} à descente (p, κ), ε ∈ (0, 1) et Nε le nombre d'appels à fnécessaires pour obtenir inf0≤l≤k ‖∇f (Xl )‖ ≤ ε. Alors

P(Nε ≤ O

(r (κε)−2

p − p0

))≥ 1− exp

(−O

(p − p0

p(κ ε)−2

)).

Déterministe : O(n2 ε−2).Probabiliste : O(r n ε−2) en probabilité⇒ O(n ε−2) lorsque r = 2 !

Serait-on meilleur (en probabilité) avec moins de directions ?


Complexité et descent probabiliste (3)

Théorème : Complexité probabiliste

Soient {Dk} à descente (p, κ), ε ∈ (0, 1) et Nε le nombre d'appels à fnécessaires pour obtenir inf0≤l≤k ‖∇f (Xl )‖ ≤ ε. Alors

P(Nε ≤ O

(r (κε)−2

p − p0

))≥ 1− exp

(−O

(p − p0

p(κ ε)−2

)).

Déterministe : O(n2 ε−2).Probabiliste : O(r n ε−2) en probabilité⇒ O(n ε−2) lorsque r = 2 !

Serait-on meilleur (en probabilité) avec moins de directions ?


Outline






Construire une suite à descente (p, κ)

On cherche à avoir

p > p0 =ln(θ)

ln(θ/γ)

avec le plus petit r = |Dk | possible.

Une technique : génération uniforme sur la sphère unité

Si

r > log2

(1− ln θ

ln γ

),

il existe (p, τ) indépendants de n tels que la suite Dk est à descente(p, τ/

√n) et p > p0.

Si γ = θ−1 = 2, choisir r ≥ 2 su�t à garantir p > 12.


Deux directions uniformes su�sent, pas une

g

g

d1 d2

d1 ∼ U(S1)⇒ ∀κ ∈ (0, 1), P(cm (d1, g) = d>1 g ≥ κ

)< 1/2.

d1, d2 ∼ U(S1)⇒ ∃κ∗ ∈ (0, 1), P (cm ({d1, d2} , g) ≥ κ∗) > 1/2.



g

d1

g

d1 d2

d1 ∼ U(S1)⇒ ∀κ ∈ (0, 1), P(cm (d1, g) = d>1 g ≥ κ

)< 1/2.

d1, d2 ∼ U(S1)⇒ ∃κ∗ ∈ (0, 1), P (cm ({d1, d2} , g) ≥ κ∗) > 1/2.



g d1

g

d1 d2

d1 ∼ U(S1)⇒ ∀κ ∈ (0, 1), P(cm (d1, g) = d>1 g ≥ κ

)< 1/2.

d1, d2 ∼ U(S1)⇒ ∃κ∗ ∈ (0, 1), P (cm ({d1, d2} , g) ≥ κ∗) > 1/2.



g d1 g

d1 d2

d1 ∼ U(S1)⇒ ∀κ ∈ (0, 1), P(cm (d1, g) = d>1 g ≥ κ

)< 1/2.

d1, d2 ∼ U(S1)⇒ ∃κ∗ ∈ (0, 1), P (cm ({d1, d2} , g) ≥ κ∗) > 1/2.


Outline






Deux problèmes d'optimisation avec contraintes linéaires

Contraintes linéaires d'égalité{minx∈Rn f (x)s.t. Ax = b.

Equivalent au problème sans contraintes minx̃∈Rn−m f (x0 +Wx̃) oùW ∈ Rn×(n−m) est une base pour null(A) et Ax0 = b.

Les résultats déterministes et probabilistes restent valables !

Contraintes d'intervalle {minx∈Rn f (x)s.t. l ≤ x ≤ u.

En pratique (déterministe) : Utiliser D⊕ = {e1, . . . , en,−e1, . . . ,−en}permet de converger et de se déplacer parallèlement aux contraintes.


Deux problèmes d'optimisation avec contraintes linéaires

Contraintes linéaires d'égalité{minx∈Rn f (x)s.t. Ax = b.

Equivalent au problème sans contraintes minx̃∈Rn−m f (x0 +Wx̃) oùW ∈ Rn×(n−m) est une base pour null(A) et Ax0 = b.

Les résultats déterministes et probabilistes restent valables !

Contraintes d'intervalle {minx∈Rn f (x)s.t. l ≤ x ≤ u.

En pratique (déterministe) : Utiliser D⊕ = {e1, . . . , en,−e1, . . . ,−en}permet de converger et de se déplacer parallèlement aux contraintes.


Algorithme (version déterministe)


Choisir un ensemble Dk d'au plus r vecteurs.Si il existe dk ∈ Dk tel que xk + αkdk est admissible and




Contraintes d'intervalle

Domaine admissible : F = {l ≤ x ≤ u}.

Contraintes proches

Les ensemblesIu(x , α) = {i : |ui − [x ]i | ≤ α}Il (x , α) = {i : |li − [x ]i | ≤ α}

dé�nissent les contraintes proches en x ∈ F pour α > 0.

αx α x


Contraintes d'intervalle (2)

Cône normal approché N(x , α) : généré positivement par

{ei}i∈Iu(x ,α) ∪ {−ei}i∈Il (x ,α) .

Cône tangent T (x , α) : cône polaire de N(x , α).

x

N(x , α)

T (x , α)

T (x , α)

N(x , α)

x


Propriété de descente réalisable

Rappel : la mesure cosinus permet d'identi�er les directions dedescente

cm(D,−∇f (x)) = maxd∈D

d>[−∇f (x)]‖d‖‖ − ∇f (x)‖

.

Descente réalisable

D est un ensemble à descente κ-admissible pour T (x , α) si D ⊂ T (x , α) et

cmT (x ,α)(D,−∇f (x)) = maxd∈D

d>[−∇f (x)]‖d‖‖PT (x ,α)[−∇f (x)]‖

≥ κ.

Avec des ensembles à descente κ-admissible : convergence + bornessur la complexité (analyse similaire au cas sans contraintes).

D⊕ ∩ T (x , α) est toujours à descente 1√n-admissible.


Propriété de descente réalisable

Rappel : la mesure cosinus permet d'identi�er les directions dedescente

cm(D,−∇f (x)) = maxd∈D

d>[−∇f (x)]‖d‖‖ − ∇f (x)‖

.

Descente réalisable

D est un ensemble à descente κ-admissible pour T (x , α) si D ⊂ T (x , α) et

cmT (x ,α)(D,−∇f (x)) = maxd∈D

d>[−∇f (x)]‖d‖‖PT (x ,α)[−∇f (x)]‖

≥ κ.

Avec des ensembles à descente κ-admissible : convergence + bornessur la complexité (analyse similaire au cas sans contraintes).

D⊕ ∩ T (x , α) est toujours à descente 1√n-admissible.


Descente admissible probabiliste

Dé�nition

Une suite {Dk} est à descente (probabiliste) (p, κ)-admissible si

P (cmT0(D0,−∇f (x0)) ≥ κ) ≥ p

∀k ≥ 1, P(cmTk

(Dk ,−∇f (Xk)) ≥ κ∣∣ D0, . . . ,Dk−1

)≥ p.

avec Tk = T (Xk ,Ak).

Garanties théoriques

Su {Dk} est à descente (p, κ)-admissible avec p > p0,

Convergence presque sûre vers un point stationnaire;

Borne de complexité en probabilité :

P(Nε ≤ O

(r(κ ε)−2

p − p0

))≥ 1− exp

(−O

(p − p0

p(κε)−2

)).


Directions aléatoires

Principales di�cultés

Dé�nir des ensembles à descente probabiliste admissible.

Estimer r et κ.

Utiliser moins de directions que dans le cas déterministe ?

Nos techniques

Basées sur les générateurs du cône tangent (le choix déterministe);

Directions aléatoires mais admissibles;

Au pire aussi coûteuses que la stratégie déterministe.


Directions aléatoires

Principales di�cultés

Dé�nir des ensembles à descente probabiliste admissible.

Estimer r et κ.

Utiliser moins de directions que dans le cas déterministe ?

Nos techniques

Basées sur les générateurs du cône tangent (le choix déterministe);

Directions aléatoires mais admissibles;

Au pire aussi coûteuses que la stratégie déterministe.


Premier choix de directions

Echantillonnage aléatoire parmi les générateurs

1 Calcul d'un ensemble déterministe Vk générant Tk ;

2 Tirer au hasard Dk ⊂ Vk de taille > |Vk |p0;3 {Dk} est à descente (p, κ)-admissible avec p > p0.


Premier choix de directions

Echantillonnage aléatoire parmi les générateurs

1 Calcul d'un ensemble déterministe Vk générant Tk ;

2 Tirer au hasard Dk ⊂ Vk de taille > |Vk |p0;3 {Dk} est à descente (p, κ)-admissible avec p > p0.

p0 = 1/2


Utiliser des sous-espaces et (donc) moins de directions

Principe

Cas sans contraintes : besoin de peu de directions;

Idem avec contraintes d'égalité : problème sans contraintes dans lenoyau de A;

Béné�que d'exploiter les sous-espaces non contraints ?

Lemme

Soit Sk un sous-espace inclus dans un cône Tk . Alors on a Tk = Sk + T c

k,

où T c

kest un cône inclus dans S⊥

k.


Second choix de directions

Deux types de vecteurs

Sous-espace Sk : Directions aléatoires;

Complément T c

k: Sous-ensemble aléatoire des générateurs.

xkSk = ∅

T c

k p0 = 1/2





Complément T c


xk

Sk

T c

k

p0 = 1/2





Complément T c


xk

Sk

T c

k= ∅

p0 = 1/2


Impact sur la complexité

Borne générale : O(rκ−2ε−2

).

Comparaison - Egalités linéaires

Méthode r κ Borne

Déterm. 2(n −m) 1√n−m O

((n −m)2ε−2

)Proba. 1 O(2(n −m)p0)

1√n−m O

((n −m)2ε−2

)Proba. 2 (subspace) O(1) τ√

n−m O((n −m)ε−2

)Comparaison - Contraintes d'intervalle sur nb < n variables seulement

Méthode r κ Borne

Déterm. 2n 1√n

O(n2ε−2

)Proba. 1 O(2np0) 1√

nO(n2ε−2

)Proba. 2 (subspace) O(1) +O (nb p0)

1√nO(n nbε

−2)Propriétés probabilistes en optimisation sans et avec dérivées 46

Résultats numériques - contraintes d'intervalle

Comparaison avec le solveur patternsearch de MATLAB.

Quatre méthodes

Nom Directions dans T (xk , αk) = Tk = Sk + T c

kGaranties

dspfd-0 D⊕ ∩ Tk , ordre aléatoire Déterm.dspfd-1 Tirage aléatoire dans D⊕ ∩ Tk Proba.dspfd-2 Vecteurs dans Sk/tirage dans D⊕ ∩ T c

kProba.

matlab D⊕ ∩ T (xk , tαk), t ∈ (0, 1) Déterm.

Pro�ls de performance

Critère : # d'appels à f (budget de 2000n) pour satisfaire

f (xk)− fbest < 10−3(f (x0)− fbest).

Problèmes de la bibliothèque CUTEst.


Pro�ls avec contraintes d'intervalles

63 problèmes avec contraintes d'intervalles, de petites tailles :2 ≤ n ≤ 20.

0 1 2 3 4 5 6 7 8 90

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

dspfd-0

dspfd-1

dspfd-2

matlab


Pro�ls avec contraintes d'intervalles (2)

31 problèmes avec contraintes d'intervalles, de tailles plus grandes :

20 ≤ n ≤ 52.

0 1 2 3 4 50

0.2

0.4

0.6

0.8

1

dspfd-0

dspfd-1

dspfd-2

matlab


Outline






Contexte

minx∈Rn

f (x)

f de classe C2,f en général non convexe.

Du premier ordre au second dans les algorithmes

L'accès à la matrice Hessienne est coûteux...

...tout comme l'algèbre linéaire associée:

Vecteurs propres;Systèmes linéaires.

Peut-on s'aider de propriétés probabilistes ?


Un thème de recherche actif

Analyse probabiliste de méthodes d'algèbre linéaire

Avec un point initial aléatoire...

La puissance itérée trouve un vecteur propre à ε près en O(ε−1)

itérations;

La méthode de Lanczos trouve un vecteur propre à ε près enO(ε−1/2

)itérations.

...avec une forte probabilité.

Utilité

En lien avec les méthodes de premier ordre;

Pour problèmes convexes et non convexes.


Convergence d'ordre deux

Points clés

Echapper aux points selles;

Détecter les valeur propres négatives de la matrice Hessienne;

Utiliser des directions de courbure négative;

Les meilleures méthodes en terme de complexité garantissent laconvergence à l'ordre deux !


Notre approche

Revisiter les méthodes e�caces en pratique;

Via leur analyse de complexité;

Incorporer des progrès récents.

Blocs de base

Méthodes de Newton-Krylov (ex : gradient conjugué):Basées sur des produits matrice/vecteur.

Recherches linéaires;

Analyse probabiliste.


Conclusions

Problèmes sans contraintes

Convergence via propriétés probabilistes.

Moins d'évaluations en théorie et en pratique.

Direct search based on probabilistic descent. Gratton, Royer,Vicente and Zhang, SIAM J. Optim., 2015.

Problèmes avec contraintes linéaires

Descente probabiliste admissible.

Se ramener à des sous-espaces �non contraints".

Méthode e�cace en pratique.

Direct search based on probabilistic feasible descent for bound

and linearly constrained problems. Gratton, Royer, Vicente andZhang, Submitted, 2017.


A suivre

Cas sans dérivées

Contraintes non linéaires;Parallélisation.

Contexte général

Etude de complexité;Courbure négative.

Merci de votre attention !

[email protected]


A suivre

Cas sans dérivées

Contraintes non linéaires;Parallélisation.

Contexte général

Etude de complexité;Courbure négative.

Merci de votre attention !

[email protected]


Documents

Propriétés probabilistes dans les algorithmes d