Search

An alternative strategy to solve the subproblems of the Method of Moving Asymptotes (MMA) is presented, based on a trust-region scheme applied to the dual of the MMA subproblem. At each iteration, the objective function of the dual problem is approximated by a regularized spectral model. A globally convergent modification to the MMA is also suggested, in which the conservative condition is relaxed by means of a summable controlled forcing sequence. Another modification to the MMA previously proposed by the authors [Optim. Methods Softw., 25 (2010), pp. 883-893] is recalled to be used in the numerical tests. This modification is based on the spectral parameter for updating the MMA models, so as to improve their quality. The performed numerical experiments confirm the efficiency of the indicated modifications, especially when jointly combined.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) Determinar as raízes de uma função polinomial nem sempre é uma tarefa fácil, existem métodos analíticos que podem ser utilizados para determinar as raízes de funções específicas, no entanto, para a maioria das funções polinomiais não existem métodos analíticos ou ainda o método existente pode requerer uma grande quantidade de cálculos. Existem métodos numéricos que buscam uma aproximação para cada raiz das funções polinomiais de modo iterativo, os métodos numéricos apresentam uma solução aproximada tanto quanto se espera que ela seja. Neste trabalho, apresentaremos algumas soluções analíticas e realizaremos uma abordagem sobre os métodos numéricos da bissecção, da falsa posição, da secante e o método numérico de Newton. Tais métodos serão abordados utilizando-se de planilhas eletrônicas de forma que os professores da Educação Básica possam utilizar deste material com estudantes do Ensino Médio. Determine the roots of a polynomial function is not always an easy task, there are analytical methods that can be used to determine the roots of specific functions, however, for most polynomial functions there are no analytical methods or the existing method may require a large number of calculations. There are numerical methods that seek an approximation for each root of the polynomial functions in an iterative way, the numerical methods present an approximate solution as much as one expects it to be. In this work, we will present some analytical solutions and approach the numerical methods of bisection, false position, secant and Newton’s numerical method. Such methods will be addressed using electronic spreadsheets, só that Basic Education teachers can use this material with high school students.

Orientadores: Sandra Augusta Santos, Maria Aparecida Diniz Ehrhardt Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica Resumo: Neste trabalho propusemos o algoritmo PSIFA, do inglês Pattern Search and Implicit Filtering Algorithm, que é um algoritmo sem derivadas desenvolvido para resolver problemas de otimização com restrições lineares e ruído na função objetivo, e que combina elementos do método de busca padrão de Lewis e Torczon (2000) e do método de filtragem implícita de Kelley (2011). Apresentamos a teoria de convergência global para o método, com enfraquecimento de hipóteses, a qual engloba o caso degenerado. Realizamos experimentos numéricos com problemas da literatura e problemas com restrições lineares degeneradas, obtidos definindo o conjunto viável a partir de cones poliedrais 3D com diversos graus de degeneração na solução. O algoritmo também foi testado com uma função objetivo cujo ruído não satisfaz as hipóteses teóricas de convergência do método. Como uma aplicação com ruído inerente foi abordado um problema de identificação de parâmetros, para o qual restrições lineares podem ser consideradas na formulação do problema. Os resultados obtidos pelo PSIFA em todos os experimentos foram comparados com os dos métodos de busca padrão e filtragem implícita, sendo o desempenho da nossa proposta bastante promissor em todas as instâncias testadas Abstract: In this work we have introduced the algorithm PSIFA - Pattern Search and Implicit Filtering Algorithm - which is a derivative-free algorithm that has been designed for linearly constrained problems with noise in the objective function, combining some elements of the pattern search approach of Lewis and Torczon (2000) with ideas from the method of implicit filtering of Kelley (2011). The global convergence analysis is presented, encompassing the degenerate case, under mild assumptions. Numerical experiments with linearly constrained problems from the literature and also with the feasible set defined by polyhedral 3D-cones with several degrees of degeneration at the solution were performed, including noisy functions that are not covered by the theoretical hypotheses. Furthermore, an instance of a parameter identification problem was considered as an application with inherent noise on the objective function for which linear constraints are present in the model. To put PSIFA in perspective, comparative tests with the Pattern Search and the Implicit Filtering algorithms have been prepared, with encouraging results Doutorado Matemática Aplicada Doutora em Matemática Aplicada FAPESP 2013/12964-4

Orientador: Prof. Dr. Ademir Alves Ribeiro Coorientadora: Prof.a Dr.a Mael Sachine Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Matemática. Defesa : Curitiba, 25/01/2021 Inclui referências: p. 60-62 Resumo: Nesta tese, estudamos uma classe de problemas de otimização, chamada Mathematical Programs with Cardinality Constraints (MPCaC)). Este tipo de problema é geralmente difícil de lidar, porque envolve uma restrição que não é contínua e nem convexa, mas fornece soluções esparsas. Assim, reformulamos o problema de uma forma adequada, modelando-o como um problema inteiro misto e então consideramos a sua contraparte contínua, a qual será referida como problema relaxado. Investigamos o problema relaxado analisando as restrições gerais em dois casos: linear e não linear. No caso linear, propomos uma abordagem geral e apresentamos uma discussão das condições de qualificação de Abadie e Guignard, provando neste caso que todo minimizador do problema relaxado satisfaz as condições de Karush-Kuhn-Tucker (KKT). Por outro lado, no caso não linear, mostramos que as condições de qualificação clássicas podem ser violadas. Motivados por encontrar um minimizador para o problema MPCaC, definimos uma nova condição de estacionariedade, mais fraca do que KKT, propondo uma abordagem unificada que vai da estacionariedade mais fraca até a mais forte (dentro de um certo espectro de condições). Entretanto, estas condições não são condições de otimalidade. Deste modo, propomos também um conceito de estacionariedade fraca aproximada chamado AW-stationarity (do inglês, Approximate Weak stationarity), desenhado para lidar com problemas MPCaC. Provamos que é uma condição de otimalidade legítima independentemente de qualquer condição de qualificação. Muitas pesquisas em condições sequenciais de otimalidade têm sido feitas para otimização não linear com restrições nos últimos anos, sendo alguns trabalhos no contexto de problemas da classe Mathematical Programs with Complementarity Constraints (MPCC). No entanto, até onde sabemos, nenhuma condição sequencial de otimalidade foi proposta para problemas MPCaC. Estabelecemos algumas relações entre a nossa condição AW-stationarity e outras condições sequenciais de otimalidade usuais, tais como AKKT, CAKKT e PAKKT. Ressaltamos que, apesar do apelo computacional das condições sequenciais de otimalidade, nosso objetivo até este momento foi discutir os aspectos teóricos de tais condições para problemas MPCaC. Os aspectos algorítmicos por trás de nossa teoria são temas de pesquisa em andamento. Abstract: In this thesis, we study a class of optimization problems, called Mathematical Programs with Cardinality Constraints (MPCaC). This kind of problem is generally difficult to deal with, because it involves a constraint that is not continuous neither convex, but provides sparse solutions. Thereby we reformulate MPCaC in a suitable way, by modeling it as mixed-integer problem and then addressing its continuous counterpart, which will be referred to as relaxed problem. We investigate the relaxed problem by analyzing the general constraints in two cases: linear and nonlinear. In the linear case, we propose a general approach and present a discussion of the Guignard and Abadie constraint qualifications, proving in this case that every minimizer of the relaxed problem satisfies the Karush-Kuhn-Tucker (KKT) conditions. On the other hand, in the nonlinear case, we show that some standard constraint qualifications may be violated. Motivated to find a minimizer for the MPCaC problem, we define new stationarity conditions, weaker than KKT, by proposing a unified approach that goes from the weakest to the strongest stationarity (within a certain range of conditions). However, these conditions are not optimality conditions. Thereby, we also propose an Approximate Weak stationarity (AW-stationarity) concept designed to deal with MPCaC problems. We proved that it is a legitimate optimality condition independently of any constraint qualification. Many research on sequential optimality conditions has been addressed for nonlinear constrained optimization in the last few years, some works in the context of Mathematical Programs with Complementarity Constraints (MPCC). However, as far as we know, no sequential optimality condition has been proposed for MPCaC problems. We also establish some relationships between our AW-stationarity and other usual sequential optimality conditions, such as AKKT, CAKKT and PAKKT. We point out that, despite the computational appeal of the sequential optimality conditions, our aim until this moment was to discuss the theoretical aspects of such conditions for MPCaC problems. The algorithmic aspects behind our theory are subject of ongoing research.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) O objetivo deste trabalho é apresentar o método dos mínimos quadrados para resolver sistemas lineares sobredeterminados, ou seja, sistemas da forma Ax=b, em que A m×n , com m>n. Neste sentido, veremos como a resolução destes sistemas estão relacionados com encontrar a projeção ortogonal b sobre o subespaço gerado pelas colunas de A . Este tipo de sistema é usado ainda para modelar um problema de geoposicionamento, cujo objetivo é determinar a posição de um receptor que recebe o sinal de vários satélites. The main goal of this work is to present the least squares method to solve overdetermined linear systems, that is, systems of the form Ax = b , where A m×n , with m > n . In this sense, we showed that the resolution of these systems is related to the orthogonal projection problem of b on the subspace generated by the columns of A. This type of system is used to model a problem of geo-positioning, whose objective is to determine the position of a receiver that receives the signal from several satellites.

Orientadora : Profª. Drª. Mael Sachine Coorientador : Prof. Dr. Ademir Alves Ribeiro Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Matemática. Defesa: Curitiba, 31/07/2017 Inclui referências : f. 110-112 Resumo: O objetivo geral deste trabalho foi realizar um estudo te.rico e uma pequena aplica..o sobre SVM, que inclui relatar justificativas para o uso de tal técnica e exibir sua interpretação geométrica e perspectiva analítica. Para aplicar a técnica em problemas de classificação, buscamos fundamentar matematicamente sua utilização, visto que envolve um problema de programação quadrática, convexa e com restrições. Para a análise da técnica, utilizamos a teoria de dualidade Lagrangiana, que notamos facilitar os cálculos e a análise das soluções. Alem disso, reescrevemos resultados que usam ponto de sela, sem precisar deste conceito. Estabelecemos algumas implicações e exibimos alguns contraexemplos, para mostrar que certos resultados decorrentes da técnica SVM encontrados na literatura não são precisos. Foram feitas algumas comparações, para analisar os diferentes parâmetros da função Kernel Gaussiana, usada para resolver o problema quando não for possível encontrar uma função de decisão no espaço de entrada. Verificamos que a eficiência da técnica depende da escolha do parâmetro de regulariza.ao, da função Kernel e seus respectivos parâmetros. Tal técnica foi testada sobre um banco de dados criado artificialmente e composto de imagens de caracteres. Para a implementação computacional, usamos a interface do programa Algencan e algumas funções próprias do Matlab. Palavras-chave: Máquinas de Vetores Suporte. Programa.ao não linear. Otimização com restrições. Dualidade Lagrangiana. Processamento de imagens. Algencan. Abstract: The general objective of this work was to perform a theoretical study and a small application about SVM, which includes reporting justifications for the use of such technique and showing its geometric interpretation and analytical perspective. In order to apply the technique to classification problems, we seek to base its use mathematically, since it involves a quadratic, convex and constrained programming problem. For the analysis of the technique, we use the theory of Lagrangian duality, which we noticed to facilitate the calculations and the analysis of the solutions. In addition, we rewrite results using a saddle point, without needing this concept. We have established some implications and have shown some counterexamples to show that certain results from the SVM technique found in the literature are not accurate. Some comparisons have been made to analyze the different parameters of the Gaussian kernel function used to solve the problem when it is not possible to find a decision function in the input space. We have verified that the efficiency of the technique depends on the choice of the regularization parameter, the kernel function and its parameters. This technique was tested on an artificially created database composed of character images. For the computational implementation, we used the Algencan program interface and some of Matlab's own functions. Keywords: Support Vector Machine. Nonlinear programming. Optimization with constraints. Lagrangian duality. Image processing. Algencan.

Orientador : Prof. Dr. Ademir Alves Ribeiro Coorientador : Profª. Drª. Gislaine Aparecida Periçaro Tese (doutorado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduação em Métodos Numéricos em Engenharia. Defesa: Curitiba, 08/06/2016 Inclui referências : f. 60-64 Área de concentração : Progressão matemática Resumo: Neste trabalho propomos algoritmos para resolver uma formulação primal-dual geral de ponto fixo aplicada ao problema de Ridge Regression. Estudamos a formulação primal para problemas de quadrados mínimos regularizado, em especial na norma L2, nomeados Ridge Regression e descrevemos a dualidade convexa para essa classe de problemas. Nossa estratégia foi considerar as formulações primal e dual conjuntamente, e minimizar o gap de dualidade entre elas. Estabelecemos o algoritmo de ponto fixo primal-dual, nomeado SRP e uma reformulação para esse método, contribuição principal da tese, a qual mostrou-se mais eficaz e robusta, designada por método acc-SRP, ou versão acelerada do método SRP. O estudo teórico dos algoritmos foi feito por meio da análise de propriedades espectrais das matrizes de iteração associadas. Provamos a convergência linear dos algoritmos e apresentamos alguns exemplos numéricos comparando duas variantes para cada algoritmo proposto. Mostramos também que o nosso melhor método, acc-SRP, possui excelente desempenho numérico na resolução de problemas muito mal-condicionados quando comparado ao Método de Gradientes Conjugados, o que o torna computacionalmente mais atraente. Palavras-chave: Métodos primais-duais, Ridge Regression, ponto fixo, dualidade, métodos acelerados Abstract: In this work we propose algorithms for solving a fixed-point general primal-dual formulation applied to the Ridge Regression problem. We study the primal formulation for regularized least squares problems, especially L2-norm, named Ridge Regression and then describe convex duality for that class of problems. Our strategy was to consider together primal and dual formulations and minimize the duality gap between them. We established the primal-dual fixed point algorithm, named SRP and a reformulation for this method, the main contribution of the thesis, which was more efficient and robust, called acc-SRP method or accelerated version of the SRP method. The theoretical study of the algorithms was done through the analysis of the spectral properties of the associated iteration matrices. We proved the linear convergence of algorithms and some numerical examples comparing two variants for each algorithm proposed were presented. We also showed that our best method, acc-SRP, has excellent numerical performance for solving very ill-conditioned problems, when compared to the conjugate gradient method, which makes it computationally more attractive. Key-words: Primal-dual methods, ridge regression, fixed point, duality, accelerated methods.

Orientadora : Profª. Drª. Elizabeth W. Karas Co-orientadora : Profª. Drª. Mael Sachine Orientador no exterior : Profª. Drª. Joaquim J. Júdice Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Matemática. Defesa: Curitiba, 25/02/2016 Inclui referências : f. 133-144 Resumo: Este trabalho engloba dois temas diferentes. Inicialmente, apresentamos um algoritmo para resolver problemas de otimizacao restrita que não faz uso das derivadas da funcao objetivo. O algoritmo mescla conceitos de restauração inexata com técnicas de filtro. Cada interação é decomposta em duas fases: uma fase de viabilidade e uma fase de otimalidade, as quais visam reduzir os valores da medida de inviabilidade e da funcao objetivo, respectivamente. A fase de otimalidade é computada por interações internas de região de confiança sem derivadas, sendo que seus modelos podem ser construídos por qualquer técnica, contanto que sejam aproximaçoes razoável para a função objetivo em torno do ponto corrente. Assumindo esta, e hipóteses clássicas, provamos que o algoritmo satisfaz certa condição de eficiência, a qual implica sua convergência global. Para a análise prática, são apresentados alguns resultados numéricos. O segundo tema refere-se a problemas de complementaridade linear. Nesta parte são discutidos alguns algoritmos de pivotamento em blocos principais, eficientes para solucionar este tipo de problema. Uma análise sobre algumas técnicas para garantia de convergência desses algoritmos _e realizada. Apresentamos alguns resultados numéricos para comparar a eficiencia e a robustez dos algoritmos discutidos. Além disso, são apresentadas duas aplicações para o método de pivotamento em blocos principais: decomposição em matrizes não negativas e métodos de gradiente projetados precondicionado. Para finalizar, nesta segunda aplicação, sugerimos uma matriz de precondicionamento. Abstract: This work covers two diferent subjects. First we present an algorithm for solving constrained optimization problems that does not make explicit use of the objective function derivatives. The algorithm mixes an inexact restoration framework with filter techniques. Each iteration is decomposed in two phases: a feasibility phase that reduces an infeasibility measure; and an optimality phase that reduces the objective function value. The optimality step is computed by derivative-free trust-region internal iterations, where the models can be constructed by any technique, provided that they are reasonable approximations of the objective function around the current point. Assuming that this and classical hypotheses hold, we prove that the algorithm satisfes an eficiency condition, which provides its global convergence. Preliminar numerical results are presented. In the second subject, we discuss the linear complementarity problem. Some block principal pivoting algorithms, eficient for solving this kind of problem, are discussed. An analysis of some techniques to guarantee convergence results of these algorithms is made. We present some numerical results to compare the eficiency and the robustness of the algorithms. Moreover we discuss two applications of the block principal pivoting: nonnegative matrix factorization and preconditioned projected gradient methods. Furthermore, in this second application, we suggest a preconditioning matrix.

Resumo: Apresenta-se um método para minimização irrestrita de uma função F : IRn ! IR duas vezes diferençável cujas derivadas estão indisponíveis. Considera-se para tal, um algoritmo iterativo de região de confiança. Durante as iterações a função objetivo é aproximada por modelos quadráticos através de interpolações polinomiais. São considerados n + 1 pontos interpoladores, os quais de_nem unicamente um polinômio linear. Para se obter modelos quadráticos consideram-se Hessianas como quaisquer matrizes simétricas uniformemente limitadas. De umas iterações para outra, os conjuntos de pontos interpoladores sofrem alterações em no máximo um elemento. Além disso, a cada iterações a função objetivo é avaliada uma única vez. O método proposto possui dois tipos de iterações, região de confiança e alternativa. As do tipo de região de confiança têm como objetivo minimizar o modelo na esperança de que grande parte dessa redução seja herdada pela função objetivo. Já as alternativas visam melhorar a disposi_c~ao dos pontos Interpol adores. Apresenta-se este método de forma algorítmica. Prova-se que se o número de iterações é infinito, se a função objetivo é limitada inferiormente e possui derivadas segundas limitadas, então todo ponto de acumulação da seqüência gerada pelo algoritmo é estacionário.

Orientador: Paulo José da Silva e Silva Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica Resumo: Este trabalho apresenta um novo modelo robusto de máquina de suporte vetorial (MSV) que tem a capacidade de suprimir a influência de \textit{outliers} para os casos de classificação linear e não linear. Esse modelo será chamado de MSVdc e está baseado no modelo LOVO-MSV, que usa amostragem seletiva. A construção do modelo utiliza resultados teóricos de dualidade para programação de diferença de convexas levando à resolução de um problema de otimização quadrático indefinido. Assim sendo, se tornará possível usar o \textit{truque do núcleo} para estender resultados e construir um classificador não linear robusto que ignore a influencia dos \textit{outliers}. Ademais, apresentam-se resultados computacionais para alguns dados artificiais e reais que confirmam que, em comparação com as máquinas de suporte vetorial de margens suaves, o modelo proposto neste trabalho é menos sensível a dados com presença de erros. Neste trabalho, a implementação computacional que compara a MSVdc e a MSV de margens suaves foi feita em Matlab2018 Abstract: In this work, a new robust model based on the Low Order Value measure Optimization for support vetor machines (LOVO-SVM) is presented. This model will be called MSVdc and has the ability of suppressing the influence of outliers by using selective sampling. The final model, after a transformation based on duality for difference of convex optimization, is trained solving a quadratic indefinite optimization problem. This way, it will be possible to use the \textit{kernel trick} to extend results and build a robust nonlinear classifier that ignores the influence of \textit{outliers}. In addition, results for artificial and real data are presented. They confirm that the LOVO-SVM model to be more stable in the presence of \textit{outliers}, compared to a soft marging suport vector machine. In this work, the computational implementation that compares the MSVdc and the smooth margin MSV was done in Matlab2018 Doutorado Matemática Aplicada Doutora em Matemática Aplicada CNPQ 141810/2016-5 CAPES