Please wait a minute...
Frontiers of Mathematics in China

ISSN 1673-3452

ISSN 1673-3576(Online)

CN 11-5739/O1

Postal Subscription Code 80-964

2018 Impact Factor: 0.565

Front. Math. China    2023, Vol. 18 Issue (5) : 367-380    https://doi.org/10.3868/s140-DDD-023-0026-x
Convergence analysis of an infeasible quasi-Newton bundle method for nonsmooth convex programming
Jie SHEN1(), Fangfang GUO2, Liping PANG2
1. School of Mathematics, Liaoning Normal University, Dalian 116029, China
2. School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China
 Download: PDF(549 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

By utilizing the improvement function, we change the nonsmooth convex constrained optimization into an unconstrained optimization, and construct an infeasible quasi-Newton bundle method with proximal form. It should be noted that the objective function being minimized in unconstrained optimization subproblem may vary along the iterations (it does not change if the null step is made, otherwise it is updated to a new function). It is necessary to make some adjustment in order to obtain the convergence result. We employ the main idea of infeasible bundle method of Sagastizàbal and Solodov, and under the circumstances that each iteration point may be infeasible for primal problem, we prove that each cluster point of the sequence generated by the proposed algorithm is the optimal solution to the original problem. Furthermore, for BFGS quasi-Newton algorithm with strong convex objective function, we obtain the condition which guarantees the boundedness of quasi-Newton matrices and the R-linear convergence of the iteration points.

Keywords Non-smooth optimization      convex constraint      improvement function      bundle method      quasi-Newton direction     
Corresponding Author(s): Jie SHEN   
Online First Date: 27 December 2023    Issue Date: 11 January 2024
 Cite this article:   
Jie SHEN,Fangfang GUO,Liping PANG. Convergence analysis of an infeasible quasi-Newton bundle method for nonsmooth convex programming[J]. Front. Math. China, 2023, 18(5): 367-380.
 URL:  
https://academic.hep.com.cn/fmc/EN/10.3868/s140-DDD-023-0026-x
https://academic.hep.com.cn/fmc/EN/Y2023/V18/I5/367
1 J F Bonnans, J Ch Gilbert, C Lemaréchal, C A Sagastizábal. A family of variable metric proximal methods. Math Program 1995; 68(1/2/3): 15–47
2 R H Byrd, J Nocedal. A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM J Numer Anal 1989; 26(3): 727–739
3 R FletcherS Leyffer. A bundle filter method for nonsmooth nonlinear optimization. Numerical Analysis Report NA/195, Dundee: Department of Mathematics, The University of Dundee, 1999
4 A Frangioni. Generalized bundle methods. SIAM J Optim 2002; 13(1): 117–156
5 W Hare, C A Sagastizábal. A redistributed proximal bundle method for nonconvex optimization. SIAM J Optim 2010; 20(5): 2442–2473
6 K C Kiwiel. Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Math, Vol 1133. Berlin: Springer-Verlag, 1985
7 K C Kiwiel. Exact penalty functions in proximal bundle methods for constrained convex nondifferentiable minimization. Math Program 1991; 52(1/2/3): 285–302
8 K C Kiwiel. A proximal bundle method with approximate subgradient linearizations. SIAM J Optim 2006; 16(4): 1007–1023
9 K C Kiwiel. A proximal-projection bundle method for Lagrangian relaxation, including semidefinite programming. SIAM J Optim 2006; 17(4): 1015–1034
10 C Lemaréchal, C A Sagastizábal. Practical aspects of the Moreau-Yosida regularization: theoretical preliminaries. SIAM J Optim 1997; 7(2): 367–385
11 R Miffin. An algorithm for constrained optimization with semismooth functions. Math Oper Res 1977; 2(2): 191–207
12 R Mifflin. A modification and an extension of Lemarechal’s algorithm for nonsmooth minimization. In: Nondifferential and Variational Techniques in Optimization, Math Program Stud, Vol 17. Berlin: Springer-Verlag, 1982, 77–90
13 R Miflin, D F Sun, L Q Qi. Quasi-Newton bundle type methods for nondifferentiable convex optimization. SIAM J Optim 1998; 8(2): 583–603
14 W OliveiraM Solodov. A doubly stabilized bundle method for nonsmooth convex optimization. 2013
15 O Pironneau, E Polak. Rate of convergence of a class of methods of feasible directions. SIAM J Numer Anal 1973; 10(1): 161–174
16 C A Sagastizabal, M Solodov. An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or a filter. SIAM J Optim 2005; 16(1): 146–169
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed