Nonnegative matrix factorization (NMF) is a useful dimension reduction method that has been investigated and applied in various areas. NMF is considered for high-dimensional data in which each element has a nonnegative value, and it provides a low-rank approximation formed by factors whose elements are also nonnegative. The nonnegativity constraints imposed on the low-rank factors not only enable natural interpretation but also reveal the hidden structure of data. Extending the benefits of NMF to multidimensional arrays, nonnegative tensor factorization (NTF) has been shown to be successful in analyzing complicated data sets. Despite the success, NMF and NTF have been actively developed only in the recent decade, and algorithmic strategies for computing NMF and NTF have not been fully studied. In this thesis, computational challenges regarding NMF, NTF, and related least squares problems are addressed. First, efficient algorithms of NMF and NTF are investigated based on a connection from the NMF and the NTF problems to the nonnegativity-constrained least squares (NLS) problems. A key strategy is to observe typical structure of the NLS problems arising in the NMF and the NTF computation and design a fast algorithm utilizing the structure. We propose an accelerated block principal pivoting method to solve the NLS problems, thereby significantly speeding up the NMF and NTF computation. Implementation results with synthetic and real-world data sets validate the efficiency of the proposed method. In addition, a theoretical result on the classical active-set method for rank-deficient NLS problems is presented. Although the block principal pivoting method appears generally more efficient than the active-set method for the NLS problems, it is not applicable for rank-deficient cases. We show that the active-set method with a proper starting vector can actually solve the rank-deficient NLS problems without ever running into rank-deficient least squares problems during iterations. Going beyond the NLS problems, it is presented that a block principal pivoting strategy can also be applied to the l1-regularized linear regression. The l1-regularized linear regression, also known as the Lasso, has been very popular due to its ability to promote sparse solutions. Solving this problem is difficult because the l1-regularization term is not differentiable. A block principal pivoting method and its variant, which overcome a limitation of previous active-set methods, are proposed for this problem with successful experimental results. Finally, a group-sparsity regularization method for NMF is presented. A recent challenge in data analysis for science and engineering is that data are often represented in a structured way. In particular, many data mining tasks have to deal with group-structured prior information, where features or data items are organized into groups. Motivated by an observation that features or data items that belong to a group are expected to share the same sparsity pattern in their latent factor representations, We propose mixed-norm regularization to promote group-level sparsity. Efficient convex optimization methods for dealing with the regularization terms are presented along with computational comparisons between them. Application examples of the proposed method in factor recovery, semi-supervised clustering, and multilingual text analysis are presented.

One of the common research goals in disciplines such as computer graphics and robotics is to understand the subtleties of human motion and develop tools for recreating natural and meaningful motion. Physical simulation of virtual human characters is a promising approach since it provides a testbed for developing and testing control strategies required to execute various human behaviors. Designing generic control algorithms for simulating a wide range of human activities, which can robustly adapt to varying physical environments, has remained a primary challenge. This dissertation introduces methods for generic and robust control of virtual characters in an interactive physical environment. Our approach is to use the information of the physical contacts between the character and her environment in the control design. We leverage high-level knowledge of the kinematics goals and the interaction with the surroundings to develop active control strategies that robustly adapt to variations in the physical scene. For synthesizing intentional motion requiring long-term planning, we exploit properties of the physical model for creating efficient and robust controllers in an interactive framework. The control design leverages the reference motion capture data and the contact information with the environment for interactive long-term planning. Finally, we propose a compact soft contact model for handling contacts for rigid body virtual characters. This model aims at improving the robustness of existing control methods without adding any complexity to the control design and opens up possibilities for new control algorithms to synthesize agile human motion.

The developed countries, heavily impacted by the economic and financial crisis of 2008, signaled the recovery with negotiations on two major international trade agreements, The Trans-Pacific Partnership and the Transatlantic Trade and Investment Partnership (TPP and TTIP, respectively). The establishment of trade agreements may minimize the effects of protectionist policies of countries/blocks, eliminating or reducing existing barriers, thus stimulating the increase in trade among member countries of such agreements. The TPP and TTIP imply the reduction of tariffs and non-tariff barriers between member countries, the United States case. Thus, competition with Brazil will tend to increase in many products, case of the chicken meat, in which the United States occupies the first position in world production, while Brazil positions itself as the largest exporter of the commodity. From this new trade matrix, the present study aims to examine the possible impacts of the Transpacific and Transatlantic agreements on the Brazilian chicken meat market. The methodology derives from a Spatial Equilibrium Model as a Mixed Complementarity Problem (MCP), based on five alternative scenarios, which aimed to highlight possible changes in the market of chicken meat from the implementation of new trade agreements. The first scenario simulates the formation of the TPP with the reduction of tariff barriers, while the second scenario presupposes the elimination of tariff and non-tariff barriers. Regarding the TTIP, scenarios 3 and 4, it is assumed the reduction of tariff barriers as well as the elimination of tariff barriers and technical constraints; in the fifth scenario was considered the simultaneous occurrence of the two agreements, through the elimination of tariff and non-tariff barriers. The results indicate that, in general, with the implementation of both agreements the Brazilian chicken meat market may invariably bring losses, particularly in relation to production, consequently, affecting producers' prices and surpluses. The most damaging scenarios for Brazil are the formation of the TPP in its broadest form, based on the elimination of tariff and non-tariff barriers, as well as the simultaneous formation of the agreements, in which the country show a net loss in welfare. From this, we emphasize the importance of negotiating trade agreements to ensure the industry conditions of expansion and access to new markets, As well as greater rigor in matters related to animal health, inspection and certification, aspects of a technical nature that have great potential to distort trade flows internationally. / Os países desenvolvidos, fortemente impactados pela crise econômica e financeira de 2008, sinalizaram a recuperação a partir de negociações de dois grandes acordos no comércio internacional, a Parceria Transpacífico e a Parceria Transatlântica de Comércio e Investimento (TPP e TTIP, respectivamente). A constituição de acordos comerciais possivelmente minimizam os efeitos das políticas protecionistas dos países/blocos, eliminando ou reduzindo as barreiras existentes, estimulando assim o aumento do comércio entre os países-membros de tais acordos. O TPP e o TTIP implicarão na redução de tarifas e barreiras não tarifárias entre os países-membros, caso dos Estados Unidos. Assim, a concorrência com o Brasil tenderá a aumentar, em muitos produtos, caso da carne de frango, no qual o país norte-americano ocupa a primeira posição na produção mundial, enquanto que o Brasil posiciona-se como maior exportador da commodity. A partir desta nova matriz de comércio, o presente estudo tem por objetivo examinar os possíveis impactos da implementação dos acordos Transpacífico e Transatlântico sobre o mercado de carne de frango brasileiro. A metodologia deriva de um Modelo de Equilíbrio Espacial na forma de um Problema de Complementaridade Mista (PCM), baseando em cinco cenários alternativos, cujo objetivo foi evidenciar possíveis mudanças no mercado da carne de frango decorrentes da implementação de novos acordos comerciais. O primeiro cenário simula a formação do TPP a partir da redução das barreiras tarifárias, já o segundo cenário pressupõe a eliminação das barreiras tarifarias e não tarifárias. Em relação ao TTIP, cenários 3 e 4, pressupõe-se a redução das barreiras tarifarias como também a eliminação das barreiras tarifárias e restrições técnicas; num quinto cenário considerou-se a ocorrência simultânea dos dois acordos, por meio da eliminação das barreiras tarifárias e não tarifárias. Os resultados indicam que, de maneira geral, com a efetivação de ambos os acordos o setor de carne de frango brasileiro, pode invariavelmente trazer prejuízos, principalmente no que se refere à produção e, em consequência, afetando os preços e os excedentes dos produtores. Os cenários mais prejudiciais ao Brasil consistem na formação do TPP em sua forma mais ampla, baseando-se na eliminação das barreiras tarifárias e não tarifarias, como também na formação simultânea dos acordos, nos quais o país apresenta perda líquida de bem estar. A partir disso, ressalta-se a importância da negociação de acordos comerciais para garantir ao setor condições de expansão e acesso a novos mercados, assim como maior rigor nas questões relacionadas à saúde animal, fiscalização e certificação, aspectos de natureza técnica que tem grande potencial de distorção dos fluxos de comércio internacionalmente.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-01-13T12:34:27Z No. of bitstreams: 1 weslleydasilvapereira.pdf: 6406997 bytes, checksum: 17a5ee95515b6ad53c2e29db478c6e81 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-01-25T17:29:23Z (GMT) No. of bitstreams: 1 weslleydasilvapereira.pdf: 6406997 bytes, checksum: 17a5ee95515b6ad53c2e29db478c6e81 (MD5) / Made available in DSpace on 2016-01-25T17:29:23Z (GMT). No. of bitstreams: 1 weslleydasilvapereira.pdf: 6406997 bytes, checksum: 17a5ee95515b6ad53c2e29db478c6e81 (MD5) Previous issue date: 2015-03-23 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / É crescente o interesse na utilização de métodos térmicos para recuperação de óleo de média e alta viscosidade. Um desses métodos é a combustão in situ, que consiste na liberação de calor no interior do reservatório através da combustão do ar injetado. As componentes mais pesadas do óleo atuam como combustível para as reações exotérmicas e o calor gerado reduz a viscosidade do óleo, estimulando o fluxo em direção aos poços de produção. Os modelos matemáticos para este método de recuperação em geral são complexos. Portanto, a obtenção de soluções analíticas para tais modelos é inviável, sendo necessária a utilização de simulações computacionais. Diversos trabalhos apresentam estudos analíticos e numéricos de modelos unidimensionais para a combustão em meios porosos. Em trabalhos anteriores, estimativas analíticas para modelos unidimensionais foram obtidas. Neste trabalho, tais estimativas são ligeiramente generalizadas através da inclusão da pressão prevalecente. É proposto um modelo bidimensional para o processo de combustão in situ em meios porosos heterogêneos que considera pressão variável. Soluções numéricas são obtidas utilizando o método de elementos finitos para a discretização espacial, o esquema de diferenças finitas de Crank-Nicolson para discretização no tempo e o método de Newton para resolução das equações não lineares resultantes. Estimativas analíticas para a temperatura e velocidade da onda de combustão são obtidas através de um modelo unidimensional simplificado. Tais estimativas são validadas com sucesso para o modelo geral através das simulações. Uma outra simplificação unidimensional do modelo geral é simulada numericamente através de duas abordagens: a primeira é similar à utilizada para a solução do modelo geral; e a segunda é escrita como um problema de complementaridade. Os problemas de complementaridade não-linear são resolvidos pelo algoritmo FDA-NCP. As duas abordagens numéricas utilizadas são comparadas com uma estimativa analítica para a onda térmica e mostram bons resultados. / There is a growing interest in using thermal methods for the recovery of medium and high viscosity oil. One of these methods is the in-situ combustion, which consists in release heat within the reservoir through combustion of the injected air. The heavier oil components are used as fuel for exothermic reactions and the generated heat reduces the oil viscosity, stimulating the flow towards the production well. In general, the mathematical models for this recovery method are complex. Therefore, the analytical solutions for such models are impossible, requiring numerical simulations. Several works present analytical and numerical studies of one-dimensional models for combustion in porous media. In previous works analytical estimates for one dimensional models were obtained. Here these estimates are slightly generalized by including the prevailing pressure. We propose a two-dimensional model for the in-situ combustion process in heterogeneous porous media, considering variable pressure. Numerical results are obtained using the finite element method for spatial discretization, Crank-Nicolson finite difference scheme for time discretization and Newton’s method for the arising nonlinear equations. Analytical estimates for combustion wave speed and combustion wave temperature are obtained using one-dimensional simplified model. These estimates are successfully validated in the general model through the simulation results. Another one-dimensional simplification of the general model is numerically simulated by two approaches: the first is similar to the one previously described; and the second one is written as a complementarity problem. The arising nonlinear complementarity problems are solved by the FDA-NCP algorithm. Both numerical approaches are compared to the analytical estimate for the thermal wave, showing good agreement.

<p>The linear complementarity problems (LCP) arise from linear or quadratic programming, or from a variety of other particular application problems, like boundary problems, network equilibrium problems,contact problems, market equilibria problems, bimatrix games etc. Recently, many people have focused on the solver of LCP with a matrix having some kind of special property, for example, when this matrix is an H+-matrix, since this property is a sufficient condition for the existence and uniqueness of the soluition of LCP. Generally speaking, solving LCP can be approached from two essentially different perspectives. One of them includes the use of so-called direct methods, in the literature also known under the name pivoting methods. The other, and from our perspective - more interesting one, which we actually focus on in this thesis,<br />is the iterative approach. Among the vast collection of iterative solvers,our choice was one particular class of modulus based iterative methods.Since the subclass of modulus based-methods is again diverse in some sense, it can be specialized even further, by the introduction and the use of matrix splittings. The main goal of this thesis is to use the theory of H -matrices for proving convergence of the modulus-based multisplit-ting methods, and to use this new technique to analyze some important properties of iterative methods once the convergence has been guaranteed.</p> / <p>Problemi linearne komplementarnosti (LCP) se javljaju kod problema linearnog i kvadratnog programiranja i kod mnogih drugih problema iz prakse, kao &scaron;to su, na&nbsp; primer, problemi sa graničnim slojem, problemi mrežnih ekvilibrijuma, kontaktni problemi, problemi određivanja trži&scaron;ne ravnoteže, problemi bimatričnih igara i mnogi drugi. Ne tako davno, veliki broj autora se bavio razvijanjem postupaka za re&scaron;avanje LCP sa matricom koja ispunjava neko specijalno svojstvo, na primer, da pripada klasi H+-matrica, budući da je dobro poznato da je ovaj uslov dovoljan da obezbedi egzistenciju i jedinstvenost re&scaron;enja LCP. Uop&scaron;teno govoreći, re&scaron;avanju LCP moguce&nbsp; je pristupiti dvojako. Prvi pristup podrazumeva upotrebu takozvanih direktnih metoda, koje su u literaturi poznate i pod nazivom metode pivota. Drugoj kategoriji, koja je i sa stanovi&scaron;ta ove teze interesantna, pripadaju iterativni postupci. S obzirom da je ova kategorija izuzetno bogata, mi smo se opredelili za jednu od najznačajnijih varijanti, a&nbsp; to je modulski iterativni postupak. Međutim, ni ova odrednica nije dovoljno adekvatna, budući da modulski postupci obuhvataju nekolicinu različitih pravaca. Zato smo se odlučili da posmatramo postupke koji se zasnivaju na razlaganjima ali i vi&scaron;estrukim razlaganjima matrice. Glavni cilj ove doktorske disertacije jeste upotreba teorije H -matrica u teoremama o konvergenciji modulskih metoda zasnovanih na multisplitinzima matrice i kori&scaron;ćenje ove nove tehnike, sa ciljem analize bitnih osobina, nakon &scaron;to je konvergencija postupka zagarantovana.</p>

本論文係研究和發展平行疊代法（PARALLEL ITERATIVE METHOD ）以解決數學規劃（ MATHEMATICAL PROGRAMMING）中之互補問題（COMPLEMENTA-RITY PROBLEM）。互補問 題源自解決國防軍事、工程經濟及管理科學等領域之應用，而由於近年來各種超級或 平行電腦不斷地創新，使得發展平行演算法以充分並有效地應用超級或平行電腦來解 決大型科學計算的問題日趨重要。 在本篇論文中，我們分別探討線性互補問題以及非線性互補問題。首先我們發展出一 半非同步（SEMI-ASYNCHRONOUS ）法來解決線性互補問題，此法之特性在於其能大幅 地減低因同步法所造成處理機閒置（IDLING）之冗額成本（OVERHEAD）；同時，也放 寬了非同步法對問題所加諸之限制，因而擴大了半非同步法所能應用之範圍。我們也 建立了有關該法收斂性（CONVERGENCE ）之理論根據。此外，線性互補問題之探討， 實為進一步研究非線性互補問題之基礎。 其次，我們提出一個整體性之架構，探討平行牛頓法（NEWTON METHOD ）及其各種變 型（VARIATIONS）來解決各種非線性互補問題，比較並研究各種方法的特性、限制及 執行效率。 然後，針對上述各種演算法，我們在教育部電算中心之IBM ３０９０上發展並模擬各 該法之平行運算，經由廣泛地實驗測試，以獲得具體之數值結果，來檢驗其效率，並 比較研究各法之適用性與優劣。最後，我們也提出一些相關之問題，以供未來後續研 究之參考。

Zusammenfassung Diese Arbeit ist ein Versuch, verschiedene klassische und neuere Methodender glatten bzw. nichtglatten Optimierung zu verallgemeinern und in ihrem Zusammenhang darzustellen. Als Hauptinstrument erweist sich dabei die sogenannte verallgemeinerte Kojima-Funktion. Neben reichlichen Beispielen setzen wir einen besonderen Akzent auf die Betrachtung von Variationsungleichungen, Komplementaritaetsaufgaben und der Standartaufgabeder mathematischen Programmierung. Unter natuerlichen Voraussetzungen an diese Probleme kann man u.a. Barriere-, Straf- und SQP-Typ-Methoden, die auf Newton-Verfahrenbasieren, aber auch Modelle, die sogenannte NCP-Funktionen benutzen, mittelsspezieller Stoerungen der Kojima-Funktion exakt modellieren. Daneben werdendurch explizite und natuerliche Wahl der Stoerungsparameter auch neue Methoden dieser Arten vorgeschlagen. Die Vorteile solcher Modellierungsind ueberzeugend vor allem wegen der direkt moeglichen (auf Stabilitaetseigenschaften der Kojima-Gleichung beruhendenden)Loesungsabschaetzungen und weil die entsprechenden Nullstellen ziemlich einfach als Loesungen bekannter Ersatzprobleme interpretiert werden koennen. Ein weiterer Aspekt der Arbeit besteht in der genaueren Untersuchungder "nichtglatten Faelle". Hier wird die Theorie von verschiedenen verallgemeinerten Ableitungen und dadurch entstehenden verallgemeinerten Newton-Verfahren, die im Buch "Nonsmooth Equations in Optimization" von B. Kummer und D. Klatte vorgeschlagen und untersucht wurde, intensiv benutzt. Entscheidend ist dabei, dass die benutzten verallgemeinerten Ableitungen auch praktisch angewandt werden koennen, da man sie exakt ausrechnen kann. / This work attempts to generalize various classical and new methods of smooth or nonsmooth optimization and to show them in their interrelation. The main tool for doing this is the so-called generalized Kojima-function. In addition to numerous examples we specialy emphasize the consideration of variational inequalities, complementarity problems and the standard problem of mathematical programming. Under natural assumptions on these problems we can model e.g. barrier-, penalty-, and SQP-Type-methods basing on Newton methods, and also methods using the so-called NCP-function exactly by means of special perturbations of the Kojima-function. Furthermore, by the explicit and natural choice of the perturbation parameters new methods of these kinds are introduced. The benefit of such a modelling is obvious, first of all due to the direct solution estimation (basing on stability properties of the Kojima-equation) and because the corresponding zeros can easily be interpreted as solutions of known subproblems. A further aspect considered in this paper is the detailed investigation of "nonsmooth cases". The theory of various generalized derivatives and resulting generalized Newton methods, which is introduced and investigated in the book "Nonsmooth Equations in Optimization" of B. Kummer and D. Klatte, is intensely used here. The crucial point is the applicability of the used generalized derivatives in practice, since they can be calculated exactly.

La modélisation du transport réactif du contaminant en milieu poreux est un problème complexe cumulant les difficultés de la modélisation du transport avec celles de la modélisation de la chimie et surtout du couplage entre les deux. Cette modélisation conduit à un système d'équations aux dérivées partielles et algébriques dont les inconnues sont les quantités d'espèces chimiques. Une approche possible, déjà utilisée par ailleurs, est de choisir la méthode globale DAE : l'utilisation d'une méthode de lignes, correspondant à la discrétisation en espace seulement, conduit à un système différentiel algébrique (DAE) qui doit être résolu par un solveur adapté. Dans notre cas, on utilise le solveur IDA de Sundials qui s'appuie sur une méthode implicite, à ordre et pas variables, et qui requiert à chaque pas de temps la résolution d'un grand système non linéaire associé à une matrice jacobienne. Cette méthode est implémentée dans un logiciel qui s'appelle GRT3D (Transport Réactif Global en 3D). Le présent travail présente une amélioration de la méthode GDAE, du point de vue de la performance, de la stabilité et de la robustesse. Nous avons ainsi enrichi les possibilités de GRT3D, par la prise en compte complète des équations de précipitation-dissolution permettant l'apparition ou la disparition d'une espèce précipitée. En complément de l'étude de la méthode GDAE, nous présentons aussi une méthode séquentielle non itérative (SNIA), qui est une méthode basée sur le schéma d'Euler explicite : à chaque pas de temps, on résout explicitement l'équation de transport et on utilise ces calculs comme données pour le système chimique, résolu dans chaque maille de façon indépendante. Nous présentons aussi une comparaison entre cette méthode et l'approche GDAE. Des résultats numériques pour deux cas tests, celui proposé par l'ANDRA (cas-test 2D) d'une part, celui proposé par le groupe MoMas (Benchmark "easy case") d'autre part, sont enfin présentés, commentés et analysés. / Modeling reactive transport of contaminants in porous media is a complex problem combining the difficulties of modeling the trasport with those of modeling the chemistry and especially the coupling between the two .This model leads to a system of partial differential equations and algebraic equations whose unknowns are the quantities of chemical species. One approach , already used elsewhere , is choosing the global DAE method : using the method of lines, discretization in space only, leads to a differential algebraic system (DAE ) to be solved by a suitable solver . In our case , the solver IDA Sundials relies on an implicit method, order is used but not variables, and requires at each time solving a large nonlinear system associated with a Jacobian matrix . This method is implemented in a software called GRT3D (Global Reactive Transport in 3D). This paper presents an improved GDAE method , from the standpoint of performance, the stability and robustness. We have enriched the possibilities of GRT3D , by taking full account of the equations of dissolution – precipitation for the appearance or disappearance of precipitated species. In addition to the study of the GDAE method, we also present a non-iterative sequential method ( SNIA ) which is a method based on the explicit Euler scheme : at each time step, we explicitly solve the transport equation and we use these calculations as data for the chemical system which is resolved in each cell independently. We also present a comparison between this method and GDAE approach . Numerical results for two test cases , one proposed by ANDRA ( 2D test case ) on one hand and one proposed by the group MOMAS ( Benchmark "easy case" ) on the other hand, are finally presented , discussed and analyzed.