Generalized Saddle Points Seeking Algorithms for Convex Optimization Problems

Abstract

The paper focuses on convex optimization problems, assuming that the cost and constraint functions are not analytically known, and only the values of the associated Lagrangian are available. One of the main contributions is the introduction of a general family of dynamical systems, whose trajectories converge to an arbitrarily small neighborhood of a saddle point of the associated Lagrangian. The vector fields of the proposed systems exploit only the values of the Lagrangian and thus are derivative-free. Unlike previous derivative-free saddle point seeking methods, this approach utilizes a generalized Lagrangian, which provides certain advantages like driftless dynamics, convergence for almost all initial conditions, and others. It is proven that, in general, the set of saddle points is practically asymptotically stable for the obtained systems. Additionally, it is demonstrated that a special choice of vector fields leads to asymptotic stability in the sense of Lyapunov. The obtained results are illustrated with several examples.

Authors 2

1. Victoria Grushkovskaya

   University of Klagenfurt

   Affiliation as printed

   University of Klagenfurt,Department of Mathematics,Klagenfurt,Austria,9020

2. Christian Ebenbauer Aachen Chair of Intelligent Control Systems

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University,Chair of Intelligent Control Systems,Aachen,Germany,52074