Iterative methods are extensively used to solve linear and nonlinear problems arising from both pure and applied sciences, and in particular, in fixed point theory and optimization. An iterative method which is used to find a fixed point of an operator or an optimal solution to an optimization problem generates a sequence in an iterative manner. We are in a hope that this sequence can converge to a solution of the problem under investigation. It is therefore quite naturally to require that the distance of this sequence to the solution set of the problem under investigation be decreasing from iteration to iteration. This is the idea of Fejer-monotonicity. In this paper, We consider quasi-Fejer monotone sequences; that is, we consider Fejer monotone sequences together with errors. Properties of quasi-Fejer monotone sequences are investigated, weak and strong convergence of quasi-Fejer monotone sequences are obtained, and an application to the convex feasibility problem is included.

Guaranteed Minimum Withdrawal Benefits(GMWB) have become popular riders on variable annuities. The pricing of a GMWB contract was originally formulated as a singular stochastic control problem which results in a Hamilton Jacobi Bellman (HJB) Variational Inequality (VI). A penalty method method can then be used to solve the HJB VI. We present a rigorous proof of convergence of the penalty method to the viscosity solution of the HJB VI assuming the underlying asset follows a Geometric Brownian Motion. A direct control method is an alternative formulation for the HJB VI. We also extend the HJB VI to the case of where the underlying asset follows a Poisson jump diffusion. The HJB VI is normally solved numerically by an implicit method, which gives rise to highly nonlinear discretized algebraic equations. The classic policy iteration approach works well for the Geometric Brownian Motion case. However it is not efficient in some circumstances such as when the underlying asset follows a Poisson jump diffusion process. We develop a combined fixed point policy iteration scheme which significantly increases the efficiency of solving the discretized equations. Sufficient conditions to ensure the convergence of the combined fixed point policy iteration scheme are derived both for the penalty method and direct control method. The GMWB formulated as a singular control problem has a special structure which results in a block matrix fixed point policy iteration converging about one order of magnitude faster than a full matrix fixed point policy iteration. Sufficient conditions for convergence of the block matrix fixed point policy iteration are derived. Estimates for bounds on the penalty parameter (penalty method) and scaling parameter (direct control method) are obtained so that convergence of the iteration can be expected in the presence of round-off error.

The objective of this PhD research program is to develop an accurate and efficient heterogeneous three-dimensional computational model for simulating the drying of wood at temperatures below the boiling point of water. The complex macroscopic drying equations comprise a coupled and highly nonlinear system of physical laws for liquid and energy conservation. Due to the heterogeneous nature of wood, the physical model parameters strongly depend upon the local pore structure, wood density variation within growth rings and variations in primary and secondary system variables. In order to provide a realistic representation of this behaviour, a set of previously determined parameters derived using sophisticated image analysis methods and homogenisation techniques is embedded within the model. From the literature it is noted that current three-dimensional computational models for wood drying do not take into consideration the heterogeneities of the medium. A significant advance made by the research conducted in this thesis is the development of a three - dimensional computational model that takes into account the heterogeneous board material properties which vary within the transverse plane with respect to the pith position that defines the radial and tangential directions. The development of an accurate and efficient computational model requires the consideration of a number of significant numerical issues, including the virtual board description, an effective mesh design based on triangular prismatic elements, the control volume finite element discretisation process for the cou- pled conservation laws, the derivation of an accurate dux expression based on gradient approximations together with flux limiting, and finally the solution of a large, coupled, nonlinear system using an inexact Newton method with a suitably preconditioned iterative linear solver for computing the Newton correction. This thesis addresses all of these issues for the case of low temperature drying of softwood. Specific case studies are presented that highlight the efficiency of the proposed numerical techniques and illustrate the complex heat and mass transport processes that evolve throughout drying.

Statistical shift-reduce parsing involves the interplay of representation learning, structured learning, and inexact search. This dissertation considers approaches that tightly integrate these three elements and explores three novel models for shift-reduce CCG parsing. First, I develop a dependency model, in which the selection of shift-reduce action sequences producing a dependency structure is treated as a hidden variable; the key components of the model are a dependency oracle and a learning algorithm that integrates the dependency oracle, the structured perceptron, and beam search. Second, I present expected F-measure training and show how to derive a globally normalized RNN model, in which beam search is naturally incorporated and used in conjunction with the objective to learn shift-reduce action sequences optimized for the final evaluation metric. Finally, I describe an LSTM model that is able to construct parser state representations incrementally by following the shift-reduce syntactic derivation process; I show expected F-measure training, which is agnostic to the underlying neural network, can be applied in this setting to obtain globally normalized greedy and beam-search LSTM shift-reduce parsers.

No description available.

Die vorliegende Arbeit befasst sich mit Schnittebenenverfahren, einer Gruppe von iterativen Algorithmen zur Minimierung einer (möglicherweise nicht glatten) konvexen Funktion über einer kompakten konvexen Menge. Wir betrachten zwei prominente Beispiele, nämlich die Ellipsoidmethode und die Methode der Vaidya, und zeigen, dass ihre Konvergenzrate auch bei Verwendung eines ungenauen Orakels erhalten bleibt. Darüber hinaus zeigen wir, dass es möglich ist, diese Methoden im Rahmen der stochastischen Optimierung effizient zu nutzen. Eine andere Richtung, in der Schnittebenenverfahren nützlich sein können, sind duale Probleme. In der Regel können die Zielfunktion und ihre Ableitungen bei solchen Problemen nur näherungsweise berechnet werden. Daher ist die Unempfindlichkeit der Methoden gegenüber Fehlern in den Subgradienten von großem Nutzen. Als Anwendungsbeispiel schlagen wir eine linear konvergierende duale Methode für einen Markow-Entscheidungsprozess mit Nebenbedienungen vor, die auf der Methode der Vaidya basiert. Wir demonstrieren die Leistungsfähigkeit der vorgeschlagenen Methode in einem einfachen RL Problem. Die Arbeit untersucht auch das Konzept der Genauigkeitszertifikate für konvexe Minimierungsprobleme. Zertifikate ermöglichen die Online-Überprüfung der Genauigkeit von Näherungslösungen. In dieser Arbeit verallgemeinern wir den Begriff der Genauigkeitszertifikate für die Situation eines ungenauen Orakels erster Ordnung. Darüber hinaus schlagen wir einen expliziten Weg zur Konstruktion von Genauigkeitszertifikaten für eine große Klasse von Schnittebenenverfahren vor. Als Nebenprodukt zeigen wir, dass die betrachteten Methoden effizient mit einem verrauschten Orakel verwendet werden können, obwohl sie ursprünglich für ein exaktes Orakel entwickelt wurden. Schließlich untersuchen wir die vorgeschlagenen Zertifikate in numerischen Experimenten und zeigen, dass sie eine enge obere Schranke für das objektive Residuum liefern. / The present thesis studies cutting plane methods, which are a group of iterative algorithms for minimizing a (possibly nonsmooth) convex function over a compact convex set. We consider two prominent examples, namely, the ellipsoid method and Vaidya's method, and show that their convergence rate is preserved even when an inexact oracle is used. Furthermore, we demonstrate that it is possible to use these methods in the context of stochastic optimization efficiently. Another direction where cutting plane methods can be useful is Lagrange dual problems. Commonly, the objective and its derivatives can only be computed approximately in such problems. Thus, the methods' insensitivity to error in subgradients comes in handy. As an application example, we propose a linearly converging dual method for a constrained Markov decision process (CMDP) based on Vaidya's algorithm. We demonstrate the performance of the proposed method in a simple RL environment. The work also investigates the concept of accuracy certificates for convex minimization problems. Certificates allow for online verification of the accuracy of approximate solutions. In this thesis, we generalize the notion of accuracy certificates for the setting of an inexact first-order oracle. Furthermore, we propose an explicit way to construct accuracy certificates for a large class of cutting plane methods. As a by-product, we show that the considered methods can be efficiently used with a noisy oracle even though they were originally designed to be equipped with an exact oracle. Finally, we illustrate the work of the proposed certificates in numerical experiments highlighting that they provide a tight upper bound on the objective residual.

Sejam GI = (VI ,AI) e GM = (VM,AM) dois grafos simples. Um mapeamento de GI para GM é um conjunto de associações, tal que cada vértice de VI está associado a um vértice de VM, e cada aresta de AI está associada a um par de vértices de VM. A cada possível associação é atribuído um custo. O problema de correspondência inexata entre grafos (PCIG) consiste em encontrar um mapeamento de GI para GM, tal que a soma dos custos de suas associações seja mínima. Nesta dissertação, resumimos os resultados encontrados na literatura sobre o PCIG e algumas de suas variações. Os resultados que incluímos aqui tratam sobre a questão de como formular o PCIG e algumas de suas variações, através de programação linear inteira. Provamos alguns resultados de complexidade computacional que relacionam variações do PCIG a problemas clássicos, como isomorfismo e partição de grafos. Fornecemos uma formulação através de programação linear inteira para o PCCA (uma variante do PCIG com conexidade e cobertura de arestas). Mostramos que o PCCA é NP-difícil quando os grafos de entrada são completos ou árvores (chamamos o segundo caso de PCCA para árvores). Apresentamos uma formulação linear inteira e um algoritmo - que é polinomial se o grau máximo dos vértices de VM for limitado por uma constante - para o PCCA para árvores. Mostramos um caso especia em que o PCCA para árvores pode ser resolvido em tempo polinomial. Por último, exibimos alguns resultados experimentais, inclusive com instâncias reais de uma aplicação do problema. / Let GI = (VI ,AI) and GM = (VM,AM) be two simple graphs. A mapping from GI to GM is an association set, such that each vertex in VI is associated to a vertex in VM, and each edge in AI is associated to a pair of vertices of VM. A cost is defined to each possible association. The inexact graph correspondence problem (IGCP) consists in finding a mapping from GI to GM, such that the sum of its associations costs is minimized. In this dissertation, we summarize the results found in the literature about the IGCP and some variations. The results included here address the question of how to formulate the IGCP and some variations, using integer linear programming. We prove some computational complexity results which relate IGCP variations with classical problems, like graph isomorphism and partitioning. We give an integer linear programming formulation to the ICEC (IGCP with connectivity and edges cover). We show that the ICEC is NP-hard when the input graphs are complete or trees (we call the second case ICEC for trees). We introduce an integer linear formulation and an algorithm - which has polynomial running time if the vertices of VM have maximum degree bounded by a constant - to the ICEC for trees. We show a especial case in which the ICEC for trees can be solved in polynomial time. Finally, we present some experimental results, also with instances of a real application of the problem.

[pt] Esta dissertação apresenta novos algoritmos aproximados e uma abordagem exata para a resolução de um problema de correspondência inexata de grafos. O problema considerado é o de correspondência entre um grafo representando um modelo genérico e outro representando dados a serem reconhecidos. Assumi-se que o grafo dos dados possui mais vértices que o do modelo. A motivação para o estudo desse problema vem de problemas de reconhecimento de cenas, que consistem na caracterização dos objetos envolvidos em uma determinada cena, assim como das relações existentes entre eles. Uma aplicação para este problema na área de reconhecimento de imagens médicas é a de efetuar-se o reconhecimento de estruturas 3D do cérebro humano, a partir de imagens obtidas por ressonância magnética. Tais imagens são previamente processadas por algum método de segmentação automática e o processo de reconhecimento consiste na busca da correspondência estrutural entre a imagem e um modelo genérico, tipicamente definido como um atlas de imagens médicas. Foram propostos novos algoritmos aproximados, tais como um algoritmo construtivo guloso aleatorizado, um procedimento de reconexão de caminhos e um GRASP que combina estes com uma técnica de busca local. Além disso, foi proposta uma formulação original do problema como um problema de programação linear inteira, que permitiu a resolução de algumas instâncias de forma exata. / [en] This dissertation presents new approximation algorithms and an exact approach to the solution of an inexact graph matching problem. The problem consists in finding the best match between a generic model graph and a graph representing an image, the latter with more nodes than the former. The motivation for studying this problem comes from a scene recognition problem, which consists in characterizing objects involved in a given scene and the relationships between them. An application of this problem appears in the analysis of medical images and consists in recognizing 3-dimensional structures in the human brain using images obtained by magnetic resonance. Such images must be previously processed by an automatic segmentation method and the recognition process consists in the search of an structural matching between the image and a generic model, typically defined as an atlas of medical images. New heuristics are proposed, such as a greedy randomized construction algorithm, a path relinking procedure and a GRASP heuristic that combines them with a local search technique. Furthermore, an original integer formulation of the problem based on integer multicommodity flows is proposed, which makes possible the exact solution of medium- sized instances.

Verification of knowledge-bases is a critical step to ensure the quality of a knowledge-based system. The success of these systems depends heavily on how qualitative the knowledge is. Manual verification is however cumbersome and error prone, especially for large knowledge-bases. This thesis provides a design theory, based upon the suggested framework by Gregor and Jones (2007). The theory proposes a general design of automated verification tools, which have the abilities of verifying heuristic knowledge in rule-based systems utilizing certainty factors. Included is a verification of completeness and consistency technique customized to this class of knowledge-based systems. The design theory is instantiated in a real-world verification tool development project at Uppsala University. Considerable attention is given to the design and implementation of this artifact – uncovering issues and considerations involved in the development process. For the knowledge management practitioner, this thesis offers guidance and recommendations for automated verification tool development projects. For the IS research community, the thesis contributes with extensions of existing design theory, and reveals some of the complexity involved with verification of a specific rule-based system utilizing certainty factors.

Submitted by Cláudia Bueno (claudiamoura18@gmail.com) on 2015-10-29T19:04:41Z No. of bitstreams: 2 Tese - Tiberio Bittencourt de Oliveira Martins.pdf: 1155588 bytes, checksum: add1eac74c4397efc29678341b834448 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-11-03T14:25:04Z (GMT) No. of bitstreams: 2 Tese - Tiberio Bittencourt de Oliveira Martins.pdf: 1155588 bytes, checksum: add1eac74c4397efc29678341b834448 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-11-03T14:25:04Z (GMT). No. of bitstreams: 2 Tese - Tiberio Bittencourt de Oliveira Martins.pdf: 1155588 bytes, checksum: add1eac74c4397efc29678341b834448 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-06-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Apresentamos, nesta tese, uma an álise da convergência do m étodo de Newton inexato com tolerância de erro residual relativa e uma an alise semi-local de m etodos de Newton robustos exato e inexato, objetivando encontrar uma singularidade de um campo de vetores diferenci avel de nido em uma variedade Riemanniana completa, baseados no princ pio majorante a m invariante. Sob hip oteses locais e considerando uma fun ção majorante geral, a Q-convergância linear do m etodo de Newton inexato com uma tolerância de erro residual relativa xa e provada. Na ausência dos erros, a an alise apresentada reobtem o teorema local cl assico sobre o m etodo de Newton no contexto Riemanniano. Na an alise semi-local dos m etodos exato e inexato de Newton apresentada, a cl assica condi ção de Lipschitz tamb em e relaxada usando uma fun ção majorante geral, permitindo estabelecer existência e unicidade local da solu ção, uni cando previamente resultados pertencentes ao m etodo de Newton. A an alise enfatiza a robustez, a saber, e dada uma bola prescrita em torno do ponto inicial que satifaz as hip oteses de Kantorovich, garantindo a convergência do m etodo para qualquer ponto inicial nesta bola. Al em disso, limitantes que dependem da função majorante para a taxa de convergência Q-quadr atica do m étodo exato e para a taxa de convergência Q-linear para o m etodo inexato são obtidos. / A local convergence analysis with relative residual error tolerance of inexact Newton method and a semi-local analysis of a robust exact and inexact Newton methods are presented in this thesis, objecting to nd a singularity of a di erentiable vector eld de ned on a complete Riemannian manifold, based on a ne invariant majorant principle. Considering local assumptions and a general majorant function, the Q-linear convergence of inexact Newton method with a xed relative residual error tolerance is proved. In the absence of errors, the analysis presented retrieves the classical local theorem on Newton's method in Riemannian context. In the semi-local analysis of exact and inexact Newton methods presented, the classical Lipschitz condition is also relaxed by using a general majorant function, allowing to establish the existence and also local uniqueness of the solution, unifying previous results pertaining Newton's method. The analysis emphasizes robustness, being more speci c, is given a prescribed ball around the point satisfying Kantorovich's assumptions, ensuring convergence of the method for any starting point in this ball. Furthermore, the bounds depending on the majorant function for Q-quadratic convergence rate of the exact method and Q-linear convergence rate of the inexact method are obtained.