Barrier operators and associated gradient-like dynamical systems for constrained minimization problems

被引:30
作者
Bolte, J
Teboulle, M
机构
[1] Univ Montpellier 2, Dept Math, ACSIOM CNRS FRE 2311, F-34095 Montpellier 5, France
[2] Tel Aviv Univ, Sch Math Sci, IL-69978 Ramat Aviv, Israel
关键词
dynamical systems; continuous gradient-like systems; elliptic barrier operators; Lotka-Volterra differential equations; asymptotic analysis; viability; Lyapunov functionals; explicit and implicit discrete schemes; interior proximal algorithms; global convergence; constrained convex minimization; Riemannian gradient methods;
D O I
10.1137/S0363012902410861
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We study some continuous dynamical systems associated with constrained optimization problems. For that purpose, we introduce the concept of elliptic barrier operators and develop a unified framework to derive and analyze the associated class of gradient-like dynamical systems, called A-driven descent method (A-DM). Prominent methods belonging to this class include several continuous descent methods studied earlier in the literature such as steepest descent method, continuous gradient projection methods and Newton-type methods as well as continuous interior descent methods such as Lotka-Volterra-type differential equations and Riemannian gradient methods. Related discrete iterative methods such as proximal interior point algorithms based on Bregman functions and second order homogeneous kernels can also be recovered within our framework and allow for deriving some new and interesting dynamics. We prove global existence and strong viability results of the corresponding trajectories of (A-DM) for a smooth objective function. When the objective function is convex, we analyze the asymptotic behavior at infinity of the trajectory produced by the proposed class of dynamical systems (A-DM). In particular, we derive a general criterion ensuring the global convergence of the trajectory of (A-DM) to a minimizer of a convex function over a closed convex set. This result is then applied to several dynamics built upon specific elliptic barrier operators. Throughout the paper, our results are illustrated with many examples.
引用
收藏
页码:1266 / 1292
页数:27
相关论文
共 37 条
[1]  
Alvarez F, 1998, APPL MATH OPT, V38, P193
[3]   An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping [J].
Alvarez, F ;
Attouch, H .
SET-VALUED ANALYSIS, 2001, 9 (1-2) :3-11
[4]  
[Anonymous], 1963, EQUATIONS DERIVEES P
[5]  
ANTIPIN AS, 1994, DIFF EQUAT+, V30, P1365
[6]   Viscosity solutions of minimization problems [J].
Attouch, H .
SIAM JOURNAL ON OPTIMIZATION, 1996, 6 (03) :769-806
[7]  
ATTOUCH H, IN PRESS J OPTIM THE
[8]  
Aubin J.-P., 1984, DIFFERENTIAL INCLUSI
[9]   Interior proximal and multiplier methods based on second order homogeneous kernels [J].
Auslender, A ;
Teboulle, M ;
Ben-Tiba, S .
MATHEMATICS OF OPERATIONS RESEARCH, 1999, 24 (03) :645-668
[10]   Asymptotic analysis for penalty and barrier methods in convex and linear programming [J].
Auslender, A ;
Cominetti, R ;
Haddou, M .
MATHEMATICS OF OPERATIONS RESEARCH, 1997, 22 (01) :43-62