ProfOptimization2016

Seminar 2025.1

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

March 20, 2025

Duas heurísticas para o problema da mochila bidimensional

Layane Rodrigues de Souza Queiroz

Neste trabalho duas heurísticas são propostas para o problema da mochila bidimensional. A primeira é uma heurística baseada no algoritmo genético de chaves aleatórias viciadas, enquanto a segunda implementa uma busca em vizinhança variável. As heurísticas consideram formas diferentes de conduzir o processo de otimização, a primeira sobre múltiplas trajetórias (isto é, uma população de indivíduos) e a segunda considerando uma trajetória única. Propõe-se na implementação da primeira heurística que a probabilidade viciada de herdar informações dos melhores indivíduos faz parte do próprio indivíduo, ao invés de ser um parâmetro constante durante a otimização. Adota-se para as heurísticas que uma solução do problema é codificada por um vetor de inteiros. Ao invés do vetor conter apenas os números que identificam os itens, propõe-se incluir outros números para auxiliar durante o posicionamento dos itens. Dessa forma, não necessariamente um item vai ser posicionado na primeira posição válida do recipiente, ajudando a escapar de possíveis ótimos locais. O posicionamento de itens no recipiente segue a sequência obtida do vetor que representa a solução, adotando-se três regras, uma que é a bottom-left e outras duas propostas com base nela. As duas heurísticas são comparadas com a heurística geral de Mundim et al. (2018), até então estado-da-arte para o problema da mochila, conseguindo obter resultados iguais ou melhores para todas as instâncias. A primeira heurística é capaz de obter soluções cuja ocupação do recipiente é quase 7% maior, na média, enquanto a segunda heurística traz uma melhora na ocupação do recipiente de quase 6%, na média, comparado com Mundim et al. (2018). Para uma instância é possível melhorar a ocupação em quase 18%.

March 27, 2025

A fully subsampled cubic regularization method for finite-sum minimization

Max Leandro Nobre Gonçalves

In this talk, we propose and analyse a fully subsampled Cubic Regularization Method (F-CRM) for solving finite-sum optimization problems. The proposed method uses a general 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.

April 3, 2025

Proximal Alternating Minimization for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality

Tiago Sousa Mota

In this talk, we will present the convergence properties of an alternating proximal minimization algorithm for non-convex structured functions of the type: L(x, y) = f (x) + Q(x, y) + g(y) , where f and g are proper lower semicontinuous functions defined on Euclidean spaces and Q is a smooth function coupling the variables x and y. The results are in a non-convex setting, assuming only that the function L satisfies the Kurdyka-Łojasiewicz inequality. The main result can be stated as follows: If L has the Kurdyka-Łojasiewicz property, then every bounded sequence generated by the algorithm converges to a critical point of L. This result is completed by the study of the convergence rate of the algorithm, which depends on the geometric properties of the function L around its critical points.

April 10, 2025

Global convergence of an augmented Lagrangian method from a Riemannian perspective

Kelvin Rodrigues Couto

Considering a standard nonlinear programming problem, it is possible to interpret a subset of equality constraints as an embedded Riemannian manifold. This presentation examines the distinctions between the Euclidean and Riemannian approaches to this class of problems. It is well-established that the linear independence constraint qualification is equivalent under both methodologies. However, when examining the recently proposed constant rank constraint qualifications, the Riemannian framework yields a weaker condition, as it requires that the gradients' rank remains constant only within the manifold itself. Conversely, the Euclidean method mandates constant rank properties throughout a full-dimensional neighborhood of the ambient space. Consequently, by applying a Riemannian augmented Lagrangian method to a standard nonlinear programming problem, standard global convergence to a Karush/Kuhn-Tucker point is achieved under a newly introduced weaker constant rank condition that considers only lower-dimensional neighborhoods. Thus, the Riemannian viewpoint demonstrates the potential to generate novel and stronger outcomes for classical optimization problems traditionally solved through Euclidean methods. Additionally, two distinct augmented Lagrangian algorithms are evaluated via an extensive computational analysis, revealing several classes of problems for which the Riemannian approach significantly outperforms the Euclidean method, producing solutions of superior quality.

April 17, 2025

Convergence of Inexact Proximal Gradient Methods for Composite Optimization Problems

Claudemir Rodrigues Santiago

In this talk, we present results based on the work by Huang et al., Inexact Proximal Gradient Methods for Non-Convex and Non-Smooth Optimization, Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), 2018. We will discuss recent advances in the development and theoretical analysis of inexact proximal gradient methods applied to composite optimization problems, both convex and non-convex. These methods are widely used in settings involving non-smooth regularization, particularly in machine learning. We introduce three variants of inexact proximal gradient algorithms (including a basic version and an accelerated version inspired by Nesterov) and present convergence analysis of the accelerated algorithm for the convex case.

April 24, 2025

A Proximal Gradient method with an explicit line search for multiobjective optimization

Leandro da Fonseca Prudente

We present a proximal gradient method for solving convex multiobjective optimization problems, where each objective function is the sum of two convex functions, with one assumed to be continuously differentiable. The algorithm incorporates a backtracking line search procedure that requires solving only one proximal subproblem per iteration, and is exclusively applied to the differentiable part of the objective functions. Under mild assumptions, we show that the sequence generated by the method convergences to a weakly Pareto optimal point of the problem. Additionally, we establish an iteration complexity bound by showing that the method finds an ε-approximate weakly Pareto point in at most O(1/ε) iterations.

May 15, 2025

Busemann function on the set of symmetric positive definite matrices

Maurício Silva Louzeiro

In this seminar, we will discuss the role of the Busemann function in optimization on manifolds. Specifically, we will present a new explicit expression for the Busemann function and its gradient in the case where the manifold is the set of symmetric positive definite matrices. We will also outline the main steps involved in deriving these expressions.

May 22, 2025

Convergence Analysis of Descent Optimization Algorithms under Polyak-Łojasiewicz-Kurdyka Conditions

Tiago Sousa Mota

In this talk, we present a comprehensive convergence analysis of generic classes of descent algorithms in nonconvex optimization under various Polyak-Łojasiewicz-Kurdyka (PLK) conditions. In particular, we revisit and extend the results on convergence rates presented by Khanh, Mordukhovich, and Tran (J. Optim. Theory Appl., 2023), refining the understanding of the zero exponent in smooth KL functions and extending the discussion on the inconsistency between the lower exponent KL property and the continuity of Lipschitz gradients to more general settings. Among other contributions, we establish finite termination of generic algorithms under lower exponent PLK conditions and superlinear convergence when a modified relative error condition can be ensured. Furthermore, we derive new convergence rates for inexact reduced gradient methods and certain variants of the boosted algorithm in DC programming. Notably, we reveal that for a broad class of difference programs, the lower-exponent PLK conditions are inherently incompatible with Lipschitz continuity of the gradient of the DC function near a local minimizer. However, we demonstrate that this inconsistency may not hold if Lipschitz continuity is replaced by gradient continuity alone.

May 29, 2025

Improved convergence rates for the multiobjective Frank-Wolfe method

Jefferson D. Gonçalves de Melo

In this talk, we analyze the convergence rates of the Frank-Wolfe method for solving convex constrained multiobjective optimization. We establish improved convergence rates under different assumptions on the objective function, the feasible set, and the localization of the limit point of the sequence generated by the method. In particular, linear converge is obtained under some special assumptions.

June 5, 2025

Busemann Functions and Some Recent Advances in Optimization on Riemannian Manifolds

Glaydston de Carvalho Bento

In this lecture, I intend to present some recent advances in optimization on Riemannian manifolds. Taking into account the absence of non-constant affine functions in complete and connected $n$-dimensional Riemannian manifolds of negative Ricci curvature on some open set, we explore theoretical aspects related to the applicability of the proximal point method to equilibrium problems, as well as the Fenchel-type conjugate defined as the supremum of convex functions, both via Busemann functions. In particular, we discuss the existence of non-trivial affine functions on Riemannian manifolds.

June 12, 2025

Método do Gradiente Projetado em variedades Hadamard

Alejandra Muñoz González

Neste seminário, abordaremos o problema da minimização de funções diferenciáveis em subconjuntos geodesicamente convexos e fechados de variedades de Hadamard. Para resolver esse problema, propomos o Método do Gradiente Projetado Riemanniano (MGPR), uma adaptação do método do gradiente projetado ao contexto Riemanniano. Analisamos as propriedades de convergência do método, estendendo resultados clássicos da otimização com restrições no espaço euclidiano para variedades de Hadamard e demonstramos sua convergência sob hipóteses adequadas.

June 26, 2025

On FISTA methods with inexact relative rules

José Roberto Ribeiro Júnior

In this talk, we discuss some recent versions of FISTA method under different relative rules.