Дисертації з теми "Optimisation nonconvexe"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-18 дисертацій для дослідження на тему "Optimisation nonconvexe".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.
Jerad, Sadok. "Approches du second ordre de d'ordre élevées pour l'optimisation nonconvex avec variantes sans évaluation de la fonction objective." Electronic Thesis or Diss., Université de Toulouse (2023-....), 2024. http://www.theses.fr/2024TLSEP024.
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
Giagkiozis, Ioannis. "Nonconvex many-objective optimisation." Thesis, University of Sheffield, 2012. http://etheses.whiterose.ac.uk/3683/.
Wahid, Faisal. "Optimisation de la rivière : enchères à court terme de l'hydroélectricité sous incertitude." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLX030.
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
Kleniati, Polyxeni M. "Decomposition schemes for polynomial optimisation, semidefinite programming and applications to nonconvex portfolio decisions." Thesis, Imperial College London, 2010. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.509792.
Wood, Derren Wesley. "Dual sequential approximation methods in structural optimisation." Thesis, Stellenbosch : Stellenbosch University, 2012. http://hdl.handle.net/10019.1/20033.
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.
Sutton, Matthew William. "Variable selection and dimension reduction for structured large datasets." Thesis, Queensland University of Technology, 2019. https://eprints.qut.edu.au/129460/1/Matthew_Sutton_Thesis.pdf.
Repetti, Audrey. "Algorithmes d'optimisation en grande dimension : applications à la résolution de problèmes inverses." Thesis, Paris Est, 2015. http://www.theses.fr/2015PESC1032/document.
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
Garrigos, Guillaume. "Descent dynamical systems and algorithms for tame optimization, and multi-objective problems." Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS191/document.
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
Ho, Vinh Thanh. "Techniques avancées d'apprentissage automatique basées sur la programmation DC et DCA." Electronic Thesis or Diss., Université de Lorraine, 2017. http://www.theses.fr/2017LORR0289.
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
Ho, Vinh Thanh. "Techniques avancées d'apprentissage automatique basées sur la programmation DC et DCA." Thesis, Université de Lorraine, 2017. http://www.theses.fr/2017LORR0289/document.
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
Belghiti, Moulay Tayeb. "Modélisation et techniques d'optimisation en bio-informatique et fouille de données." Thesis, Rouen, INSA, 2008. http://www.theses.fr/2008ISAM0002.
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
Louchart, Arthur. "Nonlinear impairments aware resource allocation for cognitive satellite systems." Electronic Thesis or Diss., Institut polytechnique de Paris, 2021. http://www.theses.fr/2021IPPAT031.
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
Samir, Sara. "Approches coopératives pour certaines classes de problèmes d'optimisation non convexe : Algorithmes parallèles / distribués et applications." Electronic Thesis or Diss., Université de Lorraine, 2020. http://www.theses.fr/2020LORR0039.
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
Gurioli, Gianmarco. "Adaptive Regularisation Methods under Inexact Evaluations for Nonconvex Optimisation and Machine Learning Applications." Doctoral thesis, 2021. http://hdl.handle.net/2158/1238314.
Juma, Raymond Wekesa. "An optimisation approach for capacity enhancement in third generation (3G) mobile networks." Thesis, 2012. http://encore.tut.ac.za/iii/cpro/DigitalItemViewPage.external?sp=1000570.
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.
Venter, Geertien. "Bydraes tot die oplossing van die veralgemeende knapsakprobleem." Thesis, 2013. http://hdl.handle.net/10500/8603.
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)
(11153640), Amir Daneshmand. "Parallel and Decentralized Algorithms for Big-data Optimization over Networks." Thesis, 2021.
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.
Dan, Teodora. "Algorithmic contributions to bilevel location problems with queueing and user equilibrium : exact and semi-exact approaches." Thèse, 2018. http://hdl.handle.net/1866/21587.