Search

Orientador: Celso Carnieri Co-orientadora: Elizabeth Wegner Karas Tese (doutorado) - Universidade Federal do Paraná, Setores de Tecnologia e Cięncias Exatas, Programa de Pós-Graduaçăo em Métodos Numéricos em Engenharia. Defesa: Curitiba, 2005 Inclui bibliografia e anexos

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.

Orientadores : Prof. Dr. Ademir Alves Ribeiro e no exterior Prof. Dr. Juan Enrique Martínez-Legaz Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Matemática. Defesa: Curitiba, 29/07/2016 Inclui referências : f. 50-52 Resumo: Este trabalho engloba dois temas diferentes. O primeiro tópico trata de apresentar dois esquemas de c-conjugação para funções semicontínuas inferiormente (sci) definidas em espaços vetoriais reais de Banach cuja norma é Fréchet diferenciável fora da origem. Ambos os esquemas são baseados numa nova caracterização de funções sci via supremo pontual de um conjunto especial de funções contínuas. Para finalizar esta primeira frente do trabalho, estes esquemas são aplicados no desenvolvimento de uma teoria de dualidade. O segundo tópico trata de uma generalização da Desigualdade Forte de Fitzpatrick em espaços vetoriais de Banach reflexivos, envolvendo funções TBC. Ao final, introduz-se uma família de funções gap para o Problema de Inclusão Monótona Maximal e, graças à generalização proposta, é possível encontrar interessantes propriedades a respeito desta família. Palavras-chave: Função semicontínua inferiormente; Conjugação convexa generalizada; Desigualdade Forte de Fitzpatrick; Problema de Inclusão Monótona Maximal. Abstract: We present two topics. Firstly, we introduce two generalized conjugation schemes for lower semi-continuous (lsc) functions defined on a real Banach space whose norm is Fréchet differentiable of the origin. Both approaches are based upon a new characterization of lower semi-continuous functions as pointwise suprema of a special class of continuous functions. In order to conclude this part of the work, we apply these ideas for building a optimization duality theory. In the second topic, we present a generalization of the strong Fitzpatrick inequality in the context of reflexive Banach spaces, involving a TBC function. We also introduce a related family of gap functions for maximal monotone inclusion problems. Thanks to the proposed generalization, we find interesting properties about this family. Keywords: Lower semi-continuous function; Generalized convex conjugation; Strong Fitzpatrick inequality; Maximal monotone inclusion problems..

Orientador: 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, 07/03/2022 Inclui referências Resumo: Uma das estratégias para resolver problemas de otimização com restrições através de métodos de penalidade externa faz uso de funções de penalidade não diferenciáveis, o que limita o uso de eficientes algoritmos suaves para resolver os subproblemas. Em vista desta dificuldade, técnicas de suavizar vêm sendo amplamente propostas na literatura. Neste trabalho, estudamos a teoria de métodos de penalidade externa, mostrando suas principais propriedades e discutindo a dicotomia entre funções de penalidade exata e suaves. Trazemos de forma unificada resultados e métodos baseados em funções que suavizam e aproximam um a função de penalidade exata. Por fim, apresentamos resultados numéricos de comparação do desempenho computacional dos métodos estudados na resolução de problemas da biblioteca CUTEst. Abstract: One of the strategies to solve constrained optimization problems through external penalty methods utilizes non-differentiable penalty functions, which limits the use of efficient smooth algorithms to solve the subproblems. In light of this difficulty, a great number of smoothing techniques have been proposed in the literature. In this work, we study the theory of exterior penalty methods. We show their main properties and discuss the dichotomy between exact and smooth penalty functions. We present on a unified manner results and methods based on functions that smooth and approximate an exact penalty function. Finally, we present numerical results comparing the com putational performance of the studied methods on the resolution of problems from the CUTEst library.

Orientadores: Sandra Augusta Santos, José Mário Martinez Pérez Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica Resumo: Neste trabalho apresentamos o estudo de dois algoritmos baseados em regiões de confiança para minimização de problemas suaves com restrições lineares. O primeiro algoritmo proposto, com uma estratégia de restrições ativas, foi desenvolvido a partir do trabalho de Gay. O segundo algoritmo apresentado explora a técnica de pontos interiores presente nos métodos de barreira. Ambos são acompanhados de respectivos resultados de boa definição e de convergência global e local. Os dois algoritmos foram testados para a resolução de problemas de distribuição de pontos em polígonos, utilizando o algoritmo de Rojas, Santos e Sorensen, livre de fatorações de matrizes, para resolver os subproblemas internos de região de confiança. O problema dos pontos no polígono não foi encontrado na literatura para o teste de algoritmos de otimização e pode ser visto como uma modificação do problema de distribuição de pontos em caixas, sugerido por Powell. Embora possua estrutura favorável para a geração de problemas com dimensão variável, e potencialmente de grande porte, no contexto livre de fatorações, trata-se de um problema difícil e desafiador, com uma grande quantidade de minimizadores locais. Experimentos numéricos comparativos entre as propostas foram feitos e analisados, indicando que os algoritmos são efetivos na obtenção de pontos estacionários de segunda ordem, com ligeira vantagem para o desempenho do algoritmo baseado em restrições ativas, em termos do tempo computacional empregado Abstract: In this work two trust-region-based algorithms are analyzed for linearly constrained minimization. The first one is an active-set method, based on Gay's ideas. The second one uses interior-point techniques of barrier methods. Both algorithms are proved to be well defined and accompanied by the respective convergence results. The implementation was developed resting upon Rojas, Santos and Sorensen matrix-free algorithm for solving the inner trust-region subproblems. The family of adopted test-problems involves the distribution of points in a polygon, a modification of Powell's problem of distributing points in a square. Despite its favorable structure for generating instances with variable and potentially large dimension, in the matrix-free context, the problem is indeed hard and challenging, with many local minimizers. Comparative computational experiments illustrate the performance of the proposed algorithms, showing that both are effective to obtain second-order stationary points, with a slight advantage of the active-set-based algorithm when it comes to the CPU time spent Doutorado Matemática Aplicada Doutor em Matemática Aplicada

Orientador: Ademir Alves Ribeiro Coorientador: Lucas Garcia Pedroso Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Matemática. Defesa : Curitiba, 27/08/2021 Inclui referências: p. 109-114 Resumo: Neste texto, apresentamos uma revisão de conceitos acerca dos métodos de agrupamento, com maior foco nos baseados em centroides. Para além das abordagens clássicas, apresentamos variações que podem ser úteis em algumas aplicações práticas, como a definição a priori do número de pontos de cada grupo e métodos que lidam com essas restrições. Abordamos uma formulação mais geral para o problema de agrupamento com restrições, onde cada ponto tem um peso associado e a soma dos pesos dos pontos que compõem cada grupo é estabelecida previamente. Tratamos este pro­blema sob as perspectivas fuzzy e não fuzzy. Por fim, apresentamos testes numéricos que atestam a competitividade de nossos métodos ante os clássicos nos casos comparáveis. Abstract: In this work, we present a review of concepts about clustering methods, with focus on centroid-based methods. In addition to the classic approaches, we present the constraints that may be useful in some practical applications, such as the a priori definition of the number of points in each group, and methods that deal with these constraints. We approach a more general formulation to the constrained clustering problem, where each point has an associated weight, and the sum of the weights of the points that make up each group is established a priori. We approach this problem from a nonfuzzy and fuzzy perspective. Finally, we present numerical tests that show the competitiveness of our methods compared to the classics in comparable cases.

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.

Orientador: Prof. Dr. Ademir Alves Ribeiro Coorientador: Prof. Dr. José Alberto Ramos Flor Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Matemática. Defesa : Curitiba, 29/01/2019 Inclui referências Resumo: Problemas de Otimização com Condições de Equilíbrio (MPEC) possuem a particularidade de não satisfazer as condições de qualificação usuais para problemas de otimização não linear. Isto representa uma dificuldade ao tentar resolver problemas MPEC com estes métodos. Recentemente, considerando a condição de qualificação MPEC-LICQ, uma adaptação para problemas MPEC da condição de qualificação de independência linear (LICQ) usual, Izmailov, Solodov e Uskov provaram que métodos baseados em Lagrangiano Aumentado de primeira ordem, convergem a pontos C-estacionários, que são mais fracos que pontos KKT. Posteriormente Andreani, Secchin e Silva melhoraram o resultado, mostrando que quando se consideram métodos baseados em Lagrangiano Aumentado de segunda ordem pode-se garantir convergência a pontos pelo menos M-estacionários, condição mais forte que C-estacionariedade, porém também mais fraca que KKT. Além disso mostraram também que considerando a condição MPECRCPLD, mais fraca que MPEC-LICQ, e que certa sequência dos multiplicadores é limitada tem-se convergência a pontos S-estacionários, que são equivalentes a KKT. Neste trabalho mostramos que estes resultados não são exclusivos do método de Lagrangiano Aumentado. Apresentamos um método baseado em PQS estabilizada de segunda ordem que pode ser aplicado a problemas MPEC, obtendo resultados equivalentes. Assim, mostramos que quando se considera MPEC-LICQ, o método PQS estabilizado também garante convergência a pontos M-estacionérios. Além disso mostramos que considerando MPEC-RCPLD e uma propriedade de limitação vinculada ao multiplicador da restrição de complementaridade também temos convergência a pontos S-estacionários. Testes numéricos são feitos para validar os resultados teóricos. Palavras-chave: Problemas de Otimização com Condições de Equilíbrio. Programação não linear. Otimização com restrições. Programação Quadrática Sequencial Estabilizada. M-estacionariedade. Abstract: Mathematical Programs with Equilibrium Constraints (MPEC) have the particularity do not satisfy the usual constraint qualifications for standard nonlinear optimization. This represents a difficulty in attempting to solve MPEC problems with the usual nonlinear optimization methods. Recently, considering the MPEC-LICQ constraint qualification, an adaptation to MPEC problems of the usual linear independence constraint qualification (LICQ), Izmailov, Solodov and Uskov proved that first order augmented Lagrangian methods converge to C-stationary points, which are weaker than KKT points. Later on Andreani, Secchin and Silva improved this result, showing that when considering second order augmented Lagrangian methods, it can be guaranteed convergence to at least M-stationary points, which are stronger than C-stationary, but still weaker than KKT. In addition, they also showed that considering the MPEC-RCPLD constraint qualification, which is weaker than MPEC-LICQ, and assuming that a certain multiplier sequence is bounded, it can be proved the convergence to S-stationary points, which are equivalent to KKT. In this work we show that these results are not exclusive of the Augmented Lagrangian method. We provide a method based on second order stabilized Sequential Quadratic Programming, which can be applied to MPEC problems, achieving equivalent results. Thus we show that when MPEC-LICQ is considered, the stabilized SQP method also guarantees convergence to M-stationary points. Moreover, we show that considering MPEC-RCPLD and a boundedness property related to the complementarity constraint multiplier, the method also has convergence to S-stationary points. Numerical tests were performed to validate the theoretical results. Keywords: Mathematical Programs with Equilibrium Constraints. Nonlinear programming. Constrained optimization. stabilized Sequential

A intermitência e a aleatoriedade dos recursos renováveis trazem desafios significativos para a robustez e operação econômica dos sistemas de energia. A otimização robusta permite a modelagem inferida através de um conjunto incerto e garante que a solução encontrada possa lidar com qualquer ocorrência possível, tendo como base esse conjunto. Estudos têm demonstrado que uma grande disseminação geográfica da capacidade instalada pode reduzir a variabilidade da energia eólica e tornar sua geração mais previsível. Atualmente, as pesquisas raramente consideram a correlação temporal e espacial entre diferentes localizações dos parques eólicos. Motivados por esses desafios, foi implementado um modelo de otimização robusta para o problema de designação de geradores, que utiliza um novo tipo de conjunto incerto correlacionado para inferir a incerteza e capturar as correlações temporais e espaciais entre os parques eólicos. Os resultados na aplicação do modelo proposto revelaram que no caso da existência de correlações consideráveis entre a geração de potência eólica, isto leva a soluções melhores comparado ao modelo convencional com prevenção contra perturbações não correlacionadas. Além disso, os resultados revelaram um desempenho superior a medida em que os valores das correlações entre os parques eólicos aumentam. Como uma conclusão, o modelo de otimização robusta proposto pode ser considerado um modelo eficaz para um ambiente contendo dados correlacionados sujeitos a incerteza. The intermittency and stochasticity of the renewable resources bring significant challenges to the robustness and economic operation of power systems. Robust optimization allows for the modeling of an uncertainty set and ensures that the chosen solution can handle any possible realization based on this uncertainty set. Studies have shown that a large geographic spread of installed capacity can reduce wind power variability and the production more predictable. Current research work rarely considers the temporal and spatial correlation among different positions in wind farms. Motivated by these challenges, we present a robust optimization model for the unit commitment (UC) problem, which models the nature of the dispatch process and utilizes a new type of correlated uncertainty sets to capture the temporal and spatial corre-lations of wind farms. The results of applying the proposed model revealed that in the case of existing considerable correlation among wind power generation, it leads a superior solutions compared with that of conventional model by preventing protection against uncorrelated perturbations. IIn addition, the results revealed that the proposed model obtains superior performance as the values of correlations among the wind farms increases. As a conclusion, the proposed robust optimization model can be considered as an effective model for an environment containing correlated uncertain data.

Orientador : 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, 23/02/2017 Inclui referências : f. 104-106 Área de concentração: Matematica Resumo: Nesta dissertação, apresentamos uma revisão de conceitos acerca do método de Levenberg-Marquardt, utilizado para o problema de quadrados mínimos não linear. Além da abordagem clássica do método, constam neste trabalho duas contribuições por nós estabelecidas. A primeira contribuição é a sugestão de um novo parâmetro de damping, ou parâmetro de Levenberg- Marquardt, que está diretamente ligado ao desempenho do método. A segunda contribuição estabelece uma nova maneira de resolução do subproblema relacionado ao método para problemas mal escalados, utilizando decomposições matriciais pautadas em direções conjugadas. Palavras-chave: Quadrados Mínimos Não Linear, Levenberg-Marquardt, Parâmetros de damping, Problemas mal escalados. Abstratc: In this work, we present a review about the Levenberg- Marquardt method, used for the Nonlinear Least Square Problem. In addition to the classical approach of the method, two contributions are made by us. The first contribution is the suggestion of a new damping parameter, or Levenberg-Marquardt parameter, that is directly linked to the performance of the method. The second contribution establishes a new approach to solve the subproblem related to the Levenberg-Marquardt method for bad scaled problems, using matrix decompositions based on Conjugated Gradients. Keywords: Nonlinear Least Squares Problem, Levenberg-Marquardt, Damping parameter, Bad scaled problems.

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.

Orientadores: Sandra Augusta Santos, Elias Salomão Helou Neto Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica Resumo: O método amostral de gradientes (GS) é um algoritmo recentemente desenvolvido para resolver problemas de otimização não suave. Fazendo uso de informações de primeira ordem da função objetivo, este método generaliza o método de máxima descida, um dos clássicos algoritmos para minimização de funções suaves. Este estudo tem como objetivo desenvolver e explorar diferentes métodos amostrais para a otimização numérica de funções não suaves. Inicialmente, provamos que é possível ter uma convergência global para o método GS na ausência do procedimento chamado "teste de diferenciabilidade". Posteriormente, apresentamos condições que devem ser esperadas para a obtenção de uma taxa de convergência local linear do método GS. Finalmente, um novo método amostral com convergência local superlinear é apresentado, o qual se baseia não somente no cálculo de gradientes, mas também nos valores da função objetivo nos pontos sorteados Abstract: The Gradient Sampling (GS) method is a recently developed tool for solving unconstrained nonsmooth optimization problems. Using just first order information of the objective function, it generalizes the steepest descent method, one of the most classical methods for minimizing a smooth function. This study aims at developing and exploring different sampling algorithms for the numerical optimization of nonsmooth functions. First, we prove that it is possible to have a global convergence result for the GS method in the abscence of the differentiability check procedure. Second, we prove in which circumstances one can expect the GS method to have a linear convergence rate. Lastly, a new sampling algorithm with superlinear convergence is presented, which rests not only upon the gradient but also on the objective function value at the sampled points Doutorado Matemática Aplicada Doutor em Matemática Aplicada CAPES FAPESP 2013/14615-7

Neste trabalho, estudaremos uma nova estrat egia para minimizar uma fun c~ao convexa sobre um cone simplicial. Este m etodo consiste em obter a solu c~ao do problema de minimiza c~ao atrav es da raiz de uma equa c~ao semi-suave associada as suas condi c~oes de otimalidade. Para encontrar essa raiz, usaremos uma vers~ao semi-suave do m etodo de Newton, onde a derivada da fun c~ao que de ne a equa c~ao semi-suave e substitu da por um subgradiente de Clarke conveniente. Para o caso em que a fun c~ao e quadr atica, veremos que e poss vel obter condi c~oes mais fracas para a converg^encia da sequ^encia gerada pelo m etodo de Newton semi-suave. Motivados por esta nova estrat egia de minimiza c~ao tamb em usaremos o m etodo de Newton semi-suave para encontrar ra zes de dois tipos espec cos de equa c~oes semi-suaves, uma associada a x+ e a outra associada a jxj. In this work, we will study a new strategy to minimize a convex function on a simplicial cone. This method consists in to obtain the solution of a minimization problem through the root of a semi-smooth equation associated to its optimality conditions. To nd this root, we use the semi-smooth version of the Newton's method, where the derivative of the function that de nes the semi-smooth equation is replaced by a convenient Clarke subgradient. For the case that the function is quadratic, we will see that it allows us to have weaker conditions for the convergence of the sequence generated by the semi-smooth Newton's method. Motivated by this new minimization strategy we will also use the semi-smooth Newton's method to nd roots of two special semi-smooth equations, one associated to x+ and the another one associated to jxj. Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES

Orientador : Prof. Dr. Ademir Alves Ribeiro Coorientador : Prof. Dr. Manoel Messias Alvino de Jesus Tese (doutorado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduação em Métodos Numéricos em Engenharia. Defesa: Curitiba, 02/09/2016 Inclui referências : f. 64-69 Área de concentração : Programação matemática Linha de pesquisa : Métodos estatíscos aplicados a engenharia Resumo: Este trabalho apresenta caracterizações em larga escala das flutuações das vazões em rios, tendo como principais técnicas os métodos empregados na Física de Sistemas Complexos. Inicialmente, foi utilizada uma estrutura de grafos de visibilidade horizontal, resultante da análise e do mapeamento em redes complexas, das séries temporais diárias de 141 estações diferentes, localizadas em 53 rios brasileiros entre os anos de 1931 e 2012. Verificou-se que as distribuições de graus dessas redes são bem descritas por distribuições exponenciais, nas quais os expoentes característicos são, em sua maior parte, numericamente maiores que aqueles obtidos para séries temporais aleatórias. O decaimento mais rápido do ajuste da exponencial, quando comparado ao ajuste de modelo da distribuição aleatória, evidência que a dinâmica de flutuações subjacentes às vazões dos rios têm uma natureza correlacionada de longo alcance. A investigação da evolução das descargas fluviais, acompanhando os valores dos expoentes característicos e os coeficientes de aglomeração globais das redes ao longo dos anos mostrou que as vazões dos rios em várias estações evoluíram tornando-se correlacionadas. Por fim, o uso de outros dois métodos de Física Estatística, típicos no estudo de sistemas complexos que são: o detrended fluctuation analysis (DFA) e a entropia e complexidade de permutação foram aplicados, mostrando, sobretudo, que o uso do espectro de permutação permite encontrar o período associado à sazonalidade natural da vazão dos rios e que, após padronizadas, as vazões tornam-se aproximadamente bem descritas por uma mesma distribuição. Fica claro, também, que as séries temporais são correlacionadas de longo alcance pela análise DFA. Por outro lado, revisitou-se três dos principais métodos existentes na literatura, que conseguem identificar correlações de longo alcance. Nominalmente: a análise de flutuação DFA, as transformações Wavelet e a análise entrópica (DEA - diffusion entropy analysis). Fez-se uma comparação entre os três métodos quanto a sua convergência para o verdadeiro valor do expoente ? de Hurst em função do tamanho das séries geradas. Nessa comparação, observou-se algumas peculiaridades de cada método; por exemplo: o DFA converge para valores superiores de ?, enquanto as transformações Wavelet e o DEA o fazem por valores inferiores. Com base nessa observação empírica, se propõe aplicar simultaneamente DFA e Wavelet. Isso fez com que a convergência para o valor verdadeiro de ? fosse alcançada para séries razoavelmente pequenas. Palavras-chaves: sistemas complexos, séries temporais, física estatística, correlações de longo alcance, entropia e complexidade de permutação, redes complexas, descargas fluviais Abstract: This paper presents broad-scale characterizations of fluctuation in river flows, principally using the methods employed in complex systems physics. Initially, we used a horizontal visibility graph structure produced by analysis and mapping of complex networks from daily temporal series of 141 different stations in 53 Brazilian rivers between 1931 and 2012. The degree distributions of these networks were found to be well-described by exponential distributions, in which most of the characteristic exponents are numerically greater than those obtained for random time series. The faster decay of exponential distribution in comparison with randomized distribution shows that the dynamics underlying the fluctuations in river flow have a long-range correlation. Investigation of the changes in river discharge, by following characteristic exponent values and global clustering coefficients of the networks over this period, showed that the river flow in several stations evolved and became correlated. Finally, we applied detrended fluctuation analysis (DFA) and entropy and complexity permutation, two methods from statistical physics which are typically used to study complex systems. These showed in particular that spectrum permutation permits the period associated with the natural seasonality of river flows to be found; after this value is normalized, flow rates are described approximately using the same distribution. The time series was also clearly seen to be correlated in the long term using DFA analysis. However, we also returned to three main methods available in the literature which can identify long-range correlations: DFA fluctuation analysis, wavelet transformation, and entropic analysis (diffusion entropy analysis, or DEA). The three methods were compared to assess their convergence for the true value for Hurst's ? exponent depending on the size of the generated series. This comparison showed some peculiarities of each method; for example: DFA converges for higher ? values while wavelet and DEA converge for lower values. Based on this empirical finding, we resolved to apply DFA and wavelet simultaneously, which caused convergence for the true ? value to be achieved for relatively small series. Key-words: complex systems, time series, statistical physics, long-range correlations, entropy and complexity of permutation, complex networks, river discharges.

Resumo: Nesta dissertação, apresenta-se um estudo a respeito de uma generalização das funções conjugadas de Fenchel para funções reais estendidas semicontlnuas inferiormente (sci) de varias variaveis reais. Considera-se para esta, o produto interno generalizado pelas funções contínuas de IRn em IRn e a base teórica e a generalizaçao dos teoremas classicos de separaçao para convexos, a qual possibilita separar por funcoes contínuas conjuntos fechados e, em particular, garante que o epigrafo de uma funcao sci pode ser separado de qualquer ponto que esteja em seu complementar. Com auxílio desses resultados, verifica-se que, para funcões sci, a conjugada proposta e propria e a conjugacao e simetrica. Prova-se tambem que esta conjugada e convexa e sci, e introduz-se os Espacos Duais Conjugados que aumentam o potencial dessa teoria, pois, dependendo da funcao correspondente, eles podem ser de dimensao finita. Aplica-se esta generalizacõo no desenvolvimento de uma dualidade para problemas de programacõo semicontínua inferior (PSCI). Garante-se que o dual desses problemas e de programacao convexa e dependendo da funçõo, pode ser restrito a um espaço dual conjugado de dimensao finita. Prova-se que o bidual e o proprio PSCI e define-se a funcõo Lagrangeana relacionada para concluir que seu minimizador em IRn e solucõo do problema primal e a funcao contínua que o maximiza e solucao do problema dual.

Resumo: Esta tese introduz dois novos resultados sobre a Classe Chebyshev-Halley para resolução de sistemas não-lineares. Os métodos dessa classe possuem convergência cúbica, tendo portanto uma taxa de convergência superior a do método de Newton. Em contrapartida, esses métodos são mais caros computacionalmente, por necessitarem de derivadas de segunda ordem. O primeiro resultado apresentado _e um resultado teórico. Introduzimos um novo raio de convergência para a Classe Chebyshev-Halley, ou seja, mostramos que dado qualquer ponto inicial pertencente à uma bola centrada em uma solução com o novo raio, a sequência gerada por qualquer método da Classe Chebyshev-Halley é bem definida e converge para a respectiva solução com taxa de convergência cúbica. Comparamos com o raio utilizado na prova de convergência dada no livro Numerische Losung Nichtlinearer Gleichungen [70] para os métodos Halley, Chebyshev e Super-Halley, através de alguns exemplos. As comparações apresentadas sugerem perspectivas futuras, tais como determinar o raio ótimo de convergência. O segundo resultado apresentado é a introdução de uma nova classe de métodos, chamada Classe Chebyshev-Halley Inexata livre de tensores, cujo objetivo _e baratear o custo computacional da Classe Chebyshev-Halley, no que tange o uso da derivada de segunda ordem e a resolução de dois sistemas lineares. A grosso modo, não utilizamos informações de derivada de segunda ordem e os dois sistemas lineares, necessários para a obtenção do passo, podem ser resolvidos de maneira inexata. Além de apresentar a prova de convergência, mostramos que, dependendo das hipóteses, os métodos dessa classe podem ter taxa de convergência superlinear, quadrática, superquadrática e cúbica. Mostramos também que essas hipóteses são bastante razoáveis. Porém, comparações numéricas são apresentadas, mostrando uma melhoria significativa quando se usa a estratégia inexata livre de tensores, proposta nesta tese, nos métodos clássicos da Classe Chebyshev-Halley.

Resumo: Discutimos neste trabalho métodos empregados para resolver problemas de programação não linear em que se deseja minimizar uma função em uma determinada região do espaço multidimensional. Para solucionar tais problemas podemos empregar algoritmos iterativos que geram uma sequência de pontos, a qual esperamos convergir para um ponto estacionário. Uma forma de induzir a convergência é fazer uso do critério de filtro para verificar se um ponto tentativo deve ser aceito como próximo iterando. Para ser aceito pelo filtro, o ponto deve provocar uma redução na função objetivo ou na medida de inviabilidade considerada, quando comparado ao ponto corrente. O ponto pode ser testado por dois tipos de critérios de filtro, original ou inclinado, definidos de acordo com a regra que mede a redução no valor da função objetivo. Neste trabalho apresentamos um algoritmo geral de filtro, globalmente convergente, que não depende do método usado para o cálculo do passo e do critério de filtro considerado. A convergência é garantida desde que o passo satisfação uma condição de eficiência que estabelece que perto de um ponto viável não estacionário a redução na função objetivo é relativamente grande. Mostramos que tal condição é satisfeita por pelo menos dois métodos empregados no cálculo do passo, um de Programação Quadrática Sequencial (PQS) e outro de Restauração Inexata (RI), para ambos os critérios de filtro. Para este primeiro método, apresentamos uma prova geral de que a condição de eficiência é satisfeita, sendo válida tanto para o critério de filtro original quanto inclinado. O algoritmo geral de filtro, bem como os algoritmos internos usados para determinar o passo foram implementados em MATLAB e testes numéricos foram realizados com problemas da coleção CUTEr. Para esses testes não foram observadas diferenças numéricas significativas entre os critérios de filtro, no entanto, o algoritmo de PQS mostrou-se mais robusto que RI e, ainda, mais eficiente em relação de número de avaliações de funções e gradientes. Analisamos também a aplicabilidade dos algoritmos estudados a problemas práticos. Para isso, consideramos um problema de otimização que surge em análise de contábilidade estrutural quando deseja-se determinar a probabilidade de falha de uma estrutura. Testes numéricos foram realizados com alguns problemas especificos da área de contábilidade estrutural e os resultados indicaram que nosso algoritmo geral de filtro pode ser empregado nesse contexto.

Orientadores: Márcia Aparecida Gomes Ruggiero, Sandra Augusta Santos Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica Resumo: O objetivo desta tese é tratar da resolução de sistemas não lineares de grande porte, em que as funções são continuamente diferenciáveis, por meio de uma abordagem híbrida que utiliza um método iterativo com duas fases. A primeira fase consiste de versões sem derivadas do método do ponto fixo empregando parâmetros espectrais para determinar o tamanho do passo da direção residual. A segunda fase é constituída pelo método de Newton inexato em uma abordagem matrix-free, em que é acoplado o método GMRES para resolver o sistema linear que determina a nova direção de busca. O método híbrido combina ordenadamente as duas fases de forma que a segunda é acionada somente em caso de falha na primeira e, em ambas, uma condição de decréscimo não-monótono deve ser verificada para aceitação de novos pontos. Desenvolvemos ainda um segundo método, em que uma terceira fase de busca direta é acionada em situações em que o excesso de buscas lineares faz com que o tamanho de passo na direção do método de Newton inexato torne-se demasiadamente pequeno. São estabelecidos os resultados de convergência dos métodos propostos. O desempenho computacional é avaliado em uma série de testes numéricos com problemas tradicionalmente encontrados na literatura. Tanto a análise teórica quanto a numérica evidenciam a viabilidade das abordagens apresentadas neste trabalho Abstract: This thesis handles large-scale nonlinear systems for which all the involved functions are continuously differentiable. They are solved by means of a hybrid approach based on an iterative method with two phases. The first phase is defined by derivative-free versions of a fixed-point method that employs spectral parameters to define the steplength along the residual direction. The second phase consists of a matrix-free inexact Newton method that employs the GMRES to solve the linear system that computes the search direction. The proposed hybrid method neatly combines the two phases in such a way that the second is called only in case the first one fails. To accept new points in both phases, a nonmonotone decrease condition upon a merit function has to be verified. A second method is developed as well, with a third phase based on direct search, that should act whenever too many line searches have excessively decreased the steplenght along the inexact- Newton direction. Convergence results for the proposed methods are established. The computational performance is assessed in a set of numerical experiments with problems from the literature. Both the theoretical and the experimental analysis corroborate the feasibility of the proposed strategies Doutorado Matemática Aplicada Doutor em Matemática Aplicada

Resumo: Nesta dissertação apresentamos brevemente algumas técnicas de diagnóstico por imagem, fazendo uma apresentação mais completa das diferentes modalidades de tomografia computadorizada. Apresentamos o problema da reconstrução de imagens e fazemos a discussão dos algoritmos de reconstrução utilizados em tomografia bem como uma discussão sobre a convergência do algoritmo de projeção ortogonal, detalhada no Capítulo 3. Criamos alguns Phantoms virtuais, sobre os quais simulamos as varreduras e medições que serão utilizadas na reconstrução das imagens através do algoritmo apresentado. Para a reconstrução desenvolvemos um aplicativo experimental no Programa Visual Basic 6, com o qual obtemos as reconstruções de imagens e avaliamos os erros na reconstrução obtida.

Orientadores: Sandra Augusta Santos, Márcia Aparecida Gomes-Ruggiero Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica Resumo: Neste trabalho propomos modificações globalmente convergentes para o Método das Assíntotas Móveis (MMA), baseadas no parâmetro espectral para a construção das aproximações das funções originais e na relaxação da condição conservadora. A informação de segunda ordem presente no parâmetro espectral é incluída nas aproximações racionais da função objetivo e das restrições não-lineares no início de cada iteração, de modo a melhorar a qualidade dos modelos. A condição conservadora é relaxada por meio de uma seqüência forçante controlada somável, de maneira que a convergência global é mantida. Também, propomos uma nova estratégia para resolver os subproblemas MMA por meio do problema dual, usando uma técnica de região de confiança. Os experimentos numéricos realizados comprovam a eficiência das estratégias propostas. Ainda, por trabalharmos com um problema aumentado associado à formulação padrão para o problema de programação não-linear com restrições de desigualdade, estabelecemos relações entre os pontos KKT do problema aumentado e os pontos correspondentes do problema original associado Abstract: In this work we propose globally convergent versions for the Method of Moving Asymptotes (MMA), based on the spectral parameter for updating the approximations of the original functions and on relaxing the conservative condition. The second-order information present in the spectral parameter is included in the rational approximations of the objective function and of the nonlinear constraints in the beginning of each iteration, so as to improve the quality of the models. The conservative condition is relaxed by means of a summable controlled forcing sequence, so that global convergence is maintained. Also, we propose a new strategy to solve the MMA subproblems by means of the dual problem, using a trust-region technique. The performed numerical experiments confirm the efficiency of the proposed strategies. In addition, by working with an extended problem associated with the standard formulation for the nonlinear programming problem with inequality constraints, we have established relationships between the KKT points of the extended problem and the corresponding points of the associated original problem Doutorado Matemática Aplicada Doutor em Matemática Aplicada

Orientadora : Elizabeth Wegner Karas Co-orientador : Ademir Alves Ribeiro Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciencias Exatas e Setor de Tecnologia, Programa de Pós-Graduaçao em Métodos Numéricos em Engenharia. Defesa: Curitiba, 2007 Inclui bibliografia

Orientadora : Profª Drª Elizabeth Wegner Karas Orientador : Prof. Dr. Ademir Alves Ribeiro Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciencias Exatas e Setor de Tecnologia, Programa de Pós-Graduaçao em Métodos Numéricos em Engenharia Inclui bibliografia Defesa: Curitiba, 2006

Orientadora: Elizabeth Wegner Karas Co-orientador: Ademir Alves Ribeiro Dissertaçao (mestrado) - Universidade Federal do Paraná, Setor de Ciencias Exatas, Programa de Pós-Graduaçao em Matamática Aplicada. Defesa: Curitiba, 2006 Inclui bibliografia Resumo: Neste trabalho estudamos as relações entre problemas quadráticos particulares. Os problemas quadráticos são muito estudados em programação não linear pelo grande número de aplicações que recaem nesse tipo de problema. Eles frequentemente são usados como subproblemas auxiliares nos algoritmos mais gerais. No estudo de métodos de resolução de problemas de programação não linear, aparecem dois importantes problemas quadráticos que envolvem uma variedade linear e uma bola fechada. Relacionado a eles há um problema geométrico. A meta deste trabalho é caracterizar as soluções de cada problema e estabelecer os vinculos existentes entre elas. A análise das relações entre tais problemas e suas soluções representa a principal contribuição da dissertação

Orientadores: Elizabeth Wegner Karas e Ademir Alves Ribeiro Inclui apęndice Dissertaçăo (mestrado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduaçăo em Métodos Numéricos em Engenharia. Defesa: Curitiba, 2005 Inclui bibliografia

Orientador: José Mario Martínez Pérez Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica Resumo: Os problemas de otimização sem derivadas surgem de modelos para os quais as derivadas das funções e das restrições envolvidas, por alguma razão, não estão disponíveis. Os motivos variam desde usuários que não querem programar as derivadas até funções excessivamente complexas e caixas-pretas, oriundas de simulações só possíveis graças ao crescimento na capacidade de processamento dos computadores. Acompanhando esse crescimento, o número de algoritmos para resolver problemas de otimização sem derivadas aumentou nos últimos anos. Porém, poucos são aqueles que conseguem lidar de forma eficiente com problemas cujos domínios são magros, como, por exemplo, quando há restrições de igualdade. Neste trabalho, apresentamos a teoria e implementação de dois algoritmos capazes de trabalhar com domínios magros em problemas de otimização sem derivadas. Ambos partem da premissa de que a parte mais custosa na resolução é a avaliação da função objetivo. Com isso em mente, o processo de resolução é dividido em duas fases. Na fase de restauração, buscamos por pontos menos inviáveis sem utilizar avaliações da função objetivo. Na fase de minimização, ou otimização, o objetivo é reduzir a função objetivo com o uso de algoritmos bem estabelecidos para problemas sem derivadas com restrições simples. O primeiro algoritmo utiliza ideias de Restauração Inexata associadas a uma tolerância decrescente à inviabilidade. Utilizando hipóteses simples e usuais dos métodos de busca direta direcional, mostramos propriedades de convergência a minimizadores globais. O segundo algoritmo recupera totalmente os resultados teóricos de um algoritmo recente de Restauração Inexata com busca linear e aplica-se a problemas nos quais apenas as derivadas da função objetivo não estão disponíveis. Testes numéricos mostram as boas propriedades dos dois algoritmos, em particular quando comparados com algoritmos baseados em penalidades Abstract: Derivative-free optimization problems arise from models whose derivatives of some functions are not available. This information is unavailable due to extremely complex and black-box functions, originated from simulation procedures, or even to user inability. Following the growth in the number of applications, the number of derivative-free algorithms has increased in the last years. However, few algorithms are able to handle thin feasible domains efficiently, for example, in the presence of equality nonlinear constraints. In the present work, we describe the theory and implementation of two algorithms capable of dealing with thin-constrained derivative-free problems. Their definition considers that the objective function evaluation is the most expensive part of the problem. Based on this principle, the process of solving a problem is split into two phases. In the restoration phase, we try to improve the feasibility without evaluating the objective function. In the minimization phase, the aim is to decrease the objective function value by using well-established algorithms in order to solve derivative-free problems with simple constraints. The _rst algorithm uses Inexact Restoration ideas together with a decreasing infeasibility tolerance. Under the usual hypotheses of direct search methods, we show global minimization results. The second algorithm extends to the derivative-free case all the theoretical results obtained in a recent line-search Inexact Restoration algorithm. In this approach, only the derivatives of the objective function are not available. We perform numerical experiments to show the advantages of each algorithm, in particular when comparing with penalty-like algorithms Doutorado Matemática Aplicada Doutor em Matemática Aplicada