Convergence analysis of an infeasible quasi-Newton bundle method for nonsmooth convex programming

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.

Key words： Non-smooth optimization; convex constraint; improvement function; bundle method; quasi-Newton direction

References

1 Bonnans J F, Gilbert J Ch, Lemaréchal C, Sagastizábal C A. A family of variable metric proximal methods. Math Program 1995; 68(1/2/3): 15–47

2 Byrd R H, Nocedal J. A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM J Numer Anal 1989; 26(3): 727–739

3 FletcherRLeyfferS. A bundle filter method for nonsmooth nonlinear optimization. Numerical Analysis Report NA/195, Dundee: Department of Mathematics, The University of Dundee, 1999

4 Frangioni A. Generalized bundle methods. SIAM J Optim 2002; 13(1): 117–156

5 Hare W, Sagastizábal C A. A redistributed proximal bundle method for nonconvex optimization. SIAM J Optim 2010; 20(5): 2442–2473

6 KiwielK C. Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Math, Vol 1133. Berlin: Springer-Verlag, 1985

7 Kiwiel K C. Exact penalty functions in proximal bundle methods for constrained convex nondifferentiable minimization. Math Program 1991; 52(1/2/3): 285–302

8 Kiwiel K C. A proximal bundle method with approximate subgradient linearizations. SIAM J Optim 2006; 16(4): 1007–1023

9 Kiwiel K C. A proximal-projection bundle method for Lagrangian relaxation, including semidefinite programming. SIAM J Optim 2006; 17(4): 1015–1034

10 Lemaréchal C, Sagastizábal C A. Practical aspects of the Moreau-Yosida regularization: theoretical preliminaries. SIAM J Optim 1997; 7(2): 367–385

11 Miffin R. An algorithm for constrained optimization with semismooth functions. Math Oper Res 1977; 2(2): 191–207

12 MifflinR. 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 Miflin R, Sun D F, Qi L Q. Quasi-Newton bundle type methods for nondifferentiable convex optimization. SIAM J Optim 1998; 8(2): 583–603

14 OliveiraWSolodovM. A doubly stabilized bundle method for nonsmooth convex optimization. 2013

15 Pironneau O, Polak E. Rate of convergence of a class of methods of feasible directions. SIAM J Numer Anal 1973; 10(1): 161–174

16 Sagastizabal C A, Solodov M. An infeasible bundle method for nonsmooth convex constrained optimization without a penalty function or a filter. SIAM J Optim 2005; 16(1): 146–169