No description available.

Métodos de Lagrangianos aumentados são muito utilizados para resolver problemas de minimização de funções sujeitas a restrições gerais. Em particular, estudamos um método de Lagrangianos aumentados que utiliza a função PHR, implementado em ALGENCAN, e observamos seu comportamento quando o aplicamos na resolução de um problema encontrado na área de Computação Gráfica. O problema estudado é um problema encontrado na geração de malhas de superfícies, na etapa de pós-processamento, para o qual propomos uma técnica de otimização visando a melhoria dos elementos da malha. Quando se trata de geração de malhas de superfícies em \'R POT. 3\', parametrizações de malhas triângulares que representam superfícies são usadas em muitas aplicações de processamento de malhas para vários fins. Muitas vezes é necessário preservar a métrica da superfície e, assim, minimizar a deformação do ângulo e da área. A técnica que propomos de otimização visa melhorar as distorções de ângulos e áreas impostas por uma parametrização. Para verificar o comportamento da técnica proposta, implementamo-na em C++ e utilizamos algumas malhas de modelos clássicos da literatura para realizar os experimentos numéricos. Os resultados obtidos foram promissores / Augmented Lagrangian methods are frequently used to solve minimization problems subject to general constraints. In particular, we study an augmented Lagrangian method that uses the PHR function, implemented in ALGENCAN, and observe its behavior when applied to solve a problem found in the field of Computer Graphics. The problem we will study and solve is found in the post-processing stage of the surface mesh generation, for which we propose an optimization technique to improve the mesh elements. When it comes to meshing surfaces in \'R POT..3\', triangular meshes parametrizations are widely used in applications of mesh processing. It is often necessary to preserve the surface metric and, thus, minimize the angle and area deformation. The optimization technique we propose aims to improve the distortions imposed by a parametrization onto angles and areas. To assert the efectiveness of the proposed technique, we implemented it in C++ language and used some classic mesh models from the literature to performe numerical experiments. The results were promising

Reconstructing sparse signals from undersampled measurements is a challenging problem that arises in many areas of data science, such as signal processing, circuit design, optical engineering and image processing. The most natural way to formulate such problems is by searching for sparse, or parsimonious, solutions in which the underlying phenomena can be represented using just a few parameters. Accordingly, a natural way to phrase such problems revolves around L0 minimization in which the sparsity of the desired solution is controlled by directly counting the number of non-zero parameters. However, due to the nonconvexity and discontinuity of the L0 norm such optimization problems can be quite difficult. One modern tactic to treat such problems is to leverage convex relaxations, such as exchanging the L0 norm for its convex analog, the L1 norm. However, to guarantee accurate reconstructions for L1 minimization, additional conditions must be imposed, such as the restricted isometry property. Accordingly, in this thesis, we propose a novel extension to current approaches revolving around truncated L1 minimization and demonstrate that such approach can, in important cases, provide a better approximation of L0 minimization. Considering that the nonconvexity of the truncated L1 norm makes truncated l1 minimization unreliable in practice, we further generalize our method to partial L1 minimization to combine the convexity of L1 minimization and the robustness of L0 minimization. In addition, we provide a tractable iterative scheme via the augmented Lagrangian method to solve both optimization problems. Our empirical study on synthetic data and image data shows encouraging results of the proposed partial L1 minimization in comparison to L1 minimization.

O Método do Lagrangeano aumentado em problemas de otimização estrutural com restrições dinâmicas, bem como os conceitos matemáticos e numéricos necessários à sua compreensão são descritos. Este método resolve uma seqüência de problemas de minimização sem restrições definidos utilizando a função objetivo e as funções restrições. Um programa de computador é desenvolvido e aplicado em diversos exemplos. Alem disto, foi efetuada uma análise de sensibilidade com relação aos parâmetros utilizados no método. O método mostrou-se eficiente nas aplicações em problemas com restrições dinâmicas. / We present the method of the augmented Lagrangian in problems of scructural optimization with dynamic restrictions, as well as its mathemathical and numerical concepts. This method solves a series of unconstrained minimization problems using the objective function and the restriction functions. A computational program is implemented and applied in several examples. The augmented Lagrangian parameters senbility is analysed. The method is quite efficient in applications in optimization problems with dynamic restrictions.

Métodos de Lagrangianos aumentados são muito utilizados para resolver problemas de minimização de funções sujeitas a restrições gerais. Em particular, estudamos um método de Lagrangianos aumentados que utiliza a função PHR, implementado em ALGENCAN, e observamos seu comportamento quando o aplicamos na resolução de um problema encontrado na área de Computação Gráfica. O problema estudado é um problema encontrado na geração de malhas de superfícies, na etapa de pós-processamento, para o qual propomos uma técnica de otimização visando a melhoria dos elementos da malha. Quando se trata de geração de malhas de superfícies em \'R POT. 3\', parametrizações de malhas triângulares que representam superfícies são usadas em muitas aplicações de processamento de malhas para vários fins. Muitas vezes é necessário preservar a métrica da superfície e, assim, minimizar a deformação do ângulo e da área. A técnica que propomos de otimização visa melhorar as distorções de ângulos e áreas impostas por uma parametrização. Para verificar o comportamento da técnica proposta, implementamo-na em C++ e utilizamos algumas malhas de modelos clássicos da literatura para realizar os experimentos numéricos. Os resultados obtidos foram promissores / Augmented Lagrangian methods are frequently used to solve minimization problems subject to general constraints. In particular, we study an augmented Lagrangian method that uses the PHR function, implemented in ALGENCAN, and observe its behavior when applied to solve a problem found in the field of Computer Graphics. The problem we will study and solve is found in the post-processing stage of the surface mesh generation, for which we propose an optimization technique to improve the mesh elements. When it comes to meshing surfaces in \'R POT..3\', triangular meshes parametrizations are widely used in applications of mesh processing. It is often necessary to preserve the surface metric and, thus, minimize the angle and area deformation. The optimization technique we propose aims to improve the distortions imposed by a parametrization onto angles and areas. To assert the efectiveness of the proposed technique, we implemented it in C++ language and used some classic mesh models from the literature to performe numerical experiments. The results were promising

O Método do Lagrangeano aumentado em problemas de otimização estrutural com restrições dinâmicas, bem como os conceitos matemáticos e numéricos necessários à sua compreensão são descritos. Este método resolve uma seqüência de problemas de minimização sem restrições definidos utilizando a função objetivo e as funções restrições. Um programa de computador é desenvolvido e aplicado em diversos exemplos. Alem disto, foi efetuada uma análise de sensibilidade com relação aos parâmetros utilizados no método. O método mostrou-se eficiente nas aplicações em problemas com restrições dinâmicas. / We present the method of the augmented Lagrangian in problems of scructural optimization with dynamic restrictions, as well as its mathemathical and numerical concepts. This method solves a series of unconstrained minimization problems using the objective function and the restriction functions. A computational program is implemented and applied in several examples. The augmented Lagrangian parameters senbility is analysed. The method is quite efficient in applications in optimization problems with dynamic restrictions.

Group sparsity reveals underlying sparsity patterns and contains rich structural information in data. Hence, exploiting group sparsity will facilitate more efficient techniques for recovering large and complicated data in applications such as compressive sensing, statistics, signal and image processing, machine learning and computer vision. This thesis develops efficient algorithms for solving a class of optimization problems with group sparse solutions, where arbitrary group configurations are allowed and the mixed L21-regularization is used to promote group sparsity. Such optimization problems can be quite challenging to solve due to the mixed-norm structure and possible grouping irregularities. We derive algorithms based on a variable splitting strategy and the alternating direction methodology. Extensive numerical results are presented to demonstrate the efficiency, stability and robustness of these algorithms, in comparison with the previously known state-of-the-art algorithms. We also extend the existing global convergence theory to allow more generality.

Orientador: José Mario Martínez Pérez / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-20T09:19:13Z (GMT). No. of bitstreams: 1 Prudente_LeandrodaFonseca_D.pdf: 1307430 bytes, checksum: 6ac8a3a70af28dce0b2cd6d839b227ef (MD5) Previous issue date: 2012 / Resumo: Algoritmos de programação não-linear práticos podem convergir para pontos inviáveis mesmo quando o problema a ser resolvido é viável. Quando isso ocorre, é natural que o usuário mude o ponto inicial e/ou parâmetros algorítmicos e reaplique o método na tentativa de encontrar uma solução viável e ótima. Desta forma, o ideal é que um algoritmo não só seja eficiente em encontrar soluções viáveis, mas também que detecte rapidamente quando ele está fadado a convergir para um ponto inviável. Na tentativa de atingir esse objetivo, apresentamos modificações em um algoritmo baseado em Lagrangiano aumentado de modo que, no caso de convergência para um ponto inviável, os subproblemas são resolvidos com tolerâncias moderadas e, mesmo assim, as propriedades de convergência global são mantidas. Experimentos numéricos são apresentados / Abstract Practical Nonlinear Programming algorithms may converge to infeasible points even when the problem to be solved is feasible. When this occurs, it is natural for the user to change the starting point and/or algorithmic parameters and reapply the method in an attempt to find a feasible and optimal solution. Thus, the ideal is that an algorithm is eficient not only in finding feasible solutions, but also in quickly detecting when it is fated to converge to an infeasible point. In pursuit of this goal, we present modifications of an algorithm based on Augmented Lagrangians so that, in the case of convergence to an infeasible point, the subproblems are solved with moderate tolerances and, even then, the global convergence properties are maintained. Numerical experiments are presented / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

In this research effort, we study three exterior penalty function approaches for solving linear programming problems. These methods are an active set l2 penalty approach (ASL2), an inequality-equality based l2 penalty approach (IEL2), and an augmented Lagrangian approach (ALAG). Particular effective variants are presented for each method, along with comments and experience on alternative algorithmic strategies that were empirically investigated. Our motivation is to examine the relative performance of these different approaches based on the basic l2 penalty function in order to provide insights into the viability of these methods for solving linear programs. To test the performance of these algorithms, a set of randomly generated problems as well as a set of NETLIB test problems from the public domain are used. By way of providing a benchmark for comparisons, we also solve the test problems using CPLEX 6.0, an advanced simplex implementation. While a particular variant (ALAG2) of ALAG performed the best for randomly generated test problems, ASL2 performed the best for the NETLIB test problems. Moreover, for test problems having only equality constraints, IEL2, and ASL2 (which is a finer-tuned version of IEL2 in this case) were comparable and yielded a second-best performance in comparison with ALAG2. Furthermore, a set of problems with relatively higher density parameter values, as well as a set of low-density problems were used to determine the effect of density on the relative performances of these methods. This experiment revealed that for linear programs with a high density parameter, ASL2 is the best alternative among the tested algorithms; whereas, for low-density problems ALAG2 is the fastest method. Moreover, although our implementation was rudimentary in comparison with CPLEX, all of the tested methods attained a final solution faster than CPLEX for the set of large-scale low-density problems, sometimes as fast as requiring only 16-23% of the effort consumed by CPLEX. Average rank tests based on the computational results obtained are performed using two different statistics, that assess the speed of convergence and the quality or accuracy of the solution, in order to determine the relative effectiveness of the algorithms and to validate our conclusions. Overall, the results provide insights into selecting algorithmic strategies based on problem structure and indicate that while this class of methods is viable for computing near optimal solutions, more research is needed to design robust and competitive exterior point methods for solving linear programming problems. However, the use of the proposed variant of the augmented Lagrangian method to solve large-scale low-density linear programs is promising and should be explored more extensively. / Master of Science

Since augmented Lagrangian methods were introduced by Powell and Hestenes, this class of methods has been investigated very intensively. While the finite dimensional case has been treated in a satisfactory manner, the infinite dimensional case is studied much less. The general approach to solve an infinite dimensional optimization problem subject to equality constraints is as follows: First one proves convergence for a basic algorithm in the Hilbert space setting. Then one discretizes the given spaces and operators in order to make numerical computations possible. Finally, one constructs a discretized version of the infinite dimensional method and tries to transfer the convergence results to the finite dimensional version of the basic algorithm. In this thesis we discuss a globally convergent augmented Lagrangian algorithm and discretize it in terms of functional analytic restriction operators. Given this setting, we prove global convergence of the discretized version of this algorithm to a stationary point of the infinite dimensional optimization problem. The proposed algorithm includes an explicit rule of how to update the discretization level and the penalty parameter from one iteration to the next one - questions that had been unanswered so far. In particular the latter update rule guarantees that the penalty parameters stay bounded away from zero which prevents the Hessian of the discretized augmented Lagrangian functional from becoming more and more ill conditioned. / Master of Science