Dissertations / Theses on the topic 'Nonconvex programming'

Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2010.
Committee Chair: Nemhauser, George; Committee Co-Chair: Ahmed, Shabbir; Committee Member: Bill Cook; Committee Member: Gu, Zonghao; Committee Member: Johnson, Ellis. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Traditionally, linear programming (LP) has been used to construct convex relaxations in the context of branch and bound for determining global optimal solutions to nonconvex optimization problems. As second-order cone programming (SOCP) and semidefinite programming (SDP) become better understood by optimization researchers, they become alternative choices for obtaining convex relaxations and producing bounds on the optimal values. In this thesis, we study the use of these convex optimization tools in constructing strong relaxations for several nonconvex problems, including 0-1 integer programming, nonconvex box-constrained quadratic programming (BoxQP), and general quadratic programming (QP). We first study a SOCP relaxation for 0-1 integer programs and a sequential relaxation technique based on this SOCP relaxation. We present desirable properties of this SOCP relaxation, for example, this relaxation cuts off all fractional extreme points of the regular LP relaxation. We further prove that the sequential relaxation technique generates the convex hull of 0-1 solutions asymptotically. We next explore nonconvex quadratic programming. We propose a SDP relaxation for BoxQP based on relaxing the first- and second-order KKT conditions, where the difficulty and contribution lie in relaxing the second-order KKT condition. We show that, although the relaxation we obtain this way is equivalent to an existing SDP relaxation at the root node, it is significantly stronger on the children nodes in a branch-and-bound setting. New advance in optimization theory allows one to express QP as optimizing a linear function over the convex cone of completely positive matrices subject to linear constraints, referred to as completely positive programming (CPP). CPP naturally admits strong semidefinite relaxations. We incorporate the first-order KKT conditions of QP into the constraints of QP, and then pose it in the form of CPP to obtain a strong relaxation. We employ the resulting SDP relaxation inside a finite branch-and-bound algorithm to solve the QP. Comparison of our algorithm with commercial global solvers shows potential as well as room for improvement. The remainder is devoted to new techniques for solving a class of large-scale linear programming problems. First order methods, although not as fast as second-order methods, are extremely memory efficient. We develop a first-order method based on Nesterov's smoothing technique and demonstrate the effectiveness of our method on two machine learning problems.

The primary objective of this thesis is to develop and implement a global optimization algorithm to solve a class of nonconvex programming problems, and to test it using a collection of engineering design problem applications.The class of problems we consider involves the optimization of a general nonconvex factorable objective function over a feasible region that is restricted by a set of constraints, each of which is defined in terms of nonconvex factorable functions. Such problems find widespread applications in production planning, location and allocation, chemical process design and control, VLSI chip design, and numerous engineering design problems. This thesis offers a first comprehensive methodological development and implementation for determining a global optimal solution to such factorable programming problems. To solve this class of problems, we propose a branch-and-bound approach based on linear programming (LP) relaxations generated through various approximation schemes that utilize, for example, the Mean-Value Theorem and Chebyshev interpolation polynomials, coordinated with a {em Reformulation-Linearization Technique} (RLT). The initial stage of the lower bounding step generates a tight, nonconvex polynomial programming relaxation for the given problem. Subsequently, an LP relaxation is constructed for the resulting polynomial program via a suitable RLT procedure. The underlying motivation for these two steps is to generate a tight outer approximation of the convex envelope of the objective function over the convex hull of the feasible region. The bounding step is thenintegrated into a general branch-and-bound framework. The construction of the bounding polynomials and the node partitioning schemes are specially designed so that the gaps resulting from these two levels of approximations approach zero in the limit, thereby ensuring convergence to a global optimum. Various implementation issues regarding the formulation of such tight bounding problems using both polynomial approximations and RLT constructs are discussed. Different practical strategies and guidelines relating to the design of the algorithm are presented within a general theoretical framework so that users can customize a suitable approach that takes advantage of any inherent special structures that their problems might possess. The algorithm is implemented in C++, an object-oriented programming language. The class modules developed for the software perform various functions that are useful not only for the proposed algorithm, but that can be readily extended and incorporated into other RLT based applications as well. Computational results are reported on a set of fifteen engineering process control and design test problems from various sources in the literature. It is shown that, for all the test problems, a very competitive computational performance is obtained. In most cases, the LP solution obtained for the initial node itself provides a very tight lower bound. Furthermore, for nine of these fifteen problems, the application of a local search heuristic based on initializing the nonlinear programming solver MINOS at the node zero LP solution produced the actual global optimum. Moreover, in finding a global optimum, our algorithm discovered better solutions than the ones previously reported in the literature for two of these test instances.
Master of Science

Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2006.
Includes bibliographical references (leaves 73-75).
In this thesis, we use a semidefinite relaxation based branch-and-bound method to solve nonconvex quadratic programming problems. Firstly, we show an interval branch-and-bound method to calculate the bounds for the minimum of bounded polynomials. Then we demonstrate four SDP relaxation methods to solve nonconvex Box constrained Quadratic Programming (BoxQP) problems and the comparison of the four methods. For some lower dimensional problems, SDP relaxation methods can achieve tight bounds for the BoxQP problem; whereas for higher dimensional cases (more than 20 dimensions), the bounds achieved by the four Semidefinite programming (SDP) relaxation methods are always loose. To achieve tight bounds for higher dimensional BoxQP problems, we combine the branch-and-bound method and SDP relaxation method to develop an SDP relaxation based branch-and-bound (SDPBB) method. We introduce a sensitivity analysis method for the branching process of SDPBB. This sensitivity analysis method can improve the convergence speed significantly.
(cont.) Compared to the interval branch-and-bound method and the global optimization software BARON, SDPBB can achieve better bounds and is also much more efficient. Additionally, we have developed a multisection algorithm for SDPBB and the multisection algorithm has been parallelized using Message Passing Interface (MPI). By parallelizing the program, we can significantly improve the speed of solving higher dimensional BoxQP problems.
by Sha Hu.
S.M.

In many applications nonsmooth nonconvex energy functions, which are Lipschitz continuous, appear quite naturally. Contact mechanics with friction is a classic example. A second example is the 1-Laplace operator and its eigenfunctions. In this work we will give an algorithm such that for every locally Lipschitz continuous function f and every sequence produced by this algorithm it holds that every accumulation point of the sequence is a critical point of f in the sense of Clarke. Here f is defined on a reflexive Banach space X, such that X and its dual space X' are strictly convex and Clarkson's inequalities hold. (E.g. Sobolev spaces and every closed subspace equipped with the Sobolev norm satisfy these assumptions for p>1.) This algorithm is designed primarily to solve variational problems or their high dimensional discretizations, but can be applied to a variety of locally Lipschitz functions. In elastic contact mechanics the strain energy is often smooth and nonconvex on a suitable domain, while the contact and the friction energy are nonsmooth and have a support on a subspace which has a substantially smaller dimension than the strain energy, since all points in the interior of the bodies only have effect on the strain energy. For such elastic contact problems we suggest a specialization of our algorithm, which treats the smooth part with Newton like methods. In the case that the gradient of the entire energy function is semismooth close to the minimizer, we can even prove superlinear convergence of this specialization of our algorithm. We test the algorithm and its specialization with a couple of benchmark problems. Moreover, we apply the algorithm to the 1-Laplace minimization problem restricted to finitely dimensional subspaces of piecewise affine, continuous functions. The algorithm developed here uses ideas of the bundle trust region method by Schramm, and a new generalization of the concept of gradients on a set. The basic idea behind this gradients on sets is that we want to find a stable descent direction, which is a descent direction on an entire neighborhood of an iteration point. This way we avoid oscillations of the gradients and very small descent steps (in the smooth and in the nonsmooth case). It turns out, that the norm smallest element of the gradient on a set provides a stable descent direction. The algorithm we present here is the first algorithm which can treat locally Lipschitz continuous functions in this generality, up to our knowledge. In particular, large finitely dimensional Banach spaces haven't been studied for nonsmooth nonconvex functions so far. We will show that the algorithm is very robust and often faster than common algorithms. Furthermore, we will see that with this algorithm it is possible to compute reliably the first eigenfunctions of the 1-Laplace operator up to disretization errors, for the first time
In vielen Anwendungen tauchen nichtglatte, nichtkonvexe, Lipschitz-stetige Energie Funktionen in natuerlicher Weise auf. Ein klassische Beispiel bildet die Kontaktmechanik mit Reibung. Ein weiteres Beispiel ist der $1$-Laplace Operator und seine Eigenfunktionen. In dieser Dissertation werden wir ein Abstiegsverfahren angeben, so dass fuer jede lokal Lipschitz-stetige Funktion f jeder Haeufungspunkt einer durch dieses Verfahren erzeugten Folge ein kritischer Punkt von f im Sinne von Clarke ist. Hier ist f auf einem einem reflexiver, strikt konvexem Banachraum definierert, fuer den der Dualraum ebenfalls strikt konvex ist und die Clarkeson Ungleichungen gelten. (Z.B. Sobolevraeume und jeder abgeschlossene Unterraum mit der Sobolevnorm versehen, erfuellt diese Bedingung fuer p>1.) Dieser Algorithmus ist primaer entwickelt worden um Variationsprobleme, bzw. deren hochdimensionalen Diskretisierungen zu loesen. Er kann aber auch fuer eine Vielzahl anderer lokal Lipschitz stetige Funktionen eingesetzt werden. In der elastischen Kontaktmechanik ist die Spannungsenergie oft glatt und nichtkonvex auf einem geeignetem Definitionsbereich, waehrend der Kontakt und die Reibung durch nicht glatte Funktionen modelliert werden, deren Traeger ein Unterraum mit wesentlich kleineren Dimension ist, da alle Punkte im Inneren des Koerpers nur die Spannungsenergie beeinflussen. Fuer solche elastischen Kontaktprobleme schlagen wir eine Spezialisierung unseres Algorithmuses vor, der den glatten Teil mit Newton aehnlichen Methoden behandelt. Falls der Gradient der gesamten Energiefunktion semiglatt in der Naehe der Minimalstelle ist, koennen wir sogar beweisen, dass der Algorithmus superlinear konvergiert. Wir testen den Algorithmus und seine Spezialisierung an mehreren Benchmark Problemen. Ausserdem wenden wir den Algorithmus auf 1-Laplace Minimierungsproblem eingeschraenkt auf eine endlich dimensionalen Unterraum der stueckweise affinen, stetigen Funktionen an. Der hier entwickelte Algorithmus verwendet Ideen des Bundle-Trust-Region-Verfahrens von Schramm, und einen neu entwickelten Verallgemeinerung von Gradienten auf Mengen. Die zentrale Idee hinter den Gradienten auf Mengen ist die, dass wir stabile Abstiegsrichtungen auf einer ganzen Umgebung der Iterationspunkte finden wollen. Auf diese Weise vermeiden wir das Oszillieren der Gradienten und sehr kleine Abstiegsschritte (im glatten, wie im nichtglatten Fall.) Es stellt sich heraus, dass das normkleinste Element dieses Gradienten auf der Umgebung eine stabil Abstiegsrichtung bestimmt. So weit es uns bekannt ist, koennen die hier entwickelten Algorithmen zum ersten Mal lokal Lipschitz-stetige Funktionen in dieser Allgemeinheit behandeln. Insbesondere wurden nichtglatte, nichtkonvexe Funktionen auf derart hochdimensionale Banachraeume bis jetzt nicht behandelt. Wir werden zeigen, dass unser Algorithmus sehr robust und oft schneller als uebliche Algorithmen ist. Des Weiteren, werden wir sehen, dass es mit diesem Algorithmus das erste mal moeglich ist, zuverlaessig die erste Eigenfunktion des 1-Laplace Operators bis auf Diskretisierungsfehler zu bestimmen

This dissertation develops efficient solution techniques for general and problem-specific applications within nonconvex optimization, exploiting the constructs of the Reformulation-Linearization Technique (RLT). We begin by developing a technique to enhance general problems in nonconvex optimization through the use of a new class of RLT cuts, called semidefinite cuts. While these cuts are valid for any general problem for which RLT is applicable, we demonstrate their effectiveness in optimizing a nonconvex quadratic objective function over a simplex. Computational results indicate that on average, the semidefinite cuts have reduced the number of nodes in the branch-and-bound tree by a factor of 37.6, while decreasing solution time by a factor of 3.4. The semidefinite cuts have also led to a significant reduction in the optimality gap at termination, in some cases producing optimal solutions for problems that could not be solved using RLT alone. We then narrow our focus to the class of mixed-integer programming (MIP) problems, and develop a modification of Bendersâ decomposition method using concepts from RLT and lift-and-project cuts. This method is particularly motivated by the class of two-stage stochastic programs with integer recourse. The key idea is to design an RLT or lift-and-project cutting plane scheme for solving the subproblems where the cuts generated have right-hand sides that are functions of the first-stage variables. An illustrative example is provided to elucidate the proposed approach. The focus is on developing a first comprehensive finitely convergent extension of Bendersâ methodology for problems having 0-1 mixed-integer subproblems. We next address a specific challenging MIP application known as the facility layout problem, and we significantly improve its formulation through outer-linearization techniques and concepts from disjunctive programming. The enhancements produce a substantial increase in the accuracy of the layout produced, while at the same time, providing a dramatic reduction in computational effort. Overall, the maximum error in department size was reduced from about 6% to nearly zero, while solution time decreased by a factor of 110. Previously unsolved test problems from the literature that had defied even approximate solution methods have been solved to exact optimality using our proposed approach.
Ph. D.

The Trust Region Subproblem (TRS), which minimizes a nonconvex quadratic function over the unit ball, is an important subproblem in trust region methods for nonlinear optimization. Even though TRS is a nonconvex problem, it can be solved in polynomial time using, for example, a semidefinite programming (SDP) relaxation. Different variants of TRS have been considered from both theoretical and practical perspectives. In this thesis, we study three variants of TRS and their SDP/conic relaxations. We first study an extended trust region subproblem (eTRS) in which the trust region equals the intersection of the unit ball with M linear cuts. When m = 0, when m = 1, or when m = 2 and the linear cuts are parallel, it is known that the eTRS optimal value equals the optimal value of a particular conic relaxation, which is solvable in polynomial time. However, it is also known that, when m ≥2 and at least two of the linear cuts intersect within the ball, i.e., some feasible point of the eTRS satisfies both linear constraints at equality, then the same conic relaxation may admit a gap with eTRS. We show that the conic relaxation admits no gap for arbitrary M as long as the linear cuts are non-intersecting. We then extend our result to a more general setting. We study an eTRS in which a quadratic function is minimized over a structured nonconvex feasible region: the unit ball with M linear cuts and R hollows. In the special case when m = 0 and r = 1, it is known that the eTRS has a tight polynomial-time solvable conic relaxation. We show that a certain conic relaxation is also tight for general R and M as long as the cuts and hollows satisfy some non-intersecting assumptions that generalize the previous paragraph. Finally, intersecting the feasible region of TRS with a second ellipsoid results in the two-trust-region subproblem (TTRS). Even though TTRS can also be solved in polynomial-time, existing approaches do not provide a concise conic relaxation. We investigate the use of conic relaxation for TTRS. Starting from the basic SDP relaxation of TTRS, which admits a gap, recent research has tightened the basic relaxation using valid second-order-cone (SOC) inequalities. For the special case of TTRS in dimension n=2, we fully characterize the remaining valid inequalities, which can be viewed as strengthened versions of the SOC inequalities just mentioned. We also demonstrate that these valid inequalities can be used computationally even when n > 2 to solve TTRS instances that were previously unsolved using techniques of conic relaxation.

Image recovery, especially image denoising and deblurring is widely studied during the last decades. Variational models can well preserve edges of images while restoring images from noise and blur. Some variational models are non-convex. For the moment, the methods for non-convex optimization are limited. This thesis finds new non-convex optimizing method called difference of convex algorithm (DCA) for solving different variational models for various kinds of noise removal problems. For imaging system, noise appeared in images can show different kinds of distribution due to the different imaging environment and imaging technique. Here we show how to apply DCA to Rician noise removal and Cauchy noise removal. The performance of our experiments demonstrates that our proposed non-convex algorithms outperform the existed ones by better PSNR and less computation time. The progress made by our new method can improve the precision of diagnostic technique by reducing Rician noise more efficiently and can improve the synthetic aperture radar imaging precision by reducing Cauchy noise within. When applying variational models to image denoising and deblurring, a significant subject is to choose the regularization parameters. Few methods have been proposed for regularization parameter selection for the moment. The numerical algorithms of existed methods for parameter selection are either complicated or implicit. In order to find a more efficient and easier way to estimate regularization parameters, we create a new image quality sharpness metric called SQ-Index which is based on the theory of Global Phase Coherence. The new metric can be used for estimating parameters for a various of variational models, but also can estimate the noise intensity based on special models. In our experiments, we show the noise estimation performance with this new metric. Moreover, extensive experiments are made for dealing with image denoising and deblurring under different kinds of noise and blur. The numerical results show the robust performance of image restoration by applying our metric to parameter selection for different variational models.

The development of wireless sensor networks (WSNs) is making it possible to monitor our cities. Due to the small size of the sensor nodes, and their capabilities of transmitting data remotely, they can be deployed at locations that are not easy or impossible to access, such as the pipelines of water distribution networks (WDNs), which plays an important role in protecting environment and securing public health.   The design of WSNs for WDNs faces major challenges. Generally, WSNs are resource-limited because most of the sensor nodes are battery powered. Thus, their resource allocation has to be carefully controlled. The thesis considers two prominent problems that occur when designing WSNs for WDNs: scheduling the sensing of the nodes of static WSNs, and sensor placement for mobile WSNs. These studies are reported in the thesis from three published or submitted papers. In the first paper, the scheduling of sleep/sensing for each sensor node is considered to maximize the whole WSNs lifetime while guaranteeing a monitoring performance constraint. The problem is transformed into an energy balancing problem, and solved by a dynamic programming based algorithm. It is proved that this algorithm finds one of the optimal solutions for the energy balancing problem. In the second paper, the question of how the energy balancing problem approximates the original scheduling problem is addressed. It is shown that even though these two problems are not equivalent, the gap of them is small enough. Thus, the proposed algorithm for the energy balancing problem can find a good approximation solution for the original scheduling problem. The second part of the thesis considers the use of mobile sensor nodes. Here, the limited resource is the number of available such mobile nodes. To maximize the monitoring coverage in terms of population, an optimization problem for determining the releasing locations for the mobile sensor nodes is formulated. An approximate solution algorithm based on submodular maximization is proposed and its performance is investigated. Beside WDNs, WSN applications for smart cities share a common characteristic: the area to monitor usually has a network structure. Therefore, the studies of this thesis can be potentially generalized for several IoT scenarios.

QC 20160419

Thesis (Ph. D.)--Ohio State University, 2004.
Title from first page of PDF file. Document formatted into pages; contains x, 71 p.; also includes graphics Includes bibliographical references (p. 69-71). Available online via OhioLINK's ETD Center

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 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

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

碩士
東海大學
應用數學研究所
83
In this thesis, we introduce vector tau-connected set,rc- connected convex set and semi-connected set. We discussemi- preinvex map which include preinvex map and arc-connectedonvex map on a semi-connected set. Any locally minimum islso a global minimum for semi-preinvex maps, so we only toiscuss the local minimum point. Alternative theorem foronvex-like is also valid for a semi-preinvex mapping on aemi-connected set. If the mappings are arc-directionallyifferentiable corresponding to a continuous map, then theritz John type Theorem is derived for semi-preinvex programmingroblems. We discuss multiobjective functions which is d-invexnd find necessary and sufficient conditions. The variationalnequality problem plays very important relation with optimizationroblem, so we introduce the pre-variational inequality ( PVI )roblem. If a mapping is invex, then x_o solves the ( PVI )roblem if and only if x_o is an optimal solution fornconstrained optimization problem. Finally, we prove there-variational problem is solvable under some conditions.

碩士
國立臺北科技大學
商業自動化與管理研究所
95
Although many algorithms and packages which can solve generalized geometric programming problems have been proposed, most of them are too time consuming and cannot guarantee to obtain a global optimum. To overcome the difficulties, this study would like to improve current optimization approaches and attempt to merge these ideas to suit the needs of strategic models. Theoretically, this study utilizes convexification strategies and convex underestimation to convert the source problem into a convex program. A global optimum can then be found by a branch-and-bound algorithm. Computationally, this study develops a global optimizer with embedded LINGO NLP Solver capable of deriving solutions with better quality. Moreover, several numerical examples are used to demonstrate the effectiveness of the developed optimizer. The results of experiments show: (1) compared with Tsai’s methods, this study uses convex underestimation instead of piecewise linearization technique to alleviate the difficulty in deciding the number of break points in advance; (2) the developed optimizer can yield tighter convex relaxations than BARON for solving some generalized geometric programming problems.

Today we are living in the era of big data, there is a pressing need for efficient, scalable and robust optimization methods to analyze the data we create and collect. Although Convex methods offer tractable solutions with global optimality, heuristic nonconvex methods are often more attractive in practice due to their superior efficiency and scalability. Moreover, for better representations of the data, the mathematical model we are building today are much more complicated, which often results in highly nonlinear and nonconvex optimizations problems. Both of these challenges require us to go beyond convex optimization. While nonconvex optimization is extraordinarily successful in practice, unlike convex optimization, guaranteeing the correctness of nonconvex methods is notoriously difficult. In theory, even finding a local minimum of a general nonconvex function is NP-hard – nevermind the global minimum. This thesis aims to bridge the gap between practice and theory of nonconvex optimization, by developing global optimality guarantees for nonconvex problems arising in real-world engineering applications, and provable, efficient nonconvex optimization algorithms. First, this thesis reveals that for certain nonconvex problems we can construct a model specialized initialization that is close to the optimal solution, so that simple and efficient methods provably converge to the global solution with linear rate. These problem include sparse basis learning and convolutional phase retrieval. In addition, the work has led to the discovery of a broader class of nonconvex problems – the so-called ridable saddle functions. Those problems possess characteristic structures, in which (i) all local minima are global, (ii) the energy landscape does not have any ''flat'' saddle points. More interestingly, when data are large and random, this thesis reveals that many problems in the real world are indeed ridable saddle, those problems include complete dictionary learning and generalized phase retrieval. For each of the aforementioned problems, the benign geometric structure allows us to obtain global recovery guarantees by using efficient optimization methods with arbitrary initialization.

Nonconvex optimization is NP-hard, even the goal is to compute a local minimizer. In applied disciplines, however, nonconvex problems abound, and simple algorithms, such as gradient descent and alternating direction, are often surprisingly effective. The ability of simple algorithms to find high-quality solutions for practical nonconvex problems remains largely mysterious. This thesis focuses on a class of nonconvex optimization problems which CAN be solved to global optimality with polynomial-time algorithms. This class covers natural nonconvex formulations of central problems in signal processing, machine learning, and statistical estimation, such as sparse dictionary learning (DL), generalized phase retrieval (GPR), and orthogonal tensor decomposition. For each of the listed problems, the nonconvex formulation and optimization lead to novel and often improved computational guarantees. This class of nonconvex problems has two distinctive features: (i) All local minimizer are also global. Thus obtaining any local minimizer solves the optimization problem; (ii) Around each saddle point or local maximizer, the function has a negative directional curvature. In other words, around these points, the Hessian matrices have negative eigenvalues. We call smooth functions with these two properties (qualitative) X functions, and derive concrete quantities and strategy to help verify the properties, particularly for functions with random inputs or parameters. As practical examples, we establish that certain natural nonconvex formulations for complete DL and GPR are X functions with concrete parameters. Optimizing X functions amounts to finding any local minimizer. With generic initializations, typical iterative methods at best only guarantee to converge to a critical point that might be a saddle point or local maximizer. Interestingly, the X structure allows a number of iterative methods to escape from saddle points and local maximizers and efficiently find a local minimizer, without special initializations. We choose to describe and analyze the second-order trust-region method (TRM) that seems to yield the strongest computational guarantees. Intuitively, second-order methods can exploit Hessian to extract negative curvature directions around saddle points and local maximizers, and hence are able to successfully escape from the saddles and local maximizers of X functions. We state the TRM in a Riemannian optimization framework to cater to practical manifold-constrained problems. For DL and GPR, we show that under technical conditions, the TRM algorithm finds a global minimizer in a polynomial number of steps, from arbitrary initializations.

碩士
國立成功大學
數學系應用數學碩博士班
98
In this thesis, we discuss the minimum of a quadratic object function with one nonconvex quadratic constraint. We want to find the primal optimal solution via its corresponding canonical dual solution. We propose the relaxed assumption, simultaneously diagonalization via congruence (SDC), rather than traditional Slater condition. Under this relaxed assumption, we prove that we can still use information from dual problem to find the primal optimal solution. The key point is when the primal solution we found via its corresponding dual solution is not the optimal solution, we can apply ``boundirification technique' to find another solution with no duality gap, and this is also the primal optimal solution. With further analysis, this primal nonconvex problem in fact equals a linearly constrained convex problem, which means a quadratic object function with one quadratic constraint is a nice-structured nonconvex problem. Finally, we have a related review and comparison to Stern and Wolkowicz's result in 1995.

Ng, Chi Kong.
"May 2003."
Thesis (Ph.D.)--Chinese University of Hong Kong, 2003.
Includes bibliographical references (p. 175-187).
Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web.
Electronic reproduction. Ann Arbor, MI : ProQuest Information and Learning Company, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web.
Mode of access: World Wide Web.
Abstracts in English and Chinese.

In this thesis, we consider the following two important subjects in the modern variational analysis for the corresponding nonconvex/nonmonotone and nonsmooth cases: geometric results and the variational inequality problem. By using the variational technique, we first present several nonsmooth (nonconvex) geometric results (including an approximate projection result, an extended extremal principle, nonconvex separation theorems, a nonconvex generalization of the Bishop-Phelps theorem and a separable point result) which extend some fundamental theorems in linear functional analysis, convex analysis and optimization theory. Then, by transforming the variational inequality problem into equivalent optimization problems, we establish some error bound result for the nonsmooth and nonmonotone variational inequality problem.
Variational arguments are classical techniques whose use can be traced back to the early development of the calculus of variations. Rooted in the physical principle of least action they have evolved greatly in connection with applications in optimization theory and optimal control. Recently, the discovery of modern variational principles and nonsmooth analysis further expand the range of applications of these techniques and give a new way for extending some geometric results in linear functional analysis and convex analysis.
Li, Guoyin.
"August 2007."
Adviser: Kung-Fu Ng.
Source: Dissertation Abstracts International, Volume: 69-02, Section: B, page: 1043.
Thesis (Ph.D.)--Chinese University of Hong Kong, 2007.
Includes bibliographical references (p. 80-86).
Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web.
Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web.
Abstract in English and Chinese.
School code: 1307.

In many applications nonsmooth nonconvex energy functions, which are Lipschitz continuous, appear quite naturally. Contact mechanics with friction is a classic example. A second example is the 1-Laplace operator and its eigenfunctions. In this work we will give an algorithm such that for every locally Lipschitz continuous function f and every sequence produced by this algorithm it holds that every accumulation point of the sequence is a critical point of f in the sense of Clarke. Here f is defined on a reflexive Banach space X, such that X and its dual space X' are strictly convex and Clarkson's inequalities hold. (E.g. Sobolev spaces and every closed subspace equipped with the Sobolev norm satisfy these assumptions for p>1.) This algorithm is designed primarily to solve variational problems or their high dimensional discretizations, but can be applied to a variety of locally Lipschitz functions. In elastic contact mechanics the strain energy is often smooth and nonconvex on a suitable domain, while the contact and the friction energy are nonsmooth and have a support on a subspace which has a substantially smaller dimension than the strain energy, since all points in the interior of the bodies only have effect on the strain energy. For such elastic contact problems we suggest a specialization of our algorithm, which treats the smooth part with Newton like methods. In the case that the gradient of the entire energy function is semismooth close to the minimizer, we can even prove superlinear convergence of this specialization of our algorithm. We test the algorithm and its specialization with a couple of benchmark problems. Moreover, we apply the algorithm to the 1-Laplace minimization problem restricted to finitely dimensional subspaces of piecewise affine, continuous functions. The algorithm developed here uses ideas of the bundle trust region method by Schramm, and a new generalization of the concept of gradients on a set. The basic idea behind this gradients on sets is that we want to find a stable descent direction, which is a descent direction on an entire neighborhood of an iteration point. This way we avoid oscillations of the gradients and very small descent steps (in the smooth and in the nonsmooth case). It turns out, that the norm smallest element of the gradient on a set provides a stable descent direction. The algorithm we present here is the first algorithm which can treat locally Lipschitz continuous functions in this generality, up to our knowledge. In particular, large finitely dimensional Banach spaces haven't been studied for nonsmooth nonconvex functions so far. We will show that the algorithm is very robust and often faster than common algorithms. Furthermore, we will see that with this algorithm it is possible to compute reliably the first eigenfunctions of the 1-Laplace operator up to disretization errors, for the first time.
In vielen Anwendungen tauchen nichtglatte, nichtkonvexe, Lipschitz-stetige Energie Funktionen in natuerlicher Weise auf. Ein klassische Beispiel bildet die Kontaktmechanik mit Reibung. Ein weiteres Beispiel ist der $1$-Laplace Operator und seine Eigenfunktionen. In dieser Dissertation werden wir ein Abstiegsverfahren angeben, so dass fuer jede lokal Lipschitz-stetige Funktion f jeder Haeufungspunkt einer durch dieses Verfahren erzeugten Folge ein kritischer Punkt von f im Sinne von Clarke ist. Hier ist f auf einem einem reflexiver, strikt konvexem Banachraum definierert, fuer den der Dualraum ebenfalls strikt konvex ist und die Clarkeson Ungleichungen gelten. (Z.B. Sobolevraeume und jeder abgeschlossene Unterraum mit der Sobolevnorm versehen, erfuellt diese Bedingung fuer p>1.) Dieser Algorithmus ist primaer entwickelt worden um Variationsprobleme, bzw. deren hochdimensionalen Diskretisierungen zu loesen. Er kann aber auch fuer eine Vielzahl anderer lokal Lipschitz stetige Funktionen eingesetzt werden. In der elastischen Kontaktmechanik ist die Spannungsenergie oft glatt und nichtkonvex auf einem geeignetem Definitionsbereich, waehrend der Kontakt und die Reibung durch nicht glatte Funktionen modelliert werden, deren Traeger ein Unterraum mit wesentlich kleineren Dimension ist, da alle Punkte im Inneren des Koerpers nur die Spannungsenergie beeinflussen. Fuer solche elastischen Kontaktprobleme schlagen wir eine Spezialisierung unseres Algorithmuses vor, der den glatten Teil mit Newton aehnlichen Methoden behandelt. Falls der Gradient der gesamten Energiefunktion semiglatt in der Naehe der Minimalstelle ist, koennen wir sogar beweisen, dass der Algorithmus superlinear konvergiert. Wir testen den Algorithmus und seine Spezialisierung an mehreren Benchmark Problemen. Ausserdem wenden wir den Algorithmus auf 1-Laplace Minimierungsproblem eingeschraenkt auf eine endlich dimensionalen Unterraum der stueckweise affinen, stetigen Funktionen an. Der hier entwickelte Algorithmus verwendet Ideen des Bundle-Trust-Region-Verfahrens von Schramm, und einen neu entwickelten Verallgemeinerung von Gradienten auf Mengen. Die zentrale Idee hinter den Gradienten auf Mengen ist die, dass wir stabile Abstiegsrichtungen auf einer ganzen Umgebung der Iterationspunkte finden wollen. Auf diese Weise vermeiden wir das Oszillieren der Gradienten und sehr kleine Abstiegsschritte (im glatten, wie im nichtglatten Fall.) Es stellt sich heraus, dass das normkleinste Element dieses Gradienten auf der Umgebung eine stabil Abstiegsrichtung bestimmt. So weit es uns bekannt ist, koennen die hier entwickelten Algorithmen zum ersten Mal lokal Lipschitz-stetige Funktionen in dieser Allgemeinheit behandeln. Insbesondere wurden nichtglatte, nichtkonvexe Funktionen auf derart hochdimensionale Banachraeume bis jetzt nicht behandelt. Wir werden zeigen, dass unser Algorithmus sehr robust und oft schneller als uebliche Algorithmen ist. Des Weiteren, werden wir sehen, dass es mit diesem Algorithmus das erste mal moeglich ist, zuverlaessig die erste Eigenfunktion des 1-Laplace Operators bis auf Diskretisierungsfehler zu bestimmen.

Gradient descent and related algorithms are ubiquitously used to solve optimization problems arising in machine learning and signal processing. In many cases, these problems are nonconvex yet such simple algorithms are still effective. In an attempt to better understand this phenomenon, we study a number of nonconvex problems, proving that they can be solved efficiently with gradient descent. We will consider complete, orthogonal dictionary learning, and present a geometric analysis allowing us to obtain efficient convergence rate for gradient descent that hold with high probability. We also show that similar geometric structure is present in other nonconvex problems such as generalized phase retrieval. Turning next to neural networks, we will also calculate conditions on certain classes of networks under which signals and gradients propagate through the network in a stable manner during the initial stages of training. Initialization schemes derived using these calculations allow training recurrent networks on long sequence tasks, and in the case of networks with low precision activation functions they make explicit a tradeoff between the reduction in precision and the maximal depth of a model that can be trained with gradient descent. We finally consider manifold classification with a deep feed-forward neural network, for a particularly simple configuration of the manifolds. We provide an end-to-end analysis of the training process, proving that under certain conditions on the architectural hyperparameters of the network, it can successfully classify any point on the manifolds with high probability given a sufficient number of independent samples from the manifold, in a timely manner. Our analysis relates the depth and width of the network to its fitting capacity and statistical regularity respectively in early stages of training.

Due to the broadcast nature of wireless medium, simultaneous transmissions interfere with each other (especially transmissions on nearby links), thus adversely affecting data rates and Quality of Service (QoS) in the system. Interference mitigation is therefore a fundamental issue that must be addressed in next generation wireless networks. An important technique for this is to control the links' transmission power. Driven by the wide spread of broadband wireless data services, a system-wide efficiency metric (i.e., system utility) is typically used to characterize the advantage of power control.
In interference-limited wireless networks where simultaneous transmissions on nearby links heavily interfere with each other, however, power control alone is not sufficient to eliminate strong levels of interference between close-by links. In this case, scheduling, which allows close-by links to take turns to be active, plays a crucial role for achieving high system performance. Joint power control and scheduling that maximizes the system utility has long been a challenging problem. The complicated coupling between the signal-to-interference ratio of concurrently active links as well as the flexibility to vary power allocation over time gives rise to a series of non-convex optimization problems, for which the global optimal solution is hard to obtain. The second goal of this thesis is to solve the non-convex joint power control and scheduling problems efficiently in a global optimal manner. In particular, it is the monotonicity rather than the convexity of the problem that we exploit to devise an efficient algorithm, referred to as S-MAPEL, to obtain the global optimal solution. To further reduce the complexity, we propose an accelerated algorithm, referred to as A-S-MAPEL, based on the inherent symmetry of the optimal solution. The optimal joint-power-control-and-scheduling solution obtained by the proposed algorithms serves as a useful benchmark for evaluating other existing schemes. With the help of this benchmark, we find that on-off scheduling is of much practical value in terms of system utility maximization if "off-the-shelf' wireless devices are to be used.
Maximizing a system-wide utility through power control is an NP-hard problem in general due to the complicated coupling interference between links. Thus, it is difficult to solve despite its paramount importance. The first goal of this thesis is to find global optimal power allocations to a variety of system utility maximization (SUM) problems based on the recent advances in monotonic optimization. Instead of tackling the non-convexity issue head on, we bypass non-convexity by exploiting the monotonic nature of the power control problem. In particular, we establish a monotonic optimization framework to maximize a system utility through power control in single-carrier or multi-carrier wireless networks. Furthermore, MAPEL and M-MAPEL are respectively proposed to obtain the global optimal power allocation efficiently in single-carrier or multi-carrier wireless networks. The main benefit of MAPEL and M-MAPEL is to provide an important benchmark for performance evaluation of other heuristic algorithms targeting the same problem. With the help of MAPEL or M-MAPEL, we evaluate the performance of several existing algorithms through extensive simulations. On the other hand, by tuning the approximation factor in MAPEL and M-MAPEL, we could engineer a desirable tradeoff between optimality and convergence time.
With the proliferation of wireless infrastructureless networks such as ad hoc and sensor networks, it is increasingly crucial to devise an algorithm that solves the power control problem in a distributed fashion. In general, distributed power control is more complicated due to the lack of centralized infrastructure. As the third goal of this thesis, we consider a distributed power control algorithm for infrastructureless ad hoc wireless networks, where each link distributively and asynchronously updates its transmission power with limited message passing among links. This algorithm provably converges to the optimal strategy that picks global optimal solutions with probability 1 despite the non-convexity of the power control problem. In contrast with existing distributed power control algorithms, our algorithm makes no stringent assumptions on the system utility functions. In particular, the utility function is allowed to be concave or non-concave, differentiable or non-differentiable, continuous or discontinuous, and monotonic or non-monotonic.
Qian, Liping.
Adviser: Yingjun (Angela) Zhang.
Source: Dissertation Abstracts International, Volume: 72-04, Section: B, page: .
Thesis (Ph.D.)--Chinese University of Hong Kong, 2010.
Includes bibliographical references (leaves 133-139).
Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web.
Electronic reproduction. Ann Arbor, MI : ProQuest Information and Learning Company, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web.
Abstract also in Chinese.

The solution of a single optimization problem often requires computationally-demanding evaluations; this is especially true in optimal design of engineering components and systems described by partial differential equations. We present a technique for the rapid and reliable optimization of systems characterized by linear-functional outputs of partial differential equations with affine parameter dependence. The critical ingredients of the method are: (i) reduced-basis techniques for dimension reduction in computational requirements; (ii) an "off-line/on-line" computational decomposition for the rapid calculation of outputs of interest and respective sensitivities in the limit of many queries; (iii) a posteriori error bounds for rigorous uncertainty and feasibility control; (iv) Interior Point Methods (IPMs) for efficient solution of the optimization problem; and (v) a trust-region Sequential Quadratic Programming (SQP) interpretation of IPMs for treatment of possibly non-convex costs and constraints.
Singapore-MIT Alliance (SMA)

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.