A first order method for finding minimal norm-like solutions of convex optimization problems

被引:35
作者
Beck, Amir [1 ]
Sabach, Shoham [2 ]
机构
[1] Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
[2] Tel Aviv Univ, Sch Math Sci, IL-69978 Ramat Aviv, Israel
基金
以色列科学基金会;
关键词
Bilevel optimization; Complexity analysis; Convex minimization; Minimal norm solution; LINEAR-PROGRAMS; REGULARIZATION; PERTURBATION;
D O I
10.1007/s10107-013-0708-2
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
We consider a general class of convex optimization problems in which one seeks to minimize a strongly convex function over a closed and convex set which is by itself an optimal set of another convex problem. We introduce a gradient-based method, called the minimal norm gradient method, for solving this class of problems, and establish the convergence of the sequence generated by the algorithm as well as a rate of convergence of the sequence of function values. The paper ends with several illustrating numerical examples.
引用
收藏
页码:25 / 46
页数:22
相关论文
共 18 条
[1]  
[Anonymous], 1999, Athena scientific Belmont
[2]  
[Anonymous], 2013, Introductory lectures on convex optimization: A basic course
[3]  
[Anonymous], 1979, SIAM REV, DOI DOI 10.1137/1021044
[4]  
Beck A., 2003, THESIS SCH MATH SCI
[5]  
Ben-Tal A., 2001, Lectures on modern convex optimization, V2
[6]  
BENISRAEL A, 1982, MATH PROGRAM STUD, V19, P16, DOI 10.1007/BFb0120981
[7]   CONVERGENCE ANALYSIS OF A PROXIMAL-LIKE MINIMIZATION ALGORITHM USING BREGMAN FUNCTIONS [J].
Chen, Gong ;
Teboulle, Marc .
SIAM JOURNAL ON OPTIMIZATION, 1993, 3 (03) :538-543
[8]  
Colson B., 2005, 4OR, V4or, P87, DOI [10.1007/s10288-005-0071-0, DOI 10.1007/S10288-005-0071-0]
[9]   FINITE PERTURBATION OF CONVEX-PROGRAMS [J].
FERRIS, MC ;
MANGASARIAN, OL .
APPLIED MATHEMATICS AND OPTIMIZATION, 1991, 23 (03) :263-273
[10]   EXACT REGULARIZATION OF CONVEX PROGRAMS [J].
Friedlander, Michael P. ;
Tseng, Paul .
SIAM JOURNAL ON OPTIMIZATION, 2008, 18 (04) :1326-1350