Consider the following system model y = Ax + e, where x is n-dimensional sparse signal, y is the measurement vector in a much lower dimension m, A is the measurement matrix and e is the error in our measurements. The Dantzig selector estimates x by solving the following optimization problem minimize || x ||₁ subject to || A'(Ax - y) ||∞ ≤ ε, (DS). This is a convex program and can be recast into a linear program and solved using any modern optimization method e.g., interior point methods. We propose a fast and efficient scheme for solving the Dantzig Selector (DS), which we call "Primal-Dual pursuit". This algorithm can be thought of as a "primal-dual homotopy" approach to solve the Dantzig selector (DS). It computes the solution to (DS) for a range of successively relaxed problems, by starting with a large artificial ε and moving towards the desired value. Our algorithm iteratively updates the primal and dual supports as ε reduces to the desired value, which gives final solution. The homotopy path solution of (DS) takes with varying ε is piecewise linear. At some critical values of ε in this path, either some new elements enter the support of the signal or some existing elements leave the support. We derive the optimality and feasibility conditions which are used to update the solutions at these critical points. We also present a detailed analysis of primal-dual pursuit for sparse signals in noiseless case. We show that if our signal is S-sparse, then we can find all its S elements in exactly S steps using about "S² log n" random measurements, with very high probability.

[pt] A indústria de transporte marítimo é essencial para o comércio internacional. No entanto, no despertar da crise financeira de 2008, essa indústria foi severamente atingida. Nessas ocasiões, empresas de transporte só são capazes de obter lucro se suas frotas forem roteadas de forma eficaz. Neste trabalho, nós estudamos uma classe de problemas de roteamento de navios relacionados ao Pickup and Delivery Problem with Time Windows. Para resolver esses problemas, nós introduzimos um método heurístico e um exato. O método heurístico é uma meta-heurística híbrida com uma vizinhança larga baseada em set partitioning, enquanto o método exato é um algoritmo de branch-and-price. Nós conduzimos experimentos em um conjunto de instâncias baseadas em rotas de navios reais. Os resultados obtidos mostram que nossos algoritmos superam as metodologias estado da arte. Em seguida, nós adaptamos o conjunto de instâncias para modelar um problema de roteamento de navios no qual a velocidade em cada segmento de rota é uma variável de decisão, e o consumo de combustível por unidade de tempo é uma função convexa da velocidade e carga do navio. A fim de resolver esse novo problema de roteamento de navios com otimização de velocidade, nós estendemos nossa meta-heurística para encontrar decisões de velocidade ótimas em toda avaliação de solução vizinha de uma busca local. Nossos experimentos demonstram que essa abordagem pode ser altamente rentável, e que requer apenas um aumento moderado de recursos computacionais. / [en] The shipping industry is essential for international trade. However, in the wake of the 2008 financial crisis, this industry was severely hit. In these times, transportation companies can only obtain profit if their fleet is routed effectively. In this work, we study a class of ship routing problems related to the Pickup and Delivery Problem with Time Windows. To solve these problems, we introduce a heuristic and an exact method. The heuristic method is a hybrid metaheuristic with a set-partitioning-based large neighborhood, while the exact method is a branch-and-price algorithm. We conduct experiments on a benchmark suite based on real-life shipping segments. The results obtained show that our algorithms largely outperform the state-of-the-art methodologies. Next, we adapt the benchmark suite to model a ship routing problem where the speed on each sailing leg is a decision variable, and fuel consumption per time unit is a convex function of the ship speed and payload. To solve this new ship routing problem with speed optimization, we extend our metaheuristic to find optimal speed decisions on every local search move evaluation. Our computational experiments demonstrate that such approach can be highly profitable, with only a moderate increase in computational effort.

La finesse de la résolution spectrale des images hyperspectrales en télédétection permet une analyse précise de la scène observée, mais leur résolution spatiale est limitée, et un pixel acquis par le capteur est souvent un mélange des contributions de différents matériaux. Le démélange spectral permet d'estimer les spectres des matériaux purs (endmembers) de la scène, et leurs abondances dans chaque pixel. Les endmembers sont souvent supposés être parfaitement représentés par un seul spectre, une hypothèse fausse en pratique, chaque matériau ayant une variabilité intra-classe non négligeable. Le but de cette thèse est de développer des algorithmes prenant mieux en compte ce phénomène. Nous effectuons le démélange localement, dans des régions bien choisies de l'image où les effets de la variabilité sont moindres, en éliminant automatiquement les endmembers non pertinents grâce à de la parcimonie collaborative. Dans une autre approche, nous raffinons l'estimation des abondances en utilisant la structure de groupe d'un dictionnaire d'endmembers extrait depuis les données. Ensuite, nous proposons un modèle de mélange linéaire étendu, basé sur des considérations physiques, qui modélise la variabilité spectrale par des facteurs d'échelle, et développons des algorithmes d'optimisation pour en estimer les paramètres. Ce modèle donne des résultats facilement interprétables et de meilleures performances que d'autres approches de la littérature. Nous étudions enfin deux applications de ce modèle pour confirmer sa pertinence. / The fine spectral resolution of hyperspectral remote sensing images allows an accurate analysis of the imaged scene, but due to their limited spatial resolution, a pixel acquired by the sensor is often a mixture of the contributions of several materials. Spectral unmixing aims at estimating the spectra of the pure materials (called endmembers) in the scene, and their abundances in each pixel. The endmembers are usually assumed to be perfectly represented by a single spectrum, which is wrong in practice since each material exhibits a significant intra-class variability. This thesis aims at designing unmixing algorithms to better handle this phenomenon. First, we perform the unmixing locally in well chosen regions of the image where variability effects are less important, and automatically discard wrongly estimated local endmembers using collaborative sparsity. In another approach, we refine the abundance estimation of the materials by taking into account the group structure of an image-derived endmember dictionary. Second, we introduce an extended linear mixing model, based on physical considerations, modeling spectral variability in the form of scaling factors, and develop optimization algorithms to estimate its parameters. This model provides easily interpretable results and outperforms other state-of-the-art approaches. We finally investigate two applications of this model to confirm its relevance.

L'analyse statique correcte d'un programme consiste à obtenir des propriétés vraies de toute exécution de ce programme. Celles-ci sont utiles pour démontrer des caractéristiques appréciables du logiciel, telles que l'absence de dépassement de capacité ou autre erreur à l'exécution quelle que soient les entrées du programme. Elles sont presque toujours établies à l'aide d'invariants inductifs : des propriétés vraies de l'état initial et telles que si elles sont vraies à une étape de calcul, alors elles restent vraies à l'étape suivante de la transition de calcul, donc sont toujours vraies par récurrence. L'interprétation abstraite est une approche traditionnelle de la recherche d'invariants numériques, que l'on peut exprimer comme une interprétation non-standard du programme dans un domaine abstrait choisi et ne tenant compte que de certaines propriétés intéressantes. Même dans un domaine aussi simple que les intervalles (un minorant et un majorant pour chaque variable), ce calcul ne converge pas nécessairement, et l'analyse doit recourir à des opérateurs d'élargissement pour forcer la convergence au détriment de la précision. Une autre approche, appelée itération de politique et inspirée par la théorie des jeux, garantit de trouver le plus fort invariant inductif dans le domaine abstrait choisi après un nombre fini d'itérations. Cependant, la description originale de cet algorithme souffrait de quelques faiblesses : elle se basait sur une conversion totale du programme en un système d'équations, sans intégration ni synergie avec les autres méthodes d'analyse. Notre nouvel algorithme est une forme locale de l'itération de politique, qui la replace dans l'itération de Kleene mais avec un opérateur d'élargissement spécial qui garantit d'obtenir le plus petit invariant inductif dans le domaine abstrait après un nombre fini de ses applications. L'itération de politique locale opère dans les domaines de contraintes linéaires données par patron, qui demandent de fixer d'avance la «forme» de l'invariant (p.ex. "x + 2y" pour obtenir "x + 2y <= 10" ). Notre seconde contribution théorique est le développement et la comparaison de plusieurs stratégies de synthèse de patrons, utilisées en conjonction avec l'itération locale de politiques. De plus, nous présentons une méthode pour générer des arbres d'accessibilité abstraite par interprétation abstraite, permettant la génération de traces de contre-exemples, et ensuite la génération de nouveaux patrons à partir d'interpolants de Craig. Notre troisième contribution concerne l'analyse interprocédurale de programmes, éventuellement récursifs. Nous proposons un algorithme qui génère pour chaque procédure un résumé, applicable à toute interprétation abstraite et notamment à l'itération de politique locale. Nous pouvons ainsi générer les invariants inductifs les plus forts dans le domaine pour un nombre fixé de résumés pour un programme récursif. Notre dernière contribution théorique est une méthode d'affaiblissement permettant de trouver des invariants inductifs, éventuellement disjonctifs, à partir de formules obtenues par exécution symbolique. Nous avons mis en œuvre toutes ces approches dans le système d'analyse statique CPAchecker, un logiciel libre, ce qui permet des communications et collaborations entre analyses. Nos techniques utilisent des résolveurs de satisfiabilité modulo théorie, capables, étant donné une formule de logique du premier ordre sur certaines théories, d'en donner un modèle ou de démontrer qu'aucun n'existe.Afin de simplifier les communications avec ces outils, nous présentons la bibliothèque JavaSMT, fournissant une interface générique. Cette bibliothèque a déjà démontré son utilité pour de nombreux chercheurs. / Static analysis concerns itself with deriving program properties which holduniversally for all program executions.Such properties are used for proving program properties (e.g. there neveroccurs an overflow or other runtime error regardless of a particular execution) and are almostinvariably established using inductive invariants: properties which holdfor the initial state and imply themselves under the program transition, and thushold universally due to induction.A traditional approach for finding numerical invariants is using abstractinterpretation, which can be seen as interpreting the program in the abstractdomain of choice, only tracking properties of interest.Yet even in the intervals abstract domain (upper and lower boundsfor each variable) such computation does not necessarily converge, and theanalysis has to resort to the use of widenings to enforceconvergence at the cost of precision.An alternative game-theoretic approach called policy iteration,guarantees to findthe least inductive invariant in the chosen abstract domain under the finitenumber of iterations.Yet the original description of the algorithm includes a number of drawbacks:it requires converting the entire program to an equation system,does not integrate with other approaches,and is unable to benefit from other analyses.Our new algorithm for running local policy iteration (LPI)instead formulates policy iteration as traditional Kleene iteration,with a widening operator that guarantees to return the least inductiveinvariant in the domain after finitely many applications.Local policy iteration runs in template linear constraint domains whichrequires setting in advance the ``shape'' of the derived invariant (e.g.$x + 2y$ for deriving $x + 2y leq 10$).Our second theoretical contribution involves development and comparison ofa number of different template synthesis strategies, when used in conjunctionwith LPI.Additionally, we present an approach for generating abstract reachabilitytrees using abstract interpretation,enabling the construction of counterexample traces,which in turns lets us generate new templates using Craig interpolants.In our third contribution we bring our attention to interprocedural andpotentially recursive programs.We develop an algorithm parameterizable with any abstract interpretation forsummary generation, and we study it's parameterization with LPI.The resulting approach is able to generate least inductive invariants in the domain for a fixed number of summaries for recursive programs.Our final theoretical contribution is a novel "formula slicing''method for finding potentially disjunctive inductive invariantsfrom program fragments obtained by symbolic execution.We implement all of these techniques in the open-source state-of-the-artCPAchecker program analysis framework, enabling communication and collaborationbetween different analyses.The techniques mentioned above rely onsatisfiability modulo theories solvers,which are capable ofgiving solutions tofirst-order formulas over certain theories or showingthat none exists.In order to simplify communication with such toolswe present the JavaSMT library, which provides a generic interface for suchcommunication.The library has shown itself to be a valuable tool, and is already used by manyresearchers.

[pt] A geração de malhas geomecânicas de reservatórios ainda é uma tarefa tediosa que consome muito tempo. Para acelerar este processo, soluções que reconstroem analiticamente a geometria do reservatório têm sido propostas, mas essas soluções não são as mais adequadas para modelagem de objetos naturais. Este trabalho propõe uma modelagem discreta para a geometria do reservatório, onde os vértices da malha são posicionados por meio da solução de um problema de otimização quadrático e convexo. O problema de otimização é modelado de forma a garantir que as malhas geomecânicas de saída sejam suaves e que ao mesmo tempo respeitem as restrições do reservatório e dos horizontes presentes. Além disso, a metodologia proposta permite uma implementação eficiente, paralelizável e de baixo consumo de memória. Casos de teste com milhões de variáveis são apresentados para validar essa abordagem. Finalmente, a metodologia proposta neste trabalho para malhas de geomecânica pode ser naturalmente estendida para a modelagem estrutural de sub-superfícies na interpretação sísmica e de restauração geológica. / [en] Geomechanical mesh generation of complex reservoirs remains a tedious task prone to errors. Recently proposed solutions based on analytical reconstruction of the sub-surfaces are not capable to represent all the geometric details of natural objects. This work proposes a discrete model where the mesh vertices are positioned based on a convex quadratic optimization process. The optimization problem seeks to guarantee smooth meshes that conform with prescribed constraints. The resulting mesh therefore respects, as far as possible, the finite volume mesh of the reservoir pay zone and the existing horizons. Finally, the proposed methodology for Geomechanical meshes can be easily extend to model sub-surfaces present in the structural interpretation and geological restauration.

In recent years, rules and regulations regarding fuel consumption of vehicles and the amount of emissions produced by them are becoming stricter. This has led the automotive industry to develop more advanced solutions to propel vehicles to meet the legal requirements. The Hybrid Electric Vehicle is one of the solutions that is becoming more popular in the automotive industry. It consists of an electrical driveline combined with a conventional powertrain, propelled by either a diesel or petrol engine. Two power sources create the possibility to choose when and how to use the power sources to propel the vehicle. The strategy that decides how this is done is referred to as an energy management strategy. Today most energy management strategies only try to reduce fuel consumption using models that describe the steady state behaviour of the engine. In other words, no reduction of emissions is achieved and all transient behaviour is considered negligible.  In this thesis, an energy management strategy incorporating engine dynamics to reduce fuel consumption and nitrogen oxide emissions have been designed. First, the models that describe how fuel consumption and nitrogen oxide emissions behave during transient engine operation are developed. Then, an energy management strategy is developed consisting of a model predictive controller that combines the equivalent consumption minimization strategy and convex optimization. Results indicate that by considering engine dynamics in the energy management strategy, both fuel consumption and nitrogen oxide emissions can be reduced. Furthermore, it is also shown that the major reduction in fuel consumption and nitrogen oxide emissions is achieved for short prediction horizons.

Dans ce travail, nous abordons les problèmes de l'analyse de la stabilité et de la synthèse de contrôleur pour une Equation aux Dérivées Partielles (EDP) parabolique linéaire de dimension 1. Ces problèmes sont résolus avec des méthodologies analogues au cadre des inégalités matricielles linéaires (LMI) pour les équations différentielles ordinaires (EDO). Nous développons une méthode pour EDP paraboliques dans laquelle nous testons la faisabilité de certaines LMIs utilisant la programmation semi-définie (SDP) pour construire des fonctions de Lyapunov quadratiques et des contrôleurs. Le cœur de notre démarche est la construction de fonctions de Lyapunov quadratiques paramétrées par les opérateurs définis positifs sur les espaces de Hilbert de dimension infinie. Contrairement aux matrices positives, il n'y a pas de méthode unique paramétrisant l'ensemble des opérateurs positifs sur un espace de Hilbert. Bien sûr, nous pouvons toujours paramétrer un sous-ensemble des opérateurs positifs en utilisant, par exemple, des scalaires positifs. Cependant, nous devons nous assurer que le paramétrage des opérateurs positifs ne doit pas être conservatif. Notre contribution est de construire une paramétrisation qui a seulement une petite quantité de conservatisme comme indiqué par nos résultats numériques. Nous utilisons des polynômes en somme des carrés (SOS) pour paramétrer l'ensemble des opérateurs positifs, linéaire et bornés sur les espaces de Hilbert. Comme son nom l'indique, un polynôme SOS est celui qui peut être représenté comme une somme de polynômes carrés. La propriété la plus importante d'un polynôme SOS est qu'il peut être représenté au moyen d'une matrice (semi-)définie positive. Cela implique que, même si le problème de polynôme (semi-)positif est NP-difficile, le problème de vérifier si polynôme est SOS (et donc (semi-)positif) peut être résolu en utilisant la SDP. Par conséquent, nous nous efforçons de construire des fonctions de Lyapunov quadratiques paramétrées par les opérateurs positifs. Ces opérateurs positifs sont à leur tour paramétrés par des polynômes SOS. Cette paramétrisation SOS nous permet de formuler le problème de faisabilité pour l'existence d'une fonction de Lyapunov quadratique comme un problème de faisabilité LMI. Le problème de la faisabilité LMI peut alors être adressé à l'aide de SDP. Dans la première partie de la thèse nous considérons analyse de stabilité et la synthèse de contrôleur aux frontières pour une large classe d'EDP paraboliques. Les EDP ont des coefficients de transport distribués spatialement. Ces EDP sont utilisés pour modéliser les processus de diffusion, de convection et de réaction de quantités physiques dans les milieux anisotropes. Nous considérons la synthèse de contrôleurs limite à la fois pour le cas de retour d'état et le cas de retour de sortie (à l'aide d'un observateur). Dans la deuxième partie de la thèse, nous concevons un contrôleur distribué pour la régulation du flux magnétique poloïdal dans un tokamak (procédé de fusion thermonucléaire par confinement magnétique). Tout d'abord, nous concevons un contrôleur régulant la pente des lignes de champ magnétique (le facteur de sécurité). La régulation du profil du facteur de sécurité est importante pour supprimer les instabilités MHD dans un tokamak. Ensuite, nous concevons un contrôleur maximisant la densité de courant bootstrap généré en interne. Une proportion accrue du courant bootstrap conduirait à une réduction des besoins énergétiques exogènes pour l'exploitation d'un tokamak. / In this work we address the problems of stability analysis and controller synthesis for one dimensional linear parabolic Partial Differential Equations (PDEs). To achieve the tasks of stability analysis and controller synthesis we develop methodologies akin to the Linear Matrix Inequality (LMI) framework for Ordinary Differential Equations (ODEs). We develop a method for parabolic PDEs wherein we test the feasibility of certain LMIs using SDP to construct quadratic Lyapunov functions and controllers. The core of our approach is the construction of quadratic Lyapunov functions parametrized by positive definite operators on infinite dimensional Hilbert spaces. Unlike positive matrices, there is no single method of parametrizing the set of all positive operators on a Hilbert space. Of course, we can always parametrize a subset of positive operators, using, for example, positive scalars. However, we must ensure that the parametrization of positive operators should not be conservative. Our contribution is constructing a parametrization which has only a small amount of conservatism as indicated by our numerical results. We use Sum-of-Squares (SOS) polynomials to parametrize the set of positive, linear and bounded operators on Hilbert spaces. As the name indicates, an SOS polynomial is one which can be represented as a sum of squared polynomials. The most important property of an SOS polynomial is that it can be represented using a positive (semi)-definite matrix. This implies that even though the problem of polynomial (semi)-positivity is NP-hard, the problem of checking if polynomial is SOS (and hence (semi)-positive) can be solved using SDP. Therefore, we aim to construct quadratic Lyapunov functions parametrized by positive operators. These positive operators are in turn parametrized by SOS polynomials. This parametrization using SOS allows us to cast the feasibility problem for the existence of a quadratic Lyapunov function as the feasibility problem of LMIs. The feasibility problem of LMIs can then be addressed using SDP. In the first part of the thesis we consider stability analysis and boundary controller synthesis for a large class of parabolic PDEs. The PDEs have spatially distributed coefficients. Such PDEs are used to model processes of diffusion, convection and reaction of physical quantities in anisotropic media. We consider boundary controller synthesis for both the state feedback case and the output feedback case (using and observer design). IN the second part of thesis we design distributed controllers for the regulation of poloidal magnetic flux in a tokamak (a thermonuclear fusion devise). First, we design the controllers to regulate the magnetic field line pitch (the safety factor). The regulation of the safety factor profile is important to suppress the magnetohydrodynamic instabilities in a tokamak. Then, we design controllers to maximize the internally generated bootstrap current density. An increased proportion of bootstrap current would lead to a reduction in the external energy requirements for the operation of a tokamak.

abstract: In this dissertation, we present a H-infinity based multivariable control design methodology that can be used to systematically address design specifications at distinct feedback loop-breaking points. It is well understood that for multivariable systems, obtaining good/acceptable closed loop properties at one loop-breaking point does not mean the same at another. This is especially true for multivariable systems that are ill-conditioned (having high condition number and/or relative gain array and/or scaled condition number). We analyze the tradeoffs involved in shaping closed loop properties at these distinct loop-breaking points and illustrate through examples the existence of pareto optimal points associated with them. Further, we study the limitations and tradeoffs associated with shaping the properties in the presence of right half plane poles/zeros, limited available bandwidth and peak time-domain constraints. To address the above tradeoffs, we present a methodology for designing multiobjective constrained H-infinity based controllers, called Generalized Mixed Sensitivity (GMS), to effectively and efficiently shape properties at distinct loop-breaking points. The methodology accommodates a broad class of convex frequency- and time-domain design specifications. This is accomplished by exploiting the Youla-Jabr-Bongiorno-Kucera parameterization that transforms the nonlinear problem in the controller to an affine one in the Youla et al. parameter. Basis parameters that result in efficient approximation (using lesser number of basis terms) of the infinite-dimensional parameter are studied. Three state-of-the-art subgradient-based non-differentiable constrained convex optimization solvers, namely Analytic Center Cutting Plane Method (ACCPM), Kelley's CPM and SolvOpt are implemented and compared. The above approach is used to design controllers for and tradeoff between several control properties of longitudinal dynamics of 3-DOF Hypersonic vehicle model -– one that is unstable, non-minimum phase and possesses significant coupling between channels. A hierarchical inner-outer loop control architecture is used to exploit additional feedback information in order to significantly help in making reasonable tradeoffs between properties at distinct loop-breaking points. The methodology is shown to generate very good designs –- designs that would be difficult to obtain without our presented methodology. Critical control tradeoffs associated are studied and compared with other design methods (e.g., classically motivated, standard mixed sensitivity) to further illustrate its power and transparency. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2018

In this doctoral thesis, we propose new iterative methods for solving a class of convex optimization problems. In general, we consider problems in which the objective function is composed of a finite sum of convex functions and the set of constraints is, at least, convex and closed. The iterative methods we propose are basically designed through the combination of incremental subgradient methods and string-averaging algorithms. Furthermore, in order to obtain methods able to solve optimization problems with many constraints (and possibly in high dimensions), generally given by convex functions, our analysis includes an operator that calculates approximate projections onto the feasible set, instead of the Euclidean projection. This feature is employed in the two methods we propose; one deterministic and the other stochastic. A convergence analysis is proposed for both methods and numerical experiments are performed in order to verify their applicability, especially in large scale problems. / Nesta tese de doutorado, propomos novos métodos iterativos para a solução de uma classe de problemas de otimização convexa. Em geral, consideramos problemas nos quais a função objetivo é composta por uma soma finita de funções convexas e o conjunto de restrições é, pelo menos, convexo e fechado. Os métodos iterativos que propomos são criados, basicamente, através da junção de métodos de subgradientes incrementais e do algoritmo de média das sequências. Além disso, visando obter métodos flexíveis para soluções de problemas de otimização com muitas restrições (e possivelmente em altas dimensões), dadas em geral por funções convexas, a nossa análise inclui um operador que calcula projeções aproximadas sobre o conjunto viável, no lugar da projeção Euclideana. Essa característica é empregada nos dois métodos que propomos; um determinístico e o outro estocástico. Uma análise de convergência é proposta para ambos os métodos e experimentos numéricos são realizados a fim de verificar a sua aplicabilidade, principalmente em problemas de grande escala.

Made available in DSpace on 2014-07-29T16:02:20Z (GMT). No. of bitstreams: 1 Dissertacao-Jose Henrique Salazar do Amaral.pdf: 346281 bytes, checksum: ed448001994e6dc5edb294a83390961a (MD5) Previous issue date: 2012-06-27 / This paper presents an analysis of convergence of the proximal point method for functions that satisfy the inequality of Lojasiewicz. / Neste trabalho é feita uma análise de convergência do Método do Ponto Proximal para funções não necessariamente convexas que satisfazem a desigualdade de &#321;ojasiewicz.