Discussion :

[le fab]

Hello

j'ai une question un peu pointue en optimisation
déjà, je place le contexte :
je fais une optimisation du productible annuel d'une centrale Hydro éléctrique
ce que je fais est très inspiré de ca

pour faire bref, une optimisation via quadprog sous MATLAB (il faut que je m'arrange pour que mon problème soit quadratique) pour des raisons de rapidité et de mémoire (fmincon trop gourmand en l’occurrence)

mes inconnues sont le débit turbiné et le débit déchargé sur des pas de 8h sur 1 an
soit près de 2190 variables !
et à peu près autant de paramètres

un des avantages de quadprod c'est que je n'ai pas a écrire ma fonction à optimiser (fonction de 2200 variables et 2200 paramètres ... sic) mais sa matrice hessian H et un vecteur f. la symbolic math toolbox m'y aide bien

et maintenant arrive mon problème
j'utilise de préférence l'algorithme 'interior point convex' qui nécessite que mon problème soit convexe ... ce qui est en général le cas
cependant, parfois mon problème ne l'est pas (quadprog me retourne une erreur) et je passe alors en algo 'active set', qui prend plus de temps, qui me trouve une solution, un minimum local, dont je ne suis pas sur qu'il soit global (puisque mon problème n'est pas convexe). en fait je suis même sur que ce n'est pas un minimum global (de visu la solution ne peut pas être la meilleure)

et je passe d'un problème convexe à un problème non convexe en changeant juste un paramètre simple
ex : prix de l'énergie 50€/MWh -> pb convexe
prix de l'énergie 400€/MWh -> pb non convexe
sic

et voici ma question
comment déterminer que mon pb est convexe ou non (hors retour de quadprog), et comprendre pourquoi afin de mieux gérer mes paramètres de manière à toujours avoir un problème convexe (et donc de toujours trouver un minimum global)
H est toujours composée de réels positifs ou nuls, f de réels négatifs ou nul, à priori c'est pas par là que ça se passe
je re précise que j'ai la symbolic math toolbox. peut être contient elle des outils pouvant m'aider ?

si y a une pointure en optimisation qui passe par là ...

Fabien

[Aleph69]

Salut,

une fonction est (strictement) convexe/concave si et seulement si sa matrice hessienne est (strictement) positive/négative.
Concrètement, pour déterminer la convexité, j'opterais pour cette solution mais il y a sûrement plus efficace :
1. calcul de la plus petite valeur propre lp et plus grande valeur propre lg de H en module;
2. si lp et lg sont (strictement) positives/négatives, la fonction est (strictement) convexe/concave;
3. sinon, il s'agit d'un problème de point-selle

[le fab]

Salut

et merci pour ta réponse
réponse que j'intuitais ... mais qui ne me va pas :
en effet, dans TOUS les cas, ma matrice Hessienne est positive, cad contient des valeurs strictement positives ET des valeurs nulles
bref, dans TOUS les cas, mon problème est convexe (jamais strictement). (ce qui me rassure dans mon travail préparatoire )

MAIS, Matlab, plus précisément quadprog avec l'algorithme interior point convex me dit parfois que mon problème n'est pas convexe et qu'il ne peut pas le résoudre
bref, peut être plus un problème matlab que mathématique

j'ai trouvé une "parade" en normalisant un des mes paramètres : mon vecteur cout de l'énergie : ça marche dans des cas qui ne marchaient pas avant, mais je ne suis pas sur de de pas tomber sur d'autre soucis de convexitude avec d'autres scénarii (d'autant qu'il me reste des soucis "pas graves" de ce coté que j'arrive à contourner, mais bon ....)

Fabien

[Alexis.M]

Je ne sais pas quelles sont les vérifications faites par la fonction d'optimisation mais si tu dis que ton problème n'est pas 'strictement' convexe cela signifie que tu as quelques valeurs propres nulles. Aux arrondis machine près il est possible que certaines d'entre elles soient calculées comme négatives (du genre -1e-15) ce qui entraîne le problème.

[le fab]

Salut et merci de ta réponse

en fait j'ai un peu avancé sur le sujet
comme je le disait ma matrice Hessian est bien composée de valeur positives ou nulles, mais à des valeurs propres (eigenvalues ) négatives (et positives et nulles)
mon problèmes n'est donc pas convexe !
(désolé, ma nullité en maths a fait que je n'avait pas pris les valeurs propres mais les valeurs tout court contenues dans la matrice)

Mais il l'est (en général) dans le domaine faisable (c'est à dire contraint par les contraintes passée à l'optimiseur).
Pour info, dans l'optimiseur quadprog, les contraintes sont des contraintes linéaires du type A*x<=b , Aeq*x=beq et lb<=x<ub, ou A et Aeq sont des matrices, x,b,beq,lb et ub des vecteurs.

et donc c'est là que se situe mon soucis :
c'est qu'en modifiant certains paramètres, ma matrice hessian est modifiée (normal) mais mes contraintes restent à l'identique. ce qui fait que pour certaines valeurs de ces paramètres, mon problème devient non convexe dans le domaine limité par ces contraintes

d'ou la sortie en erreur de la fonction quadprog, qui commence par vérifier que mon problème est bien convexe DANS le domaine contraint (faisable)

du coup là ou je bloque aujourd'hui, c'est comment vérifier que mon problème est bien convexe DANS le domaine contraint ??

aujourd'hui je sais vérifier que mon problème n'est globalement pas convexe (valeurs propres négatives et positives), mais je ne sais pas comment faire cette vérification seulement dans le domaine faisable (en dehors de lancer la fonction d'optimisation et attendre un éventuel code d'erreur en retour)
si quelqu’un a une idée, je suis preneur

désolé je tatone, mais les maths, c'est un peu loin pour moi

Fab

[Alexis.M]

Peut-être serait-il bon que tu nous donnes plus de précision sur le problème de départ. Sa forme analytique par exemple.

[le fab]

Salut

bon tout d'abord j'ai en parallèle des échanges avec le responsable optimisation chez mathworks, et sa dernière réponse est qu'il ne connait pas d'autre méthode pour déterminer si le problème est convexe sur le domaine contraint que d'utiliser la fonction quadprog et de regarder le flag de retour.
de plus lui connait précisément mon problème de départ puisqu'il est l'auteur de l'exemple (en lien dans mon premier post) à partir duquel je suis parti
bref, je pense avoir fait un peu le tour de la question, malheureusement.

je marque donc ce sujet comme résolu et remercie ceux qui l'ont lu

Fabien

PS : Alexis.M, si tu souhaites voir néanmoins plus de précisions sur le problème, il est relativement clairement formulé dans la fonction HydroelectricDamOptimization de l'exemple téléchargeable via mon premier lien de mon premier post.