Dissertations / Theses on the topic 'Optimisation nonconvexe'

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

Cette thèse est particulièrement destinée à traiter deux types de problèmes : clustering et l'alignement multiple de séquence. Notre objectif est de résoudre de manière satisfaisante ces problèmes globaux et de tester l'approche de la Programmation DC et DCA sur des jeux de données réelles. La thèse comporte trois parties : la première partie est consacrée aux nouvelles approches de l'optimisation non convexe. Nous y présentons une étude en profondeur de l'algorithme qui est utilisé dans cette thèse, à savoir la programmation DC et l'algorithme DC (DCA). Dans la deuxième partie, nous allons modéliser le problème clustering en trois sous-problèmes non convexes. Les deux premiers sous-problèmes se distinguent par rapport au choix de la norme utilisée, (clustering via les normes 1 et 2). Le troisième sous-problème utilise la méthode du noyau, (clustering via la méthode du noyau). La troisième partie sera consacrée à la bio-informatique. On va se focaliser sur la modélisation et la résolution de deux sous-problèmes : l'alignement multiple de séquence et l'alignement de séquence d'ARN par structure. Tous les chapitres excepté le premier se terminent par des tests numériques
This Ph.D. thesis is particularly intended to treat two types of problems : clustering and the multiple alignment of sequence. Our objective is to solve efficiently these global problems and to test DC Programming approach and DCA on real datasets. The thesis is divided into three parts : the first part is devoted to the new approaches of nonconvex optimization-global optimization. We present it a study in depth of the algorithm which is used in this thesis, namely the programming DC and the algorithm DC ( DCA). In the second part, we will model the problem clustering in three nonconvex subproblems. The first two subproblems are distinguished compared to the choice from the norm used, (clustering via norm 1 and 2). The third subproblem uses the method of the kernel, (clustering via the method of the kernel). The third part will be devoted to bioinformatics, one goes this focused on the modeling and the resolution of two subproblems : the multiple alignment of sequence and the alignment of sequence of RNA. All the chapters except the first end in numerical tests

Cette thèse traite le problème de l’allocation de ressources pour les communications cognitives par satellite. Dans un contexte de demandes grandissantes en terme de débit, les systèmes de communication par satellite sont amenés à utiliser des fréquences déjà employées par des systèmes terrestres. Le paradigme de la radio cognitive de type sous couche permet à un réseau secondaire d'utiliser la même bande de fréquence qu'un réseau primaire. Cependant, l'interférence créée par le réseau secondaire ne doit pas excéder une certaine limite, fixée par le réseau primaire. Nous considérons un système de communication cognitif par satellite, où des utilisateurs terrestres transmettent des informations à un satellite, ce dernier les renvoyant à une passerelle terrestre à la manière d'un relais. De cette façon, les utilisateurs terrestres du réseau secondaire satellitaire génèrent des interférences sur le réseau primaire, qui sont dues aux lobes secondaires des antennes d'émission. La gestion de la puissance de transmission des utilisateurs satellitaires secondaires devient primordiale pour limiter les interférences sur le réseau primaire terrestre et, en même temps, atteindre le débit maximal du système. De plus, la prise en compte des non-linéarités provenant du satellite, notamment l'amplificateur de haute puissance, devient cruciale lorsque celui-ci est utilisé au maximum de ses capacités. Car les effets non linéaires produit par l'amplificateur, modélisé par des séries de Volterra, dégradent les débits du système. Dans ce contexte, la thèse consiste à proposer des algorithmes d'allocation de ressources afin d'optimiser la somme des débits du système satellitaire, tout en respectant les limites d'interférence fixées par le réseau terrestre primaire, avec la prise en compte des effets non linéaires générées par les composants du satellite
This thesis addresses the problem of resource allocation for cognitive satellite communications.In a context of increasing throughput demands, satellite communication systems are required to use frequencies already used by terrestrial systems. The underlay cognitive radio paradigm allows a secondary network to use the same frequency band that a primary network uses. However, the interference created by the secondary network must not exceed a certain limit, which is set by the primary network.We consider a cognitive satellite communication system, where terrestrial users transmit information to a satellite, and that satellite sends it back to a terrestrial gateway in a relay-like fashion.In this way, the terrestrial users of the satellite secondary network generate interference on the primary network, which is due to the secondary lobes of the transmitting antennas. The management of the transmission power of the secondary satellite users becomes essential to limit the interference on the primary terrestrial network and, at the same time, to reach the maximum throughput of the system. Moreover, taking into account the nonlinearities coming from the satellite, especially the high-power amplifier, becomes crucial when the satellite is used at its maximum capabilities.This is because the non-linear effects produced by the amplifier, modeled by Volterra series, degrade the system throughput.In this context, the thesis consists in proposing resource allocation algorithms in order to optimize the sum-rate of the satellite system, while respecting the interference limits set by the primary terrestrial network, taking into account the nonlinear effects generated by the satellite components

Dans cette thèse, nous nous intéressons au développement des approches coopératives pour la résolution de certaines classes de problèmes d'optimisation non convexe qui jouent un rôle très important de par leurs applications dans de nombreux domaines. Il s'agit de combiner plusieurs algorithmes connus sous les noms des algorithmes composants (participants). La combinaison est basée principalement sur la programmation DC (Difference of Convex Functions) et DCA (DC Algorithm) avec des métaheuristiques. Pour la conception des logiciels nous utilisons les paradigmes de la programmation parallèle et distribuée. Chaque processus s'occupe d'un algorithme et communique avec les autres en appelant les fonctions de la bibliothèque MPI (Message Passing Interface) qui est un protocole de communication en programmation parallèle et distribuée. Outre l'introduction et la conclusion, la thèse est composée de quatre chapitres. Le chapitre 1 concerne les outils théoriques et algorithmiques comme servant de base méthodologique aux chapitres suivants. Le chapitre 2 s'articule autour les problèmes linéaires à variables mixtes binaires. Pour la résolution de ces problèmes, nous proposons une approche coopérative entre DCA et VNS (Variable Neighborhood Search). Puisque le schéma est constitué de deux algorithmes, nous optons pour la communication point à point entre les processus. Nous adaptons notre schéma pour résoudre le problème de localisation de l'installation avec des contraintes de capacités. Dans le chapitre 3, nous étudions la programmation quadratique à variables binaires. Nous développons une coopération entre DCA-Like (une nouvelle version de DCA) et deux autres métaheuristiques : GA (Genetic Algorithm) et MBO (Migrating Birds Optimization). Pour la communication entre les processus, nous utilisons la communication collective. Plus précisément une fonction qui permet la diffusion simultanée l'information d'un processus à tous les autres. Cette approche est adaptée et appliquée au problème d'affectation quadratique. Dans le chapitre 4, nous résolvons les problèmes de "clustering" via la minimisation de la somme des carrés par deux approches coopératives. La première consiste à combiner le DCA avec VNS et TS (Tabu Search). Quant à la deuxième, elle utilise la MBO avec les trois derniers algorithmes précités. Dans ces deux approches, nous utilisons une fonction de communication qui permet au processus d'accéder aux mémoires des autres et y enregistrer son information sans un temps d'attente
In this thesis, we are interested in developing new cooperative approaches for solving some classes of nonconvex problems which play a very important role to model real-world problems. To design the schemes of our approaches, we combine several algorithms which we call the component (participant) algorithms. The combination is mainly based on DC (Difference of Convex Functions) and DCA (DC Algorithm) with metaheuristics. To develop our solution methods, we use the paradigm of parallel and distributed programming. Therefore, each process deals with an algorithm and communicates with the others by calling the functions of the MPI (Message Passing Interface) library which is a communication protocol in parallel and distributed programming. Besides the introduction and conclusion, this thesis is composed of four chapters. Chapter 1 concerns the theoretical and algorithmic tools serving as a methodological basis for the following chapters. Chapter 2 is about the mixed binary linear programs. To solve these problems, we propose a cooperative approach between DCA and VNS (Variable Neighborhood Search). Since the scheme is constituted by two algorithms, we use the point to point communication between the processes. As an application, we adapt our scheme to solve the capacitated facility location problem. Concerning chapter 3, we study the class of binary quadratic problems. Regarding the solution methods, we develop a cooperation between DCA-like which is a new version of DCA and two other metaheuristics: GA (Genetic Algorithm) and MBO (Migrating Birds Optimization). The exchange of information between the processes is expressed by using collective communication's function. More precisely, we call a function which allows broadcasting information of a process to all the others at the same time. This cooperative approach is adapted to the quadratic assignment problem. In chapter 4, we solve the MSSC (Minimum-Sum-of-Squares Clustering) using two cooperative approaches. The first combines DCA, VNS, and TS (Tabu Search). As for the second, it combines the MBO with the other three algorithms cited before. In these two approaches, we use a function of communication that allows a process to access the memories of the others and save the information there without blocking the work of the receiving processes

The major aim of this research thesis is to handle two main challenges arising when solving unconstrained optimisation problems with second-order methods: the reduction of the per-iteration cost and the stochastic analysis of the resulting non- deterministic algorithms. This is motivated by the fact that second-order procedures can be more efficient than first-order ones on badly scaled and ill-conditioned problems, since they seem to potentially take advantage of curvature information to easier escape from saddle points, being more robust to the choice of hyperparameters and the parameters tuning, but at the price of a more expensive per-iteration cost, due to the computation of Hessian-vector products. Furthermore, the effort of reducing such a cost with inexact function and/or derivatives evaluations, that have to fulfill suitable accuracy requirements, leads to non-deterministic variants of the methods, that have to be supported by a stochastic complexity analysis. The thesis builds on a particular class of second-order globally convergent methods based on the Adaptive Cubic Regularisation (ARC) framework, motivated by the fact that its complexity, in terms of the worst-case number of iterations to reach a first-order critical point, has been proved to be optimal. To this purpose, the design, analysis and development of novel variants of ARC methods, employing inexact derivatives and/or function. evaluations, are investigated. To start with, a suitable reference version of the ARC method is firstly introduced, obtained by merging existing basic forms of ARC algorithms, in order to set the general background on adaptive cubic regularisation. Having set the scene, we then cope with the need of introducing inexactness in function and derivatives computations while conserving optimal complexity. After setting the finite-sum minimisation framework, this starts with the employment of inexact Hessian information, adaptively chosen, before moving on to an extended framework based on function estimates and approximate derivatives evaluations. The stochastic complexity analysis of the presented frameworks is thus performed. Finally, numerical tests within the context of supervised learning are reported, ranging from popular machine learning datasets to a real-life machine learning industrial application related to the parametric design of centrifugal pumps.

M. Tech. Electrical Engineering.
This study proposes a mathematical optimisation approach which invokes Genetic Algorithm (GA) for initialisation and application of Tabu Search (TS) algorithm in finding the sites of node Bs in the network to enable it have the potential to support an increased number of users requiring the increased number of services. The global optimisation can be obtained in terms of great probability as GA is applied to global search and TS is applied to the local search. The particular memory ability of TS can be integrated to GA and the prematurity of GA can be avoided by virtue of the hill-climbing ability of TS. The problem to be addressed is the determination of optimal locations of node Bs in the network based on the user distribution, while improving the QoS. The proposed approach considers the site selection as an integer problem and the site placement as a continuous problem. The two problems are focused on concurrently - finding the optimal number of node Bs that satisfies the capacity requirements in the network and hence QoS improvement. The proposed algorithm combines the strength of Genetic and Tabu Search algorithms in successive elimination of node Bs after their random distribution in the area of study. The results showed that the proposed approach produced fewer number of node Bs sites in the network that provided the required QoS. In addition, it exhibited high fitness function in the simulations meaning that it has the higher ability of achieving the objective function when it was compared to TS and GA.

Text in Afikaans
In this thesis contributions to the solution of the generalised knapsack problem are given and discussed. Attention is given to problems with functions that are calculable but not necessarily in a closed form. Algorithms and test problems can be used for problems with closed-form functions as well. The focus is on the development of good heuristics and not on exact algorithms. Heuristics must be investigated and good test problems must be designed. A measure of convexity for convex functions is developed and adapted for concave functions. A test problem generator makes use of this measure of convexity to create challenging test problems for the concave, convex and mixed knapsack problems. Four easy-to-interpret characteristics of an S-function are used to create test problems for the S-shaped as well as the generalised knapsack problem. The in uence of the size of the problem and the funding ratio on the speed and the accuracy of the algorithms are investigated. When applicable, the in uence of the interval length ratio and the ratio of concave functions to the total number of functions is also investigated. The Karush-Kuhn-Tucker conditions play an important role in the development of the algorithms. Suf- cient conditions for optimality for the convex knapsack problem with xed interval lengths is given and proved. For the general convex knapsack problem, the key theorem, which contains the stronger necessary conditions, is given and proved. This proof is so powerful that it can be used to proof the adapted key theorems for the mixed, S-shaped and the generalised knapsack problems as well. The exact search-lambda algorithm is developed for the concave knapsack problem with functions that are not in a closed form. This algorithm is used in the algorithms to solve the mixed and S-shaped knapsack problems. The exact one-step algorithm is developed for the convex knapsack problem with xed interval length. This algorithm is O(n). The general convex knapsack problem is solved by using the pivot algorithm which is O(n2). Optimality cannot be proven but in all cases the optimal solution was found and for all practical reasons this problem will be considered as being concluded. A good heuristic is developed for the mixed knapsack problem. Further research can be done on this heuristic as well as on the S-shaped and generalised knapsack problems.
Mathematical Sciences
D. Phil. (Operasionele Navorsing)

Recent decades have witnessed the rise of data deluge generated by heterogeneous sources, e.g., social networks, streaming, marketing services etc., which has naturally created a surge of interests in theory and applications of large-scale convex and non-convex optimization. For example, real-world instances of statistical learning problems such as deep learning, recommendation systems, etc. can generate sheer volumes of spatially/temporally diverse data (up to Petabytes of data in commercial applications) with millions of decision variables to be optimized. Such problems are often referred to as Big-data problems. Solving these problems by standard optimization methods demands intractable amount of centralized storage and computational resources which is infeasible and is the foremost purpose of parallel and decentralized algorithms developed in this thesis.

This thesis consists of two parts: (I) Distributed Nonconvex Optimization and (II) Distributed Convex Optimization.

In Part (I), we start by studying a winning paradigm in big-data optimization, Block Coordinate Descent (BCD) algorithm, which cease to be effective when problem dimensions grow overwhelmingly. In particular, we considered a general family of constrained non-convex composite large-scale problems defined on multicore computing machines equipped with shared memory. We design a hybrid deterministic/random parallel algorithm to efficiently solve such problems combining synergically Successive Convex Approximation (SCA) with greedy/random dimensionality reduction techniques. We provide theoretical and empirical results showing efficacy of the proposed scheme in face of huge-scale problems. The next step is to broaden the network setting to general mesh networks modeled as directed graphs, and propose a class of gradient-tracking based algorithms with global convergence guarantees to critical points of the problem. We further explore the geometry of the landscape of the non-convex problems to establish second-order guarantees and strengthen our convergence to local optimal solutions results to global optimal solutions for a wide range of Machine Learning problems.

In Part (II), we focus on a family of distributed convex optimization problems defined over meshed networks. Relevant state-of-the-art algorithms often consider limited problem settings with pessimistic communication complexities with respect to the complexity of their centralized variants, which raises an important question: can one achieve the rate of centralized first-order methods over networks, and moreover, can one improve upon their communication costs by using higher-order local solvers? To answer these questions, we proposed an algorithm that utilizes surrogate objective functions in local solvers (hence going beyond first-order realms, such as proximal-gradient) coupled with a perturbed (push-sum) consensus mechanism that aims to track locally the gradient of the central objective function. The algorithm is proved to match the convergence rate of its centralized counterparts, up to multiplying network factors. When considering in particular, Empirical Risk Minimization (ERM) problems with statistically homogeneous data across the agents, our algorithm employing high-order surrogates provably achieves faster rates than what is achievable by first-order methods. Such improvements are made without exchanging any Hessian matrices over the network.

Finally, we focus on the ill-conditioning issue impacting the efficiency of decentralized first-order methods over networks which rendered them impractical both in terms of computation and communication cost. A natural solution is to develop distributed second-order methods, but their requisite for Hessian information incurs substantial communication overheads on the network. To work around such exorbitant communication costs, we propose a “statistically informed” preconditioned cubic regularized Newton method which provably improves upon the rates of first-order methods. The proposed scheme does not require communication of Hessian information in the network, and yet, achieves the iteration complexity of centralized second-order methods up to the statistical precision. In addition, (second-order) approximate nature of the utilized surrogate functions, improves upon the per-iteration computational cost of our earlier proposed scheme in this setting.