ProfOptimization2016

Seminar 2022.1

Organizer: Leandro F. Prudente. Talks are held in the Lecture Room of IME/UFG unless otherwise stated.

June 2, 2022

Subsampled Cubic Regularization Method for Finite-Sum Minimization

Max Leandro Nobre Gonçalves

In this talk, we propose and analyze a subsampled Cubic Regularization Method (CRM) for solving finite-sum optimization problems. The new method uses random subsampling techniques to approximate the functions, gradients and Hessians in order to reduce the overall computational cost of the CRM. Under suitable hypotheses, first- and second-order iteration-complexity bounds and global convergence analyses are presented. We also discuss the local convergence properties of the method. Numerical experiments are presented to illustrate the performance of the proposed scheme.

June 9, 2022

Complexidade por iteração dos métodos: Iterative Shrinkage-Thresholding (ISTA), Fast Iterative Shrinkage-Thresholding (FISTA) e o Accelerated Forward-Backward (AFB)

Douglas Nascimento Ribeiro

No contexto de otimização existe um aspecto muito importante a ser analisado no que diz respeito a eficiência de um algoritmo. Tal eficiência pode ser mensurada pela velocidade com que a sequência, gerada pelo algoritmo, converge para uma solução do problema em questão, ou seja, a taxa de convergência assintótica ( convergência sublinear, linear ou quadrática, etc). Também podemos medir tal eficiência pela complexidade por iteração do método em questão. Neste trabalho, iremos apresentar eficiência dos métodos, ISTA, FISTA e o AFB, através da complexidade por iteração dos mesmos. Mas o que vem a ser essa “tal” complexidade por iteração? Bem, a complexidade por iteração de um método refere-se a quantidade de iterações necessárias para se obter uma solução ε-ótima para certo problema. Portanto, apresentaremos a complexidade por iteração, dos métodos já citados, do ponto de vista teórico e computacional. Para as análises computacionais utilizaremos o Julia, uma linguagem de programação.

June 23, 2022

Complexidade em métodos quase-Newton

Danilo Rodrigues de Souza

Recentemente, Anton Rodomanov e Yurii Nesterov estudaram a complexidade de métodos quase-Newton da classe convexa de Broyden. Em particular, eles mostraram que o método BFGS possui complexidade O((1/k)^(k/2)), caracterizando convergência superlinear. Nesta palestra discutiremos esses resultados com vistas à extensão para otimização multiobjetivo.

June 30, 2022

Análise dos resultados associados a uma variante do método Accelerated Forward-Backward de Nesterov

Douglas Nascimento Ribeiro

Nesta exposição apresentarei os resultados do paper: THE RATE OF CONVERGENCE OF NESTEROV’S ACCELERATED FORWARD-BACKWARD METHOD IS ACTUALLY FASTER THAN 1/k−2.

July 7, 2022

On the computation of inexact K-steepest descent directions in Vector Optimization

Luis Román Lucambio Pérez

The concept of σ-approximate steepest descent direction in vector optimization was introduced by Iusem & Grana Grummond in 2004. Recently, Graña Drummond & Fukuda wrote about the advantages of such direction in first-order algorithms when compared to the use of the steepest descent direction. In this talk, we will present an algorithm for computing a σ-approximate steepest descent direction.

July 14, 2022

Sobre o cálculo da direção de máxima descida e da direção do tipo-Newton para problemas bi-objetivos

Leandro da Fonseca Prudente

Neste seminário discutiremos as formulações duais dos problemas de calcular a direção de máxima descida e da direção do tipo-Newton para problemas bi-objetivos. Aspectos algorítmicos e numéricos serão considerados.

July 21, 2022

Computing Approximate Solutions of Composite Optimization Problems via Proximal Regularizations

Jefferson D. Gonçalves de Melo

In this talk, we will consider a non-convex composite optimization problem for which the objective function is of the form f=g+h, where g is convex and h is non-convex and differentiable with Lipschitz continuous gradient. An interesting approach for solving this problem is via convexification using proximal regularizations. We will analyze this approach and show how approximate solutions of the regularized proximal subproblems are related to the ones of the main problem, and also discuss how this approach can be applied for solving augmented Lagrangian subproblems.

July 28, 2022

Complexidade do método BFGS para otimização multiobjetivo

Danilo Rodrigues de Souza

Recentemente, surgiram trabalhos que estudam a complexidade do método BFGS para o caso escalar. Anton Rodomanov e Yurii Nesterov mostraram que o método BFGS possui complexidade O((1/k)^(k/2)), caracterizando convergência super linear. Nesta palestra apresentaremos a extensão, para otimização multiobjetivo, dos resultados obtidos no caso escalar.

August 4, 2022

Coercivity and Generalized Proximal Algorithms. Application: Traveling Around the World

Erik Alex Papa Quiroz

In this tlak it is presented an inexact proximal point algorithm using quasi distances to solve a minimization problem in the Euclidean space. This algorithm is motivated by the proximal method introduced by Attouch, Bolte and Svaiter, section 4, (Math. Program., Ser A, 137: 91-129, 2013) and Solodov and Svaiter (Set Valued Anal., 7, 323-345, 1999). In contrast, in the present approach it is considered quasi distances, arbitrary (non necessary smooth) objective functions, scalar errors in each objective regularized approximation and vectorial errors on the residual of the regularized critical point, that is, we have an error on the optimality condition of the proximal subproblem at the new point. We obtain, under a coercivity assumption of the objective function, that all accumulation points of the sequence generated by the algorithm are critical points (minimizer points in the convex case) of the minimization problem. As an application it is considered a human location problem: How to travel around the world and prepare the trip of a lifetime.

August 11, 2022

A subgradient method with non-monotone line search

Orizon Pereira Ferreira

In this talk will be presented a subgradient method with non-monotone line search for the minimization of convex functions with simple convex constraints. Different from the standard subgradient method with prefixed step sizes, the new method selects the step sizes in an adaptive way. Under mild conditions asymptotic convergence results and iteration-complexity bounds are obtained. Preliminary numerical results illustrate the relative efficiency of the proposed method.

August 18, 2022

Métodos Acelerados de Primeira Ordem

Douglas Nascimento Ribeiro

A análise da eficiência de algoritmos para resolver problemas de otimização é fundamental para o aprimoramento e elaboração de algoritmos com melhores desempenhos computacionais. Tal eficiência pode ser mensurada, por exemplo, pela ``velocidade" com que a sequência gerada pelo algoritmo converge para uma solução do problema em questão, ou seja, a taxa de convergência assintótica (convergência sublinear, linear ou quadrática, etc). A partir dos trabalhos de Nesterov e Nemirovski na década de 80, a eficiência de um algoritmo passou também a ser considerada por meio de sua complexidade por iteração, isto é, o número de iterações necessárias para obter uma ``solução aproximada" do problema de interesse. Neste trabalho, iremos analisar a complexidade por iteração dos algoritmos Iterative Shrinkage-Thresholding (ISTA), Fast Iterative Shrinkage-Thresholding (FISTA) e um método acelerado Forward-Backward de Nesterov. Este estudo será feito do ponto de vista teórico e computacional.

August 25, 2022

On Newton's method for solving generalized equations

Paulo César da Silva Júnior

In this paper written by O. P. Ferreira, C. Jean-Alexis, A. Piétrus, G. N. Silva, I am going to present the convergence properties of a Newton-type method for solving generalized equations under a majorant condition. To this end, it is used a contraction mapping principle. More precisely, I am going to present semi-local convergence analysis of the method for generalized equations involving a set-valued map, the inverse of which satisfying the Aubin property.

September 1, 2022

Conjugada de Fenchel no contexto Multiobjetivo

Tiago Sousa Mota

Nesta palestra será apresentado um breve resumo relacionado a conjugada de Fenchel e suas principais propriedades no caso escalar. Então, será discutida uma abordagem dessa teoria no contexto multiobjetivo explorando as principais propriedades com o objetivo de estudar o "DCA" para problemas vetoriais.

September 8, 2022

Método HPE e sua versão acelerada para otimização convexa

Marcus Vinícius de Morais Chagas

Nesse trabalho apresenta uma variante acelerada do extragradiente proximal híbrido (HPE) para otimização convexa, referido como uma estrutura HPE acelerada (A-HPE). Os resultados de complexidade de iteração são estabelecidos para a estrutura A-HPE, bem como uma versão especial dele, no caso de primeira ordem, que por consequência se reduzirá a método FISTA, caso o conjunto convexo fechado $\Omega=\R^{n}$.No método A-HPE é descrito no contexto de um problema de otimização convexa estruturado cujo função objetivo consiste na soma de uma função convexa suave e uma função não-suave. Nessa implementação, uma generalização de uma variante do método de Nesterov é obtido para o caso onde a componente suave da função objetivo tem Lipschitz contínua do seu gradiente.Mas antes apresentaremos as definições básicas a respeito de operador ponto-a-conjunto, e após operador $\epsilon$-alargamento segundo Burachhik,Iussem e Svaiter.

Schedule:

June 2 - Max 9 - Douglas 23 - Danilo 30 - Douglas July 7 - Luis Román 14 - Leandro 21 - Jefferson 28 - Danilo August 4 - Erik 11 - Orizon 18 - Defesa Douglas 25 - Paulo César September 1 - Tiago 8 - Marcos Vinícius