Notre objectif dans cette thèse est de résoudre un problème quadratique binaire sous contraintes mixtes par les techniques d'optimisation DC. Puisque l'optimisation DC a prouvé son efficacité pour résoudre des problèmes de grandes tailles dans différents domaines, nous avons décidé d'appliquer cette approche d'optimisation pour résoudre ce problème. La partie la plus importante de l'optimisation DC est le choix d'une décomposition adéquate qui facilite la détermination et accélère la convergence de deux suites construites. La première suite converge vers la solution optimale du problème primal et la seconde converge vers la solution optimale du problème dual. Dans cette thèse, nous proposons deux décompositions DC efficaces et simples à manipuler. L'application de l'algorithme DC (DCA) nous conduit à résoudre à chaque itération un problème quadratique convexe avec des contraintes mixtes, linéaires et quadratiques. Pour cela, il faut trouver une méthode efficace et rapide pour résoudre ce dernier problème à chaque itération. Pour cela, nous appliquons trois méthodes différentes: la méthode de Newton, la programmation semi-définie positive et la méthode de points intérieurs. Nous présentons les résultats numériques comparatifs sur les mêmes repères de ces trois approches pour justifier notre choix de la méthode la plus rapide pour résoudre efficacement ce problème. / Our objective in this work is to solve a binary quadratic problem under mixed constraints by the techniques of DC optimization. As DC optimization has proved its efficiency to solve large-scale problems in different domains, we decided to apply this optimization approach to solve this problem. The most important part of D.C. optimization is the choice of an adequate decomposition that facilitates determination and speeds convergence of two constructed suites where the first converges to the optimal solution of the primal problem and the second converges to the optimal solution of the dual problem. In this work, we propose two efficient decompositions and simple to manipulate. The application of the DC Algorithm (DCA) leads us to solve at each iteration a convex quadratic problem with mixed, linear and quadratic constraints. For it, we must find an efficient and fast method to solve this last problem at each iteration. To do this, we apply three different methods: the Newton method, the semidefinite programing and interior point method. We present the comparative numerical results on the same benchmarks of these three approaches to justify our choice of the fastest method to effectively solve this problem.

Submitted by (ana.araujo@ufrpe.br) on 2016-08-04T13:26:23Z No. of bitstreams: 1 Magali Teresopolis Reis Amaral.pdf: 5438608 bytes, checksum: a3ca949533ae94adaf7883fd465a627a (MD5) / Made available in DSpace on 2016-08-04T13:26:23Z (GMT). No. of bitstreams: 1 Magali Teresopolis Reis Amaral.pdf: 5438608 bytes, checksum: a3ca949533ae94adaf7883fd465a627a (MD5) Previous issue date: 2008-08-18 / The adjustment of the weight-age growth curves for animals plays an important role in animal production planning. These adjusted growth curves must be coherent with the biological interpretation of animal growth, which often demands imposition of constraints on model parameters.The inference of the parameters of nonlinear models with constraints, using classical techniques, presents various difficulties. In order to bypass those difficulties, a bayesian approach for adjustment of the growing curves is proposed. In this respect the bayesian proposed approach introduces restrictions on model parameters through choice of the prior density. Due to the nonlinearity, the posterior density of those parameters does not have a kernel that can be identified among the traditional distributions, and their moments can only be obtained using numerical techniques. In this work the MCMC simulation (Monte Carlo chain Markov) was implemented to obtain a summary of the posterior density. Besides, selection model criteria were used for the observed data, based on generated samples of the posterior density.The main purpose of this work is to show that the bayesian approach can be of practical use, and to compare the bayesian inference of the estimated parameters considering noninformative prior density (from Jeffreys), with the classical inference obtained by the Gauss-Newton method. Therefore it was possible to observe that the calculation of the confidence intervals based on the asymptotic theory fails, indicating non significance of certain parameters of some models, while in the bayesian approach the intervals of credibility do not present this problem. The programs in this work were implemented in R language,and to illustrate the utility of the proposed method, analysis of real data was performed, from an experiment of evaluation of system of crossing among cows from different herds, implemented by Embrapa Pecuária Sudeste. The data correspond to 12 measurements of weight of animals between 8 and 19 months old, from the genetic groups of the races Nelore and Canchim, belonging to the genotype AALLAB (Paz 2002). The results reveal excellent applicability of the bayesian method, where the model of Richard presented difficulties of convergence both in the classical and in the bayesian approach (with non informative prior). On the other hand the logistic model provided the best adjustment of the data for both methodologies when opting for non informative and informative prior density. / O ajuste de curva de crescimento peso-idade para animais tem um papel importante no planejamento da produção animal. No entanto, as curvas de crescimento ajustadas devem ser coerentes com as interpretações biológicas do crescimento do animal, o que exige muitas vezes que sejam impostas restrições aos parâmetros desse modelo.A inferência de parâmetros de modelos não lineares sujeito a restrições, utilizando técnicas clássicas apresenta diversas dificuldades. Para contornar estas dificuldades, foi proposta uma abordagem bayesiana para ajuste de curvas de crescimento. Neste sentido,a abordagem bayesiana proposta introduz as restrições nos parâmetros dos modelos através das densidades de probabilidade a priori adotadas. Devido à não linearidade, as densidades a posteriori destes parâmetros não têm um núcleo que possa ser identificado entre as distribuições tradicionalmente conhecidas e os seus momentos só podem ser obtidos numericamente. Neste trabalho, as técnicas de simulação de Monte Carlo Cadeia de Markov (MCMC) foram implementadas para obtenção de um sumário das densidades a posteriori. Além disso, foram utilizados critérios de seleção do melhor modelo para um determinado conjunto de dados baseados nas amostras geradas das densidades a posteriori.O objetivo principal deste trabalho é mostrar a viabilidade da abordagem bayesiana e comparar a inferência bayesiana dos parâmetros estimados, considerando-se densidades a priori não informativas (de Jeffreys), com a inferência clássica das estimativas obtidas pelo método de Gauss-Newton. Assim, observou-se que o cálculo de intervalos de confiança, baseado na teoria assintótica, falha, levando a não significância de certos parâmetros de alguns modelos. Enquanto na abordagem bayesiana os intervalos de credibilidade não apresentam este problema. Os programas utilizados foram implementados no R e para ilustração da aplicabilidade do método proposto, foram realizadas análises de dados reais oriundos de um experimento de avaliação de sistema de cruzamento entre raças bovinas de corte, executado na Embrapa Pecuária Sudeste. Os dados correspondem a 12 mensurações de peso dos 8 aos 19 meses de idade do grupo genético das raças Nelore e Canchim, pertencente ao grupo de genotípico AALLAB, ver (Paz 2002). Os resultados revelaram excelente aplicabilidade do método bayesiano, destacando que o modelo de Richard apresentou dificuldades de convergência tanto na abordagem clássica como bayesiana (com priori não informativa). Por outro lado o modelo Logístico foi quem melhor se ajustou aos dados em ambas metodologias quando se optou por densidades a priori não informativa e informativa.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-03-05T14:28:50Z No. of bitstreams: 2 Dissertação - Ademir Alves Aguiar - 2014.pdf: 1975016 bytes, checksum: 31320b5840b8b149afedc97d0e02b49b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-03-06T10:38:03Z (GMT) No. of bitstreams: 2 Dissertação - Ademir Alves Aguiar - 2014.pdf: 1975016 bytes, checksum: 31320b5840b8b149afedc97d0e02b49b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-03-06T10:38:03Z (GMT). No. of bitstreams: 2 Dissertação - Ademir Alves Aguiar - 2014.pdf: 1975016 bytes, checksum: 31320b5840b8b149afedc97d0e02b49b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-12-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this dissertation we present a semi-local convergence analysis for the Gauss-Newton method to solve a special class of systems of non-linear equations, under the hypothesis that the derivative of the non-linear operator satisfies a majorant condition. The proofs and conditions of convergence presented in this work are simplified by using a simple majorant condition. Another tool of demonstration that simplifies our study is to identify regions where the iteration of Gauss-Newton is “well-defined”. Moreover, special cases of the general theory are presented as applications. / Nesta dissertação apresentamos uma análise de convergência semi-local do método de Gauss-Newton para resolver uma classe especial de sistemas de equações não-lineares, sob a hipótese que a derivada do operador não-linear satisfaz uma condição majorante. As demonstrações e condições de convergência apresentadas neste trabalho são simplificadas pelo uso de uma simples condição majorante. Outra ferramenta de demonstração que simplifica o nosso estudo é a identificação de regiões onde a iteração de Gauss-Newton está “bem-definida”. Além disso, casos especiais da teoria geral são apresentados como aplicações.

Orientadores: Márcia Aparecida Gomes Ruggiero, Sandra Augusta Santos / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-21T10:21:10Z (GMT). No. of bitstreams: 1 Begiato_RodolfoGotardi_D.pdf: 3815627 bytes, checksum: 59584610cfd737a94e68dc5bf3735e25 (MD5) Previous issue date: 2012 / Resumo: O objetivo desta tese é tratar da resolução de sistemas não lineares de grande porte, em que as funções são continuamente diferenciáveis, por meio de uma abordagem híbrida que utiliza um método iterativo com duas fases. A primeira fase consiste de versões sem derivadas do método do ponto fixo empregando parâmetros espectrais para determinar o tamanho do passo da direção residual. A segunda fase é constituída pelo método de Newton inexato em uma abordagem matrix-free, em que é acoplado o método GMRES para resolver o sistema linear que determina a nova direção de busca. O método híbrido combina ordenadamente as duas fases de forma que a segunda é acionada somente em caso de falha na primeira e, em ambas, uma condição de decréscimo não-monótono deve ser verificada para aceitação de novos pontos. Desenvolvemos ainda um segundo método, em que uma terceira fase de busca direta é acionada em situações em que o excesso de buscas lineares faz com que o tamanho de passo na direção do método de Newton inexato torne-se demasiadamente pequeno. São estabelecidos os resultados de convergência dos métodos propostos. O desempenho computacional é avaliado em uma série de testes numéricos com problemas tradicionalmente encontrados na literatura. Tanto a análise teórica quanto a numérica evidenciam a viabilidade das abordagens apresentadas neste trabalho / Abstract: This thesis handles large-scale nonlinear systems for which all the involved functions are continuously differentiable. They are solved by means of a hybrid approach based on an iterative method with two phases. The first phase is defined by derivative-free versions of a fixed-point method that employs spectral parameters to define the steplength along the residual direction. The second phase consists of a matrix-free inexact Newton method that employs the GMRES to solve the linear system that computes the search direction. The proposed hybrid method neatly combines the two phases in such a way that the second is called only in case the first one fails. To accept new points in both phases, a nonmonotone decrease condition upon a merit function has to be verified. A second method is developed as well, with a third phase based on direct search, that should act whenever too many line searches have excessively decreased the steplenght along the inexact- Newton direction. Convergence results for the proposed methods are established. The computational performance is assessed in a set of numerical experiments with problems from the literature. Both the theoretical and the experimental analysis corroborate the feasibility of the proposed strategies / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientadores: Sandra Augusta Santos, Roberto Andreani / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-14T11:40:11Z (GMT). No. of bitstreams: 1 Shirabayashi_WesleyVagnerInes_D.pdf: 877226 bytes, checksum: a814cd9947431a0aee17517c4cc953f4 (MD5) Previous issue date: 2009 / Resumo: Neste trabalho reformulamos o problema de complementaridade não linear generalizado (GNCP) em cones poliedrais como um sistema não linear com restrição de não negatividade em algumas variáveis, e trabalhamos na resolução de tal reformulação por meio de estratégias de pontos interiores. Em particular, definimos dois algoritmos e provamos a convergência local de tais algoritmos sob hipóteses usuais. O primeiro algoritmo é baseado no método de Newton, e o segundo, no método tensorial de Chebyshev. O algoritmo baseado no método de Chebyshev pode ser visto como um método do tipo preditor-corretor. Tal algoritmo, quando aplicado a problemas em que as funções envolvidas são afins, e com escolhas adequadas dos parâmetros, torna-se o bem conhecido algoritmo preditor-corretor de Mehrotra. Também apresentamos resultados numéricos que ilustram a competitividade de ambas as propostas. / Abstract: In this work we reformulate the generalized nonlinear complementarity problem (GNCP) in polyhedral cones as a nonlinear system with nonnegativity in some variables and propose the resolution of such reformulation through interior-point methods. In particular we define two algorithms and prove the local convergence of these algorithms under standard assumptions. The first algorithm is based on Newton's method and the second, on the Chebyshev's tensorial method. The algorithm based on Chebyshev's method may be considered a predictor-corrector one. Such algorithm, when applied to problems for which the functions are affine, and the parameters are properly chosen, turns into the well-known Mehrotra's predictor corrector algorithm. We also present numerical results that illustrate the competitiveness of both proposals. / Doutorado / Otimização / Doutor em Matemática Aplicada

The purpose of this dissertation is to design identification methods for identifying a permanent magnet synchronous motor. The whole identification and motor control is carried out in d-q coordinates, and the program used for processing and control was the matlab simulink, together with the real time platform DSpace. The work focuses on two main areas of identification, off-line identification and on-line identification. For offline identification the frequency analysis was used with the lock rotor test to get three main parameters. They are the quadrature and direct inductances and stator resistance. In the online mode, the identified parameters were extended to magnet flux _f identified by MRAS method. The remaining parameters were again identified by frequency analysis, which was adapted into online mode, and simultaneously applied to the identification of several part in one time. The next method is Newton method, which is used for estimating stator resistance of the motor, without the need to apply any signal.

This paper studies Newton's method for solving the algebraic Riccati equation combined with an exact line search. Based on these considerations we present a Newton{like method for solving algebraic Riccati equations. This method can improve the sometimes erratic convergence behavior of Newton's method.

Η παρούσα διδακτορική διατριβή πραγματεύεται το θέμα της αποδοτικής και με βεβαιότητα εύρεσης όλων των ριζών της παραμετρικής εξίσωσης f(x;[p]) = 0, μιας συνεχώς διαφορίσιμης συνάρτησης f με [p] ένα διάνυσμα που περιγράφει όλες τις παραμέτρους της παραμετρικής εξίσωσης και τυποποιούνται με τη μορφή διαστημάτων. Για την επίλυση αυτού του προβλήματος χρησιμοποιήθηκαν εργαλεία της Διαστηματικής Ανάλυσης. Το κίνητρο για την ερευνητική ενασχόληση με το παραπάνω πρόβλημα προέκυψε μέσα από ένα κλασικό πρόβλημα αριθμητικής ανάλυσης: την αριθμητική επίλυση συστημάτων πολυωνυμικών εξισώσεων μέσω διαστηματικής ανάλυσης. Πιο συγκεκριμένα, προτάθηκε μια ευρετική τεχνική αναδιάταξης του αρχικού πολυωνυμικού συστήματος που φαίνεται να βελτιώνει σημαντικά, κάθε φορά, τον χρησιμοποιούμενο επιλυτή. Η ανάπτυξη, καθώς και τα αποτελέσματα αυτής της εργασίας αποτυπώνονται στο Κεφάλαιο 2 της παρούσας διατριβής. Στο επόμενο Κεφάλαιο 3, προτείνεται μια μεθοδολογία για την αποδοτική και αξιόπιστη επίλυση μη-γραμμικών εξισώσεων με διαστηματικές παραμέτρους, δηλαδή την αποδοτική και αξιόπιστη επίλυση διαστηματικών εξισώσεων. Πρώτα, δίνεται μια νέα διατύπωση της Διαστηματικής Αριθμητικής και αποδεικνύεται η ισοδυναμία της με τον κλασσικό ορισμό. Στη συνέχεια, χρησιμοποιείται η νέα διατύπωση της Διαστηματικής Αριθμητικής ως θεωρητικό εργαλείο για την ανάπτυξη μιας επέκτασης της διαστηματικής μεθόδου Newton που δύναται να επιλύσει όχι μόνο κλασικές μη-παραμετρικές μη-γραμμικές εξισώσεις, αλλά και παραμετρικές (διαστηματικές) μη-γραμμικές εξισώσεις. Στο Κεφάλαιο 4 προτείνεται μια νέα προσέγγιση για την αριθμητική επίλυση του προβλήματος της Ολικής Βελτιστοποίησης με περιορισμούς διαστήματα, χρησιμοποιώντας τα αποτελέσματα του Κεφαλαίου 3. Το πρόβλημα της ολικής βελτιστοποίησης, ανάγεται σε πρόβλημα επίλυσης διαστηματικών εξισώσεων, και γίνεται εφικτή η επίλυσή του με τη βοήθεια των θεωρητικών αποτελεσμάτων και της αντίστοιχης μεθοδολογίας του Κεφαλαίου 3. Στο τελευταίο Κεφάλαιο δίνεται μια νέα αλγοριθμική προσέγγιση για το πρόβλημα της επίλυσης διαστηματικών πολυωνυμικών εξισώσεων. Η νέα αυτή προσέγγιση, βασίζεται και γενικεύει την εργασία των Hansen και Walster, οι οποίοι πρότειναν μια μέθοδο για την επίλυση διαστηματικών πολυωνυμικών εξισώσεων 2ου βαθμού. / In this dissertation the problem of finding reliably and with certainty all the zeros a pa-rameterized equation f(x;[p]) = 0, of a continuously differentiable function f is considered, where [p] is an interval vector describing all the parameters of the Equation, which are formed with interval numbers. For this kind of problem, methods of Interval Analysis are used. The incentive to this scientific research was emerged from a classic numerical analysis problem: the numerical solution of polynomial systems of equations using interval analysis. In particular, a heuristic reordering technique of the initial polynomial systems of equations is proposed. This approach seems to improve significantly the used solver. The proposed technique, as well as the results of this publication are presented in Chapter 2 of this dissertation. In the next Chapter 3, a methodology is proposed for solving reliably and efficiently parameterized (interval) equations. Firstly, a new formulation of interval arithmetic is given and the equivalence with the classic one is proved. Then, an extension of interval Newton method is proposed and developed, based on the new formulation of interval arithmetic. The new method is able to solve not only classic non-linear equations but, non-linear parameterized (interval) equation too. In Chapter 4 a new approach on solving the Box-Constrained Global Optimization problem is proposed, based on the results of Chapter 3. In details, the Box-Constrained Global Optimization problem is reduced to a problem of solving interval equations. The solution of this reduction is attainable through the methodology developed in Chapter 3. In the last Chapter of this dissertation a new algorithmic approach is given for the problem of solving reliably and with certainty an interval polynomial equation of degree $n$. This approach consists in a generalization of the work of Hansen and Walster. Hansen and Walster proposed a method for solving only quadratic interval polynomial equations

Le but de cette thèse est d'étudier la méthode de Newton pour résoudre numériquement les inclusions variationnelles, appelées aussi dans la littérature les équations généralisées. Ces problèmes engendrent en général des opérateurs multivoques. La première partie est dédiée à l'extension des approches de Kantorovich et la théorie (alpha, gamma) de Smale (connues pour les équations non-linéaires classiques) au cas des inclusions variationnelles dans les espaces de Banach. Ceci a été rendu possible grâce aux développements récents des outils de l'analyse variationnelle et non-lisse tels que la régularité métrique. La seconde partie est consacrée à l'étude de méthodes numériques de type-Newton pour les inclusions variationnelles en utilisant la différentiabilité généralisée d'applications multivoques où nous proposons de linéariser à la fois les parties univoques (lisses) et multivoques (non-lisses). Nous avons montré que, sous des hypothèses sur les données du problème ainsi que le choix du point de départ, la suite générée par la méthode de Newton converge au moins linéairement vers une solution du problème de départ. La convergence superlinéaire peut-être obtenue en imposant plus de conditions sur l'approximation multivaluée. La dernière partie de cette thèse est consacrée à l'étude des équations généralisées dans les variétés Riemaniennes à valeurs dans des espaces euclidiens. Grâce à la relation entre la structure géométrique des variétés et les applications de rétractions, nous montrons que le schéma de Newton converge localement superlinéairement vers une solution du problème. La convergence quadratique (locale et semi-locale) peut-être obtenue avec des hypothèses de régularités sur les données du problème. / This thesis is devoted to present some results in the scope of Newton-type methods applied for inclusion involving set-valued mappings. In the first part, we follow the Kantorovich's and/or Smale's approaches to study the convergence of Josephy-Newton method for generalized equation (GE) in Banach spaces. Such results can be viewed as an extension of the classical Kantorovich's theorem as well as Smale's (alpha, gamma)-theory which were stated for nonlinear equations. The second part develops an algorithm using set-valued differentiation in order to solve GE. We proved that, under some suitable conditions imposed on the input data and the choice of the starting point, the algorithm produces a sequence converging at least linearly to a solution of considering GE. Moreover, by imposing some stronger assumptions related to the approximation of set-valued part, the proposed method converges locally superlinearly. The last part deals with inclusions involving maps defined on Riemannian manifolds whose values belong to an Euclidean space. Using the relationship between the geometric structure of manifolds and the retraction maps, we show that, our scheme converges locally superlinearly to a solution of the initial problem. With some more regularity assumptions on the data involved in the problem, the quadratic convergence (local and semi-local) can be ensured.

Video is a sequence of 2D images of the 3D world generated by a camera. As the camera moves relative to the real scene and elements of that scene themselves move, correlated frame-to-frame changes in the video images are induced. Humans easily identify such changes as scene motion and can readily assess attempts to quantify it. For a machine, the identification of the 2D frame-to-frame motion is difficult. This problem is addressed by the computer vision process of tracking. Tracking underpins the solution to the problem of augmenting general video sequences with artificial imagery, a staple task in the visual effects industry. The problem is difficult because tracking in general video sequences is complicated by the presence of non-rigid motion, repeated texture and arbitrary occlusions. Existing methods provide solutions that rely on imposing limitations on the scenes that can be processed or that rely on human artistry and hard work. I introduce new paradigms, frameworks and algorithms for overcoming the challenges of processing general video and thus provide solutions that fill the gap between the `automated' and `manual' approaches. The work is easily sectioned into three parts, which can be considered separately or taken together for dealing with video without limitations. The initial focus is on directly addressing practical issues of human interaction in the tracking process: a new solution is developed by explicitly incorporating the user into an interactive algorithm. It is a novel tracking system based on fast full-frame patch searching and high-speed optimal track determination. This approach makes only minimal assumptions about motion and appearance, making it suitable for the widest variety of input video. I detail an implementation of the new system using k-d trees and dynamic programming. The second distinct contribution is an important extension to tracking algorithms in general. It can be noted that existing tracking algorithms occupy a spectrum in their use of global motion information. Local methods are easily confused by occlusions, repeated texture and image noise. Global motion models offer strong predictions to see through these difficulties and have been used in restricted circumstances, but are defeated by scenes containing independently moving objects or modest levels of non-rigid motion. I present a well principled way of combining local and global models to improve tracking, especially in these highly problematic cases. By viewing rank-constrained tracking as a probabilistic model of 2D tracks instead of 3D motion, I show how one can obtain a robust motion prior that can be easily incorporated in any existing tracking algorithm. The development of the global motion prior is based on rank-constrained factorization of measurement matrices. A common difficulty comes from the frequent occurrence of occlusions in video, which means that the relevant matrices are often not complete due to missing data. This defeats standard factorization algorithms. To fully explain and understand the algorithmic complexities of factorization in this practical context, I present a common notation for the direct comparison of existing algorithms and propose a new family of hybrid approaches that combine the superb initial performance of alternation methods with the convergence power of the Newton algorithm. Together, these investigations provide a wide-ranging, yet coherent exploration of tracking non-rigid objects in video.