<p>Posmatra se problem optimizacije bez ograničenja. Za re&scaron;avanje<br />problema&nbsp; optimizacije bez ograničenja postoji mno&scaron;tvo raznovrsnih<br />metoda. Istraživanje ovde motivisano je potrebom za metodama koje<br />će brzo konvergirati.<br />Cilj je sistematizacija poznatih rezultata, kao i teorijska i numerička<br />analiza mogućnosti uvođenja parametra u gradijentne metode.<br />Najpre se razmatra problem minimizacije konveksne funkcije vi&scaron;e<br />promenljivih.<br />Problem minimizacije konveksne funkcije vi&scaron;e promenljivih ovde se<br />re&scaron;ava bez izračunavanja matrice hesijana, &scaron;to je naročito aktuelno za<br />sisteme velikih dimenzija, kao i za probleme optimizacije kod kojih<br />ne raspolažemo ni tačnom vredno&scaron;ću funkcije cilja, ni tačnom<br />vredno&scaron;ću gradijenta. Deo motivacije za istraživanjem ovde leži i u<br />postojanju problema kod kojih je funkcija cilja rezultat simulacija.<br />Numerički rezultati, predstavljeni u Glavi 6, pokazuju da uvođenje<br />izvesnog parametra može biti korisno, odnosno, dovodi do ubrzanja<br />određenog metoda optimizacije.<br />Takođe se predstavlja jedan novi hibridni metod konjugovanog<br />gradijenta, kod koga je parametar konjugovanog gradijenta<br />konveksna kombinacija dva poznata parametra konjugovanog<br />gradijenta.<br />U prvoj glavi opisuje se motivacija kao i osnovni pojmovi potrebni za<br />praćenje preostalih glava.<br />U drugoj glavi daje se pregled nekih gradijentnih metoda prvog i<br />drugog reda.<br />Četvrta glava sadrži pregled osnovnih pojmova i nekih rezultata<br />vezanih za metode konjugovanih gradijenata.<br />Pomenute glave su tu radi pregleda nekih poznatih rezultata, dok se<br />originalni doprinos predstavlja u trećoj, petoj i &scaron;estoj glavi.<br />U trećoj glavi se opisuje izvesna modifikacija određenog metoda u<br />kome se koristi multiplikativni parametar, izabran na slučajan način.<br />Dokazuje se linearna konvergencija tako formiranog novog metoda.<br />Peta glava sadrži originalne rezultate koji se odnose na metode<br />konjugovanih gradijenata. Naime, u ovoj glavi predstavlja se novi<br />hibridni metod konjugovanih gradijenata, koji je konveksna<br />kombinacija dva poznata metoda konjugovanih gradijenata.<br />U &scaron;estoj glavi se daju rezultati numeričkih eksperimenata, izvr&scaron;enih<br />na&nbsp; izvesnom skupu test funkcija, koji se odnose na metode iz treće i<br />pete glave. Implementacija svih razmatranih algoritama rađena je u<br />paketu MATHEMATICA. Kriterijum upoređivanja je vreme rada<br />centralne procesorske jedinice.6</p> / <p>The problem under consideration is an unconstrained optimization<br />problem. There are many different methods made in aim to solve the<br />optimization problems.&nbsp; The investigation made here is motivated by<br />the fact that the methods which converge fast are necessary.<br />The main goal is the systematization of some known results and also<br />theoretical and numerical analysis of the possibilities to int roduce<br />some parameters within gradient methods.<br />Firstly, the minimization problem is considered, where the objective<br />function is a convex, multivar iable function. This problem is solved<br />here without the calculation of Hessian, and such solution is very<br />important, for example, when the&nbsp; big dimension systems are solved,<br />and also for solving optimization problems with unknown values of<br />the objective function and its gradient. Partially, this investigation is<br />motivated by the existence of problems where the objective function<br />is the result of simulations.<br />Numerical results, presented in&nbsp; Chapter&nbsp; 6, show that the introduction<br />of a parameter is useful, i.e., such introduction results by the<br />acceleration of the known optimization method.<br />Further, one new hybrid conjugate gradient method is presented, in<br />which the conjugate gradient parameter is a convex combination of<br />two known conjugate gradient parameters.<br />In the first chapter, there is motivation and also the basic co ncepts<br />which are necessary for the other chapters.<br />The second chapter contains the survey of some first order and<br />second order gradient methods.<br />The fourth chapter contains the survey of some basic concepts and<br />results corresponding to conjugate gradient methods.<br />The first, the second and the fourth&nbsp; chapters are here to help in<br />considering of some known results, and the original results are<br />presented in the chapters 3,5 and 6.<br />In the third chapter, a modification of one unco nstrained optimization<br />method is presented, in which the randomly chosen multiplicative<br />parameter is used. Also, the linear convergence of such modification<br />is proved.<br />The fifth chapter contains the original results, corresponding to<br />conjugate gradient methods. Namely, one new hybrid conjugate<br />gradient method is presented, and this&nbsp; method is the convex<br />combination of two known conjugate gradient methods.<br />The sixth chapter consists of the numerical results, performed on a set<br />of test functions, corresponding to methods in the chapters 3 and 5.<br />Implementation of all considered algorithms is made in Mathematica.<br />The comparison criterion is CPU time.</p> / <p>The problem under consideration is an unconstrained optimization<br />problem. There are many different methods made in aim to solve the<br />optimization problems.&nbsp; The investigation made here is motivated by<br />the fact that the methods which converge fast are necessary.<br />The main goal is the systematization of some known results and also<br />theoretical and numerical analysis of the possibilities to int roduce<br />some parameters within gradient methods.<br />Firstly, the minimization problem is considered, where the objective<br />function is a convex, multivar iable function. This problem is solved<br />here without the calculation of Hessian, and such solution is very<br />important, for example, when the&nbsp; big dimension systems are solved,<br />and also for solving optimization problems with unknown values of<br />the objective function and its gradient. Partially, this investigation is<br />motivated by the existence of problems where the objective function<br />is the result of simulations.<br />Numerical results, presented in&nbsp; Chapter&nbsp; 6, show that the introduction<br />of a parameter is useful, i.e., such introduction results by the<br />acceleration of the known optimization method.<br />Further, one new hybrid conjugate gradient method is presented, in<br />which the conjugate gradient parameter is a convex combination of<br />two known conjugate gradient parameters.<br />In the first chapter, there is motivation and also the basic co ncepts<br />which are necessary for the other chapters.<br />Key&nbsp; Words Documentation&nbsp; 97<br />The second chapter contains the survey of some first order and<br />second order gradient methods.<br />The fourth chapter contains the survey of some basic concepts and<br />results corresponding to conjugate gradient methods.<br />The first, the second and the fourth&nbsp; chapters are here to help in<br />considering of some known results, and the original results are<br />presented in the chapters 3,5 and 6.<br />In the third chapter, a modification of one unco nstrained optimization<br />method is presented, in which the randomly chosen multiplicative<br />parameter is used. Also, the linear convergence of such modification<br />is proved.<br />The fifth chapter contains the original results, corresponding to<br />conjugate gradient methods. Namely, one new hybrid conjugate<br />gradient method is presented, and this&nbsp; method is the convex<br />combination of two known conjugate gradient methods.<br />The sixth chapter consists of the numerical results, performed on a set<br />of test functions, corresponding to methods in the chapters 3 and 5.<br />Implementation of all considered algorithms is made in Mathematica.<br />The comparison criterion is CPU time</p>

Grande parte dos componentes mecânicos e estruturas são solicitados por carregamentos que variam com o tempo e frequentemente falham por fadiga. Neste sentido, é indubitável que o modo de falha por fadiga seja considerado no projeto mecânico de componentes, equipamentos e estruturas sujeitas a carregamentos cíclicos. Os livros de projetos de máquinas ainda são os mais utilizados na indústria como referência teórica e prática ao dimensionamento contra a fadiga de produtos. Entretanto, muitos deles ainda não incluem as últimas descobertas e metodologias mais modernas para o cálculo de durabilidade de estruturas. Adicionalmente, de uma maneira geral, grande parte dos livros especializados em fadiga também não trazem informações detalhadas sobre a previsão de vida em fadiga sob a ótica do projeto mecânico, como a análise utilizando critérios de Fadiga Multiaxial e a análise de fadiga baseada em Elementos Finitos (FE-Based Fatigue Analysis). Baseado neste cenário, este trabalho tem o objetivo de propor um procedimento para avaliar a vida em fadiga de componentes e estruturas reunindo os métodos mais recentes utilizados nesta área. Dentre os vários assuntos incluídos no procedimento proposto, destacam-se: as importantes contribuições propostas pelo Conselho Alemão de Pesquisa em Engenharia (FKM-Guideline); a utilização de Análise por Elementos Finitos (FEA) na previsão de vida em fadiga; o cálculo do fator de tensão média utilizando pseudo tensões provenientes de FEA; a contabilização do efeito de entalhe em componentes com geometria complexa utilizando o Método do Gradiente de Tensão Relativo em conjunto com FEA, que pode ser aplicado tanto em carregamento uniaxial quanto em carregamento multiaxial; a contabilização do dano por fadiga em carregamento multiaxial de amplitude variável; a densidade da malha de elementos finitos adequada para utilizar em fadiga computacional; e a aplicação da teoria e dos critérios de Fadiga Multiaxial, principalmente em FE-Based Fatigue Analyses, cuja utilização é imprescindível em estruturas sujeitas a tensões cíclicas em mais de uma direção (x,y,z). / Most of mechanical components and structures are subjected to time varying loading and therefore often present fatigue failure. Therefore, it is essential to consider the fatigue failure mode in the project of components, machines and structures under cyclic loading. Design of Machine Elements books are still the most used in industry as theoretical and practical reference for designing products against fatigue. However, many of them still do not include the latest findings and methodologies used in fatigue life assessment of structures. Additionally, overall, most of the specialized fatigue books also do not include detailed information about fatigue life assessment in a mechanical project view, as the fatigue analysis using Multiaxial Fatigue criteria and the fatigue life prediction using the Finite Element Method (FE-Based Fatigue Analysis). Based on this fact, this thesis proposes a procedure for predicting component and structures fatigue life, gathering together the most recent methods used in the fatigue area. Among the several subjects included in this procedure, we can highlight: the important contributions of the German Engineering Research Council (FKM-Guideline); the use of Finite Element Analysis (FEA) in the fatigue life assessment; the calculation of the mean stress factor using the pseudo stresses from FEA; the computation of the notch eect in geometrically complex components using the Relative Stress Gradient Method in conjunction with FEA, method which can be applied both in uniaxial loading and multiaxial loading; the estimation of the fatigue damage in structures under variable amplitude multiaxial fatigue loading; the selection of an adequate Finite Element mesh density to use in computational fatigue; and the aplication of the Multiaxial Fatigue theory and criteria, specially in FE-Based Fatigue Analyses, of which use is essential in structures under ciclic stresses in 2 or 3 directions (x,y,z).

Este trabalho apresenta uma nova abordagem para a modelagem e resolução de problemas de fluxo de carga em sistemas elétricos de potência. O modelo proposto é formado simultaneamente pelo conjunto de equações não lineares que representam as restrições de carga do problema e por restrições de complementaridade associadas com as restrições de operação da rede, as quais propiciam o controle implícito das tensões nas barras com controle de geração. Também é proposta uma técnica para a obtenção dos valores discretos dos taps de tranformadores, de maneira que o ajuste dessas variáveis possa ser realizado em passos discretos. A metodologia desenvolvida consiste em tratar o sistema misto de equações e inequações não lineares como um problema de factibilidade não linear e transformá-lo em um problema de mínimos quadrados não lineares, o qual é resolvido por uma sequência de subproblemas linearizados dentro de uma região de confiança. Para a obtenção de soluções aproximadas desse subproblema foi adotado o método do gradiente conjugado de Steihaug, combinando estratégias de região de confiança e filtros multidimensionais para analisar a qualidade das soluções fornecidas. Foram realizados testes numéricos com os sistemas de 14, 30, 57, 118 e 300 barras do IEEE, e com um sistema brasileiro equivalente CESP 53 barras, os quais indicaram boa flexibilidade e robustez do método proposto. / This work presents a new approach to the load flow problem in electrical power systems and develops a methodology for its resolution. The proposed model is simultaneously composed by nonlinear equations and inequations which represent the load and operational restrictions of the system, where a set of complementarity constraints model the relationship between voltage and reactive power generation in controled buses. It is also proposed a new technique to obtaining a discrete solution for the transformer taps, allowing their discrete adjustment. The method developed treats the mixed system of equations and inequations of the load flow problem as a nonlinear feasibility problem and converts it in a nonlinear least squares problem, which is solved by minimizing a sequence of linearized subproblems, whitin a trust region. To obtain approximate solutions at every iteration, we use the Steihaug conjugate gradient method, combining trust region and multidimensional filters techniques to analyse the quality of the provided solution. Numerical results using 14, 30, 57, 118 and 300-bus IEEE power systems, and a real brazilian equivalent system CESP 53-bus, indicate the flexibility and robustness of the proposed method.

Este trabalho apresenta uma nova abordagem para a modelagem e resolução de problemas de fluxo de carga em sistemas elétricos de potência. O modelo proposto é formado simultaneamente pelo conjunto de equações não lineares que representam as restrições de carga do problema e por restrições de complementaridade associadas com as restrições de operação da rede, as quais propiciam o controle implícito das tensões nas barras com controle de geração. Também é proposta uma técnica para a obtenção dos valores discretos dos taps de tranformadores, de maneira que o ajuste dessas variáveis possa ser realizado em passos discretos. A metodologia desenvolvida consiste em tratar o sistema misto de equações e inequações não lineares como um problema de factibilidade não linear e transformá-lo em um problema de mínimos quadrados não lineares, o qual é resolvido por uma sequência de subproblemas linearizados dentro de uma região de confiança. Para a obtenção de soluções aproximadas desse subproblema foi adotado o método do gradiente conjugado de Steihaug, combinando estratégias de região de confiança e filtros multidimensionais para analisar a qualidade das soluções fornecidas. Foram realizados testes numéricos com os sistemas de 14, 30, 57, 118 e 300 barras do IEEE, e com um sistema brasileiro equivalente CESP 53 barras, os quais indicaram boa flexibilidade e robustez do método proposto. / This work presents a new approach to the load flow problem in electrical power systems and develops a methodology for its resolution. The proposed model is simultaneously composed by nonlinear equations and inequations which represent the load and operational restrictions of the system, where a set of complementarity constraints model the relationship between voltage and reactive power generation in controled buses. It is also proposed a new technique to obtaining a discrete solution for the transformer taps, allowing their discrete adjustment. The method developed treats the mixed system of equations and inequations of the load flow problem as a nonlinear feasibility problem and converts it in a nonlinear least squares problem, which is solved by minimizing a sequence of linearized subproblems, whitin a trust region. To obtain approximate solutions at every iteration, we use the Steihaug conjugate gradient method, combining trust region and multidimensional filters techniques to analyse the quality of the provided solution. Numerical results using 14, 30, 57, 118 and 300-bus IEEE power systems, and a real brazilian equivalent system CESP 53-bus, indicate the flexibility and robustness of the proposed method.

Η χρήση επαναληπτικών τεχνικών προσαρμοστικής ισοστάθμισης διαύλου αποτελεί μια σχετικά πρόσφατη και πολλά υποσχόμενη μέθοδο αντιμετώπισης του φαινομένου της διασυμβολικής παρεμβολής που εισάγεται από το κανάλι λόγω του φαινομένου της πολυδιόδευσης. Ο αλγόριθμος που έχει επικρατήσει στις περισσότερες προσαρμοστικές εφαρμογές είναι ο ελαχίστων μέσων τετραγώνων (LMS). Διακρίνεται για την απλότητά του, έχει όμως φτωχές ιδιότητες σύγκλισης. Η μέθοδος των αναδρομικών ελαχίστων τετραγώνων (RLS) είναι επίσης αρκετά διαδεδομένη και κατέχει υπερέχουσες ιδιότητες σύγκλισης. Ωστόσο παρουσιάζει μεγάλη υπολογιστική πολυπλοκότητα και αυξημένες απαιτήσεις σε μνήμη. Στα πλαίσια της εργασίας αυτής εγίνε μια προσπάθεια ανάλυσης των τεχνικών που βασίζονται στη μέθοδο των συζυγών παραγώγων (Conjugate Gradient), χρησιμοποιούνται σε προβλήματα προσαρμοστικού φιλτραρίσματος και πιο ειδικά στο πρόβλημα της προσαρμοστικής ισοστάθμισης διαύλου. Οι τεχνικές αυτές επεξεργάζονται τα δεδομένα και ανά μπλοκ. Είναι ικανές να παρέχουν ιδιότητες σύγκλισης συγκρίσιμες με αυτές της (RLS) μεθόδου, εισάγοντας υπολογιστική πολυπλοκότητα ενδιάμεσων απαιτήσεων μεταξύ των μεθόδων LMS και RLS χωρίς να παρουσιάζουν προβλήματα αριθμητικής ευστάθειας. / The use of iteration methods for adaptive equalization has received considerable attention during the past several decades. The Least Mean Squares (LMS) method, which has found widespread use owing to its simplicity, has poor convergence properties. The Recursive Least Squares (RLS) method possess superior convergence properties, but it is computationally intensive and has high storage requirements for matrix manipulations. In this MSc thesis the technique of conjugate gradients is applied for the adaptive filtering problem. Conjugate gradient algorithms for adaptive filtering applications suitable for efficient implementation has been developed and has been applied for the design of an adaptive transversal equalizer. Low cost block algorithms using the preconditioned conjugate gradient method are also discussed. The algorithms are capable of providing convergence comparable to RLS schemes at a computational complexity between the LMS and the RLS methods and does not suffer from any known instability problems.

There are several algorithms for solving the linear system of equations that arise from the finite element method with linear or near-linear computational complexity. One way is to find an approximation of the stiffness matrix that is such that it can be used in a preconditioned conjugate residual method, that is, a preconditioner to the stiffness matrix. We have studied two preconditioners for the conjugate residual method, both based on writing the stiffness matrix in block form, factorising it and then approximating the Schur complement block to get a preconditioner. We have studied the stationary reaction-diffusion-advection equation in two dimensions. The mesh is refined adaptively, giving a hierarchy of meshes. In the first method the Schur complement is approximated by the stiffness matrix at one coarser level of the mesh, in the second method it is approximated as the assembly of local Schur complements corresponding to macro triangles. For two levels the theoretical bound of the condition number is 1/(1-C²) for either method, where C is the Cauchy-Bunyakovsky-Schwarz constant. For multiple levels there is less theory. For the first method it is known that the condition number of the preconditioned stiffness matrix is O(l²), where l is the number of levels of the preconditioner, or, equivalently, the number mesh refinements. For the second method the asymptotic behaviour is not known theoretically. In neither case is the dependency of the condition number of C known. We have tested both methods on several problems and found the first method to always give a better condition number, except for very few levels. For all tested problems, using the first method it seems that the condition number is O(l), in fact it is typically not larger than Cl. For the second method the growth seems to be superlinear.

Made available in DSpace on 2014-07-29T16:02:19Z (GMT). No. of bitstreams: 1 Dissertacao Milton Gabriel Garcia dos Santos.pdf: 405990 bytes, checksum: b1b10db3be6011cbbae70bc35ed87950 (MD5) Previous issue date: 2011-10-27 / This work we study the convergence properties of the Gradient Method Designed and Descent Method for Multi-objective optimization. At first, our optimization problem is to minimize a real function of n-variables, continuously differentiable and restricted to a set of simple structure and add on the objective function of the hypothesis of pseudo-convexity or quasi-convexity. Then we consider the problem of unconstrained multi-objective optimization and add some hypotheses about the function vector, such as convexity or quasi-convexity, and is continuously differentiable. It is noteworthy that in both problems will be used to search for inexact Armijo over viable directions. / Neste trabalho faremos um estudo das propriedades de convergência do Método do Gradiente Projetado e do Método de Descida para otimização Multi-objetivo. No primeiro momento, o nosso problema de otimização será o de minimizar uma função real de nvariáveis, continuamente diferenciável e restrita a um conjunto de estrutura simples e acrescentaremos sobre a função objetivo a hipótese de quase-convexidade ou pseudoconvexidade. Em seguida iremos considerar o problema de otimização Multi-Objetivo irrestrito e adicionar algumas hipóteses sobre a função vetorial, como a convexidade ou quase-convexidade, além de ser continuamente diferenciável. É importante salientar que em ambos os problemas será utilizado a busca inexata de armijo ao longo de direções viáveis.

De nombreux systèmes physiques complexes sont modélisés à l’aide de systèmes d’équations aux dérivées partielles comprenant éventuellement des couplages et des non linéarités. Dans ce cadre, les problématiques de commande qui cherchent à définir quels sont les moyens d’actions (éventuellement en dimension infinie) permettant d’atteindre un état désiré ne sont pas triviales.Il en est de même pour l’identification en ligne de caractéristiques du système physique à partir d’informations fournies par des observations pertinentes. Cet aspect est souvent considéré comme un problème inverse dont la résolution pose de nombreuses questions spécifiques et ardues.Afin d’illustrer la problématique du déplacement judicieux d’un ensemble de capteurs mobiles pour reconstruire un terme source dans une équation aux dérivées partielles paraboliques, un dispositif est décrit dans cette étude. Il décrit des phénomènes de convection et diffusion éventuellement non linéaires.Le travail décrit dans ce document est destiné à développer une méthodologie complète en vue de réaliser une conception optimale d'expériences dans le cadre de problèmes mal posés non linéaires associés à l'évaluation de paramètres inconnus dans des systèmes décrits par des équations aux dérivées partielles. Le prototype expérimental a pour objet de tester les performances des stratégies de déploiement optimal d'un ensemble de capteurs mobile afin d’identifier des paramètres de plusieurs sources chauffantes en mouvement. / Many complex physical systems are modeled using systems of partial differential equations including possibly coupling and non-linearity. In this context, the determination of control strategies (in infinite dimension) in order to achieve a desired state is not trivial. It is obvious that quasi on-line identification of characteristics of the physical system from information provided by relevant sensors is quite complex. This optimization problem is often formulated as an inverse problem, whose resolution raises many specific questions. To illustrate the problem of the moving of a set of mobile sensors to identify a term source in parabolic partial differential equations, an experimental device is proposed in this study. Both phenomena of convection and diffusion (possibly non-linear) are taken into account. The work described in this document is intended to develop a comprehensive methodology to achieve an optimal design of experiments for nonlinear ill-posed problems associated with the evaluation of unknown parameters in systems described by partial differential equations. The experimental prototype is intended to test the performance of strategies for optimal deployment of a mobile set of sensors to identify parameters of multiple heating sources in movement.

Le travail général de cette thèse consiste à étendre les outils analytiques et algébriques usuellement employés dans la résolution de problèmes combinatoires déterministes à un cadre combinatoire stochastique. Deux cadres distincts sont étudiés : les problèmes combinatoires stochastiques discrets et les problèmes stochastiques continus. Le cadre discret est abordé à travers le problème de la forêt couvrante de poids maximal dans une formulation Two-Stage à multi-scénarios. La version déterministe très connue de ce problème établit des liens entre la fonction de rang dans un matroïde et la formulation duale, via l'algorithme glouton. La formulation stochastique discrète du problème de la forêt maximale couvrante est transformée en un problème déterministe équivalent, mais du fait de la multiplicité des scénarios, le dual associé est en quelque sorte incomplet. Le travail réalisé ici consiste à comprendre en quelles circonstances la formulation duale atteint néanmoins un minimum égal au problème primal intégral. D'ordinaire, une approche combinatoire classique des problèmes de graphes pondérés consiste à rechercher des configurations particulières au sein des graphes, comme les circuits, et à explorer d'éventuelles recombinaisons. Pour donner une illustration simple, si on change d'une manière infinitésimale les valeurs de poids des arêtes d'un graphe, il est possible que la forêt couvrante de poids maximal se réorganise complètement. Ceci est vu comme un obstacle dans une approche purement combinatoire. Pourtant, certaines grandeurs analytiques vont varier de manière continue en fonction de ces variations infinitésimales, comme la somme des poids des arêtes choisies. Nous introduisons des fonctions qui rendent compte de ces variations continues, et nous examinons dans quels cas les formulations duales atteignent la même valeur que les formulations primales intégrales. Nous proposons une méthode d'approximation dans le cas contraire et nous statuons sur la NP complétude de ce type de problème.Les problèmes stochastiques continus sont abordés via le problème de sac à dos avec contrainte stochastique. La formulation est de type ``chance constraint'', et la dualisation par variable lagrangienne est adaptée à une situation où la probabilité de respecter la contrainte doit rester proche de $1$. Le modèle étudié est celui d'un sac à dos où les objets ont une valeur et un poids déterminés par des distributions normales. Dans notre approche, nous nous attachons à appliquer des méthodes de gradient directement sur la formulation en espérance de la fonction objectif et de la contrainte. Nous délaissons donc une possible reformulation classique du problème sous forme géométrique pour détailler les conditions de convergence de la méthode du gradient stochastique. Cette partie est illustrée par des tests numériques de comparaison avec la méthode SOCP sur des instances combinatoires avec méthode de Branch and Bound, et sur des instances relaxées. / The global purpose of this thesis is to study the conditions to extend analytical and algebraical properties commonly observed in the resolution of deterministic combinatorial problems to the corresponding stochastic formulations of these problems. Two distinct situations are treated : discrete combinatorial stochastic problems and continuous stochastic problems. Discrete situation is examined with the Two Stage formulation of the Maximum Weight Covering Forest. The well known corresponding deterministic formulation shows the connexions between the rank function of a matroid, the greedy algorithm , and the dual formulation. The discrete stochastic formulation of the Maximal Covering Forest is turned into a deterministic equivalent formulation, but, due to the number of scenarios, the associated dual is not complete. The work of this thesis leads to understand in which cases the dual formulation still has the same value as the primal integer formulation. Usually, classical combinatorial approaches aim to find particular configurations in the graph, as circuits, in order to handle possible reconfigurations. For example, slight modifications of the weights of the edges might change considerably the configuration of the Maximum Weight Covering Forest. This can be seen as an obstacle to handle pure combinatorial proofs. However, some global relevant quantities, like the global weight of the selected edges during the greedy algorithm, have a continuous variation in function of slight modifications. We introduce some functions in order to outline these continuous variations. And we state in which cases Primal integral problems have the same objective values as dual formulations. When it is not the case, we propose an approximation method and we examine the NP completeness of this problem.Continuous stochastic problems are presented with the stochastic Knapsack with chance constraint. Chance constraint and dual Lagrangian formulation are adapted in the case where the expected probability of not exceeding the knapsack capacity is close to $1$. The introduced model consists in items whose costs and rewards follow normal distributions. In our case, we try to apply direct gradient methods without reformulating the problem into geometrical terms. We detail convergence conditions of gradient based methods directly on the initial formulation. This part is illustrated with numerical tests on combinatorial instances and Branch and Bound evaluations on relaxed formulations.

Magnetic resonance perfusion imaging is a today's very promising method for medicine diagnosis. This thesis deals with a sparse representation of signals, low-rank matrix recovery and compressed sensing, which allows overcoming present physical limitations of magnetic resonance perfusion imaging. Several models for reconstruction of measured perfusion data is introduced and numerical methods for their software implementation, which is an important part of the thesis, is mentioned. Proposed models are verified on simulated and real perfusion data from magnetic resonance.