Academic literature on the topic 'Optimisation nonconvexe'

We give a formula on the ε−subdifferential of the difference of two convex functions. As a by-product of this formula, one recovers a recent result of Hiriart-Urruty, namely, a necessary and sufficient condition for global optimality in nonconvex optimisation.

AbstractLinear multiplicative programs are an important class of nonconvex optimisation problems that are currently the subject of considerable research as regards the development of computational algorithms. In this paper, we show that mathematical programs of this nature are, in fact, a special case of more general signomial programming, which in turn implies that research on this latter problem may be valuable in analysing and solving linear multiplicative programs. In particular, we use signomial programming duality theory to establish a dual program for a nonconvex linear multiplicative program. An interpretation of the dual variables is given.

Même si l'optimisation non linéaire semble (a priori) être un domaine mature, de nouveaux schémas de minimisation sont proposés ou redécouverts pour les problèmes modernes à grande échelle. A titre d'exemple et en rétrospective de la dernière décennie, nous avons vu une vague de méthodes du premier ordre avec différentes analyses, malgré le fait que les limitations théoriques bien connues de ces méthodes ont été discutées en profondeur auparavant. Cette thèse explore deux lignes principales de recherche dans le domaine de l'optimisation non-convexe avec un accent particulier sur les méthodes de second ordre et d'ordre supérieur. Dans la première série de travaux, nous nous concentrons sur les algorithmes qui ne calculent pas les valeurs des fonctions et opèrent sans connaissance d'aucun paramètre, car les méthodes du premier ordre les plus adaptées pour les problèmes modernes appartiennent à cette dernière catégorie. Nous commençons par redéfinir l'algorithme bien connu d'Adagrad dans un cadre de région de confiance et utilisons ce dernier paradigme pour étudier deux classes d'algorithmes OFFO (Objective-Free Function Optimization) déterministes du premier ordre. Pour permettre des algorithmes OFFO exacts plus rapides, nous proposons ensuite une méthode de régularisation adaptative déterministe d'ordre p qui évite le calcul des valeurs de la fonction. Cette approche permet de retrouver la vitesse de convergence bien connu du cadre standard lors de la recherche de points stationnaires, tout en utilisant beaucoup moins d'informations. Dans une deuxième série de travaux, nous analysons les algorithmes adaptatifs dans le cadre plus classique où les valeurs des fonctions sont utilisées pour adapter les paramètres. Nous étendons les méthodes de régularisation adaptatives à une classe spécifique d'espaces de Banach en développant un algorithme de descente du gradient de Hölder. En plus, nous étudions un algorithme de second ordre qui alterne entre la courbure négative et les étapes de Newton avec une vitesse de convergence quasi optimal. Pour traiter les problèmes de grande taille, nous proposons des versions sous-espace de l'algorithme qui montrent des performances numériques prometteuses. Dans l'ensemble, cette recherche couvre un large éventail de techniques d'optimisation et fournit des informations et des contributions précieuses aux algorithmes d'optimisation adaptatifs et sans paramètres pour les fonctions non convexes. Elle ouvre également la voie à des développements théoriques ultérieurs et à l'introduction d'algorithmes numériques plus rapides
Even though nonlinear optimization seems (a priori) to be a mature field, new minimization schemes are proposed or rediscovered for modern large-scale problems. As an example and in retrospect of the last decade, we have seen a surge of first-order methods with different analysis, despite the fact that well-known theoretical limitations of the previous methods have been thoroughly discussed.This thesis explores two main lines of research in the field of nonconvex optimization with a narrow focus on second and higher order methods.In the first series, we focus on algorithms that do not compute function values and operate without knowledge of any parameters, as the most popular currently used first-order methods fall into the latter category. We start by redefining the well-known Adagrad algorithm in a trust-region framework and use the latter paradigm to study two first-order deterministic OFFO (Objective-Free Function Optimization) classes. To enable faster exact OFFO algorithms, we then propose a pth-order deterministic adaptive regularization method that avoids the computation of function values. This approach recovers the well-known convergence rate of the standard framework when searching for stationary points, while using significantly less information.In the second set of papers, we analyze adaptive algorithms in the more classical framework where function values are used to adapt parameters. We extend adaptive regularization methods to a specific class of Banach spaces by developing a Hölder gradient descent algorithm. In addition, we investigate a second-order algorithm that alternates between negative curvature and Newton steps with a near-optimal convergence rate. To handle large problems, we propose subspace versions of the algorithm that show promising numerical performance.Overall, this research covers a wide range of optimization techniques and provides valuable insights and contributions to both parameter-free and adaptive optimization algorithms for nonconvex functions. It also opens the door for subsequent theoretical developments and the introduction of faster numerical algorithms

As many-objective optimisation problems become more prevalent, evolutionary algorithms that are based on Pareto dominance relations are slowly becoming less popular due to severe limitations that such an approach has for this class of problems. At the same time decomposition-based methods, which have been employed traditionally in mathematical programming, are consistently increasing in popularity. These developments have been led by recent research studies that show that decomposition-based algorithms have very good convergence properties compared to Pareto-based algorithms. Decomposition-based methods use a scalarising function to decompose a problem with multiple objectives into several single objective subproblems. The subproblems are defined with the help of weighting vectors. The location on the Pareto front that each subproblem tends to converge, strongly depends on the choice of weighting vectors and the scalarising function. Therefore, the selection of an appropriate set of weighting vectors to decompose the multi-objective problem, determines the distribution of the final Pareto set approximation along the Pareto front. Currently a limiting factor in decomposition-based methods is that the distribution of Pareto optimal points cannot be directly controlled, at least not to a satisfactory degree. Generalised Decomposition is introduced in this thesis as a way to optimally solve this problem and enable the analyst and the decision maker define and obtain the desired distribution of Pareto optimal solutions. Furthermore, many algorithms generate a set of Pareto optimal solutions. An interesting question is whether such a set can be used to generate more solutions in specific locations of the Pareto front. Pareto Estimation - a method introduced in this thesis - answers this question quite positively. The decision maker, using the Pareto Estimation method can request a set of solutions in a particular region on the Pareto front, and although not guaranteed to be generated in the exact location, it is shown that the spatial accuracy of the produced solutions is very high. Also the cost of generating these solutions is several orders of magnitude lower compared with the alternative to restart the optimisation.

Le problème de l'hydro-offre consiste à calculer des d'offre optimales afin de maximiser le bénéfice attendu d'un producteur hydroélectrique participant à un marché de l'électricité. Il combine le processus décisionnel du négociant et de l'hydro-répartiteur en un seul problème d'optimisation stochastique. C'est un problème de prise de décision séquentielle, et peut être formulé comme un programme stochastique à plusieurs étages.Ces modèles peuvent être difficiles à résoudre lorsque la fonction de valeur n'est pas concave. Dans cette thèse, nous étudions quelques-unes des limites du problème hydro-bidding et proposons une nouvelle méthode d'optimisation stochastique appelée le Mixed-Integer Dynamic Approximation Scheme (MIDAS). MIDAS résout des programmes stochastiques nonconvex avec des fonctions de valeurs monotones. Il fonctionne de manière similaire à la Stochastic Dual Dynamic Programming (SDDP), mais au lieu d'utiliser hyperplans, il utilise des fonctions d'étape pour créer une approximation externe de la fonction de valeur. MIDAS converge « almost surely » à (T+1)ε solution optimale quand les variables d'état continues, et à la solution optimale exacte quand les variables d'état entier.Nous utilisons MIDAS pour résoudre trois types de problèmes hydro-bidding qui sont nonconvex. Le premier modèle hydro-bidding que nous résolvons des variables d'état entier parce que des productions discrètes. Dans ce modèle, nous démontrer que les constructions MIDAS offrent qui sont meilleures que SDDP. Le prochain modèle hydro-bidding utilise processus de prix autorégressif au lieu d'une Markov chain. Le dernier modèle hydro-bidding intègre les effets d'eau de tête, où la fonction de production d'énergie dépend du niveau de stockage du réservoir et du débit d'eau de la turbine. Dans tous ces modèles, nous démontrons la convergence de MIDAS dans des itérations finies.Le temps de convergence de MIDAS est supérieur à SDDP parce que des sous-problèmes est la mixed-integer programs (MIP). Pour les modèles d'enchères hydrauliques à variables d'état continues, son temps de calcul dépend de la valeur de le δ. Si le δ est grand, alors il réduit le temps de calcul de la convergence mais il augmente également l'erreur d'optimalité ε.Afin d'accélérer le MIDAS, nous avons introduit deux heuristiques. La première heuristique est une heuristique de sélection de fonction d'étape, qui est similaire au schéma « cut selection » dans le SDDP. Cette heuristique améliore le temps de résolution jusqu'à 64%. La seconde heuristique résout itérativement les sous-problèmes MIP dans MIDAS en utilisant des MIP plus petits, plutôt que comme un seul grand MIP. Cette heuristique améliore le temps de résolution jusqu'à 60%. En appliquant les deux heuristiques, nous avons pu utiliser MIDAS pour résoudre un problème hydro-bidding avec 4 réservoirs, 4 stations et des entier variables d'état
The hydro-bidding problem is about computing optimal offer policies in order to maximize the expected profit of a hydroelectric producer participating in an electricity market. It combines the decision making process of both the trader and the hydro-dispatcher into one stochastic optimization problem. It is a sequential decision making problem, and can be formulated as a multistage stochastic program.These models can be difficult to solve when the value function is not concave. In this thesis, we study some of the limitations of the hydro-bidding problem, and propose a new stochastic optimization method called the Mixed-Integer Dynamic Approximation Scheme (MIDAS). MIDAS solves nonconvex, stochastic programs with monotonic value functions. It works in similar fashion to the Stochastic Dual Dynamic Programming (SDDP), but instead of using cutting planes, it uses step functions to create an outer approximation of the value function. MIDAS will converge almost surely to (T+1)ε optimal policies for continuous state variables, and to the exact optimum policy for integer state variables.We use MIDAS to solve three types of nonconvex hydro-bidding problem. The first hydro-bidding model we solve has integer state variables due to discrete production states. In this model we demonstrate that MIDAS constructs offer policies which are better than SDDP. The next hydro-bidding model has a mean reverting autoregressive price processs instead of a Markov chain. The last hydro-bidding incorporates headwater effects, where the power generation function is dependent on both the reservoir storage level and the turbine waterflow. In all of these models, we demonstrate convergence of MIDAS in finite iterations.MIDAS takes significantly longer to converge than SDDP due to its mixed-integer program (MIP) sub-problems. For hydro-bidding models with continuous state variables, its computation time depends on the value of δ. A larger δ reduces the computation time for convergence but also increases optimality error ε.In order to speed up MIDAS, we introduced two heuristics. The first heuristic is a step function selection heuristic, which is similar to the cut selection scheme in SDDP. This heuristic improves the solution time by up to 64%. The second heuristic iteratively solves the MIP sub-problems in MIDAS using smaller MIPs, rather than as one large MIP. This heuristic improves the solution time up to 60%. Applying both of the heuristics, we were able to use MIDAS to solve a hydro-bidding problem, consisting of a 4 reservoir, 4 station hydro scheme with integer state variables

Thesis (PhD)--Stellenbosch University, 2012
ENGLISH ABSTRACT: This dissertation addresses a number of topics that arise from the use of a dual method of sequential approximate optimisation (SAO) to solve structural optimisation problems. Said approach is widely used because it allows relatively large problems to be solved efficiently by minimising the number of expensive structural analyses required. Some extensions to traditional implementations are suggested that can serve to increase the efficacy of such algorithms. The work presented herein is concerned primarily with three topics: the use of nonconvex functions in the definition of SAO subproblems, the global convergence of the method, and the application of the dual SAO approach to large-scale problems. Additionally, a chapter is presented that focuses on the interpretation of Sigmund’s mesh independence sensitivity filter in topology optimisation. It is standard practice to formulate the approximate subproblems as strictly convex, since strict convexity is a sufficient condition to ensure that the solution of the dual problem corresponds with the unique stationary point of the primal. The incorporation of nonconvex functions in the definition of the subproblems is rarely attempted. However, many problems exhibit nonconvex behaviour that is easily represented by simple nonconvex functions. It is demonstrated herein that, under certain conditions, such functions can be fruitfully incorporated into the definition of the approximate subproblems without destroying the correspondence or uniqueness of the primal and dual solutions. Global convergence of dual SAO algorithms is examined within the context of the CCSA method, which relies on the use and manipulation of conservative convex and separable approximations. This method currently requires that a given problem and each of its subproblems be relaxed to ensure that the sequence of iterates that is produced remains feasible. A novel method, called the bounded dual, is presented as an alternative to relaxation. Infeasibility is catered for in the solution of the dual, and no relaxation-like modification is required. It is shown that when infeasibility is encountered, maximising the dual subproblem is equivalent to minimising a penalised linear combination of its constraint infeasibilities. Upon iteration, a restorative series of iterates is produced that gains feasibility, after which convergence to a feasible local minimum is assured. Two instances of the dual SAO solution of large-scale problems are addressed herein. The first is a discrete problem regarding the selection of the point-wise optimal fibre orientation in the two-dimensional minimum compliance design for fibre-reinforced composite plates. It is solved by means of the discrete dual approach, and the formulation employed gives rise to a partially separable dual problem. The second instance involves the solution of planar material distribution problems subject to local stress constraints. These are solved in a continuous sense using a sparse solver. The complexity and dimensionality of the dual is controlled by employing a constraint selection strategy in tandem with a mechanism by which inconsequential elements of the Jacobian of the active constraints are omitted. In this way, both the size of the dual and the amount of information that needs to be stored in order to define the dual are reduced.
AFRIKAANSE OPSOMMING: Hierdie proefskrif spreek ’n aantal onderwerpe aan wat spruit uit die gebruik van ’n duale metode van sekwensi¨ele benaderde optimering (SBO; sequential approximate optimisation (SAO)) om strukturele optimeringsprobleme op te los. Hierdie benadering word breedvoerig gebruik omdat dit die moontlikheid skep dat relatief groot probleme doeltreffend opgelos kan word deur die aantal duur strukturele analises wat vereis word, te minimeer. Sommige uitbreidings op tradisionele implementerings word voorgestel wat kan dien om die doeltreffendheid van sulke algoritmes te verhoog. Die werk wat hierin aangebied word, het hoofsaaklik betrekking op drie onderwerpe: die gebruik van nie-konvekse funksies in die defini¨ering van SBO-subprobleme, die globale konvergensie van die metode, en die toepassing van die duale SBO-benadering op grootskaalse probleme. Daarbenewens word ’n hoofstuk aangebied wat fokus op die interpretasie van Sigmund se maasonafhanklike sensitiwiteitsfilter (mesh independence sensitivity filter) in topologie-optimering. Dit is standaard praktyk om die benaderde subprobleme as streng konveks te formuleer, aangesien streng konveksiteit ’n voldoende voorwaarde is om te verseker dat die oplossing van die duale probleem ooreenstem met die unieke stasionˆere punt van die primaal. Die insluiting van niekonvekse funksies in die definisie van die subprobleme word selde gepoog. Baie probleme toon egter nie-konvekse gedrag wat maklik deur eenvoudige nie-konvekse funksies voorgestel kan word. In hierdie werk word daar gedemonstreer dat sulke funksies onder sekere voorwaardes met vrug in die definisie van die benaderde subprobleme inkorporeer kan word sonder om die korrespondensie of uniekheid van die primale en duale oplossings te vernietig. Globale konvergensie van duale SBO-algoritmes word ondersoek binne die konteks van die CCSAmetode, wat afhanklik is van die gebruik en manipulering van konserwatiewe konvekse en skeibare benaderings. Hierdie metode vereis tans dat ’n gegewe probleem en elk van sy subprobleme verslap word om te verseker dat die sekwensie van iterasies wat geproduseer word, toelaatbaar bly. ’n Nuwe metode, wat die begrensde duaal genoem word, word aangebied as ’n alternatief tot verslapping. Daar word vir ontoelaatbaarheid voorsiening gemaak in die oplossing van die duaal, en geen verslappings-tipe wysiging word benodig nie. Daar word gewys dat wanneer ontoelaatbaarheid te¨engekom word, maksimering van die duaal-subprobleem ekwivalent is aan minimering van sy begrensingsontoelaatbaarhede (constraint infeasibilities). Met iterasie word ’n herstellende reeks iterasies geproduseer wat toelaatbaarheid bereik, waarna konvergensie tot ’n plaaslike KKT-punt verseker word. Twee gevalle van die duale SBO-oplossing van grootskaalse probleme word hierin aangespreek. Die eerste geval is ’n diskrete probleem betreffende die seleksie van die puntsgewyse optimale veselori¨entasie in die tweedimensionele minimum meegeefbaarheidsontwerp vir veselversterkte saamgestelde plate. Dit word opgelos deur middel van die diskrete duale benadering, en die formulering wat gebruik word, gee aanleiding tot ’n gedeeltelik skeibare duale probleem. Die tweede geval behels die oplossing van in-vlak materiaalverspredingsprobleme onderworpe aan plaaslike spanningsbegrensings. Hulle word in ’n kontinue sin opgelos met die gebruik van ’n yl oplosser. Die kompleksiteit en dimensionaliteit van die duaal word beheer deur gebruik te maak van ’n strategie om begrensings te selekteer tesame met ’n meganisme waardeur onbelangrike elemente van die Jacobiaan van die aktiewe begrensings uitgelaat word. Op hierdie wyse word beide die grootte van die duaal en die hoeveelheid inligting wat gestoor moet word om die duaal te definieer, verminder.

Recent advances in biomedical technology have allowed us to collect massive quantities of data in the hopes of gaining a better understanding of biological phenomena. This research develops new methods to tackle the challenging problem of determining which parts of these data sets provide useful information. The new methods have been used as a tool to help determine the efficacy of a new HIV vaccine.

Une approche efficace pour la résolution de problèmes inverses consiste à définir le signal (ou l'image) recherché(e) par minimisation d'un critère pénalisé. Ce dernier s'écrit souvent sous la forme d'une somme de fonctions composées avec des opérateurs linéaires. En pratique, ces fonctions peuvent n'être ni convexes ni différentiables. De plus, les problèmes auxquels on doit faire face sont souvent de grande dimension. L'objectif de cette thèse est de concevoir de nouvelles méthodes pour résoudre de tels problèmes de minimisation, tout en accordant une attention particulière aux coûts de calculs ainsi qu'aux résultats théoriques de convergence. Une première idée pour construire des algorithmes rapides d'optimisation est d'employer une stratégie de préconditionnement, la métrique sous-jacente étant adaptée à chaque itération. Nous appliquons cette technique à l'algorithme explicite-implicite et proposons une méthode, fondée sur le principe de majoration-minimisation, afin de choisir automatiquement les matrices de préconditionnement. L'analyse de la convergence de cet algorithme repose sur l'inégalité de Kurdyka-L ojasiewicz. Une seconde stratégie consiste à découper les données traitées en différents blocs de dimension réduite. Cette approche nous permet de contrôler à la fois le nombre d'opérations s'effectuant à chaque itération de l'algorithme, ainsi que les besoins en mémoire, lors de son implémentation. Nous proposons ainsi des méthodes alternées par bloc dans les contextes de l'optimisation non convexe et convexe. Dans le cadre non convexe, une version alternée par bloc de l'algorithme explicite-implicite préconditionné est proposée. Les blocs sont alors mis à jour suivant une règle déterministe acyclique. Lorsque des hypothèses supplémentaires de convexité peuvent être faites, nous obtenons divers algorithmes proximaux primaux-duaux alternés, permettant l'usage d'une règle aléatoire arbitraire de balayage des blocs. L'analyse théorique de ces algorithmes stochastiques d'optimisation convexe se base sur la théorie des opérateurs monotones. Un élément clé permettant de résoudre des problèmes d'optimisation de grande dimension réside dans la possibilité de mettre en oeuvre en parallèle certaines étapes de calculs. Cette parallélisation est possible pour les algorithmes proximaux primaux-duaux alternés par bloc que nous proposons: les variables primales, ainsi que celles duales, peuvent être mises à jour en parallèle, de manière tout à fait flexible. A partir de ces résultats, nous déduisons de nouvelles méthodes distribuées, où les calculs sont répartis sur différents agents communiquant entre eux suivant une topologie d'hypergraphe. Finalement, nos contributions méthodologiques sont validées sur différentes applications en traitement du signal et des images. Nous nous intéressons dans un premier temps à divers problèmes d'optimisation faisant intervenir des critères non convexes, en particulier en restauration d'images lorsque l'image originale est dégradée par un bruit gaussien dépendant du signal, en démélange spectral, en reconstruction de phase en tomographie, et en déconvolution aveugle pour la reconstruction de signaux sismiques parcimonieux. Puis, dans un second temps, nous abordons des problèmes convexes intervenant dans la reconstruction de maillages 3D et dans l'optimisation de requêtes pour la gestion de bases de données
An efficient approach for solving an inverse problem is to define the recovered signal/image as a minimizer of a penalized criterion which is often split in a sum of simpler functions composed with linear operators. In the situations of practical interest, these functions may be neither convex nor smooth. In addition, large scale optimization problems often have to be faced. This thesis is devoted to the design of new methods to solve such difficult minimization problems, while paying attention to computational issues and theoretical convergence properties. A first idea to build fast minimization algorithms is to make use of a preconditioning strategy by adapting, at each iteration, the underlying metric. We incorporate this technique in the forward-backward algorithm and provide an automatic method for choosing the preconditioning matrices, based on a majorization-minimization principle. The convergence proofs rely on the Kurdyka-L ojasiewicz inequality. A second strategy consists of splitting the involved data in different blocks of reduced dimension. This approach allows us to control the number of operations performed at each iteration of the algorithms, as well as the required memory. For this purpose, block alternating methods are developed in the context of both non-convex and convex optimization problems. In the non-convex case, a block alternating version of the preconditioned forward-backward algorithm is proposed, where the blocks are updated according to an acyclic deterministic rule. When additional convexity assumptions can be made, various alternating proximal primal-dual algorithms are obtained by using an arbitrary random sweeping rule. The theoretical analysis of these stochastic convex optimization algorithms is grounded on the theory of monotone operators. A key ingredient in the solution of high dimensional optimization problems lies in the possibility of performing some of the computation steps in a parallel manner. This parallelization is made possible in the proposed block alternating primal-dual methods where the primal variables, as well as the dual ones, can be updated in a quite flexible way. As an offspring of these results, new distributed algorithms are derived, where the computations are spread over a set of agents connected through a general hyper graph topology. Finally, our methodological contributions are validated on a number of applications in signal and image processing. First, we focus on optimization problems involving non-convex criteria, in particular image restoration when the original image is corrupted with a signal dependent Gaussian noise, spectral unmixing, phase reconstruction in tomography, and blind deconvolution in seismic sparse signal reconstruction. Then, we address convex minimization problems arising in the context of 3D mesh denoising and in query optimization for database management

Dans une première partie, nous nous intéressons aux systèmes dynamiques gradients gouvernés par des fonctions non lisses, mais aussi non convexes, satisfaisant l'inégalité de Kurdyka-Lojasiewicz. Après avoir obtenu quelques résultats préliminaires pour la dynamique de la plus grande pente continue, nous étudions un algorithme de descente général. Nous prouvons, sous une hypothèse de compacité, que tout suite générée par ce schéma général converge vers un point critique de la fonction. Nous obtenons aussi de nouveaux résultats sur la vitesse de convergence, tant pour les valeurs que pour les itérés. Ce schéma général couvre en particulier des versions parallélisées de la méthode forward-backward, autorisant une métrique variable et des erreurs relatives. Cela nous permet par exemple de proposer une version non convexe non lisse de l'algorithme Levenberg-Marquardt. Enfin, nous proposons quelques applications de ces algorithmes aux problèmes de faisabilité, et aux problèmes inverses. Dans une seconde partie, cette thèse développe une dynamique de descente associée à des problèmes d'optimisation vectoriels sous contrainte. Pour cela, nous adaptons la dynamique de la plus grande pente usuelle aux fonctions à valeurs dans un espace ordonné par un cône convexe fermé solide. Cette dynamique peut être vue comme l'analogue continu de nombreux algorithmes développés ces dernières années. Nous avons un intérêt particulier pour les problèmes de décision multi-objectifs, pour lesquels cette dynamique de descente fait décroitre toutes les fonctions objectif au cours du temps. Nous prouvons l'existence de trajectoires pour cette dynamique continue, ainsi que leur convergence vers des points faiblement efficients. Finalement, nous explorons une nouvelle dynamique inertielle pour les problèmes multi-objectif, avec l'ambition de développer des méthodes rapides convergeant vers des équilibres de Pareto
In a first part, we focus on gradient dynamical systems governed by non-smooth but also non-convex functions, satisfying the so-called Kurdyka-Lojasiewicz inequality.After obtaining preliminary results for a continuous steepest descent dynamic, we study a general descent algorithm. We prove, under a compactness assumption, that any sequence generated by this general scheme converges to a critical point of the function.We also obtain new convergence rates both for the values and the iterates. The analysis covers alternating versions of the forward-backward method, with variable metric and relative errors. As an example, a non-smooth and non-convex version of the Levenberg-Marquardt algorithm is detailed.Applications to non-convex feasibility problems, and to sparse inverse problems are discussed.In a second part, the thesis explores descent dynamics associated to constrained vector optimization problems. For this, we adapt the classic steepest descent dynamic to functions with values in a vector space ordered by a solid closed convex cone. It can be seen as the continuous analogue of various descent algorithms developed in the last years.We have a particular interest for multi-objective decision problems, for which the dynamic make decrease all the objective functions along time.We prove the existence of trajectories for this continuous dynamic, and show their convergence to weak efficient points.Then, we explore an inertial dynamic for multi-objective problems, with the aim to provide fast methods converging to Pareto points

Dans cette thèse, nous développons certaines techniques avancées d'apprentissage automatique dans le cadre de l'apprentissage en ligne et de l'apprentissage par renforcement (« reinforcement learning » en anglais -- RL). L'épine dorsale de nos approches est la programmation DC (Difference of Convex functions) et DCA (DC Algorithm), et leur version en ligne, qui sont reconnues comme de outils puissants d'optimisation non convexe, non différentiable. Cette thèse se compose de deux parties : la première partie étudie certaines techniques d'apprentissage automatique en mode en ligne et la deuxième partie concerne le RL en mode batch et mode en ligne. La première partie comprend deux chapitres correspondant à la classification en ligne (chapitre 2) et la prédiction avec des conseils d'experts (chapitre 3). Ces deux chapitres mentionnent une approche unifiée d'approximation DC pour différents problèmes d'optimisation en ligne dont les fonctions objectives sont des fonctions de perte 0-1. Nous étudions comment développer des algorithmes DCA en ligne efficaces en termes d'aspects théoriques et computationnels. La deuxième partie se compose de quatre chapitres (chapitres 4, 5, 6, 7). Après une brève introduction du RL et ses travaux connexes au chapitre 4, le chapitre 5 vise à fournir des techniques efficaces du RL en mode batch basées sur la programmation DC et DCA. Nous considérons quatre différentes formulations d'optimisation DC en RL pour lesquelles des algorithmes correspondants basés sur DCA sont développés. Nous traitons les problèmes clés de DCA et montrons l'efficacité de ces algorithmes au moyen de diverses expériences. En poursuivant cette étude, au chapitre 6, nous développons les techniques du RL basées sur DCA en mode en ligne et proposons leurs versions alternatives. Comme application, nous abordons le problème du plus court chemin stochastique (« stochastic shortest path » en anglais -- SSP) au chapitre 7. Nous étudions une classe particulière de problèmes de SSP qui peut être reformulée comme une formulation de minimisation de cardinalité et une formulation du RL. La première formulation implique la norme zéro et les variables binaires. Nous proposons un algorithme basé sur DCA en exploitant une approche d'approximation DC de la norme zéro et une technique de pénalité exacte pour les variables binaires. Pour la deuxième formulation, nous utilisons un algorithme batch RL basé sur DCA. Tous les algorithmes proposés sont testés sur des réseaux routiers artificiels
In this dissertation, we develop some advanced machine learning techniques in the framework of online learning and reinforcement learning (RL). The backbones of our approaches are DC (Difference of Convex functions) programming and DCA (DC Algorithm), and their online version that are best known as powerful nonsmooth, nonconvex optimization tools. This dissertation is composed of two parts: the first part studies some online machine learning techniques and the second part concerns RL in both batch and online modes. The first part includes two chapters corresponding to online classification (Chapter 2) and prediction with expert advice (Chapter 3). These two chapters mention a unified DC approximation approach to different online learning algorithms where the observed objective functions are 0-1 loss functions. We thoroughly study how to develop efficient online DCA algorithms in terms of theoretical and computational aspects. The second part consists of four chapters (Chapters 4, 5, 6, 7). After a brief introduction of RL and its related works in Chapter 4, Chapter 5 aims to provide effective RL techniques in batch mode based on DC programming and DCA. In particular, we first consider four different DC optimization formulations for which corresponding attractive DCA-based algorithms are developed, then carefully address the key issues of DCA, and finally, show the computational efficiency of these algorithms through various experiments. Continuing this study, in Chapter 6 we develop DCA-based RL techniques in online mode and propose their alternating versions. As an application, we tackle the stochastic shortest path (SSP) problem in Chapter 7. Especially, a particular class of SSP problems can be reformulated in two directions as a cardinality minimization formulation and an RL formulation. Firstly, the cardinality formulation involves the zero-norm in objective and the binary variables. We propose a DCA-based algorithm by exploiting a DC approximation approach for the zero-norm and an exact penalty technique for the binary variables. Secondly, we make use of the aforementioned DCA-based batch RL algorithm. All proposed algorithms are tested on some artificial road networks

Dans cette thèse, nous développons certaines techniques avancées d'apprentissage automatique dans le cadre de l'apprentissage en ligne et de l'apprentissage par renforcement (« reinforcement learning » en anglais -- RL). L'épine dorsale de nos approches est la programmation DC (Difference of Convex functions) et DCA (DC Algorithm), et leur version en ligne, qui sont reconnues comme de outils puissants d'optimisation non convexe, non différentiable. Cette thèse se compose de deux parties : la première partie étudie certaines techniques d'apprentissage automatique en mode en ligne et la deuxième partie concerne le RL en mode batch et mode en ligne. La première partie comprend deux chapitres correspondant à la classification en ligne (chapitre 2) et la prédiction avec des conseils d'experts (chapitre 3). Ces deux chapitres mentionnent une approche unifiée d'approximation DC pour différents problèmes d'optimisation en ligne dont les fonctions objectives sont des fonctions de perte 0-1. Nous étudions comment développer des algorithmes DCA en ligne efficaces en termes d'aspects théoriques et computationnels. La deuxième partie se compose de quatre chapitres (chapitres 4, 5, 6, 7). Après une brève introduction du RL et ses travaux connexes au chapitre 4, le chapitre 5 vise à fournir des techniques efficaces du RL en mode batch basées sur la programmation DC et DCA. Nous considérons quatre différentes formulations d'optimisation DC en RL pour lesquelles des algorithmes correspondants basés sur DCA sont développés. Nous traitons les problèmes clés de DCA et montrons l'efficacité de ces algorithmes au moyen de diverses expériences. En poursuivant cette étude, au chapitre 6, nous développons les techniques du RL basées sur DCA en mode en ligne et proposons leurs versions alternatives. Comme application, nous abordons le problème du plus court chemin stochastique (« stochastic shortest path » en anglais -- SSP) au chapitre 7. Nous étudions une classe particulière de problèmes de SSP qui peut être reformulée comme une formulation de minimisation de cardinalité et une formulation du RL. La première formulation implique la norme zéro et les variables binaires. Nous proposons un algorithme basé sur DCA en exploitant une approche d'approximation DC de la norme zéro et une technique de pénalité exacte pour les variables binaires. Pour la deuxième formulation, nous utilisons un algorithme batch RL basé sur DCA. Tous les algorithmes proposés sont testés sur des réseaux routiers artificiels
In this dissertation, we develop some advanced machine learning techniques in the framework of online learning and reinforcement learning (RL). The backbones of our approaches are DC (Difference of Convex functions) programming and DCA (DC Algorithm), and their online version that are best known as powerful nonsmooth, nonconvex optimization tools. This dissertation is composed of two parts: the first part studies some online machine learning techniques and the second part concerns RL in both batch and online modes. The first part includes two chapters corresponding to online classification (Chapter 2) and prediction with expert advice (Chapter 3). These two chapters mention a unified DC approximation approach to different online learning algorithms where the observed objective functions are 0-1 loss functions. We thoroughly study how to develop efficient online DCA algorithms in terms of theoretical and computational aspects. The second part consists of four chapters (Chapters 4, 5, 6, 7). After a brief introduction of RL and its related works in Chapter 4, Chapter 5 aims to provide effective RL techniques in batch mode based on DC programming and DCA. In particular, we first consider four different DC optimization formulations for which corresponding attractive DCA-based algorithms are developed, then carefully address the key issues of DCA, and finally, show the computational efficiency of these algorithms through various experiments. Continuing this study, in Chapter 6 we develop DCA-based RL techniques in online mode and propose their alternating versions. As an application, we tackle the stochastic shortest path (SSP) problem in Chapter 7. Especially, a particular class of SSP problems can be reformulated in two directions as a cardinality minimization formulation and an RL formulation. Firstly, the cardinality formulation involves the zero-norm in objective and the binary variables. We propose a DCA-based algorithm by exploiting a DC approximation approach for the zero-norm and an exact penalty technique for the binary variables. Secondly, we make use of the aforementioned DCA-based batch RL algorithm. All proposed algorithms are tested on some artificial road networks

In this communication advances in data processing techniques applied to Airlines Revenue Management are displayed. The general introduction presents a brief review of Airlines Revenue Management. The first of the paper introduces the problem of updating the probability distributions of demand for reservations. This updating process, facing the stochastic nature of demand for travel, is a cornerstone for the design of an efficient on-line decision support system to control the reservation process for a flight by an airline. The considered problem is formulated as a dual geometric problem to which an unconstrained nonconvex, primal geometric problem is associated. A genetic algorithm optimization approach is proposed to solve the primal geometric problem, and then the classical geometric primal-dual transformations provide the solution to the initial problem. Then, the second part of the paper considers the design of a new Decision Support System for improving the reservation control process of airlines. A new recursive Dynamic Programming model for maximum expected revenue evaluation is defined, which, contrarily to other approaches, takes explicitly into account daily booking request arrivals. A practical Backward Dynamic Programming algorithm is established, leading to the design of an on-line optimisation module for Revenue Management. In this study two cases are considered. The first one considers that fare classes are not physically confined and the obtained results are extended in the second case to cover the situations where confinement of fare classes (Business Class and Economy Class) is applied.

VV4RTOS is an activity supported by the European Space Agency aimed at the development and validation of a framework for the verification and validation of spacecraft guidance, navigation, and control (GNC) systems based on embedded optimisation, tailored to handle different layers of abstraction, from guidance and control (G&C) requirements down to hardware level. This is grounded on the parallel design and development of real-time optimisation-based G&C software, allowing to concurrently identify, develop, consolidate, and validate a set of engineering practices and analysis & verification tools to ensure safe code execution of the designed G&C software as test cases but aimed at streamlining general industrial V&V processes. This paper presents: 1) a review of the challenges and the state-of-the-art of formal verification methods applicable to optimization-based software; 2) the implementation for an embedded application and the analysis from a V&V standpoint of a conic optimization solver; 3) the technical approach devised towards and enhanced V&V process; and 4) experimental results up to processor-in-the-loop tests and conclusions. In general, this activity aims to contribute to the widespread usage of convex optimisation-based techniques across the space industry by 1) augmenting the traditional GNC software Design & Development Verification & Validation (DDVV) methodologies to explicitly address iterative embedded optimisation algorithms that are paramount for the success of new and extremely relevant space applications (from powered landing to active debris removal, from actuator allocation to attitude guidance & control) guaranteeing safe, reliable, repeatable, and accurate execution of the SW; and 2) consolidating the necessary tools for the fast prototyping and qualification of G&C software, grounded on strong theoretical foundations for the solution of convex optimisation problems generated by posing, discretization, convexification, and transcription of nonlinear nonconvex optimal control problems to online-solvable optimisation problems. Sound guidelines are provided for the high-to-low level translation of mission requirements and objectives aiming at their interfacing with verifiable embedded solvers tailored for the underlying hardware and exploiting the structure present in the common optimisation/optimal control problems. To fulfil this mandate, two avenues of research and development were followed: the development of a benchmarking framework with optimisation-based G&C and the improvement of the V&V process – two radical advances with respect to traditional GNC DDVV. On the first topic, the new optimisation-based hierarchy was exploited, from high-level requirements and objectives that can be mathematically posed as optimal control problems, themselves organised in different levels of abstraction, complexity, and time-criticality depending on how close to the actuator level they are. The main line of this work is then focused on the core component of optimisation-based G&C – the optimisation solver – starting with a formal analysis of its mathematical properties that allowed to identify meaningful requirements for V&V, and, concurrently, with a thorough, step-by-step, design and implementation for embedding in a space target board. This application-agnostic analysis and development was associated with the DDVV of specific usecases of optimisation-based G&C for common space applications of growing complexity, exploring different challenges in the form of convex problem complexity (up to second-order cone programs), problem size (model predictive control and trajectory optimization), and nonlinearity (both translation and attitude control problems). The novel V&V approach relies on the combination and exploitation of the two main approaches: classical testing of the global on-board software, and local and compositional, formal, math-driven, verification. While the former sees systems as black boxes, feeding it with comprehensive inputs and analysing statistically the outputs, the latter delves deep into the sub-components of the software, effectively seeing it as white boxes whenever mathematically possible. In between the two approaches lies the optimal path to a thorough, dependable, mathematically sound verification and validation process: local, potentially application-agnostic, validation of the building blocks with respect to mathematical specifications leading up to application-specific testing of global complex systems, this time informed by the results of local validation and testing. The deep analysis of the mathematical properties of the optimisation algorithm allows to derive requirements with increasing complexity (e.g., from “the code implements the proper computations”, to higher level mathematical properties such as optimality, convergence, and feasibility). These are related to quantities of interest that can be both verified resorting to e-ACSL specifications and Frama-C in a C-code implementation of the solver, but also observed in online monitors in Simulink or in post-processing during the model/software-in-the-loop testing. Finally, the activity applies the devised V&V process to the benchmark designs, from model-in-the-loop Monte Carlo testing, followed by autocoding and software-in-the-loop equivalence testing in parallel with the Frama-C runtime analysis, and concluded by processor-in-the-loop testing in a Hyperion on-board computer based around a Xilinx Zynq 7000 SoC.