CCOR Workshop on Nonlinear Programming

13:00-14:00

Radu Ioan Bot: Fast methods for linearly constrained convex optimization problems in continuous and discrete time

In this talk we address the minimization of a continuously differentiable convex function under linear equality constraints.

We consider a second-order dynamical system with asymptotically vanishing damping term formulated in terms of the Augmented Lagrangian associated with the minimization problem. Time discretization leads to an inertial algorithm with a general rule for the inertial parameters that covers the classical ones by Nesterov, Chambolle-Dossal and Attouch-Cabot used in the context of fast gradient methods. In both settings we prove fast convergence of the primal-dual gap, the feasibility measure, and the objective function value along the generated trajectory/iterates, and weak convergence of the primal-dual trajectory/iterates to a primal-dual optimal solution.

For the unconstrained minimization of a convex differentiable function, we rediscover all convergence statements obtained in the literature for Nesterov’s accelerated gradient method.

If time permits, an alternative approach relying on the fast solving of monotone equations will be also presented.

14:00-14:30 Coffee break

14:30-15:00

Tibor Illés: New algorithms for generating Pareto-optimal points of multi-objective optimization problems

Co-authors: Sorin-Mihai Grad (Department of Applied Mathematics, ENSTA, Paris) Petra R. Rigó (Corvinus Centre for Operations Research, Corvinus University of Budapest)

In the presentation, we present a new algorithm for generating Pareto-optimal points of multi-objective optimization problems. One of the cornerstones of the algorithm is the way in which the joint decreasing directions of the objective functions are determined. In our case, we use a linear programming auxiliary problem to determine (one of) the joint decreasing directions. The LP auxiliary problem can be solved efficiently in polynomial time. Variants of our new algorithm were also developed for different classes of multi-objective optimization problems like unconstrained, problems with sign restricted variables, and problems with linear constraints.

For each problem class, for the sequence of points produced by our algorithm during the solution of multi-objective optimization problems we prove that if we have an accumulation point then it is a substationary point, as well. In addition, if we assume that the objective functions are convex, then the substationary point is also a Pareto-optimal solution to the problem.

We will be able to complete our result by developing the conditions and proofs that ensure the existence of the accumulation point of the series of points produced by the algorithm.

15:00-15:30

Marianna Eisenberg-Nagy: Linear and nonlinear programming-based approaches to deciding matrix sufficiency

Co-authors: Tibor Illés (Corvinus Centre for Operations Research, Corvinus University of Budapest), Anita Varga (Institute of Mathematics, Budapest University of Technology and Economics), Janez Povh, Janez Žerovnik (Faculty of Mechanical Engineering, University of Ljubljana)

In this talk we deal with different aspects of sufficient matrices, one of the most important matrix classes introduced in connection with linear complementarity problems.

Tseng proved in 2000 that the decision problem whether a matrix is sufficient is co-NP hard. We investigate two different algorithms for determining the sufficiency of a given matrix: a linear programming-based algorithm, and an algorithm that facilitates nonlinear programming reformulations of the definition of sufficiency.

We tested the efficiency of these methods on our recently launched benchmark data set.

You can inquire about the possibility of connecting online at the email address marianna.eisenberg-nagy@uni-corvinus.hu.

We encourage all interested colleagues to participate at these interesting events.