Inexact Bundle Methods For Two Types Of Nonsmooth Convex Optimization Problems

For nonsmooth optimization problems,such as minimax problems,two-stage stochastic programming problems,etc,these problems are difficult to calculate the exact first-order information(function values and subgradients),so that the nonsmooth optimization methods based on accurate data is slower or even impossible to solve.Therefore,how to establish feasible and efficient nonsmooth optimization methods to solve these practical problems has be-come a research focus for optimization researchers at home and aboard.Aim-ing at the above difficulties,inexact bundle methods for solving two types of nonsmooth convex optimization problems are proposed.Firstly,we propose a proximal-projection bundle method based on ora-cles with on-demand accuracy for a class of nonsmooth optimization prob-lems with convex set constraint.The oracles depend on two additional param-eters,namely,a desent target and an error bound.According to the selection of the two parameters,the oracles contain five cases of exact,partially inex-act,inexact,asymptotically exact and partially asymptotically exact oracles.The method transforms it into an equivalent nonsmooth unconstrained convex optimization problem by introducing an indicator function.Each iteration alternately solves two subproblems based on the oracles,namely,proximal subproblems and projection subproblems.The proximal subproblem keeps the polyhedron model of the objective function unchanged and linearizes the indicator function.The projector problem linearizes the polyhedron model and keeps the indicator function unchanged.Solving the proximal subprob-lem is to generate an approximate linearized model of the objective function under the condition of on-demand accuracy oracles;Solving the projection subproblem is to obtain the trial point.Finally,the global convergence of the algorithm under different types of the oracles is established.Secondly,for a class of unconstrained convex optimization problems with special structure,and the objective function which is the sum of two nonsmooth convex functions,an alternating linearized bundle method with on-demand accuracy oracles is proposed.The oracles contain the five cases of oracles above.Each iteration alternately solves two subproblems based on the oracles and each subproblem linearizes one function which the other function remains unchanged.Finally,the global convergence of the algorithm is established under different types of the oracles.Finally,preliminary numerical experiments are carried out on the inexact bundle methods proposed in this paper.For all kinds of the oracles,the test instances are a few two-stage stochastic programming problems which are a telecommunication design and the motor freight carrier routing problems.Compared with the existing methods,the inexact bundle methods proposed in this paper have more advantages in numerical results.