• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 5
  • 4
  • 1
  • Tagged with
  • 13
  • 5
  • 4
  • 3
  • 3
  • 3
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Lossless convexification of quadrotor motion planning with experiments

Pehlivantürk, Can 09 October 2014 (has links)
This thesis describes a motion planning method that is designed to guide an autonomous quadrotor. The proposed method is based on a novel lossless convexication, which was first introduced in (12), that allows convex representations of many non-convex control constraints, such as that of the quadrotors. The second contribution of this thesis is to include two separate methods to generate path constraints that capture non-convex position constraints. Using the convexied optimal trajectory generation problem with physical and path constraints, an algorithm is developed that generates fuel optimal trajectories given the initial state and desired final state. As a proof of concept, a quadrotor testbed is developed that utilize a state-of-the-art motion tracking system. The quadrotor is commanded via a ground station where the convexified optimal trajectory generation algorithm is successfully implemented together with a trajectory tracking feedback controller. / text
2

Lossless convexification of optimal control problems

Harris, Matthew Wade 30 June 2014 (has links)
This dissertation begins with an introduction to finite-dimensional optimization and optimal control theory. It then proves lossless convexification for three problems: 1) a minimum time rendezvous using differential drag, 2) a maximum divert and landing, and 3) a general optimal control problem with linear state constraints and mixed convex and non-convex control constraints. Each is a unique contribution to the theory of lossless convexification. The first proves lossless convexification in the presence of singular controls and specifies a procedure for converting singular controls to the bang-bang type. The second is the first example of lossless convexification with state constraints. The third is the most general result to date. It says that lossless convexification holds when the state space is a strongly controllable subspace. This extends the controllability concepts used previously, and it recovers earlier results as a special case. Lastly, a few of the remaining research challenges are discussed. / text
3

Valid Inequalities for Mixed-Integer Linear and Mixed-Integer Conic Programs

Yildiz, Sercan 01 May 2016 (has links)
Mixed-integer programming provides a natural framework for modeling optimization problems which require discrete decisions. Valid inequalities, used as cutting-planes and cuttingsurfaces in integer programming solvers, are an essential part of today’s integer programming technology. They enable the solution of mixed-integer programs of greater scale and complexity by providing tighter mathematical descriptions of the feasible solution set. This dissertation presents new structural results on general-purpose valid inequalities for mixedinteger linear and mixed-integer conic programs. Cut-generating functions are a priori formulas for generating a cutting-plane from the data of a mixed-integer linear program. This concept has its roots in the work of Balas, Gomory, and Johnson from the 1970s. It has received renewed attention in the past few years. Gomory and Johnson studied cut-generating functions for the corner relaxation of a mixedinteger linear program, which ignores the nonnegativity constraints on the basic variables in a tableau formulation. We consider models where these constraints are not ignored. In our first contribution, we generalize a classical result of Gomory and Johnson characterizing minimal cut-generating functions in terms of subadditivity, symmetry, and periodicity. Our analysis also exposes shortcomings in the usual definition of minimality in our general setting. To remedy this, we consider stronger notions of minimality and show that these impose additional structure on cut-generating functions. A stronger notion than the minimality of a cut-generating function is its extremality. While extreme cut-generating functions produce powerful cutting-planes, their structure can be very complicated. For the corner relaxation of a one-row integer linear program, Gomory and Johnson identified continuous, piecewise linear, minimal cut-generating functions with only two distinct slope values as a “simple” class of extreme cut-generating functions. In our second contribution, we establish a similar result for a one-row problem which takes the nonnegativity constraint on the basic variable into account. In our third contribution, we consider a multi-row model where only continuous nonbasic variables are present. Conforti, Cornuéjols, Daniilidis, Lemaréchal, and Malick recently showed that not all cutting-planes can be obtained from cut-generating functions in this framework. They also conjectured a natural condition under which cut-generating functions might be sufficient. In our third contribution, we prove that this conjecture is true. This justifies the recent research interest in cut-generating functions for this model. Despite the power of mixed-integer linear programming, many optimization problems of practical and theoretical interest cannot be modeled using a linear objective function and constraints alone. Next, we turn to a natural generalization of mixed-integer linear programming which allows nonlinear convex constraints: mixed-integer conic programming. Disjunctive inequalities, introduced by Balas in the context of mixed-integer linear programming in the 1970s, have been a principal ingredient in the practical success of mixed-integer programming in the last two decades. In order to extend our understanding of disjunctive inequalities to mixed-integer conic programming, we pursue a principled study of two-term disjunctions on conic sets. In our fourth contribution, we consider two-term disjunctions on a general regular cone. A result of Kılınç-Karzan indicates that conic minimal valid linear inequalities are all that is needed for a closed convex hull description of such sets. First we characterize the structure of conic minimal and tight valid linear inequalities for the disjunction. Then we develop structured nonlinear valid inequalities for the disjunction by grouping subsets of valid linear inequalities. We analyze the structure of these inequalities and identify conditions which guarantee that a single such inequality characterizes the closed convex hull of the disjunction. In our fifth and sixth contributions, we extend our earlier results to the cases where the regular cone under consideration is a direct product of second order cones and nonnegative rays and where it is the positive semidefinite cone. Disjunctions on these cones deserve special attention because they provide fundamental relaxations for mixed-integer second-order cone and mixed-integer semidefinite programs. We identify conditions under which our valid convex inequalities can be expressed in computationally tractable forms and present techniques to generate low-complexity relaxations when these conditions are not satisfied. In our final contribution, we provide closed convex hull descriptions for homogeneous two-term disjunctions on the second-order cone and general two-term disjunctions on affine cross-sections of the second-order cone. Our results yield strong convex disjunctive inequalities which can be used as cutting-surfaces in generic mixed-integer conic programming solvers.
4

New relaxations for composite functions

Taotao He (7047464) 13 August 2019 (has links)
Mixed-integer nonlinear programs are typically solved using branch-and-bound algorithms. A key determinant of the success of such methods is their ability to construct tight and tractable relaxations. The predominant relaxation strategy used by most state-of-the-art solvers is the factorable programming technique. This technique recursively traverses the expression tree for each nonlinear function and relaxes each operator over a bounding box that covers the ranges for all the operands. While it is versatile, and allows finer control over the number of introduced variables, the factorable programming technique often leads to weak relaxations because it ignores operand structure while constructing the relaxation for the operator.<div>In this thesis, we introduce new relaxations, called composite relaxations, for composite functions by convexifying the outer-function over a polytope, which models an ordering structure of outer-approximators of inner functions. We devise a fast combinatorial algorithm to separate the hypograph of concave-extendable supermodular outer-functions over the polytope, although the separation problem is NP-Hard in general. As a consequence, we obtain large classes of inequalities that tighten prevalent factorable programming relaxations. The limiting composite relaxation obtained with infinitely many outer-approximators for each inner-function is shown to be related to the solution of an optimal transport problem. Moreover, composite relaxations can be seamlessly embedded into a discretization scheme to relax nonlinear programs with mixed-integer linear programs. Combined with linearization, composite relaxations provide a framework for deriving cutting planes used in relaxation hierarchies and more.<br></div>
5

HyunJuOhDissertation.pdf

Hyun-Ju Oh (14228162) 09 December 2022 (has links)
<p>In this thesis, we devise a new finite branch-and-bound algorithm for disjoint bilinear programs. In these problems, there are two vectors of variables, $\b{x}$ and $\b{y}$, and two polytopes $P_{\b{x}}$ and $P_{\b{y}}$ such that $\b{x}$ (resp. $\b{y}$) is chosen from $P_{\b{x}}$ (resp. $P_{\b{y}}$) so that a bilinear objective function is minimized. By a bilinear objective, we mean that the objective becomes linear when either one of $\b{x}$ or $\b{y}$ is fixed. </p> <p>  This branch-and-bound scheme uses a relaxation that is derived using the reformulation-linearization technique (RLT). The RLT relaxation is constructed by taking products of constraints and linearizing the bilinear terms using introduced variables. The quality of this relaxation improves as higher order products and the corresponding monomial terms are linearized. Although it is known that, as RLT relaxations are constructed with increasingly higher order linearizations, the relaxation eventually converges to the true optimal value. However, no finite convergence properties are known. In contrast, we show that the first level of the RLT hierarchy suffices to convexify the problem when one of the polytopes is a simplex. Then, using this insight we devise a new class of relaxations by combining RLT with a variant of the double description procedure, where the latter lifts a polytope into a simplex in a finite number of steps.  This leads us to a finite hierarchy of relaxations that converges to the optimal value. Although this hierarchy is finite, from a computational perspective, we find that the relaxations grow rapidly in size. However, we utilize the insight to derive a simplicial branch-and-bound scheme, that expresses each polytope as a union of simplices allowing us to converge finitely to the optimal solution for the problem. We perform preliminary numerical experiments to show that this approach holds promise and competes favorably with state-of-the-art methods on larger instances.</p>
6

Etude de relaxations en traitement d'images. Application à la segmentation et autres problèmes multi-étiquettes. / Relaxations in image processing, application to segmentation and others multi-label problems

Yildizoglu, Romain 08 July 2014 (has links)
Cette thèse étudie différentes relaxations pour minimiser des fonctionnelles non convexes qui apparaissent en traitement d’images. Des problèmes comme la segmentation d’image peuvent en effet s’écrire comme un problème de minimisation d’une certaine fonctionnelle, le minimiseur représentant la segmentation recherchée. Différentes méthodes ont été proposées pour trouver des minima locaux ou globaux de la fonctionnelle non convexe du modèle de Mumford-Shah constant par morceaux à deux phases. Certaines approches utilisent une relaxation convexe qui permet d’obtenir des minima globaux de la fonctionnelle non convexe. On rappelle et compare certaines de ces méthodes et on propose un nouveau modèle par bande étroite, qui permet d’obtenir des minima locaux tout en utilisant des algorithmes robustes qui proviennent de l’optimisation convexe. Ensuite, on construit une relaxation convexe d’un modèle de segmentation à deux phases qui repose sur la comparaison entre deux histogrammes donnés et les histogrammes estimés globalement sur les deux régions de la segmentation. Des relaxations pour des problèmes multi-étiquettes à plusieurs dimensions comme le flot optique sont également étudiées. On propose une relaxation convexe avec un algorithme itératif qui ne comprend que des projections qui se calculent exactement, ainsi qu’un nouvel algorithme pour une relaxation convexe sur chaque variable mais non convexe globalement. On étudie la manière d’estimer une solution du problème non convexe original à partir d’une solution d’un problème relaxé en comparant des méthodes existantes avec des nouvelles / In this thesis we study different relaxations of non-convex functionals that can be found in image processing. Some problems, such as image segmentation, can indeed be written as the minimization of a functional. The minimizer of the functional represents the segmentation. Different methods have been proposed in order to find local or global minima of the non-convex functional of the two-phase piecewise constant Mumford-Shah model. With a convex relaxation of this model we can find a global minimum of the nonconvex functional. We present and compare some of these methods and we propose a new model with a narrow band. This model finds local minima while using robust convex optimization algorithms. Then a convex relaxation of a two-phase segmentation model is built that compares two given histograms with those of the two segmented regions. We also study some relaxations of high-dimension multi-label problems such as optical flow computation. A convex relaxation with a new algorithm is proposed. The algorithm is iterative with exact projections. A new algorithm is given for a relaxationthat is convex in each variable but that is not convex globally. We study the problem of constructing a solution of the original non-convex problem with a solution of the relaxed problem. We compare existing methods with new ones.
7

Programmation mathématique en tomographie discrète / Mathematical programming for discrete tomography

Tlig, Ghassen 13 November 2013 (has links)
La tomographie est un ensemble de techniques visant à reconstruirel’intérieur d’un objet sans toucher l’objet lui même comme dans le casd’un scanner. Les principes théoriques de la tomographie ont été énoncéspar Radon en 1917. On peut assimiler l’objet à reconstruire à une image,matrice, etc.Le problème de reconstruction tomographique consiste à estimer l’objet àpartir d’un ensemble de projections obtenues par mesures expérimentalesautour de l’objet à reconstruire. La tomographie discrète étudie le cas où lenombre de projections est limité et l’objet est défini de façon discrète. Leschamps d’applications de la tomographie discrète sont nombreux et variés.Citons par exemple les applications de type non destructif comme l’imageriemédicale. Il existe d’autres applications de la tomographie discrète, commeles problèmes d’emplois du temps.La tomographie discrète peut être considérée comme un problème d’optimisationcombinatoire car le domaine de reconstruction est discret et le nombrede projections est fini. La programmation mathématique en nombres entiersconstitue un outil pour traiter les problèmes d’optimisation combinatoire.L’objectif de cette thèse est d’étudier et d’utiliser les techniques d’optimisationcombinatoire pour résoudre les problèmes de tomographie. / The tomographic imaging problem deals with reconstructing an objectfrom a data called a projections and collected by illuminating the objectfrom many different directions. A projection means the information derivedfrom the transmitted energies, when an object is illuminated from a particularangle. The solution to the problem of how to reconstruct an object fromits projections dates to 1917 by Radon. The tomographic reconstructingis applicable in many interesting contexts such as nondestructive testing,image processing, electron microscopy, data security, industrial tomographyand material sciences.Discete tomography (DT) deals with the reconstruction of discret objectfrom limited number of projections. The projections are the sums along fewangles of the object to be reconstruct. One of the main problems in DTis the reconstruction of binary matrices from two projections. In general,the reconstruction of binary matrices from a small number of projections isundetermined and the number of solutions can be very large. Moreover, theprojections data and the prior knowledge about the object to reconstructare not sufficient to determine a unique solution. So DT is usually reducedto an optimization problem to select the best solution in a certain sense.In this thesis, we deal with the tomographic reconstruction of binaryand colored images. In particular, research objectives are to derive thecombinatorial optimization techniques in discrete tomography problems.
8

Contribution au développement d’une loi de guidage autonome par platitude : application à une mission de rentrée atmosphérique

Morio, Vincent 19 May 2009 (has links)
Cette thèse porte sur le développement d'une loi de guidage autonome par platitude pour les véhicules de rentrée atmosphérique. La problématique associée au développement d'une loi de guidage autonome porte sur l'organisation globale, l'intégration et la gestion de l'information pertinente jusqu'à la maîtrise du système spatial durant la phase de rentrée. La loi de guidage autonome proposée dans ce mémoire s'appuie sur le concept de platitude, afin d'effectuer un traitement des informations à bord, dans le but double d'attribuer un niveau de responsabilité et d'autonomie au véhicule, déchargeant ainsi le segment sol de tâches opérationnelles "bas niveau", pour lui permettre de mieux assumer son rôle de coordination globale. La première partie de ce mémoire traite de la caractérisation formelle de sorties plates pour les systèmes non linéaires régis par des équations différentielles ordinaires, ainsi que pour les systèmes linéaires à retards. Des algorithmes constructifs sont proposés afin de calculer des sorties plates candidates sous un environnement de calcul formel standard. Dans la seconde partie, une méthodologie complète et générique de replanification de trajectoires de rentrée atmosphérique est proposée, afin de doter la loi de guidage d'un certain niveau de tolérance à des pannes actionneur simple/multiples pouvant survenir lors des phases critiques d'une mission de rentrée atmosphérique. En outre, une méthodologie d'annexation superellipsoidale est proposée afin de convexifier le problème de commande optimale décrit dans l'espace des sorties plates. La loi de guidage proposée est ensuite appliquée étape par étape à une mission de rentrée atmosphérique pour la navette spatiale américaine STS-1. / This thesis deals with the design of an autonomous guidance law based on flatness approach for atmospheric reentry vehicles. The problematic involved by the design of an autonomous guidance law relates to the global organization, the integration and the management of relevant data up to the mastering of the spacecraft during the re-entry mission. The autonomous guidance law proposed in this dissertation is based on flatness concept, in order to perform onboard processing so as to locally assign autonomy and responsibility to the vehicle, thus exempting the ground segment from "low level" operational tasks, so that it can ensure more efficiently its mission of global coordination. The first part of the manuscript deals with the formal characterization of flat outputs for nonlinear systems governed by ordinary differential equations, as well as for linear time-delay systems. Constructive algorithms are proposed in order to compute candidate flat outputs within a standard formal computing environment. In the second part of the manuscript, a global and generic reentry trajectory replanning methodology is proposed in order to provide a fault-tolerance capability to the guidance law, when facing single/multiple control surface failures that could occur during the critical phases of an atmospheric reentry mission. In addition, a superellipsoidal annexion method is proposed so as to convexify the optimal control problem described in the flat outputs space. The proposed guidance law is then applied step by step to an atmospheric reentry mission for the US Space Shuttle orbiter STS-1.
9

[en] STOCHASTIC PROGRAMMING WITH ENDOGENOUS UNCERTAINTY: AN APPLICATION IN HUMANITARIAN LOGISTICS / [pt] MODELOS DE PROGRAMAÇÃO ESTOCÁSTICA COM INCERTEZAS ENDÓGENAS: UMA APLICAÇÃO EM LOGÍSTICA HUMANITÁRIA

BRUNO DA COSTA FLACH 02 April 2019 (has links)
[pt] Neste trabalho estudamos uma classe de problemas de otimização estocástica com incertezas endógenas que é formulado como um problema de programação não-linear inteira (MINLP). Esta classe de problemas difere dos problemas de otimização estocástica geralmente estudados na literatura pelo fato de que que a distribuição de probabilidade dos parâmetros aleatórios depende das decisões tomadas. Apesar de discutido dentro do contexto do problema de logística humanitária, a metodologia proposta e os resutados obtidos são válidos para uma classe geral de problemas que agrega uma variedade de aplicações. Em particular, propõe-se (i) uma técnica de convexificação de polinômios de variáveis binárias, (ii) um algoritmo de geração de cortes e (iii) a incorporação dos conceitos de importance sampling dentro do contexto de otimização estocástica de modo a permitir a solução de grandes instâncias do problema. Os resultados computacionais apresentados demonstram as vantagens da metodologia proposta ao permitir a solução de instâncias significativamente maiores que aquelas atualmente apresentadas em trabalhos relacionados. / [en] In this work we study a class of stochastic programming problems with endogenous uncertainty – i.e., those in which the probability distribution of the random parameters is decision-dependent – which is formulated as a mixed integer non-linear programming (MINLP) problem. Although discussed in the context of the humanitarian logistics problem, the proposed methodology and obtained results are also valid for a more general class of problems which comprehends a variety of applications. In particular, we propose (i) a convexification technique for polynomials of binary variables, (ii) an efficient cutgeneration algorithm and (iii) the incorporation of importance sampling concepts into the stochastic programming framework so as to allow the solution of large instances of the problem. Computational results demonstrate the effectiveness of the proposed methodology by solving instances significantly larger than those reported in related works.
10

Programmation mathématique en tomographie discrète

Tlig, Ghassen 13 November 2013 (has links) (PDF)
La tomographie est un ensemble de techniques visant à reconstruirel'intérieur d'un objet sans toucher l'objet lui même comme dans le casd'un scanner. Les principes théoriques de la tomographie ont été énoncéspar Radon en 1917. On peut assimiler l'objet à reconstruire à une image,matrice, etc.Le problème de reconstruction tomographique consiste à estimer l'objet àpartir d'un ensemble de projections obtenues par mesures expérimentalesautour de l'objet à reconstruire. La tomographie discrète étudie le cas où lenombre de projections est limité et l'objet est défini de façon discrète. Leschamps d'applications de la tomographie discrète sont nombreux et variés.Citons par exemple les applications de type non destructif comme l'imageriemédicale. Il existe d'autres applications de la tomographie discrète, commeles problèmes d'emplois du temps.La tomographie discrète peut être considérée comme un problème d'optimisationcombinatoire car le domaine de reconstruction est discret et le nombrede projections est fini. La programmation mathématique en nombres entiersconstitue un outil pour traiter les problèmes d'optimisation combinatoire.L'objectif de cette thèse est d'étudier et d'utiliser les techniques d'optimisationcombinatoire pour résoudre les problèmes de tomographie.

Page generated in 0.1469 seconds