CEOC Seminars 2005 December 9, 2005 Computação Simbólica de Leis de Conservação no Cálculo das Variações e Controlo Óptimo - proposta de um novo package de funções para o Maple Resumo: Os problemas de optimização dinâmica (em espaços de funções) tratados pelo cálculo das variações e pelo controlo óptimo, são normalmente resolvidos por recurso a equações diferenciais não lineares de difícil resolução, que derivam das condições necessárias de Euler-Lagrange e do Princípio do Máximo de Pontryagin, respectivamente. Uma forma de as simplificar consiste em obter leis de conservação (primeiros integrais dessas equações diferenciais). Se em áreas como a Física e a Economia a questão da existência de leis de conservação é resolvida de forma bastante natural, a própria aplicação sugerindo as leis de conservação (e.g. conservação de energia, conservação da quantidade de movimento, conservação do rendimento, etc.), de um ponto de vista estritamente matemático, o processo de obtenção das leis de conservação ou, até mesmo, a demonstração de que elas existem (ou não), deixa de ser uma questão óbvia. Nesta apresentação mostramos como um sistema de computação algébrica como o Maple pode ser muito útil na abordagem a estas questões. Concretamente, propomos um package de funções computacionais simbólicas, por nós desenvolvidas, que permitem, de uma forma sistemática e automática, identificar leis de conservação, tanto no controlo óptimo como no contexto clássico do cálculo das variações. December 2, 2005 Aerodinâmica do movimento em meios rarefeitos e transporte de massa Resumo: Estudamos problemas de resistência mínima e máxima ao movimento de corpos em meios rarefeitos (nas condições do chamado "fluxo livre de moleculas") com reflexões absolutamente elásticas. O meio pode ter temperatura nula ou não nula; o corpo pode estar em rotação, uniforme ou não uniforme. Vai ser demonstrado que este tipo de problemas reduz-se ao problema de Monge-Kantorovich de transporte óptimo de massa. November 25, 2005 Maximizing Surprise Abstract: The Surprise Examination or Unexpected Hanging Paradox has long Fascinated mathematicians and philosophers, as the number of publications devoted to it attests. In this talk, the optimization problems arising from an information theoretic avoidance of the Paradox are examined and solved. They provide a very satisfactory application of both the Kuhn-Tucker theory and of various classical inequalities and estimation techniques. Although the necessary convex analytic concepts are recalled in the course of the talk, some elementary knowledge of optimization is assumed. Those unfamiliar with this background may simply ignore a couple of proofs and few technical details. November 18, 2005 Bem iluminar um ponto em tempo linear e o diagrama de Voronoi MIR Resumo: Pretende-se dar continuação ao estudo da 1-boa iluminação de alcance limitado como uma variante dos problemas clássicos de iluminação em Geometria Computacional. Com este propósito, será apresentado um algoritmo linear para 1-bem iluminar um ponto, assim como para encontrar o alcance mínimo das luzes para esse efeito. Será também estudado o diagrama de Voronoi MIR que divide o espaço das luzes em várias regiões 1-bem iluminadas. Será proposto um algoritmo cúbico para a sua construção, além da apresentação de várias propriedades e exemplos do diagrama final. November 11, 2005 Estruturas de Dirac e algebróides de Lie Resumo: Apresentamos as principais noções e propriedades destas estruturas geométricas, bem como algumas das suas aplicações. November 4, 2005 Modelos de Programação Inteira em Gestão de Florestas com Restrições Espaciais Resumo: Os interesses mais recentes pela qualidade do ambiente, por exemplo, protecção da vida selvagem, redução da erosão, aumento da qualidade da água e preservação da beleza natural, adicionaram condições espaciais à gestão das florestas para produção de madeira. Uma condição espacial bem conhecida requere que as áreas das clareiras resultantes do corte raso das árvores não sejam superiores a um dado valor. Existem duas abordagens de modelação principais para limitar as áreas das clareiras no escalonamento do corte raso. A abordagem clássica – unit restriction model (URM) – considera que a área de duas unidades de gestão adjacentes excede a área de clareira máxima, não sendo possível intervir nas duas unidades de gestão no mesmo período. Na segunda abordagem - area restriction model (ARM) – as áreas das unidades de gestão podem ser bastante inferiores à área de clareira máxima e, assim, o corte raso de duas unidades de gestão adjacentes pode não constituir uma violação. O ARM melhora significativamente a qualidade das soluções de gestão, dada a sua grande flexibilidade. No entanto, é bastante mais difícil de resolver porque é mais combinatório. Nesta apresentação, resumem-se as abordagens exactas em programação inteira descritas na literatura e descreve-se uma nova abordagem para o ARM. Apresentam-se testes computacionais com florestas reais e hipotéticas. October 14, 2005 Some results concerning the thermistor Problem Abstract: In this work, we are interested with the so-called thermistor problem described by a system of non-linear partial differential equations with quadratical growth in the gradient. The mathematical study of this system allow us to obtain the existence and, in some cases, the uniqueness, of a physical admissible solution. On the other hand, the system can be reduced to a single, but still realistic non local parabolic equation. By using a dynamical systems approach, some existence and uniqueness results are proved and the existence of a compact attractor is shown. July 29, 2005 Parametric Optimal Control Problems Abstract: The problem of dependence of solutions to optimal control problems on a parameter is a subject of intensive studies. The reason for this lies in the fact that while modeling complex control systems perturbations and uncertainties appearing in dynamic models may be modeled by parameters entering the dynamic equations, boundary conditions, state and control constraints. Sensitivity analysis of the solutions depending on parameters allows to evaluate the changes in the solutions caused by “small” perturbations in the parameters. Moreover, studies of dependence of solutions on the parameters form the basis for the methods of constructing solutions of extremal problems by means of path-following methods and are used for constructing feedback controls. Most of the papers on the subject perform the sensitivity analysis and investigate the dependence of solutions of optimal control problems on a parameter under assumption that the solution of the “unperturbed” system is regular for all values of the parameter. However, in feedback control and in path-following methods there occur situations when it is necessary to know the behaviour of solutions in a neighborhood of an irregular (bifurcation) point. Therefore the knowledge of the behaviour of solutions in a neighborhood of irregular points is of major importance. The paper is devoted to the construction of solutions to a family of one parametric optimal control problems with state and control constraints. The main attention is paid to irregular (bifurcation) points. We investigate general case where we do not imply any restrictions on the order of the system and on the number of switching points of the optimal control and on an order of irregularity. The outline of the talk is the following: Problem statement Solution structure and defining elements Properties of solutions to control problems in a neighborhood of regular point. Properties of the solutions in a neighborhood of an irregular point. - construction of new Lagrange vector - construction of new solution structure anf defining elements - constructing solutions to perturbed control problems Generalizations July 20, 2005 Control theory on time scales Abstract: A time scale is a closed subset of the set of real numbers. It serves as a model of time. If it is the whole set of reals, we have the continuous time, while for the set of integers we get the discrete time. One can imagine more complicated models, when time is partly discrete and partly continuous. The differential calculus on time scales is a generalization of the standard differential calculus on the real line and the calculus of finite differences. Thus the theory of differential equations on time scales unifies differential and difference equations. It is a starting point for the control theory on time scales. This theory includes the standard theories of continuous-time systems and discrete-time systems, but allows also for mixed cases where time changes its nature. The talk will contain a short introduction to the calculus on time scales and an overview of recent results and the current research on control systems on time scales. July 12, 2005 Counting Dyck paths with constraints Abstract: A Dyck path is a sequence of up-steps and down-steps of small sizes such that the end is at the same level 0 as the beginning and no step leads to a negative level. A peak is a local maximum of the level. We show how to count Dyck paths with some constraints on the number of the peaks and their levels. A special case is proposed as problem 11150 in American Mathematical Monthly. June 22, 2005 Using Geometric Programming for Solving Nonstochastic Uncertainty Models in Finance Abstract: A class of models is presented that has its origins to nonstochastic uncertainty modeling that began with Norbert Wiener in the 40's and pioneered by A. B. Kurzhanski in the Russian literature. In our approach the underlying law of motion of a financial instrument is a linear differential equation under uncertainty with perturbations for the financial instrument generating the time series. Instead of stochastic characteristics of uncertainty being known, only sets of possible values of perturbations are known, where a finite set of observed data points is taken as inputs into the system. Analogous to the classical Vasicek SDE the dependent variable represents an integrand (the "forward rate") in a continuous time discounting mechanism involving its integral in exponentiation. This structure establishes a connection to geometric programming of Duffin et al.(1967), and we obtain a two-sided geometric programming approximation problem. Properties of a very efficient primal-dual interior point algorithm for solving the primal and dual geometric programs simultaneously are reviewed based upon joint work with co-authors during the mid.90's in Iowa City. Numerical results are presented for the problem of extracting the spot interest rate curve from Government Bills and coupon-paying Notes & Bonds data. Finally, when the law of motion is of Dothan-type we obtain a GP model that can be used for tracking any financial series accurately. May 20, 2005 Alguns problemas de optimização em bilhares: resultados analíticos e numéricos Resumo: A partir de um estudo dos problemas de resistência máxima e mínima de corpos rugosos, introduzem-se um majorante e um minorante obtidos analiticamente. Adicionalmente, apresentam-se resultados decorrentes da simulação numérica. May 13, 2005 Optimization and Highly Informative Graph Invariants Abstract: It is known that graph invariants, which contain a great quantity of information on graph structure (for example, spectral invariants), are obtained by solving some extremal problems on graphs. Recently, such highly informative graph invariants are applied in solving optimization problems on graphs (e.g., the travelling salesman problem (TSP)). Using these paradigms, several relations, interconnections and interactions between graph theory and mathematical programming are described. A model of TSP based on semidefinite programming and algebraic connectivity of graphs is described. A class of relaxations of this TSP model is defined and some solution techniques based on this class are proposed. Several examples of graph invariants defined by some kind of optimization tasks are also presented. Using several spectrally based graph invariants we treat the graph isomorphism problem. May 11, 2005 An Introduction to the Theory of Graph Spectra Abstract: The spectrum of a graph is defined as the spectrum of a matrix associated to the graph; in most cases it is the adjacency matrix although some other graph matrices are used. The beginnings of the theory of graph spectra are connected with the first mathematical paper in the subject, published by L. Collatz and U. Sinogowitz in 1957. The background of the subject is the Perron-Frobenius theory of non-negative matrices. Several techniques for treating graph theory problems using eigenvalues have been developed: e.g., the interlacing theorem, the use of graph eigenspaces, the star complement technique and many others. There are many connections of the theory of graph spectra with other parts of combinatorics as well as with algebra and geometry. The theory can be classified also as a part of algebraic graph theory and of algebraic combinatorics. It is very much used in theoretical chemistry but also has some relevance to other applied fields, e.g. physics, electrical engineering and computer science. April 29, 2005 Teorema de Noether Não-Conservativo em Controlo Óptimo Resumo: Apresentamos, no contexto do controlo óptimo, uma extensão do Teorema de Noether para sistemas dinâmicos sob acção de forças não conservativas. Como corolário obtemos as quantidades conservadas obtidas por Jing-Li Fu e Li-Qun Chen em 2003 (Phys.Lett.A 317). April 15, 2005 Analysis of vibrations in some machine units with discrete parameters Abstract: Vibrations in the controlled machine units with discrete parameters are studied. The mathematical model is a system of ordinary differential equations of the fifth order with nonlinear boundary conditions. For the investigations the averaging method is applied, which allows to determine conditions of stability of both one-frequency stationary modes and biharmonic ones. Amplitudes of the vibrations, as well as the character of transient to the stationary modes, are obtained. Dependence of stationary modes on the different parameters of the system is analyzed. Using feedbacks, one can optimize functioning of the machine units with discrete parameters. The results may be applied in industry for the design of new improved technical systems. April 8, 2005 Leis de Conservação para minimizantes mal comportados do Cálculo das Variações e Controlo Óptimo Resumo: O estudo de problemas de controlo óptimo com controlos a tomar valores em regiões não-limitadas é uma área de grande investigação actual, por exemplo em aplicações envolvendo "materiais inteligentes". Quando não existem restrições aos valores das variáveis de controlo, como acontece no cálculo das variações, é bem conhecido que existe a possibilidade dos minimizantes não satisfazerem o Princípio Máximo de Pontryagin ou as condições necessárias de Euler-Lagrange. Tal possibilidade é devida ao facto das hipóteses da teoria da existência precisarem de ser complementadas com condições adicionais de regularidade de modo aos argumentos que conduzem às condições necessárias de optimalidade serem válidos. Não obstante a discrepância entre as hipóteses de ambas as teorias, J. Ball demonstrou em 1984 que, para problemas invariantes em relação à variável independente, a lei de conservação de energia (conservação do Hamiltoniano) ainda é válida para minimizantes que não satisfazem a equação de Euler-Lagrange. Recentemente, em 2002, G. Francfort e J. Sivaloganathan generalizaram o resultado de Ball, dando exemplos de aplicação em hiper-estasticidade. Nesta palestra generalizamos os resultados encontrados na literatura para o contexto mais geral do controlo óptimo, demonstrando como obter leis de conservação válidas para minimizantes que não satisfazem necessariamente o Princípio de Máximo de Pontryagin. April 1, 2005 Bases de Gröbner e Matróides Orientados Resumo: Os números de intersecção e de enlace em matróides orientados, que constituem uma generalização abstracta e combinatória dos conhecidos números de intersecção e de enlace em espaços euclidianos, são definidos como funções polinomiais por polinómios no ideal em que os matróides orientados podem ser vistos como variedades algébricas; neste contexto, torna-se importante o conhecimento de uma Base de Gröbner para o ideal da variedade dos quirotopes. March 18, 2005 Quantum analogue of Newton's problem of the body of least resistance Abstract: We shall discuss the Quantum (or Wave) analogue of Newton's problem of the body of least resistance. We define mathematically resistance or the total momentum transmitted to the body by the flow of quantum particles (or acoustic wave). Using recently obtained (our) results we point out some physical differences between quantum and classical case. More exactly, we shall discuss explicit formula for resistance of a hard sphere and the problem of scattering by obstacle of arbitrary shape in case of small velocities (low frequencies). March 11, 2005 Casamentos estáveis e colocação de professores Resumo: O problema dos casamentos estáveis (stable marriage problem) é um problema clássico de optimização combinatória. Visa a determinação dum emparelhamento estável entre n homens e n mulheres: isto é, n casamentos monogâmicos tais que nenhum homem prefere uma mulher que não é a sua e que o prefere também relativamente ao seu marido. Neste seminário serão abordadas variantes deste problema com aplicações e concursos para afectação de pessoas (por exemplo, estudantes a cursos universitários e professores a escolas). March 4, 2005 Algumas Variantes à Definição Clássica de Iluminação em Geometria Computacional Resumo: Pretende-se introduzir o conceito de t-boa iluminação como uma variante dos problemas clássicos de iluminação em Geometria Computacional. Para este fim, vão ser apresentadas as definições clássicas de iluminação e também a definição de Ntafos de iluminação de alcance limitado. Serão estudados algoritmos para o cálculo de 1-boa iluminação e 2-boa iluminação sem obstáculos no plano, assim como um algoritmo para o cálculo da 1-boa iluminação quando existe um óbstaculo convexo no plano. Vai ser introduzida uma nova variante ao conceito da t-boa iluminação: a 1-boa iluminação de alcance limitado. Serão focados os problemas da 1-boa iluminação de um ponto, de um segmento e de uma linha poligonal fechada para focos de alcance limitadom para os quais serão propostos dois algoritmos em desenvolvimento. February 25, 2005 Trajectos Óptimos em Redes com Parâmetros Aleatórios Resumo: Nesta apresentação o problema considerado é a optimização do valor esperado de uma dada função utilidade numa rede aleatória orientada. Os arcos dessa rede têm associadas distâncias (custos, tempos) que são variáveis aleatórias reais. O que se pretende é determinar o trajecto óptimo (ou não dominado) de um nó inicial para um nó terminal que optimiza o valor esperado da função utilidade considerada. Se os parâmetros associados aos arcos da rede forem variáveis aleatórias contínuas então a formulação teórica e os resultados computacionais são baseados em modelos bi-critério. Caso os parâmetros sejam variáveis aleatórias discretas a solução, apresentada para o problema, é uma generalização das equações de Bellman utilizadas para a determinação do trajecto óptimo determinístico. February 18, 2005 Aproximação Estocástica Resumo: Pretende-se estimar o zero, ou um dos zeros, de uma função, em que a medida é sujeita a uma perturbação aleatória, com recurso a algoritmos iterativos. Para este fim, vão ser apresentados os algoritmos: de Robbins-Monroe, de medianização, e de Kesten, para os quais as propriedades assimptóticas estão bem estudadas e são optimais. Serão apresentados dois novos algoritmos desenvolvidos com vista a melhorar a velocidade de convergência mas quando o processo se encontra inicialmente em 'regime transitório'. O primeiro é uma generalização do algoritmo de Kesten (Plakhov e Cruz, 2004) e o segundo, motivado por técnicas heurísticas de redes neuronais, usa adaptação multiplicativa do passo (Plakhov e Cruz, 2004). Resultados assimptóticos e exemplos numéricos vão ser expostos. February 11, 2005 Analysis of Vibrations in Large Flexible Hybrid Systems Abstract: The mathematical model of a real flexible elastic system with distributed and discrete parameters is considered. It is a partial differential equation with non-classical boundary conditions. Complexity of the boudary conditions results in the impossibility to find exact analytical solutions. To address the problem, we use the asymptotical method of small parameter together with the numerical method of normal fundamental systems of solutions. These methods allow us to invetigate vibrations, and a technique for determination of complex eigenvalues of the considered boundary value problem is developed. The conditions, at which vibration processes of different character take place, are defined. Dependence of the vibration frequencies on physical parameters of the hybrid system is studied. We show that introduction of different feedbacks into the system allow one to control the frequency spectrum, in which excitation of vibrations is possible. February 4, 2005 Forest Trees for online data Abstract: In this talk we present a system for induction of forest of functional trees from data streams able to detect concept drift. The Ultra Fast Forest of Trees (UFFT) is an incremental algorithm, that works online, processing each example in constant time, and performing a single scan over the training examples. It uses analytical techniques to choose the splitting criteria, and the information gain to estimate the merit of each possible splitting-test. For multi-class problems the algorithm builds a binary tree for each possible pair of classes, leading to a forest of trees. Decision nodes and leaves may contain naive-Bayes classifiers playing different roles during the induction process. Naive-Bayes in leaves are used to classify test examples. Naive-Bayes in inner nodes can be used as a multivariate splitting-tests if chosen by the splitting criteria, and used to detect changes in the class-distribution of the examples that traverse the node. This methodology was tested with artificial and real-world data sets. The experimental results show a very good performance in comparision to a batch decision tree learner, and high capacity to detect drift in the distribution of the examples. January 14, 2005 Topologia Digital Resumo: A topologia digital estuda as propriedades topológicas de imagens binárias. Nesta palestra apresentam-se as definições básicas da topologia digital e algumas das suas aplicações. Adicionalmente, introduzem-se certas relações entre topologias digitais e reticulados. January 12, 2005 Optimal Transportation with costs changing concavity Abstract: This lecture concerns a classical optimization problem formulated by Monge in 1781. Motivated by economics, the problem is described as follows: Given a distribution f of iron mines throughout the countryside, and a distribution g of factories which require iron ore, decide which mines should supply ore to each factory in order to minimize the total transportation costs. Taking the mine and factories to be distributed continuously throughout Euclidian space - or a Riemannian manifold - and the cost per ton of ore transported from the mine at x to the factory at y to be specified as a function of the distance, yields a problem with deep connections to geometry and non-linear PDE. For costs c(x,y) = h(d(x,y)) given by strictly convex or strictly concave increasing functions h >= 0 of the distance, the solution takes the form of a measure-preserving map between the measures f and g. It is unique, and uniquely characterized by its geometry. Even on the line this mapping may be intricate. However, when the concavity of the costs changes signs, much less is known. We describe some results and examples which arise from problems in economics and computer vision. January 11, 2005 Optimization with convexity constraints: numerical methods January 7, 2005 Matroides de Coxeter - diferentes caracterizações Resumo: Serão apresentadas diferentes caracterizações de Matroides de Coxeter, focando algumas abordagens para o seu estudo e as suas interligações a outros assuntos. Procurar-se-á indicar a situação actual, apontando o que é conhecido e o muito que falta descobrir.