contractor KKT without rigor mode

[bneveu]

with KKT contractor and without rigor mode, the optimizer cannot find the optimal solution :
(ibex 2.8.3)
ex7_2_5.bch

../../../bin/ibexopt ../benchs/easy/ex7_2_5.bch --kkt -r 1.e-6 -a 1.e-6
running............

unreached precision

f* in [10122.4932382,10145.3622818]
(best bound)

x* = (78 ; 33 ; 30.0590509888 ; 45 ; 36.8136491705)
(best feasible point)

relative precision on f*: 0.00225413769565
absolute precision on f*: 22.8690435552
cpu time used: 0.183157000001s
number of cells: 432

---

without kkt
../../../bin/ibexopt ../benchs/easy/ex7_2_5.bch -r 1.e-6 -a 1.e-6

optimization successful!

f* in [10122.483123,10122.4932455]
(best bound)

x* = (78 ; 33 ; 29.9957400551 ; 45 ; 36.7753270585)
(best feasible point)

relative precision on f*: 9.99999999874e-07 [passed]
absolute precision on f*: 0.0101224932442
cpu time used: 0.0190170000001s
number of cells: 16

---

with rigor mode
../../../bin/ibexopt ../benchs/easy/ex7_2_5.bch -r 1.e-6 -a 1.e-6 --rigor --kkt

optimization successful!

f* in [10122.4831157,10122.4932382]
(best bound)

x* in (<78, 78> ; <33, 33> ; [29.99574002530507, 29.99574002530512] ; <45, 45> ; [36.77532709353545, 36.77532709353551])
(best feasible point)

relative precision on f*: 9.999999998719125e-07 [passed]
absolute precision on f*: 0.01012249323684956
cpu time used: 0.01828700000000001s
number of cells: 14

[gchabert]

Je ne suis pas sûr qu'il s'agisse d'un bug. Et pour dire la vérité, j'étais surpris que cela ne se soit pas produit jusqu'ici!

La particularité du contracteur KKT est qu'il contracte les boîtes indépendament du loup courant, c'est à dire qu'il peut très bien supprimer un vecteur x admissible tel que f(x)<=loup, chose qu'un contracteur "classique" ne fait jamais. Du coup, s'il fonctionne "trop bien", il réduit une boîte avant qu'on ait pu trouvé un loup. En particulier, les conditions KKT peuvent faire qu'une inégalité est activée, auquel cas la contracteur revient à appliquer une égalité, qui n'est pas "épaissie". Le problème n'est donc pas vraiment le contracteur KKT mais plutôt le LoupFinder basé sur les linéarisations intérieures qui n'est plus assez efficace; il faut une recherche de loup qui gère les égalités et sorte éventuellement de la boîte courante , ce que fait précisément le LoupFinderCertify lorsque --rigor est activé.

En conclusion, il faut sans doute basculer en mode rigoureux dès que KKT est activé, même si le problème initial ne comporte que des inégalités. A confirmer...

[gchabert]

Note: KuhnTuckerLP fonctionne lui sans --rigor sur ce bench. Ce n'est pas évident de savoir pourquoi: peut-être parce que XNewton est moins contractant que Newton (une histoire de point fixe?), peut-être aussi est-ce un hasard. Je n'ai pas creusé plus.

[bneveu]

J'ai quand même du mal à comprendre que ce contracteur coupe la branche où se trouve l'optimum, sans qu'il y ait de bug, quand il n'y a que des inégalités: cet exemple ex7_2_5 est peut être particulier car certaines variables ont leur valeur optimale sur les bords de la boîte initiale ?
Même s'il ne trouve pas de loup dans la boite courante, il devrait continuer de bissecter (il n'y a plus de limite sur la boite dans ibexopt ?) , or on s'arrête à 426 boites et si la boite est toute petite, son évaluation en un point devrait donner le bon loup.

[gchabert]

Le contracteur ne perd pas l'optimum, d'ailleurs on a le bon uplo à la fin. Mon hypothèse est qu'il contracte trop les boîtes pour permettre d'y trouver un loup. Ca s'applique aussi aux toutes petites boîtes. Du coup, faute de loup, il y a moins d'upper-bounding dans la recherche donc plus de bissection ce qui explique le nombre plus important de boîtes total (>400).

[bneveu]

oui, mais l'optimiseur ne devrait pas s'arrêter de bissecter avant d'avoir une boite qui n'est plus bissectable (c.a.d quasi ponctuelle)
La simple évaluation de la fonction sur cette boite devrait trouver l'optimum.

[gchabert]

L'optimiseur finit effectivement par tomber sur des boîtes non bissectables (on le voit avec --trace). Mais la simple évaluation ne fonctionne pas car les petites boîtes se trouvent pile à la frontière des inégalités (l'optimum n'est pas à l'intérieur du domaine).

[bneveu]

J'ai regardé la trace. Effectivement un point optimal est trouvé, mais est rejeté par le test is_inner
qui semble être trop fort.
En effet, en évaluant les contraintes sur le point trouvé, on a
vector cts ([-1.309991036042206, -1.309991036042205] ; [-0, 6.66133814775094e-16] ; [-1.02137997023271057, -1.021379970271055] ; [-0.3785973391150664, -0.3785973391150658] ; [-1.9984014445282e-15, -4.440892098500626e-16] ; [-0.3184830116553233, -0.3184830116553227])
la deuxième est pratiquement à 0.
Comme on évalue une boite dégénérée, ne pourrait-on pas remplacer ce test par f_ctrs[i].eval.lb(pt) <= 0

[gchabert]

Comme on évalue une boite dégénérée, ne pourrait-on pas remplacer ce test par f_ctrs[i].eval.lb(pt) <= 0

On perdrait en rigueur... Autant utiliser le LoupFinderCertify non (--rigor) ?

[bneveu]

C'est vrai, mais
je regarde quand même si ça améliore les résultats en temps de calcul.
Dans l'article d'Antigone, ils vérifient les contraintes (égalités et inégalités) à 1.e-4.
On pourrait sans honte vérifier f_ctrs[i].eval.ub() <= eps_h

J'ai commencé à essayer le mode --rigor, mais dès les premiers essais, je n'obtiens pas le bon optimum pour ex2_1_9 et ex5_4_4_ (cf issue #411)

[bneveu]

Ça ne marche pas vraiment. Il reste des cas unreached precision.
Je pense qu'il faut pour le moment ne pas utiliser kkt en mode normal.
kktLP marche, mais avec un surcoût prohibitif.

[gchabert]

Ok, si je résume ce ticket et #404, on pourrait appliquer la chose suivante:

• si le problème est sans contrainte: on applique kkt par défaut
• s'il y a des contraintes :
  • on n'applique pas kkt par défaut
  • si l'utilisateur force le recours à kkt via --kkt, l'optimiseur bascule automatiquement en mode rigor car c'est nécessaire avec des égalités (sinon, risque de perte d'optimalité) et fortement souhaitable avec des inégalités (car difficulté à trouver des loups).

Ok pour toi?
(note: actuellement, il se produit l'inverse, kkt est automatiquement désactivé si on n'est pas en mode rigor et en présence d'égalités)

[bneveu]

Oui, ce me semble bon.

J'ai comparé rapidement le mode rigor avec et sans kkt.
Ce n'est pas évident de savoir si kkt est bénéfique : il obtient des gains importants (entre 20% et un facteur 2) sur douze instances et des pertes significatives mais limitées (entre 10% et 20%)
sur trente instances et importantes sur 2 instances (facteur 2 sur ex7_2_9 , entre 1.5 et 2 sur srcpm).
Il faudrait faire une analyse plus en profondeur.

[gchabert]

Effectivement, je proposais kkt=>rigor mais pas forcément rigor=>kkt. Merci du coup pour l'analyse de perf; c'est vrai qu'en l'état, c'est difficile de se faire un avis et il y a sans doute quelque chose à comprendre en décortiquant les résolutions... mais c'est un boulot très fastidieux. En attendant, on garde donc les deux options --rigor et --kkt. Je fais la modif et je clos le ticket.

[gchabert]

Juste un détail néanmoins: si on applique kkt dans le cas sans contrainte, il faut donc aussi passer en mode rigor systématiquement. Normalement, on ne devrait pas perdre en temps puisqu'il n'y a pas de contrainte à vérifier (hormis les bords de la boîte), mais je préfère prévenir... !

[bneveu]

Pourquoi doit-on passer en mode rigor, s'il n'y a pas de contrainte ?
Il n'y a pas de risque de point faisable rejeté.
Ceci dit, sur quelques exemples testés, cela semble n'avoir aucune influence sur le nombre de noeuds, juste un surcoût de 1%, à la limite du significatif.

[gchabert]

C'est dans le cas où le point se situe au bord de la boîte. KKT peut réduire le domaine à un intervalle trop petit pour y trouver un loup.

[bneveu]

Je ne vois pas le problème. Tout point étant par définition faisable, il suffit d'évaluer un point de cette petite boite.

[gchabert]

Ah oui, j'ai craqué... même si on a une boîte réduite à un flottant ça ne pose pas de problème !
C'est l'avantage des contraintes de bornes :-D

[gchabert]

C'est bon. A mon sens, il devenait nécessaire de créer une classe intermédiaire pour proprement configurer l'optimiseur (il y avait trop de paramètres à passer au constructeur d'Optimizer, et certains étaient initialisés hors-constructeur, bref, c'était la pagaille). J'en ai profité pour reprendre et supprimer un vieux code inutilisé de 2014 qui était censé faire cela.
Au passage, j'ai créé une classe Optimizer04Config (dans optim/src/strategy) qui reprend exactement l'actuel optimizer04. Cela veut dire que tu peux remplacer le code de ton exécutable optimizer04.cpp par le suivant:

#include "ibex.h"

using namespace ibex;

int main(int argc, char** argv) {
  Optimizer04Config config(argc, argv);	
  Optimizer o(config);
  o.optimize(config.sys->box);
  o.report();     // printing the results     
}

Si ça te plaît, on peut conserver cette nouvelle classe Optimizer04Config dans le plugin optim, ce qui t'éviterait de devoir le mettre à jour en parallèle d'ibex. L'autre avantage est qu'on pourrait aussi instancier cet optimiseur depuis C++ (et pas seulement l'avoir en exécutable). Qu'en penses-tu?

[bneveu]

Ça me paraît bien.
L'idée est de modifier ce fichier quand on ajoute ou change un paramétrage ?
Il faudrait ajouter le kkt pour les problèmes non contraints dans Optimizer04Config::get_ctc(
J'ai essayé en mettant à la fin de la fonction
if (sys->nb_ctr == 0){
ctckkt = &rec(new CtcKuhnTucker(*norm_sys, true));
ctcxn = &rec(new CtcCompo (*ctc, *ctckkt));
}

mais je ne retrouve pas exactement la même exécution qu'avec la nouvelle version ibexopt incluant kkt pour les problèmes non contraints
Pourtant, il me semble que le paramétrage suivant est le même.(avce optimizer04 le nouvel optimiseur générique)
./optimizer04 ../benchs/benchs-unconstrainedoptim/dixon-price20.bch acidhc4 xn lsmearmg bs 1 0 1.e-6 1000 1
f* in [0,3.5306e-07]
(best bound)

x* = (1.0003 ; 0.707154 ; 0.594616 ; 0.545259 ; 0.522184 ; 0.511022 ; 0.505496 ; 0.502741 ; 0.501371 ; 0.500701 ; 0.500353 ; 0.500188 ; 0.500094 ; 0.500053 ; 0.500039 ; 0.500039 ; 0.500007 ; 0.500025 ; 0.500005 ; -0.499999)
(best feasible point)

relative precision on f*: inf
absolute precision on f*: 3.5306e-07 [passed]
cpu time used: 0.729397s
number of cells: 2684

../../../bin/ibexopt ../benchs/benchs-unconstrainedoptim/dixon-price20.bch -a 1.e-6 -r 1.e-6
f* in [0,5.33753235388e-07]
(best bound)

x* = (0.99993684425 ; 0.707166325102 ; 0.594622821729 ; 0.545326337799 ; 0.522197912537 ; 0.511023029996 ; 0.505530807283 ; 0.502782029065 ; 0.501413080298 ; 0.500688176443 ; 0.500355584352 ; 0.500183933701 ; 0.500113796099 ; 0.500057341458 ; 0.500055298811 ; 0.500058258775 ; 0.500043492043 ; 0.500030532877 ; 0.500020122734 ; -0.500006399851)
(best feasible point)

relative precision on f*: inf
absolute precision on f*: 5.33753235388e-07 [passed]
cpu time used: 2.77536600001s
number of cells: 2422

[bneveu]

J'ai remis OptimLargestFirst comme bissecteur de substitution dans LSmear et LSmearmg dans Optimizer04Config , comme
dans DefaultOptimizerConfig, mais la résolution est toujours différente.

./optimizer04 ../benchs/benchs-unconstrainedoptim/dixon-price20.bch acidhc4 xn lsmearmg bs 1 0 1.e-6 1000 1
f* in [0,6.97026e-07]
(best bound)

x* = (1.00016 ; 0.70705 ; 0.594537 ; 0.545211 ; 0.52209 ; 0.510891 ; 0.505374 ; 0.502691 ; 0.501383 ; 0.500743 ; 0.500406 ; 0.500216 ; 0.500116 ; 0.500072 ; 0.500055 ; 0.500045 ; 0.500044 ; 0.500013 ; 0.500021 ; -0.500002)
(best feasible point)

relative precision on f*: inf
absolute precision on f*: 6.97026e-07 [passed]
cpu time used: 0.584158s
number of cells: 1626

[bneveu]

Avec les dernières mises à jour de Optimizer04Config pour que DefaultOptimizerConfig soit un cas
particulier, le problème est réglé.

Pour éviter la duplication du code, il serait peut-être bien que DefaultOptimizerConfig appelle
Optimizer04Config avec un paramétrage particulier.