Un Algorithme Parall Le Pour Les Probl Mes D Optimisation Quadratique Convexes De Grande Taille Dont La Structure Est Issue De La Discr Tisation De Probl Mes De Contr Le Optimal

Un algorithme parallèle pour les problèmes d'optimisation quadratique convexes de grande taille dont la structure est issue de la discrétisation de problèmes de contrôle optimal

L'OBJET DE CE MEMOIRE EST L'ETUDE NUMERIQUE D'UNE METHODE DE RESOLUTION DES PROBLEMES DE CONTROLE OPTIMAL AVEC CONTRAINTES SUR L'ETAT BASEE SUR L'UTILISATION DES TECHNIQUES DE PROGRAMMATION MATHEMATIQUE AVEC CONTRAINTES. L'IDEE DE BASE DE LA METHODE CONSISTE A APPROCHER LES FONCTIONS INCONNUES: L'ETAT ET LA COMMANDE, PAR DES POLYNOMES D'INTERPOLATION ET A TRAITER LE SYSTEME DIFFERENTIEL TRADUISANT LA DYNAMIQUE DU PROBLEME PAR COLLOCATION. LE PROBLEME DE PROGRAMMATION MATHEMATIQUE RESULTANT, QUI POSSEDE UNE STRUCTURE DE CONTRAINTES EN ESCALIER, SERA RESOLU PAR LA METHODE DE PROGRAMMATION SEQUENTIELLE QUADRATIQUE (S.Q.P). NOUS EXPOSERONS L'IMPLEMENTATION QUI A ETE FAITE DE CET ALGORITHME AINSI QUE DES DIAGNOSTIQUES DE DIFFICULTES NUMERIQUES RENCONTREES. NOUS CONSTRUIRONS ENSUITE UN ALGORITHME DE DECOMPOSITION PARALLELE POUR PROBLEMES D'OPTIMISATION QUADRATIQUE A CONTRAINTES LINEAIRES EN ESCALIER, PROBLEMES QUE L'ON DOIT RESOUDRE A CHAQUE ITERATION DE LA METHODE S.Q.P. POUR CALCULER LA DIRECTION DE DESCENTE. CET ALGORITHME, BASE SUR LES METHODES ITERATIVES D'ALGEBRE LINEAIRE, ET NOTAMMENT SUR L'ALGORITHME SEMI-ITERATIF DE TCHEYBYCHEFF, FERA APPARAITRE LE PARALLELISME GRACE A UNE TRANSFORMATION PREALABLE (OU MANIPULATION) DU PROBLEME A TRAITER. CE PARALLELISME CONSISTERA EN LA RESOLUTION SIMULTANEE DE PROBLEMES QUADRATIQUES DE PETITE TAILLE. NOUS TESTERONS EN ENVIRONNEMENT SEQUENTIEL LE COMPORTEMENT NUMERIQUE DE L'ALGORITHME ET NOTAMMENT L'INFLUENCE DE LA MANIPULATION DU PROBLEME SUR LA PRECISION DES RESULTATS, PUIS NOUS EFFECTUERONS DES MESURES DE GAINS EN TEMPS DE CALCUL EN ENVIRONNEMENT PARALLELE. NOUS CONCLURONS ENFIN, EN DONNANT QUELQUES EXEMPLES DE PROBLEMES DE CONTROLE OPTIMAL RESOLUS VIA LA METHODE S.Q.P.

Un algorithme parallele pour les problemes d'optimisation quadratique convexes de grande taille dont la structure est issue de la discretisation de problemes de controle optimal

Modèles quadratiques et décomposition parallèle pour l'optimisation sans dérivées

L'optimisation sans dérivées (DFO) et l'optimisation de boites noires (BBO) sont deux disciplines qui traitent des problèmes dont la formulation analytique est inaccessible partiellement ou totalement et qui résultent souvent de simulations informatiques. Les algorithmes DFO et BBO s'appliquent typiquement à des problèmes de petite dimension. Parmi ces méthodes, l'algorithme de recherche directe par treillis adaptatifs (MADS) est une méthode itérative qui se base sur une discrétisation de l'espace et des directions de recherche pour sélectionner et évaluer des points de l'espace. Cette thèse explore deux extensions de MADS qui permettent d'améliorer les résultats de la méthode ainsi que de s'attaquer à des problèmes de plus grande taille. Dans la première extension, MADS utilise des modèles dans l'étape de recherche menant à la création d'une série de sous-problèmes quadratiques avec contraintes quadratiques. Deux méthodes d'optimisation non linéaire classiques sont décrites : la fonction de pénalité exacte en norme `1 et le Lagrangien augmenté. De plus, une nouvelle méthode nommée le Lagrangien augmenté en norme `1 combine les points forts des deux algorithmes précédents. Cette dernière méthode est bien adaptée pour les problèmes quadratiques avec contraintes quadratiques vu qu'elle se base sur un terme de pénalité en norme `1 qui permet de traiter un problème quadratique par morceaux au lieu d'un problème quartique si le Lagrangien augmenté standard est utilisé. La nouvelle méthode du Lagrangien augmenté en norme `1 est décrite pour les problèmes non linéaires avec des contraintes d'égalités. Une analyse conduite sur l'itération interne de l'algorithme prouve que la convergence vers un point stationnaire se fait avec une vitesse surperlinéaire en deux étapes. De plus, l'analyse de l'itération externe de la méthode établit que l'algorithme converge globalement et que le paramètre de pénalité est borné. Dans la seconde extension, l'algorithme de décomposition parallèle de l'espace de la recherche directe par treillis adaptatifs (PSD-MADS), qui est une méthode parallèle asynchrone pour les problèmes de boites noires de grande taille, utilise une stratégie de sélection aléatoire des variables pour la construction des sous-problèmes. Plusieurs stratégies sont proposées pour sélectionner les variables les plus influentes du problème et explorer l'espace des solutions de manière plus efficace. Ces stratégies se basent sur des outils statistiques pour évaluer l'influence des variables sur les différentes sorties et sur la méthode de classification k-mean pour grouper les variables avec plus ou moins le même niveau d'influence. De plus, une méthode hybride qui combine cette nouvelle stratégie avec l'approche aléatoire de sélection de variables est présentée. Les nouvelles méthodes améliorent les résultats de PSD-MADS et les tests numériques sont conduits sur des problèmes de taille allant jusqu'à 4000 variables.