Otimização Não Linear de Mínimos Quadrados

O problema de otimização de mínimos quadrados e apresentado como uma classe importante de problemas de minimização sem restrições. A importância dessa classe de problemas deriva das bem conhecidas aplicações a estimação de parâmetros no contexto das analises de regressão e de resolução de sistemas de equações não lineares. Apresenta-se uma revisão dos métodos de otimização de mínimos quadrados lineares e de algumas técnicas conhecidas de linearização. Faz-se um estudo dos principais métodos de gradiente usados para problemas não lineares gerais: Métodos de Newton e suas modificações incluindo os métodos Quasi-Newton mais usados (DFP e BFGS). Introduzem-se depois métodos específicos de gradiente para problemas de mínimos quadrados: Gauss-Newton e Levenberg-Larquardt. Apresenta-se uma variedade de exemplos selecionados na literatura para testar os diferentes métodos usando rotinas MATLAB. Faz-se uma an alise comparativa dos algoritmos baseados nesses ensaios computacionais que exibem as vantagens e desvantagens dos diferentes métodos.

On the throughput-WIP trade-off in queueing systems, diminishing returns and the threshold property: A linear programming approach

We present a new unifying framework for investigating throughput-WIP(Work-in-Process) optimal control problems in queueing systems,based on reformulating them as linear programming (LP) problems withspecial structure: We show that if a throughput-WIP performance pairin a stochastic system satisfies the Threshold Property we introducein this paper, then we can reformulate the problem of optimizing alinear objective of throughput-WIP performance as a (semi-infinite)LP problem over a polygon with special structure (a thresholdpolygon). The strong structural properties of such polygones explainthe optimality of threshold policies for optimizing linearperformance objectives: their vertices correspond to the performancepairs of threshold policies. We analyze in this framework theversatile input-output queueing intensity control model introduced byChen and Yao (1990), obtaining a variety of new results, including (a)an exact reformulation of the control problem as an LP problem over athreshold polygon; (b) an analytical characterization of the Min WIPfunction (giving the minimum WIP level required to attain a targetthroughput level); (c) an LP Value Decomposition Theorem that relatesthe objective value under an arbitrary policy with that of a giventhreshold policy (thus revealing the LP interpretation of Chen andYao's optimality conditions); (d) diminishing returns and invarianceproperties of throughput-WIP performance, which underlie thresholdoptimality; (e) a unified treatment of the time-discounted andtime-average cases.

Exact tests for correlation and for the slope in simple linear regressions without making assumptions

We present an exact test for whether two random variables that have known bounds on their support are negatively correlated. The alternative hypothesis is that they are not negatively correlated. No assumptions are made on the underlying distributions. We show by example that the Spearman rank correlation test as the competing exact test of correlation in nonparametric settings rests on an additional assumption on the data generating process without which it is not valid as a test for correlation.We then show how to test for the significance of the slope in a linear regression analysis that invovles a single independent variable and where outcomes of the dependent variable belong to a known bounded set.

A test of the predictive validity of non-linear QALY models using time trade-off utilities

This paper presents a test of the predictive validity of various classes ofQALY models (i.e., linear, power and exponential models). We first estimatedTTO utilities for 43 EQ-5D chronic health states and next these states wereembedded in health profiles. The chronic TTO utilities were then used topredict the responses to TTO questions with health profiles. We find that thepower QALY model clearly outperforms linear and exponential QALY models.Optimal power coefficient is 0.65. Our results suggest that TTO-based QALYcalculations may be biased. This bias can be avoided using a power QALY model.

Implementing TURF analysis through binary linear programming

This paper introduces the approach of using Total Unduplicated Reach and Frequency analysis (TURF) to design a product line through a binary linear programming model. This improves the efficiency of the search for the solution to the problem compared to the algorithms that have been used to date. The results obtained through our exact algorithm are presented, and this method shows to be extremely efficient both in obtaining optimal solutions and in computing time for very large instances of the problem at hand. Furthermore, the proposed technique enables the model to be improved in order to overcome the main drawbacks presented by TURF analysis in practice.

Erosão dos solos em Cabo Verde - Estudos dos Processos e Quantificação de Três Bacias na Ilha de Santiago

L’archipel du Cap Vert constitué de 10 îles volcaniques appartient à la zone sahélienne qui s’étend de l’atlantique jusqu’à la mer rouge. Depuis, plusieurs décennies le Cap Vert est affecté par la désertification causée en grande partie par la récession climatique et l’érosion des sols. Ces facteurs, associés à la forte pression anthropique sur les ressources, à l’orographie accidentée et à des pluies tropicales parfois diluviennes, provoquent de sérieuses pertes du patrimoine foncier. Cependant, depuis son Indépendance en 1975, le Gouvernement a mené un vaste programme d’arborisation, de restauration des terres et d’aménagement des cours d’eau. Pourtant, très peu de recherches ont été menées pour évaluer les actions de protection et de conservation des sols et des eaux. Par conséquent, il n’existe quasiment pas de données sur la problématique de la dégradation des terres ni de bilans. Dans le cadre de ce travail, nous avons étudié les différents facteurs qui contrôlent l’érosion hydrique des sols. Nous avons plus particulièrement cherché à différencier les effets des activités humaines, notamment agricoles, de ceux des facteurs climatiques comme les précipitations et la génération des écoulements. Nous avons également établi les premiers bilans d’exportations de matières en suspension et en solution dans le contexte de l’archipel du Cap Vert. L’étude a été menée à l’échelle de trois bassins versants de l’ile de Santiago Cap-Vert. Ces trois bassins versant (Longueira, Grande et Godim) sont localisés dans la partie centrale de l’île de Santiago et représentatifs des divers modes d’occupation du sol et des différents climats de l’île. Il existe un gradient climatique entre les trois bassins versants. En effet, Longueira qui présente une superficie de 4,18 km2, une pente moyenne de 47 %, se localise dans une zone humide couverte à 69 % par une forêt et une surface agricole de 17 %. Grande avec une superficie de 1,87 km2, se localise en zone sub humide pour une pente moyenne de 50 %, il est essentiellement agricole. Godim, avec une superficie de 2,0 km2, se localise en zone semi aride, il est particulièrement agricole et sa pente moyenne est de 32 %. Pour ces trois bassins versants, les écoulements de crue à l’exutoire ont été mesurés et échantillonnés de 2004 à 2009. Le bassin versant de Longueira a fait l’objet d’un suivi plus poussé, notamment en termes de fréquence d’échantillonnage et de suivi des écoulements hors crue. Sur chaque échantillon nous avons procédé à la détermination de la concentration des matières en suspension ainsi qu’à l’analyse des éléments majeurs. Les résultats obtenus montrent que l’érosion mécanique dans les 3 bassins versants est caractérisée par une forte variabilité spatiale et temporelle. Sur la période 2005-2009, le bilan moyen annuel pour les bassins versants de Longueira, Grande et Godim est de : 4266, 157 et 10,1 t.km2.an-1 respectivement. La saison humide 2006 a été la plus érosive pour l’ensemble des trois bassins versants et particulièrement dans Longueira avec 2 crues exceptionnelles qui ont généré une concentration moyenne de matières en suspension supérieure à 100 g/l. En revanche, les saisons 2005 et 2008 ont été dans l’ensemble peu érosives car les concentrations moyennes ne dépassèrent pas 20 g/l. Par ailleurs, il n’y a pas eu de lames d’eau écoulées pour les saisons 2005 et 2007 pour le bassin de Godim. Sur le bassin de Longueira, l’étude des phénomènes d’hystérésis permet de caractériser chaque crue et de montrer que l’évolution temporelle des exportations de matières en suspension au cours de la saison est fortement influencée par les activités agricoles. En effet, la première crue provoque l’exportation massive des sédiments disponibles et localisés dans le lit du cours d’eau. En conséquence, la seconde est moins exportatrice de sédiments. Un mois après les premières pluies, les activités de sarclage diminuent la densité du couvert végétal et destructurent la partie superficielle des sols, ce qui provoque à nouveau une très forte exportation de sédiments lors de la troisième crue. Les résultats de l’érosion chimique sur le bassin de Longueira indiquent que le taux d’érosion chimique moyen s’élève à 45 t.km2.an-1 avec une forte variabilité temporelle. En effet, les saisons les plus humides de 2006 et 2007 sont les plus exportatrices de matières en solution, alors que 2005 a eu une faible exportation. L’utilisation du modèle de mélanges EMMA (End-Members Mixing Analysis) montre que les écoulements hypodermique et profond, qui alimentent le cours d’eau en éléments dissous, sont les principaux facteurs de l’érosion chimique. On montre ainsi que les écoulements hors crue sont à l’origine de plus de 90% des flux d’érosion chimique. L’écoulement superficiel, qui contribue à environ 70 % du débit du cours d’eau en crue, constitue un facteur de premier plan de l’érosion mécanique des sols.

Restless bandits, linear programming relaxations and a primal-dual index heuristic

We develop a mathematical programming approach for the classicalPSPACE - hard restless bandit problem in stochastic optimization.We introduce a hierarchy of n (where n is the number of bandits)increasingly stronger linear programming relaxations, the lastof which is exact and corresponds to the (exponential size)formulation of the problem as a Markov decision chain, while theother relaxations provide bounds and are efficiently computed. Wealso propose a priority-index heuristic scheduling policy fromthe solution to the first-order relaxation, where the indices aredefined in terms of optimal dual variables. In this way wepropose a policy and a suboptimality guarantee. We report resultsof computational experiments that suggest that the proposedheuristic policy is nearly optimal. Moreover, the second-orderrelaxation is found to provide strong bounds on the optimalvalue.

On heuristic and linear models of judgment: Mapping the demand for knowledge

Research on judgment and decision making presents a confusing picture of human abilities. For example, much research has emphasized the dysfunctional aspects of judgmental heuristics, and yet, other findings suggest that these can be highly effective. A further line of research has modeled judgment as resulting from as if linear models. This paper illuminates the distinctions in these approaches by providing a common analytical framework based on the central theoretical premise that understanding human performance requires specifying how characteristics of the decision rules people use interact with the demands of the tasks they face. Our work synthesizes the analytical tools of lens model research with novel methodology developed to specify the effectiveness of heuristics in different environments and allows direct comparisons between the different approaches. We illustrate with both theoretical analyses and simulations. We further link our results to the empirical literature by a meta-analysis of lens model studies and estimate both human andheuristic performance in the same tasks. Our results highlight the trade-off betweenlinear models and heuristics. Whereas the former are cognitively demanding, the latterare simple to use. However, they require knowledge and thus maps of when andwhich heuristic to employ.

O Primal e o Dual na programação Linear

O tema da Programação Linear, com as suas particularizações do Problema dos Transportes e do Problema da Afectação de Recursos, é hoje estudado em cursos diversos onde uma disciplina de Investigação Operacional esteja presente. Trata-se, em última análise, de um problema de cálculo de extremos condicionados, seja de máximo ou de mínimo, que apresenta características muito particulares e de grande elegância simbólica. Também os Problemas dos Transportes e da Afectação de Recursos se podem resolver como problemas de Programação Linear, através do Algoritmo Simplex, embora seja preferível o recurso a algoritmos próprios, de muitíssimo maior simplicidade: o Algoritmo dos Transportes e o Algoritmo Húngaro, respectivamente. De molde a facilitar a compreensão do que realmente está em jogo, consideram-se aqui dois casos de determinação de extremos e de extremos condicionados, mas ao nível do final do ensino secundário.

Erosão hídrica em diferentes preparos do solo logo após as colheitas de milho e trigo, na presença e na ausência dos resíduos culturais

O preparo do solo, o qual influencia o manejo dos resíduos culturais e a rugosidade superficial, associado ao tipo de cultura utilizada, é um dos fatores que afetam a suscetibilidade do solo à erosão hídrica. Utilizando chuvas simuladas na intensidade constante de 64 mm h-1, com durações suficientes para que o escoamento superficial atingisse taxa constante de descarga, foram avaliados, em Eldorado do Sul (RS), de 1992 a 1994, em condições de campo, os seguintes tratamentos de preparo do solo: semeadura direta, na presença e na ausência dos resíduos recém-colhidos de milho e trigo; escarificação, na presença e na ausência dos resíduos recém-colhidos de milho e trigo + milho logo após a colheita do trigo; e aração + gradagem, na presença e ausência dos resíduos recém-colhidos de milho e trigo + milho logo após a colheita do trigo. Utilizou-se um solo podzólico vermelho-amarelo franco-arenoso e declividade média de 0,066 m m-1. As perdas de solo e água foram fortemente influenciadas pela rugosidade e cobertura superficiais. Na semeadura direta e aração + gradagem, a manutenção dos resíduos culturais na superfície reduziu as perdas de solo em relação à sua remoção manual quase completa. A semeadura direta com os resíduos culturais foi o tratamento mais eficaz na redução da erosão e a aração + gradagem, sem os resíduos, o menos eficaz. A escarificação com os resíduos culturais na superfície apresentou maior perda de solo do que a semeadura direta e aração + gradagem também com os resíduos na superfície. Em geral, as perdas de água por escoamento superficial seguiram o mesmo comportamento das perdas de solo.