Localizer-based Level Bundle Methods For Nonsmooth Constrained Convex Optimization

Nonsmooth optimization is a special class of optimization problems which is widely used in image denoising,optimal control,machine learning,compressed sensing and other practical fields.It is an important research branch of optimization theory and method,and also a hot research field for many scholars at home and abroad.The design of fast and effective numerical solution methods is one of the core contents of nonsmooth optimization research.The existing nonsmooth optimization methods mainly focus on solving unconstrained or simple constrained optimization problems.However,many practical problems often have complex constraints.On the other hand,with the rise of some practical fields,such as artificial intelligence,machine learning,big data,etc.Many nonsmooth optimization problems are characterized by large scale,complex structure and difficulty in solving.Therefore,how to design new efficient methods for solving nonsmooth constrained optimization problems is an important research topic.In this paper,two novel level bundle methods are proposed for solving general nonsmooth convex constrained optimization problems.Firstly,a localizer-based level bundle method is proposed for nonsmooth convex constrained optimization.The main features of this method are: an approximate polyhedron model of the original problem is constructed by means of the idea of bundle method;the improvement function is introduced to measure the decrease of the objective function and the feasibility of the constraint function;the algorithm adopts the pattern of external iteration and nested inner loop,which is easier to analyze the complexity of the algorithm;in the subproblem,the proximal function is used to generalize the Euclidean distance,which can make full use of the geometry of the feasible set and thus reduce the computation cost;a simple and effective approximation to the level set is obtained by introducing a sequence of localizers instead of the traditional bundle aggregation and compression strategies;the global convergence and iteration complexity of the algorithm are analyzed.Secondly,an improved localizer-based constrained level bound method is proposed.Although the above method has good theoretical properties,it may occur that the subproblem is infeasible(i.e.,the constraints are incompatible)in the iterative process.Therefore,it is necessary to judge the feasibility of the subproblem in advance.However,in some critical cases,this may lead to numerical error.In order to overcome this difficulty,a relatively relaxed feasibility detection criterion is proposed.When the criterion is satisfied,the subproblem must be consistent,thus avoiding the direct judgment of its feasibility and enhancing the numerical stability.The improved method still has global convergence and the corressponding iteration complexity.Finally,the two constrained level bundle methods proposed in this paper are tested numerically and compared with the existing method.Numerical results show that the constrained level bundle methods presented in this paper have some advantages.