Dissertations / Theses on the topic 'Quadratically Constrained Linear Programming'
To see the other types of publications on this topic, follow the link: Quadratically Constrained Linear Programming.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Quadratically Constrained Linear Programming.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
P, Van Voorhis Timothy. "The quadratically constrained quadratic program." Diss., Georgia Institute of Technology, 1997. http://hdl.handle.net/1853/23379.
Full text
2
Wang, Guanglei. "Relaxations in mixed-integer quadratically constrained programming and robust programming." Thesis, Evry, Institut national des télécommunications, 2016. http://www.theses.fr/2016TELE0026/document.
Full textAbstract:
De nombreux problèmes de la vie réelle sont exprimés sous la forme de décisions à prendre à l’aide de l’information accessible dans le but d’atteindre certains objectifs. La programmation numérique a prouvé être un outil efficace pour modéliser et résoudre une grande variété de problèmes de ce type. Cependant, de nombreux problèmes en apparence faciles sont encore durs à résoudre. Et même des problèmes faciles de programmation linéaire deviennent durs avec l’incertitude de l’information disponible. Motivés par un problème de télécommunication où l’on doit associer des machines virtuelles à des serveurs tout en minimisant les coûts, nous avons employé plusieurs outils de programmation mathématique dans le but de résoudre efficacement le problème, et développé de nouveaux outils pour des problèmes plus généraux. Dans l’ensemble, résumons les principaux résultats de cette thèse comme suit. Une formulation exacte et plusieurs reformulations pour le problème d’affectation de machines virtuelles dans le cloud sont données. Nous utilisons plusieurs inégalités valides pour renforcer la formulation exacte, accélérant ainsi l’algorithme de résolution de manière significative. Nous donnons en outre un résultat géométrique sur la qualité de la borne lagrangienne montrant qu’elle est généralement beaucoup plus forte que la borne de la relaxation continue. Une hiérarchie de relaxation est également proposée en considérant une séquence de couverture de l’ensemble de la demande. Ensuite, nous introduisons une nouvelle formulation induite par les symétries du problème. Cette formulation permet de réduire considérablement le nombre de termes bilinéaires dans le modèle, et comme prévu, semble plus efficace que les modèles précédents. Deux approches sont développées pour la construction d’enveloppes convexes et concaves pour l’optimisation bilinéaire sur un hypercube. Nous établissons plusieurs connexions théoriques entre différentes techniques et nous discutons d’autres extensions possibles. Nous montrons que deux variantes de formulations pour approcher l’enveloppe convexe des fonctions bilinéaires sont équivalentes. Nous introduisons un nouveau paradigme sur les problèmes linéaires généraux avec des paramètres incertains. Nous proposons une hiérarchie convergente de problèmes d’optimisation robuste – approche robuste multipolaire, qui généralise les notions de robustesse statique, de robustesse d’affinement ajustable, et de robustesse entièrement ajustable. En outre, nous montrons que l’approche multipolaire peut générer une séquence de bornes supérieures et une séquence de bornes inférieures en même temps et les deux séquences convergent vers la valeur robuste des FARC sous certaines hypothèses modéréesMany real life problems are characterized by making decisions with current information to achieve certain objectives. Mathematical programming has been developed as a successful tool to model and solve a wide range of such problems. However, many seemingly easy problems remain challenging. And some easy problems such as linear programs can be difficult in the face of uncertainty. Motivated by a telecommunication problem where assignment decisions have to be made such that the cloud virtual machines are assigned to servers in a minimum-cost way, we employ several mathematical programming tools to solve the problem efficiently and develop new tools for general theoretical problems. In brief, our work can be summarized as follows. We provide an exact formulation and several reformulations on the cloud virtual machine assignment problem. Then several valid inequalities are used to strengthen the exact formulation, thereby accelerating the solution procedure significantly. In addition, an effective Lagrangian decomposition is proposed. We show that, the bounds providedby the proposed Lagrangian decomposition is strong, both theoretically and numerically. Finally, a symmetry-induced model is proposed which may reduce a large number of bilinear terms in some special cases. Motivated by the virtual machine assignment problem, we also investigate a couple of general methods on the approximation of convex and concave envelopes for bilinear optimization over a hypercube. We establish several theoretical connections between different techniques and prove the equivalence of two seeming different relaxed formulations. An interesting research direction is also discussed. To address issues of uncertainty, a novel paradigm on general linear problems with uncertain parameters are proposed. This paradigm, termed as multipolar robust optimization, generalizes notions of static robustness, affinely adjustable robustness, fully adjustable robustness and fills the gaps in-between. As consequences of this new paradigms, several known results are implied. Further, we prove that the multipolar approach can generate a sequence of upper bounds and a sequence of lower bounds at the same time and both sequences converge to the robust value of fully adjustable robust counterpart under some mild assumptions
3
Crowe, Mitch. "Nonlinearly constrained optimization via sequential regularized linear programming." Thesis, University of British Columbia, 2010. http://hdl.handle.net/2429/29648.
Full textAbstract:
This thesis proposes a new active-set method for large-scale nonlinearly con
strained optimization. The method solves a sequence of linear programs to
generate search directions. The typical approach for globalization is based on
damping the search directions with a trust-region constraint; our proposed ap
proach is instead based on using a 2-norm regularization term in the objective.
Numerical evidence is presented which demonstrates scaling inefficiencies
in current sequential linear programming algorithms that use a trust-region
constraint. Specifically, we show that the trust-region constraints in the trustregion
subproblems significantly reduce the warm-start efficiency of these subproblem
solves, and also unnecessarily induce infeasible subproblems. We also
show that the use of a regularized linear programming (RLP) step largely elim
inates these inefficiencies and, additionally, that the dual problem to RLP is
a bound-constrained least-squares problem, which may allow for very efficient
subproblem solves using gradient-projection-type algorithms.
Two new algorithms were implemented and are presented in this thesis,
based on solving sequences of RLPs and trust-region constrained LPs. These
algorithms are used to demonstrate the effectiveness of each type of subproblem,
which we extrapolate onto the effectiveness of an RLP-based algorithm with the
addition of Newton-like steps.
All of the source code needed to reproduce the figures and tables presented
in this thesis is available online at
http: //www.cs.ubc.ca/labs/scl/thesis/lOcrowe/
4
Zhao, Jianmin. "Optimal Clustering: Genetic Constrained K-Means and Linear Programming Algorithms." VCU Scholars Compass, 2006. http://hdl.handle.net/10156/1583.
Full text
5
Hardin, Jill Renea. "Resource-constrained scheduling and production planning : linear programming-based studies." Diss., Georgia Institute of Technology, 2001. http://hdl.handle.net/1853/24857.
Full text
6
Wang, Yanhui. "Affine scaling algorithms for linear programs and linearly constrained convex and concave programs." Diss., Georgia Institute of Technology, 1996. http://hdl.handle.net/1853/24919.
Full text
7
Viana, Luiz Alberto do Carmo. "Dependency constrained minimum spanning tree." Universidade Federal do CearÃ, 2016. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=17302.
Full textAbstract:
FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgicoIntroduzimos o problema de Ãrvore Geradora com DependÃncias MÃnima, AGDM(G,D,w), definido sobre um grafo G(V,E) e um digrafo D(E,A), cujos vÃrtices sÃo as arestas de G e cujos arcos definem dependÃncias entre tais arestas. O problema consiste em encontrar, dentre as Ãrvores geradoras do grafo G(V,E) que satisfaÃam as restriÃÃes de dependÃncia impostas pelo digrafo de entrada D(E,A), uma que tenha custo mÃnimo, segundo a ponderaÃÃo w das arestas de G. As restriÃÃes de dependÃncia exigem que uma aresta e de G sà pode fazer parte de uma soluÃÃo se for uma fonte em D ou se fizer parte da soluÃÃo alguma outra aresta à tal que o arco (e′, e) esteja em D. Provamos que decidir se hà soluÃÃo viÃvel para AGDM(G,D,w) à um problema NP-completo, mesmo quando G à um cacto cordal e D à a uniÃo de arborescÃncias de altura no mÃximo 2. Sua NP-completude tambÃm à mostrada ainda que G seja bipartido, as restriÃÃes de dependÃncia ocorram apenas entre arestas adjacentes de G e formem arborescÃncias de altura no mÃximo 2. Resultados idÃnticos sÃo obtidos para as variantes do problema onde, nas restriÃÃes de dependÃncia, substitui-se o requisito âalgumaâ por âexatamente umaâ ou âtodaâ. Para resolver o problema, apresentamos algumas formulaÃÃes de programaÃÃo inteira e desigualdades vÃlidas. Propomos uma estratÃgia para reduzir a dimensÃo do problema, excluindo arestas de G com base na estrutura de D. Avaliamos os modelos e algoritmos propostos usando instÃncias geradas aleatoriamente. Resultados computacionais sÃo reportados.
We introduce the Dependency Constrained Minimum Spanning Tree Problem, DCMST(G,D,w), defined over a graph G(V,E) and a digraph D(E,A), whose vertices are the edges of G and whose arcs describe dependency relations between these edges. Such problem consists of finding, among the spanning trees of G(V,E) satisfying the dependency constraints imposed by D(E,A), that one whose cost is minimum, according to a edgeweight function w. The dependency constraints impose that an edge e of G can be part of a solution either if it is a source in D or if some other edge e′, such that the arc (e′, e) is in D, is part of it as well. We prove that deciding whether there is a feasible solution to DCMST(G,D,w) is an NP-complete problem, even if G is a chordal cactus and D is a union of arborescences of height at most 2. NP-completeness also applies if G is bipartite, the dependency constraints occur only between adjacent edges of G and their related arcs describe arborescences whose height is at most 2. The same results are obtained for the problem variants which demand that, instead of âsomeâ, âexactly oneâor âallâdependencies be part of a solution. To solve the problem, we introduce some integer programming formulations and some valid inequalities. We propose a strategy to reduce the problem dimension by excluding some edges of G according to the structure of D. We evaluate the introduced models and algorithms using randomly generated instances. Computational results are reported.
8
Aslan, Murat. "The Cardinality Constrained Multiple Knapsack Problem." Master's thesis, METU, 2008. http://etd.lib.metu.edu.tr/upload/12610131/index.pdf.
Full textAbstract:
The classical multiple knapsack problem selects a set of items and assigns each to one of the knapsacks so as to maximize the total profit. The knapsacks have limited capacities. The cardinality constrained multiple knapsack problem assumes limits on the number of items that are to be put in each knapsack, as well. Despite many efforts on the classical multiple knapsack problem, the research on the cardinality constrained multiple knapsack problem is scarce.
In this study we consider the cardinality constrained multiple knapsack problem. We propose heuristic and optimization procedures that rely on the optimal solutions of the linear programming relaxation problem. Our computational results on the large-sized problem instances have shown the satisfactory performances of our algorithms.
9
Pedroso, Lucas Garcia. "Programação não linear sem derivadas." [s.n.], 2009. http://repositorio.unicamp.br/jspui/handle/REPOSIP/307473.
Full textAbstract:
Orientadores: Jose Mario Martinez, Maria Aparecida Diniz EhrhardtTese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica
Made available in DSpace on 2018-08-14T08:44:35Z (GMT). No. of bitstreams: 1 Pedroso_LucasGarcia_D.pdf: 1569234 bytes, checksum: 22491a86b6f7cc218acc26f3c2cb768a (MD5) Previous issue date: 2009
Resumo: Neste trabalho propomos um algoritmo Lagrangiano Aumentado sem derivadas para o problema geral de otimização. Consideramos o método introduzido por Andreani, Birgin, Martínez e Schuverdt, eliminando os cálculos de derivadas inerentes ao algoritmo através de modificações adequadas no critério de parada. Foram mantidos os bons resultados teóricos do método, como convergência sob a condição de qualificação CPLD e a limitação do parâmetro de penalidade. Experimentos numéricos são apresentados, entre os quais destacamos um exemplo de problema sem derivadas baseado na simulação de áreas de figuras no plano.
Abstract: We propose in this work a derivative-free Augmented Lagrangian algorithm for the general problem of optimization. We consider the method due to Andreani, Birgin, Martínez and Schuverdt, eliminating the derivative computations in the algorithm by making suitable modifications on the stopping criterion. The good theoretical results of the method were mantained, as convergence under the CPLD constraint qualification and the limitation of the penalty parameter. Numerical experiments are presented, and the most relevant of them is an example of derivative-free problem based on the simulation of areas of figures on the plane.
Doutorado
Otimização Matematica
Doutor em Matemática Aplicada
10
Vanden, Berghen Frank. "Constrained, non-linear, derivative-free, parallel optimization of continuous, high computing load, noisy objective functions." Doctoral thesis, Universite Libre de Bruxelles, 2004. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/211177.
Full textAbstract:
The main result is a new original algorithm: CONDOR ("COnstrained, Non-linear, Direct, parallel Optimization using trust Region method for high-computing load, noisy functions"). The aim of this algorithm is to find the minimum x* of an objective function F(x) (x is a vector whose dimension is between 1 and 150) using the least number of function evaluations of F(x). It is assumed that the dominant computing cost of the optimization process is the time needed to evaluate the objective function F(x) (One evaluation can range from 2 minutes to 2 days). The algorithm will try to minimize the number of evaluations of F(x), at the cost of a huge amount of routine work. CONDOR is a derivate-free optimization tool (i.e. the derivatives of F(x) are not required. The only information needed about the objective function is a simple method (written in Fortran, C++,) or a program (a Unix, Windows, Solaris, executable) which can evaluate the objective function F(x) at a given point x. The algorithm has been specially developed to be very robust against noise inside the evaluation of the objective function F(x). This hypotheses are very general, the algorithm can thus be applied on a vast number of situations. CONDOR is able to use several CPU's in a cluster of computers. Different computer architectures can be mixed together and used simultaneously to deliver a huge computing power. The optimizer will make simultaneous evaluations of the objective function F(x) on the available CPU's to speed up the optimization process. The experimental results are very encouraging and validate the quality of the approach: CONDOR outperforms many commercial, high-end optimizer and it might be the fastest optimizer in its category (fastest in terms of number of function evaluations). When several CPU's are used, the performances of CONDOR are currently unmatched (may 2004). CONDOR has been used during the METHOD project to optimize the shape of the blades inside a Centrifugal Compressor (METHOD stands for Achievement Of Maximum Efficiency For Process Centrifugal Compressors THrough New Techniques Of Design). In this project, the objective function is based on a 3D-CFD (computation fluid dynamic) code which simulates the flow of the gas inside the compressor.Doctorat en sciences appliquées
info:eu-repo/semantics/nonPublished
11
Lieder, Felix [Verfasser]. "Projection Based Methods for Conic Linear Programming — Optimal First Order Complexities and Norm Constrained Quasi Newton Methods / Felix Lieder." Düsseldorf : Universitäts- und Landesbibliothek der Heinrich-Heine-Universität Düsseldorf, 2018. http://d-nb.info/1166398277/34.
Full text
12
Nguyen, Ngoc Anh. "Explicit robust constrained control for linear systems : analysis, implementation and design based on optimization." Thesis, Université Paris-Saclay (ComUE), 2015. http://www.theses.fr/2015SACLC012/document.
Full textAbstract:
Les lois de commande affines par morceaux ont attiré une grande attention de la communauté d'automatique de contrôle grâce à leur pertinence pour des systèmes contraints, systèmes hybrides; également pour l'approximation de commandes nonlinéaires. Pourtant, leur mise en oeuvre est soumise à quelques difficultés. Motivé par l'intérêt à cette classe de commandes, cette thèse porte sur leur analyse, mise en oeuvre et synthèse.La première partie de cette thèse a pour but le calcul de la marge de robustesse et de la marge de fragilité pour une loi de commande affine par morceaux donnée et un système linéaire discret. Plus précisément, la marge de robustesse est définie comme l'ensemble des systèmes linéaires à paramètres variants que la loi de commande donnée garde les trajectoires dans de la région faisable. D'ailleurs, la marge de fragilité comprend toutes les variations des coefficients de la commande donnée telle que l'invariance de la région faisable soit encore garantie. Il est montré que si la région faisable donnée est un polytope, ces marges sont aussi des polytopes.La deuxième partie de ce manuscrit est consacrée au problème de l'optimalité inverse pour la classe des fonctions affines par morceaux. C'est-à-dire, l'objective est de définir un problème d'optimisation pour lequel la solution optimale est équivalente à la fonction affine par morceaux donnée. La méthodologie est fondée sur le convex lifting, i.e., un variable auxiliaire, scalaire, qui permet de définir un ensemble convex à partir de la partition d'état de la fonction affine par morceaux donnée. Il est montré que si la fonction affine par morceaux donnée est continue, la solution optimale de ce problème redéfini sera unique. Par contre, si la continuité n'est pas satisfaite, cette fonction affine par morceaux sera une solution optimale parmi les autres du problème redéfini.En ce qui concerne l’application dans la commande prédictive, il sera montré que n'importe quelle loi de commande affine par morceaux continue peut être obtenue par un autre problème de commande prédictive avec l'horizon de prédiction au plus égal à 2. A côté de cet aspect théorique, ce résultat sera utile pour faciliter la mise en oeuvre des lois de commandes affines par morceaux en évitant l'enregistrement de la partition de l'espace d'état. Dans la dernière partie de ce rapport, une famille de convex liftings servira comme des fonctions de Lyapunov. En conséquence, ce "convex lifting" sera déployé pour synthétiser des lois de commande robustes pour des systèmes linéaires incertains, également en présence de perturbations additives bornées. Des lois implicites et explicites seront obtenues en même temps. Cette méthode permet de garantir la faisabilité récursive et la stabilité robuste. Cependant, cette fonction de Lyapunov est limitée à l'ensemble λ −contractive maximal avec une constante scalaire 0 ≤ λ < 1 qui est plus petit que l'ensemble contrôlable maximal. Pour cette raison, une extension de cette méthode pour l'ensemble contrôlable de N − pas, sera présentée. Cette méthode est fondée sur des convex liftings en cascade où une variable auxiliaire sera utilisée pour servir comme une fonction de Lyapunov. Plus précisément, cette variable est non-négative, strictement décroissante pour les N premiers pas et égale toujours à 0 − après. Par conséquent, la stabilité robuste est garantiePiecewise affine (PWA) feedback control laws have received significant attention due to their relevance for the control of constrained systems, hybrid systems; equally for the approximation of nonlinear control. However, they are associated with serious implementation issues. Motivated from the interest in this class of particular controllers, this thesis is mostly related to their analysis and design.The first part of this thesis aims to compute the robustness and fragility margins for a given PWA control law and a linear discrete-time system. More precisely, the robustness margin is defined as the set of linear time-varying systems such that the given PWA control law keeps the trajectories inside a given feasible set. On a different perspective, the fragility margin contains all the admissible variations of the control law coefficients such that the positive invariance of the given feasible set is still guaranteed. It will be shown that if the given feasible set is a polytope, then so are these robustness/fragility margins.The second part of this thesis focuses on inverse optimality problem for the class of PWA controllers. Namely, the goal is to construct an optimization problem whose optimal solution is equivalent to the given PWA function. The methodology is based on emph convex lifting: an auxiliary 1− dimensional variable which enhances the convexity characterization into recovered optimization problem. Accordingly, if the given PWA function is continuous, the optimal solution to this reconstructed optimization problem will be shown to be unique. Otherwise, if the continuity of this given PWA function is not fulfilled, this function will be shown to be one optimal solution to the recovered problem.In view of applications in linear model predictive control (MPC), it will be shown that any continuous PWA control law can be obtained by a linear MPC problem with the prediction horizon at most equal to 2 prediction steps. Aside from the theoretical meaning, this result can also be of help to facilitate implementation of PWA control laws by avoiding storing state space partition. Another utility of convex liftings will be shown in the last part of this thesis to be a control Lyapunov function. Accordingly, this convex lifting will be deployed in the so-called robust control design based on convex liftings for linear system affected by bounded additive disturbances and polytopic uncertainties. Both implicit and explicit controllers can be obtained. This method can also guarantee the recursive feasibility and robust stability. However, this control Lyapunov function is only defined over the maximal λ −contractive set for a given 0 ≤ λ < 1 which is known to be smaller than the maximal controllable set. Therefore, an extension of the above method to the N-steps controllable set will be presented. This method is based on a cascade of convex liftings where an auxiliary variable will be used to emulate a Lyapunov function. Namely, this variable will be shown to be non-negative, to strictly decrease for N first steps and to stay at 0 afterwards. Accordingly, robust stability is sought
13
Siqueira, Abel Soares 1986. "Controle dinâmico de infactibilidade para programação não linear." [s.n.], 2013. http://repositorio.unicamp.br/jspui/handle/REPOSIP/307118.
Full textAbstract:
Orientador: Francisco de Assis Magalhães Gomes NetoTese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica
Made available in DSpace on 2018-08-24T00:24:19Z (GMT). No. of bitstreams: 1 Siqueira_AbelSoares_D.pdf: 1465105 bytes, checksum: 2cba750df9607e9cb37b5799b157c850 (MD5) Previous issue date: 2013
Resumo: Uma maneira de resolver problemas gerais de programação não linear é utilizar estratégias de passos compostos. Essas estratégias normalmente combinam um passo tangente às restrições e um passo normal, alternando entre a diminuição da função objetivo e da norma da infactibilidade. Esse tipo de método exige o controle dos passos ou dos iterandos, para que não se perca o progresso de um vii passo no outro. Apresentaremos uma extensão do método de Controle Dinâmico da Infactibilidade, que utiliza uma estratégia de controle de passos chamado de Cilindros de Confiança. Esse método foi desenvolvido para problemas com restrições apenas de igualdade, e nossa extensão lida com restrições gerais. Mostraremos testes numéricos comparando nosso método com um método do mesmo tipo
Abstract: One way to solve general nonlinear programming problems is the composite-step strategies. These strategies usually combine a step tangent to the constraints and a normal step, alternating between reducing the objective function value and the norm of the infeasibility. This kind of method requires the control of the steps or the iterates, in order to prevent one step from destroying the progress of another. We will present an extension of the Dynamic Control of Infeasibility method, which utilizes a strategy to control the steps known as Trust Cylinders. This method was originally designed for problems with equality contraints only, and our extension will handle general constraints. We'll show numerical experiments comparing our method with another composite-step method
Doutorado
Matematica Aplicada
Doutor em Matemática Aplicada
14
Mitradjieva-Daneva, Maria. "Feasible Direction Methods for Constrained Nonlinear Optimization : Suggestions for Improvements." Doctoral thesis, Linköping : Department of Mathematics, Linköping University, 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-8811.
Full text
15
Qiu, Feng. "Probabilistic covering problems." Diss., Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/47567.
Full textAbstract:
This dissertation studies optimization problems that involve probabilistic covering constraints. A probabilistic constraint evaluates and requires that the probability that a set of constraints involving random coefficients with known distributions hold satisfy a minimum requirement. A covering constraint involves a linear inequality on non-negative variables with a greater or equal to sign and non-negative coefficients. A variety of applications, such as set cover problems, node/edge cover problems, crew scheduling, production planning, facility location, and machine learning, in uncertain settings involve probabilistic covering constraints.
In the first part of this dissertation we consider probabilistic covering linear programs. Using the sampling average approximation (SAA) framework, a probabilistic covering linear program can be approximated by a covering k-violation linear program (CKVLP), a deterministic covering linear program in which at most k constraints are allowed to be violated. We show that CKVLP is strongly NP-hard. Then, to improve the performance of standard mixed-integer programming (MIP) based schemes for CKVLP, we (i) introduce and analyze a coefficient strengthening scheme, (ii) adapt and analyze an existing cutting plane technique, and (iii) present a branching technique. Through computational experiments, we empirically verify that these techniques are significantly effective in improving solution times over the CPLEX MIP solver. In particular, we observe that the proposed schemes can cut down solution times from as much as six days to under four hours in some instances. We also developed valid inequalities arising from two subsets of the constraints in the original formulation. When incorporating them with a modified coefficient strengthening procedure, we are able to solve a difficult probabilistic portfolio optimization instance listed in MIPLIB 2010, which cannot be solved by existing approaches.
In the second part of this dissertation we study a class of probabilistic 0-1 covering problems, namely probabilistic k-cover problems. A probabilistic k-cover problem is a stochastic version of a set k-cover problem, which is to seek a collection of subsets with a minimal cost whose union covers each element in the set at least k times. In a stochastic setting, the coefficients of the covering constraints are modeled as Bernoulli random variables, and the probabilistic constraint imposes a minimal requirement on the probability of k-coverage. To account for absence of full distributional information, we define a general ambiguous k-cover set, which is ``distributionally-robust." Using a classical linear program (called the Boolean LP) to compute the probability of events, we develop an exact deterministic reformulation to this ambiguous k-cover problem. However, since the boolean model consists of exponential number of auxiliary variables, and hence not useful in practice, we use two linear program based bounds on the probability that at least k events occur, which can be obtained by aggregating the variables and constraints of the Boolean model, to develop tractable deterministic approximations to the ambiguous k-cover set. We derive new valid inequalities that can be used to strengthen the linear programming based lower bounds. Numerical results show that these new inequalities significantly improve the probability bounds. To use standard MIP solvers, we linearize the multi-linear terms in the approximations and develop mixed-integer linear programming formulations. We conduct computational experiments to demonstrate the quality of the deterministic reformulations in terms of cost effectiveness and solution robustness. To demonstrate the usefulness of the modeling technique developed for probabilistic k-cover problems, we formulate a number of problems that have up till now only been studied under data independence assumption and we also introduce a new applications that can be modeled using the probabilistic k-cover model.
16
Sahin, Cem. "Optimization Of Electricity Markets In The Price Based And Security Constrained Unit Commitment Problems Frameworks." Phd thesis, METU, 2010. http://etd.lib.metu.edu.tr/upload/12612242/index.pdf.
Full textAbstract:
Operation of the electricity markets is subject to a number of strict and specific constraints such as continuous load-generation balance, security of supply, and generation technology related limitations. Contributions have been made to two important problems of the Electricity Markets, in the context of this study.
In this study, Price Based Unit Commitment problem in the literature, which is a tool for the GENCO for operations planning, is extended considering the interdependencies between the Natural Gas (NG) and Electricity infrastructures and the uncertainty of Wind Power generation. The effect of the NG infrastructure physical limitations is considered via linearized NG transmission system equations, and the Wind energy sources and conventional generation resource uncertainties are simulated by Monte-Carlo simulations. The contribution of the forward energy Bilateral Contracts (BC), as a financial risk hedging tool is also included by modeling these in the proposed PBUC framework. In the case studies , it is observed that a GENCO could prevent its financial losses due to NG interruptions, by depositing only a portion of the midterm interrupted NG in the storage facilities.
The Security Constrained Unit Commitment (SCUC) Problem is widely accepted tool in the industry which models the market clearing process. This study integrates two novelties to the SCUC problem&bull
A discrete demand response model to consider active participation of the consumers, &bull
A hybrid deterministic/stochastic contingency model to represent the N-1 contingencies together with the uncertainties related with the wind power generation and system load. It is observed that the curtailment of available wind power capacity would enable the TSO to take corrective actions against occurrence of the contingencies and realization of the uncertainties in the most possible economical manner.
17
Excoffier, Mathilde. "Chance-Constrained Programming Approaches for Staffing and Shift-Scheduling Problems with Uncertain Forecasts : application to Call Centers." Thesis, Paris 11, 2015. http://www.theses.fr/2015PA112244/document.
Full textAbstract:
Le problème de dimensionnement et planification d'agents en centre d'appels consiste à déterminer sur une période le nombre d'interlocuteurs requis afin d'atteindre la qualité de service exigée et minimiser les coûts induits. Ce sujet fait l'objet d'un intérêt croissant pour son intérêt théorique mais aussi pour l'impact applicatif qu'il peut avoir. Le but de cette thèse est d'établir des approches en contraintes en probabilités en considérant l'incertitude de la demande.Tout d'abord, la thèse présente un modèle en problème d'optimisation stochastique avec contrainte en probabilité jointe traitant la problématique complète en une étape afin d'obtenir un programme facile à résoudre. Une approche basée sur l'idée de continuité est proposée grâce à des lois de probabilité continues, une nouvelle relation entre les taux d'arrivées et les besoins théoriques et la linéarisation de contraintes. La répartition du risque global est faite pendant le processus d'optimisation, permettant une solution au coût réduit. Ces solutions résultantes respectent le niveau de risque tout en diminuant le coût par rapport à d'autres approches.De plus, le modèle en une étape est étendu pour améliorer sa représentation de la réalité. D'une part, le modèle de file d'attente est amélioré et inclus la patience limitée des clients. D'autre part, une nouvelle expression de l'incertitude est proposée pour prendre la dépendance des périodes en compte.Enfin, une nouvelle représentation de l'incertitude est considérée. L'approche distributionally robust permet de modéliser le problème sous l'hypothèse que la loi de probabilité adéquate est inconnue et fait partie d'un ensemble de lois, défini par une moyenne et une variance données. Le problème est modélisé par une contrainte en probabilité jointe. Le risque à chaque période est définie par une variable à optimiser.Un problème déterministe équivalent est proposé et des approximations linéaires permettent d'obtenir une formulation d'optimisation linéaireThe staffing and shift-scheduling problems in call centers consist in deciding how many agents handling the calls should be assigned to work during a given period in order to reach the required Quality of Service and minimize the costs. These problems are subject to a growing interest, both for their interesting theoritical formulation and their possible applicative effects. This thesis aims at proposing chance-constrained approaches considering uncertainty on demand forecasts.First, this thesis proposes a model solving the problems in one step through a joint chance-constrained stochastic program, providing a cost-reducing solution. A continuous-based approach leading to an easily-tractable optimization program is formulated with random variables following continuous distributions, a new continuous relation between arrival rates and theoritical real agent numbers and constraint linearizations. The global risk level is dynamically shared among the periods during the optimization process, providing reduced-cost solution. The resulting solutions respect the targeted risk level while reducing the cost compared to other approaches.Moreover, this model is extended so that it provides a better representation of real situations. First, the queuing system model is improved and consider the limited patience of customers. Second, another formulation of uncertainty is proposed so that the period correlation is considered.Finally, another uncertainty representation is proposed. The distributionally robust approach provides a formulation while assuming that the correct probability distribution is unknown and belongs to a set of possible distributions defined by given mean and variance. The problem is formulated with a joint chance constraint. The risk at each period is a decision variable to be optimized. A deterministic equivalent problem is proposed. An easily-tractable mixed-integer linear formulation is obtained through piecewise linearizations
18
Cheon, Myun-Seok. "Global Optimization of Monotonic Programs: Applications in Polynomial and Stochastic Programming." Diss., Available online, Georgia Institute of Technology, 2005, 2005. http://etd.gatech.edu/theses/available/etd-04152005-130317/unrestricted/Cheon%5FMyunSeok%5F200505%5Fphd.pdf.
Full textAbstract:
Thesis (Ph. D.)--Industrial & Systems Engineering, Georgia Institute of Technology, 2005.Barnes, Earl, Committee Member ; Shapiro, Alex, Committee Member ; Realff, Matthew, Committee Member ; Al-Khayyal, Faiz, Committee Chair ; Ahmed, Shabbir, Committee Co-Chair. Includes bibliographical references.
19
Grose, Roger T. "Cost-constrained project scheduling with task durations and costs that may increase over time demonstrated with the U.S. Army future combat systems /." Thesis, View thesis via NPS View thesis via DTIC, 2004. http://handle.dtic.mil/100.2/ADA424957.
Full textAbstract:
Thesis (M.S. in Operations Research)--Naval Postgraduate School, 2004.Title from title screen (viewed June 28, 2005). "June 2004." Includes bibliographical references (p. 59-61). Also issued in paper format.
20
Grey, Audley Bruce. "Unified solution of security-constrained unit commitment (SCUC) problem using a linear programming methodology : a dissertation presented to the faculty of the Graduate School, Tennessee Technological University /." Click to access online version, 2007. http://proquest.umi.com/pqdweb?index=88&did=1397913351&SrchMode=1&sid=1&Fmt=6&VInst=PROD&VType=PQD&RQT=309&VName=PQD&TS=1255446163&clientId=28564.
Full text
21
Prudente, Leandro da Fonseca 1985. "Inviabilidade em métodos de lagrangiano aumentado." [s.n.], 2012. http://repositorio.unicamp.br/jspui/handle/REPOSIP/307467.
Full textAbstract:
Orientador: José Mario Martínez PérezTese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica
Made available in DSpace on 2018-08-20T09:19:13Z (GMT). No. of bitstreams: 1 Prudente_LeandrodaFonseca_D.pdf: 1307430 bytes, checksum: 6ac8a3a70af28dce0b2cd6d839b227ef (MD5) Previous issue date: 2012
Resumo: Algoritmos de programação não-linear práticos podem convergir para pontos inviáveis mesmo quando o problema a ser resolvido é viável. Quando isso ocorre, é natural que o usuário mude o ponto inicial e/ou parâmetros algorítmicos e reaplique o método na tentativa de encontrar uma solução viável e ótima. Desta forma, o ideal é que um algoritmo não só seja eficiente em encontrar soluções viáveis, mas também que detecte rapidamente quando ele está fadado a convergir para um ponto inviável. Na tentativa de atingir esse objetivo, apresentamos modificações em um algoritmo baseado em Lagrangiano aumentado de modo que, no caso de convergência para um ponto inviável, os subproblemas são resolvidos com tolerâncias moderadas e, mesmo assim, as propriedades de convergência global são mantidas. Experimentos numéricos são apresentados
Abstract Practical Nonlinear Programming algorithms may converge to infeasible points even when the problem to be solved is feasible. When this occurs, it is natural for the user to change the starting point and/or algorithmic parameters and reapply the method in an attempt to find a feasible and optimal solution. Thus, the ideal is that an algorithm is eficient not only in finding feasible solutions, but also in quickly detecting when it is fated to converge to an infeasible point. In pursuit of this goal, we present modifications of an algorithm based on Augmented Lagrangians so that, in the case of convergence to an infeasible point, the subproblems are solved with moderate tolerances and, even then, the global convergence properties are maintained. Numerical experiments are presented
Doutorado
Matematica Aplicada
Doutor em Matemática Aplicada
22
Oliveira, Fabiana Rodrigues de. "Estudo de alguns métodos clássicos de otimização restrita não linear." Universidade Federal de Uberlândia, 2012. https://repositorio.ufu.br/handle/123456789/16795.
Full textAbstract:
Coordenação de Aperfeiçoamento de Pessoal de Nível SuperiorIn this work some classical methods for constrained nonlinear optimization are studied. The mathematical formulations for the optimization problem with equality and inequality constrained, convergence properties and algorithms are presented. Furthermore, optimality conditions of rst order (Karush-Kuhn-Tucker conditions) and of second order. These conditions are essential for the demonstration of many results. Among the methods studied, some techniques transform the original problem into an unconstrained problem (Penalty Methods, Augmented Lagrange Multipliers Method). In others methods, the original problem is modeled as one or as a sequence of quadratic subproblems subject to linear constraints (Quadratic Programming Method, Sequential Quadratic Programming Method). In order to illustrate and compare the performance of the methods studied, two nonlinear optimization problems are considered: a bi-dimensional problem and a problem of mass minimization of a coil spring. The obtained results are analyzed and confronted with each other.
Neste trabalho são estudados alguns métodos clássicos de otimização restrita não linear. São abordadas a formulação matemática para o problema de otimização com restrições de igualdade e desigualdade, propriedades de convergência e algoritmos. Além disso, são relatadas as condições de otimalidade de primeira ordem (condições de Karush-Kuhn-Tucker) e de segunda ordem. Estas condições são essenciais para a demonstração de muitos resultados. Dentre os métodos estudados, algumas técnicas transformam o problema original em um problema irrestrito (Métodos de Penalidade, Método dos Multiplicadores de Lagrange Aumentado). Em outros métodos, o problema original é modelado como um ou uma seqüência de subproblemas quadráticos sujeito _a restrições lineares (Método de Programação Quadrática, Método de Programação Quadrática Seqüencial). A fim de ilustrar e comparar o desempenho dos métodos estudados são considerados dois problemas de otimização não linear: um problema bidimensional e o problema de minimização da massa de uma mola helicoidal. Os resultados obtidos são examinados e confrontados entre si.
Mestre em Matemática
23
Gentil, Jan Marcel Paiva. "Estudo e implementação de um método de restrições ativas para problemas de otimização em caixas." Universidade de São Paulo, 2010. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-28082010-115947/.
Full textAbstract:
Problemas de otimização em caixas são de grande importância, não só por surgirem naturalmente na formulação de problemas da vida prática, mas também por aparecerem como subproblemas de métodos de penalização ou do tipo Lagrangiano Aumentado para resolução de problemas de programação não-linear. O objetivo do trabalho é estudar um algoritmo de restrições ativas para problemas de otimização em caixas recentemente apresentado chamado ASA e compará-lo à versão mais recente de GENCAN, que é também um método de restrições ativas. Para tanto, foi elaborada uma metodologia de testes robusta e minuciosa, que se propõe a remediar vários dos aspectos comumente criticados em trabalhos anteriores. Com isso, puderam ser extraídas conclusões que levaram à melhoria de GENCAN, conforme ficou posteriormente comprovado por meio da metodologia aqui introduzida.Box-constrained optimization problems are of great importance not only for naturally arising in several real-life problems formulation, but also for their occurrence as sub-problems in both penalty and Augmented Lagrangian methods for solving nonlinear programming problems. This work aimed at studying a recently introduced active-set method for box-constrained optimization called ASA and comparing it to the latest version of GENCAN, which is also an active-set method. For that purpose, we designed a robust and thorough testing methodology intended to remedy many of the widely criticized aspects of prior works. Thereby, we could draw conclusions leading to GENCAN\'s further development, as it later became evident by means of the same methodology herein proposed.
24
Bueno, Luís Felipe Cesar da Rocha 1983. "Otimização com restrições LOVO, restauração inexata e o equilíbrio inverso de Nash." [s.n.], 2011. http://repositorio.unicamp.br/jspui/handle/REPOSIP/307465.
Full textAbstract:
Orientador: José Mario Martínez PerezTese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica.
Made available in DSpace on 2018-08-19T04:47:30Z (GMT). No. of bitstreams: 1 Bueno_LuisFelipeCesardaRocha_D.pdf: 2718304 bytes, checksum: ca1c9aa7730e88989e17a5b89049c2ee (MD5) Previous issue date: 2011
Resumo: Nesse trabalho serão propostos métodos de Lagrangiano Aumentado para tratar problemas com restrições do tipo LOVO, serão propostos novos métodos de Restauração Inexata e será introduzido o conceito de Equilíbrio Inverso de Nash. Teoremas sobre condições de otimalidade para problemas do tipo LOVO serão apresentados. Um algoritmo do tipo Lagrangiano Aumentado será proposto para abordar esse problema e teoremas de convergência global serão demonstrados. Resultados computacionais serão realizados para uma aplicação em otimização de carteiras em investimentos de grande impacto. Um método híbrido de Restauração Inexata será proposto combinando uma modificação, que usa o Lagrangiano Afiado como função de mérito, do método global de Fischer e Friedlander e o método local de Birgin e Martínez. Teoremas de convergência global e local serão apresentados. Um método de Restauração Inexata para problemas em que as derivadas da função objetivo não estejam disponíveis será introduzido. Nesse método todas as ferramentas da otimização tradicional serão usadas na fase de restauração e uma regularização será feita na fase de otimização. Teoremas de convergência global serão demonstrados e resultados numéricos apresentados. O conceito de Equilíbrio Inverso de Nash será introduzido e um método de Restauração Inexata será proposto para abordar esse problema. Esse método será uma extensão de um novo método de Restauração Inexata para problemas em dois níveis que também será proposto neste trabalho. Exemplos ilustrativos para uma aplicação para o problema de equilíbrio de Arrow-Debreu serão exibidos
Abstract: In this work an Augmented Lagrangian method will be proposed to deal with LOVO constraints, also some new Inexact Restoration methods will be presented and the Inverse Nash Equilibrium concept will be introduced. Theorems about optimality conditions for LOVO-like problems will be presented. Three Augmented Lagrangian algorithms will be proposed to approach this problem and global convergence theorems will be proved. Computational results will be performed for an application in portfolio optimization with impact. A modification of the Fischer-Friedlander global method using the Sharp Lagrangian as a merit function will be proposed. A hybrid Inexact Restoration method combining this modification and the Birgin-Martínez local method will be introduced. Global and local convergence theorems will be presented. An Inexact Restoration method for problems in which the derivatives of the objective function are not available will be introduced. In this method it will be used all the optimization traditional tools in the restoration process as well as a regularization strategy in the optimization phase. Global convergence theorems will be demonstrated and numerical results will be presented. The concept of Inverse Nash Equilibrium will be introduced and an Inexact Restoration method will be proposed to deal with this problem. This method is an extension of a new Inexact Restoration method for bilevel programming that will also be proposed in this work. Some illustrative examples for an application for the Arrow- Debreu equilibrium problem will be given
Doutorado
Matematica Aplicada
Doutor em Matemática Aplicada
25
Sobral, Francisco Nogueira Calmon 1984. "Otimização sem derivadas em conjuntos magros." [s.n.], 2012. http://repositorio.unicamp.br/jspui/handle/REPOSIP/307469.
Full textAbstract:
Orientador: José Mario Martínez PérezTese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica
Made available in DSpace on 2018-08-20T03:18:55Z (GMT). No. of bitstreams: 1 Sobral_FranciscoNogueiraCalmon_D.pdf: 3255516 bytes, checksum: 380cc11e2ad93213e66f456ef5945f1c (MD5) Previous issue date: 2012
Resumo: Os problemas de otimização sem derivadas surgem de modelos para os quais as derivadas das funções e das restrições envolvidas, por alguma razão, não estão disponíveis. Os motivos variam desde usuários que não querem programar as derivadas até funções excessivamente complexas e caixas-pretas, oriundas de simulações só possíveis graças ao crescimento na capacidade de processamento dos computadores. Acompanhando esse crescimento, o número de algoritmos para resolver problemas de otimização sem derivadas aumentou nos últimos anos. Porém, poucos são aqueles que conseguem lidar de forma eficiente com problemas cujos domínios são magros, como, por exemplo, quando há restrições de igualdade. Neste trabalho, apresentamos a teoria e implementação de dois algoritmos capazes de trabalhar com domínios magros em problemas de otimização sem derivadas. Ambos partem da premissa de que a parte mais custosa na resolução é a avaliação da função objetivo. Com isso em mente, o processo de resolução é dividido em duas fases. Na fase de restauração, buscamos por pontos menos inviáveis sem utilizar avaliações da função objetivo. Na fase de minimização, ou otimização, o objetivo é reduzir a função objetivo com o uso de algoritmos bem estabelecidos para problemas sem derivadas com restrições simples. O primeiro algoritmo utiliza ideias de Restauração Inexata associadas a uma tolerância decrescente à inviabilidade. Utilizando hipóteses simples e usuais dos métodos de busca direta direcional, mostramos propriedades de convergência a minimizadores globais. O segundo algoritmo recupera totalmente os resultados teóricos de um algoritmo recente de Restauração Inexata com busca linear e aplica-se a problemas nos quais apenas as derivadas da função objetivo não estão disponíveis. Testes numéricos mostram as boas propriedades dos dois algoritmos, em particular quando comparados com algoritmos baseados em penalidades
Abstract: Derivative-free optimization problems arise from models whose derivatives of some functions are not available. This information is unavailable due to extremely complex and black-box functions, originated from simulation procedures, or even to user inability. Following the growth in the number of applications, the number of derivative-free algorithms has increased in the last years. However, few algorithms are able to handle thin feasible domains efficiently, for example, in the presence of equality nonlinear constraints. In the present work, we describe the theory and implementation of two algorithms capable of dealing with thin-constrained derivative-free problems. Their definition considers that the objective function evaluation is the most expensive part of the problem. Based on this principle, the process of solving a problem is split into two phases. In the restoration phase, we try to improve the feasibility without evaluating the objective function. In the minimization phase, the aim is to decrease the objective function value by using well-established algorithms in order to solve derivative-free problems with simple constraints. The _rst algorithm uses Inexact Restoration ideas together with a decreasing infeasibility tolerance. Under the usual hypotheses of direct search methods, we show global minimization results. The second algorithm extends to the derivative-free case all the theoretical results obtained in a recent line-search Inexact Restoration algorithm. In this approach, only the derivatives of the objective function are not available. We perform numerical experiments to show the advantages of each algorithm, in particular when comparing with penalty-like algorithms
Doutorado
Matematica Aplicada
Doutor em Matemática Aplicada
26
Dutia, Dharini. "Multi-Robot Task Allocation and Scheduling with Spatio-Temporal and Energy Constraints." Digital WPI, 2019. https://digitalcommons.wpi.edu/etd-theses/1298.
Full textAbstract:
Autonomy in multi-robot systems is bounded by coordination among its agents. Coordination implies simultaneous task decomposition, task allocation, team formation, task scheduling and routing; collectively termed as task planning. In many real-world applications of multi-robot systems such as commercial cleaning, delivery systems, warehousing and inventory management: spatial & temporal constraints, variable execution time, and energy limitations need to be integrated into the planning module. Spatial constraints comprise of the location of the tasks, their reachability, and the structure of the environment; temporal constraints express task completion deadlines. There has been significant research in multi-robot task allocation involving spatio-temporal constraints. However, limited attention has been paid to combine them with team formation and non- instantaneous task execution time. We achieve team formation by including quota constraints which ensure to schedule the number of robots required to perform the task. We introduce and integrate task activation (time) windows with the team effort of multiple robots in performing tasks for a given duration. Additionally, while visiting tasks in space, energy budget affects the robots operation time. We map energy depletion as a function of time to ensure long-term operation by periodically visiting recharging stations. Research on task planning approaches which combines all these conditions is still lacking. In this thesis, we propose two variants of Team Orienteering Problem with task activation windows and limited energy budget to formulate the simultaneous task allocation and scheduling as an optimization problem. A complete mixed integer linear programming (MILP) formulation for both variants is presented in this work, implemented using Gurobi Optimizer and analyzed for scalability. This work compares the different objectives of the formulation like maximizing the number of tasks visited, minimizing the total distance travelled, and/or maximizing the reward, to suit various applications. Finally, analysis of optimal solutions discover trends in task selection based on the travel cost, task completion rewards, robot's energy level, and the time left to task inactivation.
27
Paris, Jean-Marc. "Validation de données de systèmes dynamiques non-linéaires : application à la détection de défauts." Vandoeuvre-les-Nancy, INPL, 1998. http://www.theses.fr/1998INPL048N.
Full textAbstract:
La complexité croissante des processus industriels demande une automatisation de plus en plus développée. La commande et la maintenance de ces processus nécessitent le suivi des mesures pour permettre une bonne détection de défauts capteurs aussi rapidement que possible. Avant l'utilisation des données recueillies sur un processus, il est nécessaire d'implémenter une procédure de validation de données pour réconcilier les données avec le modèle du processus. Ce mémoire propose une méthode de validation de données de systèmes dynamiques non-linéaires. Les résultats obtenus par la validation de données sont ensuite utilisés pour détecter et localiser des défauts capteurs sur un processus. Tout d'abord, nous présentons une méthode de validation de données de systèmes dynamiques non-linéaires basée sur une procédure de linéarisation-estimation associée à une fenêtre glissante. L’évolution du système est observée à travers une fenêtre contenant un nombre fini d'observations. L’estimation consiste alors à résoudre un problème d'optimisation quadratique formule sur la fenêtre d'estimation sous contraintes linéarisées. La procédure linéarisation-estimation est répétée jusqu'à la convergence de l'estimation. Puis, nous présentons différentes méthodes de détection de défauts capteurs. La localisation d'un défaut est ensuite assurée par un banc d'estimateurs pilotes par différents ensembles de mesures. Il est important d'identifier mais aussi de corriger les défauts capteurs. Nous proposons une stratégie d'élimination en série ou la mesure en défaut est éliminée de la procédure de validation de données. L’efficacité des méthodes présentées est mise en évidence sur la simulation d'un processus hydraulique constitué d'un réseau de cuves interconnectées.
28
Canahuire, Cabello Ruth Vanessa 1983. "Projeto de controladores H-infinito de ordem reduzida e compensação de saturação em estruturas flexíveis." [s.n.], 2014. http://repositorio.unicamp.br/jspui/handle/REPOSIP/265939.
Full textAbstract:
Orientador: Alberto Luiz SerpaTese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecânica
Made available in DSpace on 2018-08-25T12:10:51Z (GMT). No. of bitstreams: 1 CanahuireCabello_RuthVanessa_D.pdf: 5994310 bytes, checksum: 0f754dbcbe2bce27101f33806ca7f190 (MD5) Previous issue date: 2014
Resumo: A síntese de controle H-infinito de estruturas flexíveis pode levar à obtenção de controladores de alta ordem. Estes controladores podem apresentar dificuldades para a implementação prática acarretando atrasos de resposta no sistema. Para evitar esse problema, este trabalho apresenta duas sínteses de controladores H-infinito de ordem reduzida por realimentação de saída. Para este propósito, são formulados dois problemas de otimização para a obtenção de controladores de ordem reduzida considerando que as matrizes de estado do controlador estão na forma canônica controlável e canônica modal. As duas sínteses propostas estão baseadas na minimização da norma H-infinito garantindo a estabilidade do sistema em malha fechada. Outro problema considerado neste trabalho são os efeitos de saturação dos atuadores sobre o sistema controlado. A saturação, quando presente no sistema, pode levar a uma perda de desempenho e as vezes à instabilidade da planta. Para tratar o problema de saturação é proposto um problema de otimização baseado no projeto de compensadores anti-windup. A abordagem proposta usa a síntese do problema H-infinito para minimizar diretamente os efeitos do sinal de saturação sobre o sinal de desempenho. Finalmente, as formulações são verificadas no controle ativo de vibração sobre um modelo teórico e em uma bancada experimental com uma viga de alumínio engastada-livre. Os métodos mostraram ter bom desempenho garantindo a estabilidade do sistema em malha fechada. Os problemas de otimização são resolvidos usando algoritmos genéticos e alguns aspectos numéricos são discutidos
Abstract: The H-infinity controller synthesis for flexible structures leads to full-order controllers. This can represent difficulties for practical controller implementation arising delay in the system response. To avoid this difficulty, this work presents two reduced order H-infinity controllers synthesis based on output feedback. For this goal, it is formulated two optimization problem to obtain a reduced order controller in its state-space controllable canonical form and state-space modal canonical form. The two proposed synthesis are based on the minimization of the H-infinity norm ensuring the stability of the closed loop system. Another problem considered in this work is related to the effects of saturation of the actuators on the controlled system. The saturation in the system can lead to a performance loss and occasionally to the instability of the plant. An optimization problem based on anti-windup compensator design is proposed to treat this problem. The proposed approach uses the H-infinity controller synthesis to minimize directly the saturation effects on the performance signal. Finally, the formulations are verified in the active control of vibration of a theoretical model and a cantilever aluminium beam is used on an experimental bench. The methods proposed presented good performance in terms of the stability of the closed loop system. The optimization problems are solved using genetic algorithms and some numerical aspects are discussed
Doutorado
Mecanica dos Sólidos e Projeto Mecanico
Doutora em Engenharia Mecânica
29
Sahli, Abderrahim. "Problèmes d'ordonnancement avec production et consommation des ressources." Thesis, Compiègne, 2016. http://www.theses.fr/2016COMP2309/document.
Full textAbstract:
La plupart des travaux de recherches sur les problèmes d'ordonnancement traitent le cas des ressources renouvelables, c'est-à-dire des ressources qui sont exigées en début d'exécution de chaque tâche et sont restituées en fin d'exécution. Peu d'entre eux abordent les problèmes à ressources consommables, c'est-à-dire des ressources non restituées en fin d'exécution. Le problème de gestion de projet à contraintes de ressources (RCPSP) est le problème à ressources renouvelables le plus traité dans la littérature. Dans le cadre de cette thèse, nous nous sommes intéressés à une généralisation du problème RCPSP qui correspond au cas où les tâches sont remplacées par des événements liés par des relations de précédence étendues. Chaque événement peut produire ou consommer une quantité de ressources à sa date d'occurrence et la fonction économique reste la durée totale à minimiser. Nous avons nommé cette généralisation ERCPSP (Extended RCPSP). Nous avons élaboré des modèles de programmation linéaire pour résoudre ce problème. Nous avons proposé plusieurs bornes inférieures algorithmiques exploitant les travaux de la littérature sur les problèmes cumulatifs. Ensuite, nous avons élargi la portée des méthodes utilisées pour la mise en place de méthodes de séparation et évaluation. Nous avons traité aussi des cas particuliers par des méthodes basées sur la programmation dynamiqueThis thesis investigates the Extended Resource Constrained Project Scheduling Problem (ERCPSP). ERCPSP is a general scheduling problem where the availability of a resource is depleted and replenished at the occurrence times of a set of events. It is an extension of the Resource Constrained Project Scheduling Problem (RCPSP) where activities are replaced by events, which have to be scheduled subject to generalized precedence relations. We are interested in this thesis in proposing new methodologies and approaches to solve ERCPSP. First, we study some polynomial cases of this problem and we propose a dynamic programming algorithm to solve the parallel chain case. Then, we propose lower bounds, mixed integer programming models, and a branch-and-bound method to solve ERCPSP. Finally, we develop an instance generator dedicated to this problem
30
Wang, Chenghao. "Contribution à l’optimisation robuste de réseaux." Thesis, Compiègne, 2021. http://www.theses.fr/2021COMP2632.
Full textAbstract:
Cette thèse a pour objectif la proposition de nouvelles approches algorithmiques et de modélisation pour la résolution de certains problèmes d’optimisation de réseau dans les domaines des transports et des télécommunications. Plus précisément, les problèmes étudiés tombent dans le domaine du transport aérien, nommément le problème d’affectation des niveaux de vol dans l’espace aérienne, et dans le domaine des télécommunications où on traite des problèmes d’allocation de ressources dans les réseaux 5G. Un aspect important qui a été pris en compte dans cette étude est l’incertitude des données, c’est-à-dire le fait qu’une partie des données d’entrée ne sont pas connues de façon précise. Notre tâche a consisté à modéliser chacun des problèmes, proposer une formulation compacte des variantes déterministe et robuste, et proposer des approches appropriées pour les résoudre. Les problèmes étudiés tombent dans la catégorie des problèmes NP-complets et ils sont difficile à résoudre même pour des instances de taille modeste. Ils deviennent encore plus difficiles dans leur version robuste. Pour le problème d’affectation des niveaux de vols, nous avons considéré les incertitudes liées à l’heure de départ qui sont modélisées via un modèle de mélange gaussien. Le problème est modélisé comme un « chance-constrained problem » et résolu par un algorithme heuristique de génération de contraintes. Il s’agit d’une approche générale qui trouvera des applications plus large que ceux étudiés dans cette thèse. Ensuite, nous avons étudié la conception optimale des réseaux sans fil de 5ème génération (5G) dans le contexte de l’architectures Superfluid. Plus précisément, l’architecture 5G Superfluid est basée sur des entités de réseau appelées « Bloc Fonctionnel Réutilisable » (RFB) qui sont à la base des réseaux 5G. Nous avons étudié le problème de conception d’un tel réseau Superfluid à coût minimum pour lequel une formulation en programme linéaire mixte suivie d’une approche de résolution utilisant la décomposition de Benders a été implémentée ont été proposées. Enfin, le problème spécifique de conception de réseaux virtuels a été considéré sous l’angle de l’efficacité énergétique. Nous avons proposé une formulation de programmation linéaire en nombres entiers mixte du problème robuste, et présentons une nouvelle matheuristique basée sur la combinaison d’un algorithme génétique avec la recherche de voisinage. Les résultats numériques ont porté sur des instances de taille réalistes et ont montré la validité des modèles et des approches proposéesThis Ph.D. Thesis is focused on proposing new optimization modeling and algorithmic approaches for dealing with real-world network optimization problems arising in the transportation and telecommunications fields. Since the focus has been on real-world applications, a relevant aspect that has been taken into account is data uncertainty, i.e. the fact that the value of a subset of input data of the problem is not exactly known when the problem is solved. More precisely, in the context of transportation problems, it was considered the flight level assignment problem, which arises in air traffic management. It aims at establishing the flight levels of a set of aircraft in order to improve the total assignment revenue, to reduce the total number of flight conflicts and also the total en-route delay. In this context, we proposed a new chance-constrained optimization problem and iterative constraint-generation heuristic which is based on both analytical and sampling methods. Besides transportation problems, this Thesis has also focused on the optimal design of 5th generation of wireless networks (5G) considering Superfluid and virtual architectures. Specifically, the 5G Superfluid architecture is based on atomic virtual entities called Reusable Functional Block (RFB). We investigated the problem of minimizing the total installation costs of a 5G Superfluid network (composed of virtual entities and realized over a physical network) while guaranteeing constraint on user coverage, downlink traffic performance and technical constraints on RFBs of different nature. To solve this hard problem, we proposed a Benders decomposition approach. Concerning instead the design of general virtual networks, we adopted a green paradigm that pursues energy-efficiency and tackled a state-of-the-art robust mixed integer linear programming formulation of the problem, by means of a new matheuris tic based on combining a genetic algorithm with exact large neighborhood searches. Results of computational tests executed considering realistic problem instances have shown the validity of all the new optimization modeling and algorithmic approaches proposed in this Thesis for the transportation and telecommunications problems sketched above
31
Andretta, Marina. "Tópicos em otimização com restrições lineares." Universidade de São Paulo, 2008. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-01092008-114422/.
Full textAbstract:
Métodos do tipo Lagrangiano Aumentado são muito utilizados para minimização de funções sujeitas a restrições gerais. Nestes métodos, podemos separar o conjunto de restrições em dois grupos: restrições fáceis e restrições difíceis. Dizemos que uma restrição é fácil se existe um algoritmo disponível e eficiente para resolver problemas restritos a este tipo de restrição. Caso contrário, dizemos que a restrição é difícil. Métodos do tipo Lagrangiano aumentado resolvem, a cada iteração, problemas sujeitos às restrições fáceis, penalizando as restrições difíceis. Problemas de minimização com restrições lineares aparecem com freqüência, muitas vezes como resultados da aproximação de problemas com restrições gerais. Este tipo de problema surge também como subproblema de métodos do tipo Lagrangiano aumentado. Assim, uma implementação eficiente para resolver problemas com restrições lineares é relevante para a implementação eficiente de métodos para resolução de problemas de programação não-linear. Neste trabalho, começamos considerando fáceis as restrições de caixa. Introduzimos BETRA-ESPARSO, uma versão de BETRA para problemas de grande porte. BETRA é um método de restrições ativas que utiliza regiões de confiança para minimização em cada face e gradiente espectral projetado para sair das faces. Utilizamos BETRA (denso ou esparso) na resolução dos subproblemas que surgem a cada iteração de ALGENCAN (um método de lagrangiano aumentado). Para decidir qual algoritmo utilizar para resolver cada subproblema, desenvolvemos regras que escolhem um método para resolver o subproblema de acordo com suas características. Em seguida, introduzimos dois algoritmos de restrições ativas desenvolvidos para resolver problemas com restrições lineares (BETRALIN e GENLIN). Estes algoritmos utilizam, a cada iteração, o método do Gradiente Espectral Projetado Parcial quando decidem mudar o conjunto de restrições ativas. O método do gradiente Espectral Projetado Parcial foi desenvolvido especialmente para este propósito. Neste método, as projeções são computadas apenas em um subconjunto das restrições, com o intuito de torná-las mais eficientes. Por fim, tendo introduzido um método para minimização com restrições lineares, consideramos como fáceis as restrições lineares. Incorporamos BETRALIN e GENLIN ao arcabouço de Lagrangianos aumentados e verificamos experimentalmente a eficiência e eficácia destes métodos que trabalham explicitamente com restrições lineares e penalizam as demais.Augmented Lagrangian methods are widely used to solve general nonlinear programming problems. In these methods, one can split the set of constraints in two groups: the set of easy and hard constraints. A constraint is called easy if there is an efficient method available to solve problems subject to that kind of constraint. Otherwise, the constraints are called hard. Augmented Lagrangian methods solve, at each iteration, problems subject to the set of easy constraints while penalizing the set of hard constraints. Linearly constrained problems appear frequently, sometimes as a result of a linear approximation of a problem, sometimes as an augmented Lagrangian subproblem. Therefore, an efficient method to solve linearly constrained problems is important for the implementation of efficient methods to solve nonlinear programming problems. In this thesis, we begin by considering box constraints as the set of easy constraints. We introduce a version of BETRA to solve large scale problems. BETRA is an active-set method that uses a trust-region strategy to work within the faces and spectral projected gradient to leave the faces. To solve each iteration\'s subproblem of ALGENCAN (an augmented Lagrangian method) we use either the dense or the sparse version of BETRA. We develope rules to decide which box-constrained inner solver should be used at each augmented Lagrangian iteration that considers the main characteristics of the problem to be solved. Then, we introduce two active-set methods to solve linearly constrained problems (BETRALIN and GENLIN). These methods use Partial Spectral Projected Gradient method to change the active set of constraints. The Partial Spectral Projected Gradient method was developed specially for this purpose. It computes projections onto a subset of the linear constraints, aiming to make the projections more efficient. At last, having introduced a linearly-constrained solver, we consider the set of linear constraints as the set of easy constraints. We use BETRALIN and GENLIN in the framework of augmented Lagrangian methods and verify, using numerical experiments, the efficiency and robustness of those methods that work with linear constraints and penalize the nonlinear constraints.
32
López, Ramos Francisco. "Conjoint design of railway lines and frequency setting under semi-congested scenarios." Doctoral thesis, Universitat Politècnica de Catalunya, 2014. http://hdl.handle.net/10803/144940.
Full textAbstract:
This thesis develops mathematical programming models which integrate network design (ND) and line frequency setting (LFS) phases. These appear in transport planning studies that extend an existing urban public transportation system (UPTS) and are suitable for underground and rapid transit systems. The ND phase extends the working UPTS, taking as inputs the locations of candidate stretches and stations on the new lines, as well as construction costs which cannot exceed the available infrastructure budget. Regarding the LFS phase, frequencies and vehicles are assigned to functioning and newly built lines, providing that they do not exceed resource capacities and the time horizon. The developed models take into account the type of service patterns that may operate on the lines of the transport system. They include local services, where vehicles halt at every node in the line, and express services, in which vehicles halt at only a subset of nodes in the line. A passenger assignment model allows solving, simultaneously, the ND and LFS phases under a system optimum point of view.
The combined model has two variants: one which deals with inelastic demand and another which faces elasticities in demand. The latter originates from changes in the modal choice proportions of travelers and may result from modifications in the public transport system. The former does not take into account competition among several modes of transportation and it is formulated as a mixed-integer linear programming problem. In contrast, the latter allows passengers to travel via two modes of transportation: public transport and private car. It is formulated as a mixed-integer linear bi-level programming problem (MILBP) with discrete variables only in the upper level. In both models, a complementary network is used to model transfers among lines and to reach the passenger¿s origin and/or destination nodes when the constructed UPTS does not cover them.
The model with inelastic demand is initially solved by means of the commercial solver CPLEX under three different mathematical formulations for the ND phase. The first two are exact approaches based on extensions of Traveling Salesman Problem formulations for dynamic and static treatment of the line¿s subtours, whereas the last one is an approximation inspired by constrained k-shortest path algorithms. In order to deal with large-sized networks, a quasi-exact solution framework is employed. It consists of three solving blocks: the corridor generation algorithm (CGA), the line splitting algorithm (LSA), and a specialized Benders decomposition (SBD). The LSA and CGA are heuristic techniques that allow skipping some of the non-polynomial properties. They are related to the number of lines under construction and the number of feasible corridors that can be generated. As for the SBD, it is an exact method that splits the original mathematical programming problem into a series of resolutions, composed of two mathematical problems which are easier to solve. Regarding the elastic demand variant, it is solved under the same framework as the specialized Benders decomposition adaptation for solving MILBP, which results from this variant formulation.
The inelastic demand variant is applied to two test cases based on underground network models for the cities of Seville and Santiago de Chile. Origin destination trip matrices and other parameters required by the models have been set to likely values using maps and published studies. The purpose of these networks is to test the models and algorithms on realistic scenarios, as well as to show their potentialities. Reported results show that the quasi-exact approach is comparable to approximate techniques in terms of performance. Regarding the elastic demand variant, the model is more complex and can be applied only to smaller networks.
Finally, some further lines of research for both modeling and algorithmic issues are discussed.
33
Giuliani, Luca. "Extending the Moving Targets Method for Injecting Constraints in Machine Learning." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2021. http://amslaurea.unibo.it/23885/.
Full textAbstract:
Informed Machine Learning is an umbrella term that comprises a set of methodologies in which domain knowledge is injected into a data-driven system in order to improve its level of accuracy, satisfy some external constraint, and in general serve the purposes of explainability and reliability. The said topid has been widely explored in the literature by means of many different techniques. Moving Targets is one such a technique particularly focused on constraint satisfaction: it is based on decomposition and bi-level optimization and proceeds by iteratively refining the target labels through a master step which is in charge of enforcing the constraints, while the training phase is delegated to a learner. In this work, we extend the algorithm in order to deal with semi-supervised learning and soft constraints. In particular, we focus our empirical evaluation on both regression and classification tasks involving monotonicity shape constraints. We demonstrate that our method is robust with respect to its hyperparameters, as well as being able to generalize very well while reducing the number of violations on the enforced constraints. Additionally, the method can even outperform, both in terms of accuracy and constraint satisfaction, other state-of-the-art techniques such as Lattice Models and Semantic-based Regularization with a Lagrangian Dual approach for automatic hyperparameter tuning.
34
Foster, James Daniel. "Mixed-integer quadratically-constrained programming, piecewise-linear approximation and error analysis with applications in power flow." Thesis, 2014. http://hdl.handle.net/1959.13/1048192.
Full textAbstract:
Research Doctorate - Doctor of Philosophy (PhD)This thesis investigates of the structure and solution of quadratically constrained optimization problems incorporating models of electrical power flow through transmission networks. Approximation of the equations and inequalities describing electrical power flow play a central role. Mixed-integer nonlinear programming (MINLP) theory is applied to determining good bounds to the optimal values of power flow optimization problems. After reviewing the literature on power system planning and design methods using mixed-integer programming, we apply recently developed MINLP software tools to the problem of distributed generation design in a distribution network. We investigate the merits of three mixed-integer programming approaches for finding good designs for new generator installation, along with a method for determining lower bounds on the optimal design objective by solving a knapsack problem. We then turn our attention to a typical continuous optimization problem with power flow constraints with the objective of minimising power loss. The natural question is how to construct good approximations of the equations and inequalities describing power flow. The analytic derivation of the error in the solutions of an approximate system of equations is considered. We then give a united analysis of the special structure of certain nonconvex quadratic functions that appear within the power flow constraints. It is seen that these quadratic functions can be reduced to the symmetric paraboloid function over the real plane by a linear eigenvector-based transformation of variables. Techniques are then presented for exploiting this special paraboloid structure. A systematic study of piecewise-linear approximations to this fundamental paraboloid function is set forth through the framework of the Delaunay triangulation, an object possessing a rich theory from the area of computational geometry. We consider piecewise-linear functions which interpolate the paraboloid function at the vertices of partitions of convex regions, and propose a theory for the optimization of partition geometry. Such partition optimization is over families of partitions possessing the same topology and a fixed number of polytopes, with the objective that an optimal partition minimises the maximum separation between the paraboloid function and the piecewise-linear function generated from the partition. We finally present a novel global optimization approach to forming strong outer approximating convex programs of nonconvex power flow optimization problems. This is achieved through replacing reverse convex quadratic inequality constraints in the transformed problem with a linear mixed-integer model based on piecewise-linear functions interpolating the paraboloid function. Our approach enables the computation of lower bounds to the value of the global optimum of power flow optimization problems with convex objectives.
35
Ding, Yichuan. "On Efficient Semidefinite Relaxations for Quadratically Constrained Quadratic Programming." Thesis, 2007. http://hdl.handle.net/10012/3044.
Full textAbstract:
Two important topics in the study of Quadratically Constrained Quadratic Programming (QCQP) are how to exactly solve a QCQP with few constraints in polynomial time and how to find an inexpensive and strong relaxation bound for a QCQP with many constraints. In this thesis, we first review some important results on QCQP, like the S-Procedure, and the strength of Lagrangian Relaxation and the semidefinite relaxation. Then we focus on two special classes of QCQP, whose objective and constraint functions take the form trace(X^TQX + 2C^T X) + β, and trace(X^TQX + XPX^T + 2C^T X)+ β respectively, where X is an n by r real matrix. For each class of problems, we proposed different semidefinite relaxation formulations and compared their strength. The theoretical results obtained in this thesis have found interesting applications, e.g., solving the Quadratic Assignment Problem.
36
"Novel Reformulations and Relaxations for Quadratically Constrained Quadratic Programming." 2016. http://repository.lib.cuhk.edu.hk/en/item/cuhk-1292666.
Full text
37
"Approximation algorithms for Lp-ball and quadratically constrained polynomial optimization problems." 2013. http://library.cuhk.edu.hk/record=b6115682.
Full textAbstract:
本论文着重研究了带有Lp模球约束以及二次约束的多项式优化问题的计算复杂度以及关于此类问题的近似算法。在本论文中，利用张量对称化的技巧，我们首次证明了当P∈ [2 ，∞] ，任意高阶的带有Lp模球约束的多项式优化问题均为NP 困难。借助模的对偶性质，我们将这类优化问题转化为求解凸体半径的问题，从而使得我们获得了之前研究所无法使用的算法工具。具体来说，利用计算凸几何的算法工具，对于Lp模球约束的多项式优化问题，我们得到了近似比为[附圖]的确定性多项式时间近似算法，其中d为目标多项式的阶次， n 为问题的维度。使用随机算法，我们将近似比进一步提高为此类问题的己知最优值。[附圖]。此外，我们发展了计算凸几何当中对于凸体半径的计算方法，从而设计出了一种对二次约束多项式优化问题近似比为[附圖]的近似算法，其中m为问题的约束个数。我们的结果涵盖并提高了之前关于此类问题的研究结果。我们相信在本论文中使用的新的算法工具，将在今后的多项式优化问题研究中得到更广泛的应用。In this thesis, we present polynomial time approximation algorithms for solving various homogeneous polynomial optimization problems and their multilinear relaxations. Specifically, for the problems with Lp ball constraint, where P∈ [2 ，∞], by reducing them to that of determining the Lq-diameter of certain convex body, we show that they can be approximated to within a factor of [with formula] in deterministic polynomial time, where q = p=(p - 1) is the conjugate of p, n is the number of variables, and d is the degree of the polynomial. We further show that with the help of randomization, the approximation guarantee can be improved to [with formula], which is independent of p and is currently the best for the aforementioned problems. Moreover, we extend the argument of deterministic algorithm mentioned above to solve the quadratically constrained polynomial optimization problems. In particular, for any intersection of ellipsoids K, we can, in polynomial time, construct a random polytope P, which satisfies [with formula]. Then, by reducing the problem to that of evaluating the maximum polytopal norm [with formula] induced by P, over certain convex body, we can approximate the quadratically constrained problem within a factor of [with formula] in polynomial time. Our results unify and generalize those in the literature, which focus either on the quadratic case or the case where [with formula]. We believe that the wide array of tools used in this thesis will have further applications in the study of polynomial optimization problems.
Detailed summary in vernacular field only.
Hou, Ke.
On title page "p" is subscript.
Thesis (Ph.D.) Chinese University of Hong Kong, 2013.
Includes bibliographical references (leaves 106-111).
Abstracts also in Chinese.
38
"Cardinality constrained discrete-time linear-quadratic control." 2005. http://library.cuhk.edu.hk/record=b5892706.
Full textAbstract:
Gao Jianjun.Thesis (M.Phil.)--Chinese University of Hong Kong, 2005.
Includes bibliographical references (leaves 75-76).
Abstracts in English and Chinese.
Chapter 1 --- Introduction --- p.1
Chapter 2 --- Solution Framework Using Dynamic Programming --- p.7
Chapter 2.1 --- Difficulty of using dynamic programming --- p.8
Chapter 2.2 --- Scalar-state problems --- p.12
Chapter 2.3 --- Time-invariant system --- p.17
Chapter 2.4 --- Illustrative example of a scalar-state problem --- p.21
Chapter 3 --- Cardinality Constrained Quadratic Optimization --- p.26
Chapter 3.1 --- Reformulation --- p.27
Chapter 3.2 --- NP hardness --- p.31
Chapter 3.3 --- Solving CCQP with an efficient branch and bound method --- p.34
Chapter 3.3.1 --- Efficient branch and bound algorithm --- p.34
Chapter 3.3.2 --- Geometrical interpretation of the proposed ranking order --- p.48
Chapter 3.3.3 --- Additional algorithmic ideas for enhancing computational efficiency --- p.56
Chapter 3.4 --- Numerical example and computational results --- p.60
Chapter 4 --- Summary and Future Work --- p.73
39
"Distribution-free, uniformly-tighter linear approximations for chance-constrained programming." Sloan School of Management, Massachusetts Institute of Technology, 1990. http://hdl.handle.net/1721.1/2290.
Full text
40
"On cardinality constrained optimization." Thesis, 2009. http://library.cuhk.edu.hk/record=b6074943.
Full textAbstract:
Although cardinality constraints naturally arise in many applications, e.g., in portfolio selection problems of choosing small number of assets from a large pool of stocks or dynamic portfolio selection problems with limited trading dates within a given time horizon and in subset selection of the regression analysis, the state-of-the-art in cardinality constrained optimization has been stagnant up to this stage, largely due to the inherent combinatorial nature of such hard problems. We focus in this research on developing efficient and implementable solution algorithms for cardinality constrained optimization by investigating prominent structures and hidden properties of such problems. More specifically, we develop solution algorithms for four specific cardinality constrained optimization problems, including (i) the cardinality constrained linear-quadratic control problem, (ii) the optimal control problem of linear switched system with limited number of switching, (iii) the time cardinality constrained dynamic mean- variance portfolio selection problem, and (iv) cardinality constrained quadratic optimization problem. Taking advantages of a linear-quadratic structure of cardinality constrained optimization problems, we strive for analytical solutions when possible. More specifically, we derive an analytical solution for problem (iii) and obtain for both problems (i) and (ii) semi-analytical expressions of the solution governed by a family of Ricatti-like equations, which still suffer an exponentially growing complexity. To achieve high-performance of the solution algorithm, we devise algorithms of a branch and bound (BnB) type with various tight and computationally-cheap lower bounds achieved by identifying suitable SDP formulations and by exploiting geometric properties of the problem. We demonstrate efficiency of our proposed solution schemes evidenced from numerical experiments and present a firm step-forward in tackling this long-standing challenge of cardinality constrained optimization.Gao, Jianjun.
Adviser: Duan Li.
Source: Dissertation Abstracts International, Volume: 72-11, Section: B, page: .
Thesis (Ph.D.)--Chinese University of Hong Kong, 2009.
Includes bibliographical references (leaves 134-142).
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, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web.
Abstract also in Chinese.
41
Yu-ChangTai and 戴毓璋. "Using Linear Programming to Solve Reliability-Constrained Task Scheduling in Computer Clusters." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/84933250090521038189.
Full textAbstract:
碩士國立成功大學
資訊工程學系
102
In parallel computing environment, the reliability is an important issue in the scheduling problem. Optimizing both finish time and reliability in task scheduling problem is a NP-complete problem. In order to increase the reliability of task scheduling, duplicating task is a very common technique. In this thesis, we propose a method of linear programming to find the most suitable duplication number of each task as possible, such that there is fastest finish time in the scheduling. Otherwise, the reliability must meet the requirement specified by users or systems. In this study, the reliability evaluation considers both processor and communication link. The reliability is a probability representing successful implementation of an application in computer clusters. Finally, the experimental results show that the presented algorithm outperforms other ones proposed.
42
"On safe tractable approximations of chance-constrained linear matrix inequalities with partly dependent perturbations." 2011. http://library.cuhk.edu.hk/record=b5894803.
Full textAbstract:
Cheung, Sin Shuen.Thesis (M.Phil.)--Chinese University of Hong Kong, 2011.
Includes bibliographical references (leaves 55-59).
Abstracts in English and Chinese.
Abstract --- p.i
Acknowledgement --- p.iii
Chapter 1 --- Introduction --- p.1
Chapter 2 --- Preliminaries --- p.5
Chapter 2.1 --- Heuristics by Hoeffding and Janson --- p.5
Chapter 2.2 --- Facts in Matrix Theory --- p.10
Chapter 2.3 --- Facts in Probability --- p.11
Chapter 3 --- General Chance-Constrained LMIs --- p.18
Chapter 3.1 --- Probability Inequalities --- p.18
Chapter 3.2 --- Safe Tractable Approximations --- p.22
Chapter 4 --- Chance-Constrained Quadratically Perturbed LMIs --- p.27
Chapter 4.1 --- Exact Proper Fractional Covers --- p.27
Chapter 4.2 --- Bounding the Matrix Moment Generating Functions --- p.32
Chapter 5 --- Computational Study --- p.39
Chapter 5.1 --- Update Procedures for Safe Tractable Approximations --- p.39
Chapter 5.2 --- A Numerical Example and Comparisons --- p.44
Chapter 6 --- Conclusion --- p.54
Bibliography --- p.55
43
"Integration of constraint programming and linear programming techniques for constraint satisfaction problem and general constrained optimization problem." 2001. http://library.cuhk.edu.hk/record=b5890598.
Full textAbstract:
Wong Siu Ham.Thesis (M.Phil.)--Chinese University of Hong Kong, 2001.
Includes bibliographical references (leaves 131-138).
Abstracts in English and Chinese.
Abstract --- p.ii
Acknowledgments --- p.vi
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Motivation for Integration --- p.2
Chapter 1.2 --- Thesis Overview --- p.4
Chapter 2 --- Preliminaries --- p.5
Chapter 2.1 --- Constraint Programming --- p.5
Chapter 2.1.1 --- Constraint Satisfaction Problems (CSP's) --- p.6
Chapter 2.1.2 --- Satisfiability (SAT) Problems --- p.10
Chapter 2.1.3 --- Systematic Search --- p.11
Chapter 2.1.4 --- Local Search --- p.13
Chapter 2.2 --- Linear Programming --- p.17
Chapter 2.2.1 --- Linear Programming Problems --- p.17
Chapter 2.2.2 --- Simplex Method --- p.19
Chapter 2.2.3 --- Mixed Integer Programming Problems --- p.27
Chapter 3 --- Integration of Constraint Programming and Linear Program- ming --- p.29
Chapter 3.1 --- Problem Definition --- p.29
Chapter 3.2 --- Related works --- p.30
Chapter 3.2.1 --- Illustrating the Performances --- p.30
Chapter 3.2.2 --- Improving the Searching --- p.33
Chapter 3.2.3 --- Improving the representation --- p.36
Chapter 4 --- A Scheme of Integration for Solving Constraint Satisfaction Prob- lem --- p.37
Chapter 4.1 --- Integrated Algorithm --- p.38
Chapter 4.1.1 --- Overview of the Integrated Solver --- p.38
Chapter 4.1.2 --- The LP Engine --- p.44
Chapter 4.1.3 --- The CP Solver --- p.45
Chapter 4.1.4 --- Proof of Soundness and Completeness --- p.46
Chapter 4.1.5 --- Compared with Previous Work --- p.46
Chapter 4.2 --- Benchmarking Results --- p.48
Chapter 4.2.1 --- Comparison with CLP solvers --- p.48
Chapter 4.2.2 --- Magic Squares --- p.51
Chapter 4.2.3 --- Random CSP's --- p.52
Chapter 5 --- A Scheme of Integration for Solving General Constrained Opti- mization Problem --- p.68
Chapter 5.1 --- Integrated Optimization Algorithm --- p.69
Chapter 5.1.1 --- Overview of the Integrated Optimizer --- p.69
Chapter 5.1.2 --- The CP Solver --- p.74
Chapter 5.1.3 --- The LP Engine --- p.75
Chapter 5.1.4 --- Proof of the Optimization --- p.77
Chapter 5.2 --- Benchmarking Results --- p.77
Chapter 5.2.1 --- Weighted Magic Square --- p.77
Chapter 5.2.2 --- Template design problem --- p.78
Chapter 5.2.3 --- Random GCOP's --- p.79
Chapter 6 --- Conclusions and Future Work --- p.97
Chapter 6.1 --- Conclusions --- p.97
Chapter 6.2 --- Future work --- p.98
Chapter 6.2.1 --- Detection of implicit equalities --- p.98
Chapter 6.2.2 --- Dynamical variable selection --- p.99
Chapter 6.2.3 --- Analysis on help of linear constraints --- p.99
Chapter 6.2.4 --- Local Search and Linear Programming --- p.99
Appendix --- p.101
Proof of Soundness and Completeness --- p.101
Proof of the optimization --- p.126
Bibliography --- p.130
44
Chen, Chan Hui, and 詹蕙珍. "The Resource-Constrained Multiple-Project Scheduling Problem with Multiple Fuzzy Objectives Non-linear Programming." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/09011704259285909618.
Full textAbstract:
碩士國立屏東科技大學
工業管理系
92
The purpose of this study is to develop a multiple fuzzy objective non-linear programming (MFONLP) model for solving the resource-constrained multi-project scheduling problem (RCMPSP). Two novel goals, maximization of total project net present value and the minimization of the total project duration, are involved in the RCMPSP model. Factors considered in the proposed model are the number of projects, the quantity of renewable-resources available, the quantity of capital available, multiple objective functions, the project delay penalty and the project early completion bonus. By using these factors as objective trade-off components with multiple fuzzy goals, the proposed model is practically developed to provide various scenarios on specific satisfactory levels. Two project-scheduling cases are implemented to test the proposed model. The implementation is designed as several scenarios to determine the objective variations of goal components. The implementation results demonstrate that the use of MFONLP models could provide project manager with further insight into the systematic analysis. Furthermore, an evaluation is conducted to compare the effectiveness between the proposed model with the goal programming model and Zimmermann model. The comparison results demonstrate that the MFONLP model yields a higher total project net present value and a lower total project duration than that the two existing models do. The proposed MFONLP model also demonstrates more flexibility for application to the RCMPSP-DCF, which is useful for project manager while making decisions.
45
Espinoza, Francisco. "A New Interpolation Approach for Linearly Constrained Convex Optimization." Thesis, 2012. http://hdl.handle.net/10754/244891.
Full textAbstract:
In this thesis we propose a new class of Linearly Constrained Convex Optimization
methods based on the use of a generalization of Shepard's interpolation formula. We
prove the properties of the surface such as the interpolation property at the boundary
of the feasible region and the convergence of the gradient to the null space of the
constraints at the boundary. We explore several descent techniques such as steepest
descent, two quasi-Newton methods and the Newton's method. Moreover, we implement
in the Matlab language several versions of the method, particularly for the
case of Quadratic Programming with bounded variables. Finally, we carry out performance
tests against Matab Optimization Toolbox methods for convex optimization
and implementations of the standard log-barrier and active-set methods. We conclude
that the steepest descent technique seems to be the best choice so far for our
method and that it is competitive with other standard methods both in performance
and empirical growth order.
46
Chen, Chien-Chu, and 陳建助. "Application of Fuzzy Multi-Objective Linear Programming on the Robust Resource-Constrained Multi-Project Scheduling Problems." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/76354092911141579847.
Full textAbstract:
碩士國立屏東科技大學
工業管理系所
97
The purpose of this study is to formulate a fuzzy multiobjective non-linear programming (FMONLP) model to solve the robust resource-constrained multi-project scheduling problems (RRCMPSP). Project slack time and maximization robustness are considered as factors in terms of project resources and capital limitation in the proposed model. An optimal satisfactory level is deployed to demonstrate the trade-offs among fuzzy multi-objectives for the use of project managers. The implementation is designed as several aspects to demonstrate the parameter variations of FMONLP and its superior to previous models. The implementation results also demonstrate that the use of FMONLP to solve RRCMPSP could help project managers explain to the theoretical rigor not found in simpler decision models for project management.
47
Guindon, David Leo. "Design of nearly linear-phase recursive digital filters by constrained optimization." Thesis, 2007. http://hdl.handle.net/1828/296.
Full textAbstract:
The design of nearly linear-phase recursive digital filters using constrained optimization is investigated. The design technique proposed is expected to be useful in applications where both magnitude and phase response specifications need to be satisfied. The overall constrained optimization method is formulated as a quadratic programming problem based on Newton’s method. The objective function, its gradient vector and Hessian matrix as well as a set of linear constraints are derived. In this analysis, the independent variables are assumed to be the transfer function coefficients. The filter stability issue and convergence efficiency, as well as a ‘real axis attraction’ problem are solved by integrating the corresponding bounds into the linear constraints of the optimization method. Also, two initialization techniques for providing efficient starting points for the optimization are investigated and the relation between the zero and pole positions and the group delay are examined. Based on these ideas, a new objective function is formulated in terms of the zeros and poles of the transfer function expressed in polar form and integrated into the optimization process. The coefficient-based and polar-based objective functions are tested and compared and it is shown that designs using the polar-based objective function produce improved results. Finally, several other modern methods for the design of nearly linear-phase recursive filters are compared with the proposed method. These include an elliptic design combined with an optimal equalization technique that uses a prescribed group delay, an optimal design method with robust stability using conic-quadratic-programming updates, and an unconstrained optimization technique that uses parameterization to guarantee filter stability. It was found that the proposed method generates similar or improved results in all comparative examples suggesting that the new method is an attractive alternative for linear-phase recursive filters of orders up to about 30.
48
Wang, Lin-In, and 王玲英. "An Application of Gray Linear Programming to Power Plant Expansion Strategies as Constrained by Ambient Air Quality." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/78691907252627844601.
Full textAbstract:
碩士逢甲大學
環境工程與科學所
91
The growing demand of electricity in recent years in Taiwan is a result of high-tech industry expansions and living standard enhancement. To meet increasing demand generating capacity (particularly coal-fired power plants) will have to increase. Expansions in power production will place additional burden on the environment in terms of air pollution. Therefore, it is imperative to expand generating capacity while maintaining environmental quality. The objective of this research is to identify the best expansion strategies of coal-fired power plants as constrained by the ambient air quality. Major substances of the research are Apply an air quality model to calculate the ambient air quality effects resulting from an increase of one unit of generator at a power plant (call these effects as transfer coefficients) Adopt the gray linear programming technique to identify the number of generating units (integers) allowable at each power plant under the constraint of air quality standard Include the concept of prevention of significant deterioration of ambient air quality in expansion strategies Perform the sensitivity analysis─the increase of extra generating capacity when the emissions from power plant stacks are reduced The research selected the central region of Taiwan as a case study. Results of the study ascertain the feasibility and validity of the research concept.
49
Adeyefa, Segun Adeyemi. "Satisticing solutions for multiobjective stochastic linear programming problems." Thesis, 2011. http://hdl.handle.net/10500/5703.
Full textAbstract:
Multiobjective Stochastic Linear Programming is a relevant topic. As a matter of fact,
many real life problems ranging from portfolio selection to water resource management
may be cast into this framework.
There are severe limitations in objectivity in this field due to the simultaneous presence
of randomness and conflicting goals. In such a turbulent environment, the mainstay of
rational choice does not hold and it is virtually impossible to provide a truly scientific
foundation for an optimal decision.
In this thesis, we resort to the bounded rationality and chance-constrained principles to
define satisficing solutions for Multiobjective Stochastic Linear Programming problems.
These solutions are then characterized for the cases of normal, exponential, chi-squared
and gamma distributions.
Ways for singling out such solutions are discussed and numerical examples provided for
the sake of illustration.
Extension to the case of fuzzy random coefficients is also carried out.Decision Sciences
50
Adeyefa, Segun Adeyemi. "Satisficing solutions for multiobjective stochastic linear programming problems." Thesis, 2011. http://hdl.handle.net/10500/5703.
Full textAbstract:
Multiobjective Stochastic Linear Programming is a relevant topic. As a matter of fact,
many real life problems ranging from portfolio selection to water resource management
may be cast into this framework.
There are severe limitations in objectivity in this field due to the simultaneous presence
of randomness and conflicting goals. In such a turbulent environment, the mainstay of
rational choice does not hold and it is virtually impossible to provide a truly scientific
foundation for an optimal decision.
In this thesis, we resort to the bounded rationality and chance-constrained principles to
define satisficing solutions for Multiobjective Stochastic Linear Programming problems.
These solutions are then characterized for the cases of normal, exponential, chi-squared
and gamma distributions.
Ways for singling out such solutions are discussed and numerical examples provided for
the sake of illustration.
Extension to the case of fuzzy random coefficients is also carried out.Decision Sciences