This dissertation addresses optimization of cubic polynomial problems. Heuristics for finding good quality feasible solutions and for improving on existing feasible solutions for a complex industrial problem, involving cubic and pooling constraints among other complicating constraints, have been developed. The heuristics for finding feasible solutions are developed based on linear approximations to the original problem that enforce a subset of the original problem constraints while it tries to provide good approximations for the remaining constraints, obtaining in this way nearly feasible solutions. The performance of these heuristics has been tested by using industrial case studies that are of appropriate size, scale and structure. Furthermore, the quality of the solutions can be quantified by comparing the obtained feasible solutions against upper bounds on the value of the problem. In order to obtain these upper bounds we have extended efficient existing techniques for bilinear problems for this class of cubic polynomial problems. Despite the efficiency of the upper bound techniques good upper bounds for the industrial case problem could not be computed efficiently within a reasonable time limit (one hour). We have applied the same techniques to subproblems with the same structure but about one fifth of the size and in this case, on average, the gap between the obtained solutions and the computed upper bounds is about 3%. In the remaining part of the thesis we look at global optimization of cubic polynomial problems with non-negative bounded variables via branch and bound. A theoretical study on the properties of convex underestimators for non-linear terms which are quadratic in one of the variables and linear on the other variable is presented. A new underestimator is introduced for this class of terms. The final part of the thesis describes the numerical testing of the previously mentioned underestimators together with approximations obtained by considering lifted approximations of the convex hull of the (x x y) terms. Two sets of instances are generated for this test and the descriptions of the procedures to generate the instances are detailed here. By analyzing the numerical results we can conclude that our proposed underestimator has the best behavior in the family of instances where the only non-linear terms present are of the form (x x y). Problems originating from least squares are much harder to solve than the other class of problems. In this class of problems the efficiency of linear programming solvers plays a big role and on average the methods that use these solvers perform better than the others.

The class of POP (Polynomial Optimization Problems) covers a wide rang of optimization problems such as 0 - 1 integer linear and quadratic programs, nonconvex quadratic programs and bilinear matrix inequalities. In this paper, we review some methods on solving the unconstraint case: minimize a real-valued polynomial p(x) : Rn → R, as well the constraint case: minimize p(x) on a semialgebraic set K, i.e., a set defined by polynomial equalities and inequalities. We also summarize some questions that we are currently considering. / Singapore-MIT Alliance (SMA)

Cette thèse présente une étude des systèmes dynamiques polynomiaux motivée à la fois par le grand spectre d'applications de cetteclasse (modèles de réactions chimiques, modèles de circuits électriques ainsi que les modèles biologiques) et par la difficulté (voire incapacité)de la résolution théorique de tels systèmes. Dans une première partie préliminaire, nous présentons les polynômes multi-variés et nous introduisons les notions de forme polaire d'un polynôme (floraison) et de polynômes de Bernstein qui seront d'un grand intérêt par la suite. Dans une deuxième partie, nous considérons le problème d'optimisation polynomial dit POP. Nous décrivons dans un premier temps les principales méthodes existantes permettant de résoudre ou d'approcher la solution d'un tel problème. Puis, nous présentons deux relaxations linéaires se basant respectivement sur le principe de floraison ainsi que les polynômes de Bernstein permettant d'approcher la valeur optimale du POP. La dernière partie de la thèse sera consacré aux applications de nos deux méthodes de relaxation dans le cadre des systèmes dynamiques polynomiaux. Une première application s'inscrit dans le cadre de l'analyse d'atteignabilité: en effet, on utilisera notre relaxation de Bernsteinpour pouvoir construire un algorithme permettant d'approximer les ensembles atteignables d'un système dynamique polynomial discrétisé. Une deuxième application sera la vérification et le calcul d'invariants pour un système dynamique polynomial. Une troisième application consiste à calculer un contrôleur et un invariant pour un système dynamique polynomial soumis à des perturbations. Dans le contexte de l'invariance, on utilisera la relaxation se basant sur le principe de floraison.Enfin, une dernière application sera d'exploiter les principales propriétés de la forme polaire pour pouvoir étudier des systèmes dynamiques polynomiaux dans des rectangles. / This thesis presents a study of polynomial dynamical systems motivated by both thewide spectrum of applications of this class (chemical reaction models, electrical modelsand biological models) and the difficulty (or inability) of theoretical resolutionof such systems.In a first preliminary part, we present multivariate polynomials and we introducethe notion of polar form of a polynomial (blossoming) and Bernstein polynomialswhich will be of great interest thereafter.In a second part, we consider the polynomial optimization problem said POP.We first describe existing methods allowing us to solve or approximate the solution5TABLE DES MATI`ERES 6of such problems. Then, we present two linear relaxations based respectively on theblossoming principle and the Bernstein polynomials allowing us to approximate theoptimal value of the POP.The last part of the thesis is devoted to applications of the two relaxation methodsin the context of polynomial dynamical systems. A first application is in thecontext of reachability analysis. In fact, we use our Bernstein relaxation in order tobuild an algorithm allowing us to approximate the reachable sets of a discretizedpolynomial dynamical system. A second application deals with the verification andthe computation of invariants for polynomial dynamical systems. A third applicationconsists in calculating a controller and an invariant for a polynomial dynamicalsystem subject to disturbances. For the invariance problem, we use the relaxationbased on the blossoming principle. Finally, the last application consists in exploitingthe main properties of the polar form in order to study polynomial dynamicalsystems in rectangles.

abstract: In this thesis, we focus on some of the NP-hard problems in control theory. Thanks to the converse Lyapunov theory, these problems can often be modeled as optimization over polynomials. To avoid the problem of intractability, we establish a trade off between accuracy and complexity. In particular, we develop a sequence of tractable optimization problems - in the form of Linear Programs (LPs) and/or Semi-Definite Programs (SDPs) - whose solutions converge to the exact solution of the NP-hard problem. However, the computational and memory complexity of these LPs and SDPs grow exponentially with the progress of the sequence - meaning that improving the accuracy of the solutions requires solving SDPs with tens of thousands of decision variables and constraints. Setting up and solving such problems is a significant challenge. The existing optimization algorithms and software are only designed to use desktop computers or small cluster computers - machines which do not have sufficient memory for solving such large SDPs. Moreover, the speed-up of these algorithms does not scale beyond dozens of processors. This in fact is the reason we seek parallel algorithms for setting-up and solving large SDPs on large cluster- and/or super-computers. We propose parallel algorithms for stability analysis of two classes of systems: 1) Linear systems with a large number of uncertain parameters; 2) Nonlinear systems defined by polynomial vector fields. First, we develop a distributed parallel algorithm which applies Polya's and/or Handelman's theorems to some variants of parameter-dependent Lyapunov inequalities with parameters defined over the standard simplex. The result is a sequence of SDPs which possess a block-diagonal structure. We then develop a parallel SDP solver which exploits this structure in order to map the computation, memory and communication to a distributed parallel environment. Numerical tests on a supercomputer demonstrate the ability of the algorithm to efficiently utilize hundreds and potentially thousands of processors, and analyze systems with 100+ dimensional state-space. Furthermore, we extend our algorithms to analyze robust stability over more complicated geometries such as hypercubes and arbitrary convex polytopes. Our algorithms can be readily extended to address a wide variety of problems in control such as Hinfinity synthesis for systems with parametric uncertainty and computing control Lyapunov functions. / Dissertation/Thesis / Doctoral Dissertation Mechanical Engineering 2016

abstract: Increasing interest in individualized treatment strategies for prevention and treatment of health disorders has created a new application domain for dynamic modeling and control. Standard population-level clinical trials, while useful, are not the most suitable vehicle for understanding the dynamics of dosage changes to patient response. A secondary analysis of intensive longitudinal data from a naltrexone intervention for fibromyalgia examined in this dissertation shows the promise of system identification and control. This includes datacentric identification methods such as Model-on-Demand, which are attractive techniques for estimating nonlinear dynamical systems from noisy data. These methods rely on generating a local function approximation using a database of regressors at the current operating point, with this process repeated at every new operating condition. This dissertation examines generating input signals for data-centric system identification by developing a novel framework of geometric distribution of regressors and time-indexed output points, in the finite dimensional space, to generate sufficient support for the estimator. The input signals are generated while imposing “patient-friendly” constraints on the design as a means to operationalize single-subject clinical trials. These optimization-based problem formulations are examined for linear time-invariant systems and block-structured Hammerstein systems, and the results are contrasted with alternative designs based on Weyl's criterion. Numerical solution to the resulting nonconvex optimization problems is proposed through semidefinite programming approaches for polynomial optimization and nonlinear programming methods. It is shown that useful bounds on the objective function can be calculated through relaxation procedures, and that the data-centric formulations are amenable to sparse polynomial optimization. In addition, input design formulations are formulated for achieving a desired output and specified input spectrum. Numerical examples illustrate the benefits of the input signal design formulations including an example of a hypothetical clinical trial using the drug gabapentin. In the final part of the dissertation, the mixed logical dynamical framework for hybrid model predictive control is extended to incorporate a switching time strategy, where decisions are made at some integer multiple of the sample time, and manipulation of only one input at a given sample time among multiple inputs. These are considerations important for clinical use of the algorithm. / Dissertation/Thesis / Ph.D. Electrical Engineering 2014

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第22588号 / 情博第725号 / 新制||情||124(附属図書館) / 京都大学大学院情報学研究科通信情報システム専攻 / (主査)教授 湊 真一, 教授 五十嵐 淳, 教授 山本 章博 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

L’objectif général de cette thèse est d’appliquer une méthode d’optimisation polynomiale basée sur la théorie des moments à certains problèmes de vision artificielle. Ces problèmes sont en général non convexes et classiquement résolus à l’aide de méthodes d’optimisation locales Ces techniques ne convergent généralement pas vers le minimum global et nécessitent de fournir une estimée initiale proche de la solution exacte. Les méthodes d’optimisation globale permettent d’éviter ces inconvénients. L’optimisation polynomiale basée sur la théorie des moments présente en outre l’avantage de prendre en compte des contraintes. Dans cette thèse nous étendrons cette méthode aux problèmes de minimisation d’une somme d’un grand nombre de fractions rationnelles. De plus, sous certaines hypothèses de "faible couplage" ou de "parcimonie" des variables du problème, nous montrerons qu’il est possible de considérer un nombre important de variables tout en conservant des temps de calcul raisonnables. Enfin nous appliquerons les méthodes proposées aux problèmes de vision par ordinateur suivants : minimisation des distorsions projectives induites par le processus de rectification d’images, estimation de la matrice fondamentale, reconstruction 3D multi-vues avec et sans distorsions radiales. / The overall objective of this thesis is to apply a polynomial optimization method, based on moments theory, on some vision problems. These problems are often nonconvex and they are classically solved using local optimization methods. Without additional hypothesis, these techniques don’t converge to the global minimum and need to provide an initial estimate close to the exact solution. Global optimization methods overcome this drawback. Moreover, the polynomial optimization based on moments theory could take into account particular constraints. In this thesis, we extend this method to the problems of minimizing a sum of many rational functions. In addition, under particular assumptions of "sparsity", we show that it is possible to deal with a large number of variables while maintaining reasonable computation times. Finally, we apply these methods to particular computer vision problems: minimization of projective distortions due to image rectification process, Fundamental matrix estimation, and multi-view 3D reconstruction with and without radial distortions.

Le but de cette thèse est de calculer l'optimum d'un polynôme sur un ensemble semi-algébrique et les points où cet optimum est atteint. Pour atteindre cet objectif, nous combinons des méthodes de base de bord avec la hiérarchie de relaxation convexe de Lasserre afin de réduire la taille des matrices de moments dans les problèmes de programmation semi-définie positive (SDP). Afin de vérifier si le minimum est atteint, nous apportons un nouveau critère pour vérifier l'extension plate de Curto Fialkow utilisant des bases orthogonales. En combinant ces nouveaux résultats, nous fournissons un nouvel algorithme qui calcule l'optimum et les points minimiseurs. Nous décrivons plusieurs expérimentations et des applications dans différents domaines qui prouvent la performance de l'algorithme. Au niveau théorique nous prouvons aussi la convergence finie d'une hiérarchie SDP construite à partir d'un idéal de Karush-Kuhn-Tucker et ses conséquences dans des cas particuliers. Nous étudions aussi le cas particulier où les minimiseurs ne sont pas des points de KKT en utilisant la variété de Fritz-John. / The objective of this thesis is to compute the optimum of a polynomial on a closed basic semialgebraic set and the points where this optimum is reached. To achieve this goal we combine border basis method with Lasserre's hierarchy in order to reduce the size of the moment matrices in the SemiDefinite Programming (SDP) problems. In order to verify if the minimum is reached we describe a new criterion to verify the flat extension condition using border basis. Combining these new results we provide a new algorithm which computes the optimum and the minimizers points. We show several experimentations and some applications in different domains which prove the perfomance of the algorithm. Theorethically we also prove the finite convergence of a SDP hierarchie contructed from a Karush-Kuhn-Tucker ideal and its consequences in particular cases. We also solve the particular case where the minimizers are not KKT points using Fritz-John Variety.

In this work, we advance the understanding of the fundamental limits of computation for binary polynomial optimization (BPO), which is the problem of maximizing a given polynomial function over all binary points. In our main result we provide a novel class of BPO that can be solved efficiently both from a theoretical and computational perspective. In fact, we give a strongly polynomial-time algorithm for instances whose corresponding hypergraph is β-acyclic. We note that the β-acyclicity assumption is natural in several applications including relational database schemes and the lifted multicut problem on trees. Due to the novelty of our proving technique, we obtain an algorithm which is interesting also from a practical viewpoint. This is because our algorithm is very simple to implement and the running time is a polynomial of very low degree in the number of nodes and edges of the hypergraph. Our result completely settles the computational complexity of BPO over acyclic hypergraphs, since the problem is NP-hard on α-acyclic instances.Our algorithm can also be applied to any general BPO problem that contains β-cycles. For these problems, the algorithm returns a smaller instance together with a rule to extend any optimal solution of the smaller instance to an optimal solution of the original instance.

L’objectif de cette thèse porte sur des recherches théoriques et algorithmiques d’optimisation locale et globale via les techniques de programmation DC & DCA, Séparation et Evaluation (SE) ainsi que les techniques de relaxation DC/SDP, pour résoudre plusieurs types de problèmes d’optimisation non convexe (notamment en Optimisation Combinatoire et Optimisation Polynomiale). La thèse comporte quatre parties :La première partie présente les outils fondamentaux et les techniques essentielles en programmation DC & l’Algorithme DC (DCA), ainsi que les techniques de relaxation SDP, et les méthodes de séparation et évaluation (SE).Dans la deuxième partie, nous nous intéressons à la résolution de problèmes de programmation quadratique et linéaire mixte en variables entières. Nous proposons de nouvelles approches locales et globales basées sur DCA, SE et SDP. L’implémentation de logiciel et des simulations numériques sont aussi étudiées.La troisième partie explore des approches de la programmation DC & DCA en les combinant aux techniques SE et SDP pour la résolution locale et globale de programmes polynomiaux. Le programme polynomial avec des fonctions polynomiales homogènes et son application à la gestion de portefeuille avec moments d’ordre supérieur en optimisation financière ont été discutés de manière approfondie dans cette partie.Enfin, nous étudions dans la dernière partie un programme d’optimisation sous contraintes de type matrices semi-définies via nos approches de la programmation DC. Nous nous consacrons à la résolution du problème de réalisabilité des contraintes BMI et QMI en contrôle optimal.L’ensemble de ces travaux a été implémenté avec MATLAB, C/C++ ... nous permettant de confirmer l’utilisation pratique et d’enrichir nos travaux de recherche. / The main objective of this thesis focuses on theoretical and algorithmic researches of local and global optimization techniques to DC programming & DCA with Branch and Bound (B&B) and the DC/SDP relaxation techniques to solve several types of non-convex optimization problems (including Combinatorial Optimization and Polynomial Optimization). This thesis is divided into four parts :We present in the first part some fondamental theorems and essential techniques in DC programming & DC Algorithm (DCA), the SDP Relaxation techniques, as well as the Branch and Bound methods (B&B).In the second part, we are interested in solving mixed integer quadratic and linear programs. We propose new local and global approaches based on DCA, B&B and SDP. The implementation of software and numerical simulations have also been investigated.The third part explores the DC programming approaches & DCA combined with a B&B technique and SDP for locally and globally solving a class of polynomial programming. The polynomial program with homogeneous polynomial functionsand its application to portfolio selection problem involving higher order moments in financial optimization have been deeply studied in this part.Finally, in the last part, we present our research on optimization problems under constraints of semi-definite matrices via our DC programming approaches. This part is dedicated to the resolution of the BMI and QMI feasibility problems in the field of optimal control.All these proposed methods have been implemented with MATLAB, C++ etc., that allowing us to confirm the practical use and enrich our research works.