In this document, we study the nonnegative least squares primal-dual method for solving linear programming problems. In particular, we investigate connections between this primal-dual method and the classical Hungarian method for the assignment problem. Firstly, we devise a fast procedure for computing the unrestricted least squares solution of a bipartite matching problem by exploiting the special structure of the incidence matrix of a bipartite graph. Moreover, we explain how to extract a solution for the cardinality matching problem from the nonnegative least squares solution. We also give an efficient procedure for solving the cardinality matching problem on general graphs using the nonnegative least squares approach. Next we look into some theoretical results concerning the minimization of p-norms, and separable differentiable convex functions, subject to linear constraints described by node-arc incidence matrices for graphs. Our main result is the reduction of the assignment problem to a single nonnegative least squares problem. This means that the primal-dual approach can be made to converge in one step for the assignment problem. This method does not reduce the primal-dual approach to one step for general linear programming problems, but it appears to give a good starting dual feasible point for the general problem.

Nosso objetivo com este trabalho é contribuir para o aperfeiçoamento da ação educativa do professor de matemática na Educação Básica, tanto em formação inicial quanto em formação continuada. Apresentamos algumas abordagens elementares para estudo de Máximos e Mínimos que utilizam conteúdos próprios dos anos finais do Ensino Fundamental e do Ensino Médio embasados principalmente na obra Maxima and Minima without Calculus (NIVEN, 1981). Discutimos os conceitos de Conhecimento Especializado e de Horizontes de Conteúdo Matemático como justificativa para a relevância do uso deste material, que foram cunhados por pesquisadores da Universidade de Michigan, liderados por Deborah Ball no artigo Content Knowledge for Teaching: What Makes it Special? (2008). Trazemos uma análise crítica da abordagem utilizada para o tema em alguns livros didáticos de Ensino Médio. Discorremos sobre os quatro conceitos de Médias aritmética, geométrica, harmônica e quadrática partindo de problemas que originaram tais conceitos. Mostramos ainda como podem ser naturalmente associados a medidas de segmentos definidos em quadrados, trapézios e semicírculos que evidenciam claramente certas desigualdades entre elas. A seguir, como aplicação de produtos notáveis e trinômios do segundo grau, apresentamos problemas algébricos e geométricos envolvendo máximos e mínimos e discutimos suas soluções. Estabelecemos e provamos algebricamente as desigualdades entre as quatro médias (de até quatro números positivos), que são aplicadas para a determinação de pontos de máximo ou mínimo de funções variadas em problemas contextualizados. Por fim generalizamos e provamos as desigualdades entre as médias para n números positivos e desenvolvemos várias outras aplicações. / This work intends to be a contribution to the improvement of the educational action of mathematics school teachers in both initial or continuous formation. We present some elementary approaches for the study of Maxima and Minima that use final years of Elementary and High School contents only, mainly based on Ivan Nivens book Maxima and Minima without Calculus (NIVEN, 1981). We discuss the concepts of Specialized and Horizons Knowledge of Mathematical Content as a justification for the relevance of the use of this material, which were been introducted by the University of Michigans researchers, led by Deborah Ball, in the article - Content Knowledge for Teaching: What Makes it Special? (2008). We bring a critical analysis of the approach employed for the topic (maxima and minima) in some high school textbooks. We discuss the four concepts of averages - arithmetic, geometric, harmonic and quadratic - starting from problems that originated them. We also show how they can be naturally associated with measures of segments defined in squares, trapezoids and semicircles so that we can clearly visualise certains inequalities between them. Next, as an application of notable products and of second degree trinomials, we present algebraic and geometric problems of maxima or minima and discuss their solutions. We establish and prove algebraically the inequalities between the four averages (up to four positive numbers), which are applied to determine maximum or minimum points of varied functions in contextualized problems. Finally we generalize and prove the averages inequalities for n positive numbers and we develop several applications.

Indiana University-Purdue University Indianapolis (IUPUI) / Evolutionary testing (ET) techniques (e.g., mutation, crossover, and natural selection) have been applied successfully to many areas of software engineering, such as error/fault identification, data mining, and software cost estimation. Previous research has also applied ET techniques to performance testing. Its application to performance testing, however, only goes as far as finding the best and worst case, execution times. Although such performance testing is beneficial, it provides little insight into performance characteristics of complex functions with multiple branches. This thesis therefore provides two contributions towards performance testing of software systems. First, this thesis demonstrates how ET and genetic algorithms (GAs), which are search heuristic mechanisms for solving optimization problems using mutation, crossover, and natural selection, can be combined with a constraint solver to target specific paths in the software. Secondly, this thesis demonstrates how such an approach can identify local minima and maxima execution times, which can provide a more detailed characterization of software performance. The results from applying our approach to example software applications show that it is able to characterize different execution paths in relatively short amounts of time. This thesis also examines a modified exhaustive approach which can be plugged in when the constraint solver cannot properly provide the information needed to target specific paths.