<p dir="ltr">Constrained optimization plays a crucial role in numerous scientific and engineering fields, where solutions must satisfy specific constraints while optimizing an objective function. The complexity of these problems has driven the development of efficient algorithms. Primal-dual methods, particularly, have been a powerful class of algorithms capable of tackling constrained optimization problems. This dissertation introduces and analyzes new Lagrangian-based primal-dual methods, exploring their applications in the equilibrium computation of generalized Nash games and non-convex constrained optimization problems. </p><p dir="ltr">Generalized Nash games, also known as generalized Nash equilibrium problems, expand the concept of classical Nash games by incorporating coupled constraints, which substantially increase their computational complexity. These games are prevalent in a variety of real-world applications, such as electricity markets, economic markets, transportation networks, and various multi-agent systems, where decision-makers are required to engage in strategic actions while also considering coupled constraints. We develop a primal-dual first-order method for efficient computation of generalized Nash equilibrium, providing its theoretical foundations and practical implementation. </p><p dir="ltr">Non-convex constrained optimization problems often emerge across various application domains, presenting significant theoretical and computational challenges due to the presence of non-convex constraints and objective functions. To address these challenges, we propose and analyze novel Lagrangian-based primal-dual methods designed to manage non-convex constraints and establish their convergence properties. We perform extensive numerical experiments to demonstrate the practicality and versatility of our proposed methods. The results show the efficacy of our methods in tackling the computational challenges associated with generalized Nash games and non-convex constrained optimization.</p>

Dans le contexte de la vision par ordinateur cette thèse étudie le problème d’appariement d’images dans le cadre de la télédétection pour la géologie. Plus précisément, nous disposons dans ce travail de deux images de la même scène géographique, mais acquises à partir de deux points de vue différents et éventuellement à un autre moment. La tâche d’appariement est d'associer à chaque pixel de la première image un pixel de la seconde image.Bien que ce problème soit relativement facile pour les êtres humains, il reste difficile à résoudre par un ordinateur. De nombreuses approches pour traiter cette tâche ont été proposées. Les techniques les plus prometteuses formulent la tâche comme un problème d'optimisation numérique. Malheureusement, le nombre d'inconnues ainsi que la nature de la fonction à optimiser rendent ce problème extrêmement difficile à résoudre. Cette thèse étudie deux approches avec un schéma multi-échelle pour résoudre le problème numérique sous-jacent / This thesis studies the computer vision problem of image registration in the context of geological remote sensing surveys. More precisely we dispose in this work of two images picturing the same geographical scene but acquired from two different view points and possibly at a different time. The task of registration is to associate to each pixel of the first image its counterpart in the second image.While this problem is relatively easy for human-beings, it remains an open problem to solve it with a computer. Numerous approaches to address this task have been proposed. The most promising techniques formulate the task as a numerical optimization problem. Unfortunately, the number of unknowns along with the nature of the objective function make the optimization problem extremely difficult to solve. This thesis investigates two approaches along with a coarsening scheme to solve the underlying numerical problem

Computational theories of structure-from-motion and stereo vision only specify the computation of three-dimensional surface information at points in the image at which the irradiance changes. Yet, the visual perception is clearly of complete surfaces, and this perception is consistent for different observers. Since mathematically the class of surfaces which could pass through the known boundary points provided by the stereo system is infinite and contains widely varying surfaces, the visual system must incorporate some additional constraints besides the known points in order to compute the complete surface. Using the image irradiance equation, we derive the surface consistency constraint, informally referred to as no news is good news. The constraint implies that the surface must agree with the information from stereo or motion correspondence, and not vary radically between these points. An explicit form of this surface consistency constraint is derived, by relating the probability of a zero-crossing in a region of the image to the variation in the local surface orientation of the surface, provided that the surface albedo and the illumination are roughly constant. The surface consistency constraint can be used to derive an algorithm for reconstructing the surface that "best" fits the surface information provided by stereo or motion correspondence.

The QoS Steiner Tree Problem asks for the most cost efficient way to multicast multimedia to a heterogeneous collection of users with different data consumption rates. We assume that the cost of using a link is not constant but rather depends on the maximum bandwidth routed through the link. Formally, given a graph with costs on the edges, a source node and a set of terminal nodes, each one with a bandwidth requirement, the goal is to find a Steiner tree containing the source, and the cheapest assignment of bandwidth to each of its edges so that each source-to-terminal path in the tree has bandwidth at least as large as the bandwidth required by the terminal. Our main contributions are: (1) New flow-based integer linear program formulation for the problem; (2) First implementation of 4.311 primal-dual constant factor approximation algorithm; (3) an extensive experimental study of the new heuristics and of several previously proposed algorithms.

We propose a family of search directions based on primal-dual entropy in the context of interior point methods for linear programming. This new family contains previously proposed search directions in the context of primal-dual entropy. We analyze the new family of search directions by studying their primal-dual affine-scaling and constant-gap centering components. We then design primal-dual interior-point algorithms by utilizing our search directions in a homogeneous and self-dual framework. We present iteration complexity analysis of our algorithms and provide the results of computational experiments on NETLIB problems.

We propose a family of search directions based on primal-dual entropy in the context of interior point methods for linear programming. This new family contains previously proposed search directions in the context of primal-dual entropy. We analyze the new family of search directions by studying their primal-dual affine-scaling and constant-gap centering components. We then design primal-dual interior-point algorithms by utilizing our search directions in a homogeneous and self-dual framework. We present iteration complexity analysis of our algorithms and provide the results of computational experiments on NETLIB problems.

This thesis is a computational study of recently developed algorithms which aim to overcome degeneracy in the simplex method. We study the following algorithms: the non-negative least squares algorithm, the least-squares primal-dual algorithm, the least-squares network flow algorithm, and the combined-objective least-squares algorithm. All of the four algorithms use least-squares measures to solve their subproblems, so they do not exhibit degeneracy. But they have never been efficiently implemented and thus their performance has also not been proved. In this research we implement these algorithms in an efficient manner and improve their performance compared to their preliminary results. For the non-negative least-squares algorithm, we develop the basis update technique and data structure that fit our purpose. In addition, we also develop a measure to help find a good ordering of columns and rows so that we have a sparse and concise representation of QR-factors. The least-squares primal-dual algorithm uses the non-negative least-squares problem as its subproblem, which minimizes infeasibility while satisfying dual feasibility and complementary slackness. The least-squares network flow algorithm is the least-squares primal-dual algorithm applied to min-cost network flow instances. The least-squares network flow algorithm can efficiently solve much bigger instances than the least-squares primal-dual algorithm. The combined-objective least-squares algorithm is the primal version of the least-squares primal-dual algorithm. Each subproblem tries to minimize true objective and infeasibility simultaneously so that optimality and primal feasibility can be obtained together. It uses a big-M to minimize the infeasibility. We developed the techniques to improve the convergence rates of each algorithm: the relaxation of complementary slackness condition, special pricing strategy, and dynamic-M value. Our computational results show that the least-squares primal-dual algorithm and the combined-objective least-squares algorithm perform better than the CPLEX Primal solver, but are slower than the CPLEX Dual solver. The least-squares network flow algorithm performs as fast as the CPLEX Network solver.

Ce travail de recherche explore les processus de liaisons conduisant à l’émergence des liens fraternels dans les groupes thérapeutiques et les groupes de formation. A partir d’une approche psychanalytique, nous cherchons à définir le fraternel en tenant compte des trois espaces intra-, inter- et trans- subjectifs. Les études menées au sujet des liens familiaux nous permettent de postuler que la fratrie peut servir de modèle pour décrire les processus groupaux par lesquels des liens fraternels se tissent entre des enfants qui ne sont pas familiers. Dans une première partie, les propositions théoriques exposées sont illustrées par différents objets culturels tels que des mythes et des contes. Dans une deuxième partie, nos hypothèses sont mises à l’épreuve des dispositifs de groupes de formation à l’université et d’un dispositif de groupe thérapeutique. Le traitement des observations à l’aide de « la méthode des quatre colonnes » permet d’explorer notre matériel clinique de recherche. D’une façon transitoire, nous avons vu apparaître quatre registres différents du processus de liaisons conduisant à la formation de liens fraternels. Ces registres sont organisés par des mécanismes inconscients. Ils mettent en jeu des fantasmes originaires et les défenses psychiques présidant une transition des registres archaïques vers un registre intermédiaire puis un registre fraternel. Dans une troisième partie, nos hypothèses sont discutées sur trois niveaux (culturel, théorique et clinique) et reprises pour définir les quatre registres des liens fraternels dans les différents dispositifs de groupe. / The presented research explores the processes of links leading to the emergence of fraternal bonds in therapeutic groups and training groups. From a psychoanalytic approach, we seek to place the issue in a fraternal definition which takes into account the intra-, inter- and trans- subjective space. Drawing on studies of family ties, we postulated that siblings can serve as a model for describing group processes by which fraternal links forged between children who are not familiar. In the first part, exposed theoretical propositions are first compared to the results of analyzes made upon different cultural objects such as myths and tales. In the second part, our hypotheses are tested by a setting of groups of university training and a therapeutic group. Treatment of observations using "the method of the four columns" allows the exploration of our clinical research material. On a transitional basis, we saw the emergence of four different registers of the process of connections leading to the formation of fraternal ties. These records are organized by unconscious mechanisms. These involve primal fantasies and psychic defenses presiding over a transition of archaic records towards an intermediate register and finally to a fraternal register.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

<p> Freud's Totem and Taboo was one of the more controversial additions to the literature of religious theory. The two major hypotheses of the work are the parallel between ontogenetic and phylogenetic evolution, and the primal horde parricide. The first hypothesis has rarely been taken seriously. The second, although never verified with anthropological evidence, has generated further hypotheses based upon its value as a symbolic representation rather than an actual occurrence. Paul Roazen has suggested that the primal horde parricide hypothesis possesses characteristics similar to those of most social contract theories. He posited, in light of this, that Totem and Taboo ought to be considered a kind of social contract, although it has never been thought of this way. </p> <p> The major school of philosophical thought which has continued to maintain interest in Totem and Taboo, long after the main anthropological assertions have been dispelled, is the French structuralist movement and its successors. Through the work of Levi-Strauss, carried on with theorists such as Lacan, Bataille, and Derrida, Totem and Taboo has maintained value as important work. The French structuralists have sustained a tradition that began with Rousseau of combining mathematical reasoning and linguistic theory together with anthropological speculation raised in Totem and Taboo. Thus in light of Roazen's hypothesis and the structuralist treatment of Totem and Taboo, together with Bryan Skyrms' s recent work on Rousseau and the mathematics of social contract theory, I posit that Totem and Taboo is comparable to Rousseau's Social Contract, in which human nature, politics, myth and mathematics merge. Implicitly Totem and Taboo contains a novel theory of the political development of society. </p> / Thesis / Doctor of Philosophy (PhD)