Cutting plane algorithms and approximate lower subdifferentiability (Q535075): Difference between revisions

This paper introduced and investigated a notation of approximate lower subdifferentiability. It used the fact that a conjugation of the Fenchel-Moreau type can be introduced for quasiconvex functions using quasi-affine functions or the coupling functional. This paper intends to use this concept to develop cutting plane algorithms. It relaxes the compactness assumption on sublevels sets and the boundedness assumption on the lower subgradient made other paper and, more importantly, the authors allow the occurrence of some inaccuracy. In order to guarantee the convergence of the algorithm, the authors require a weak form of boundedness of approximate lower subdifferentials. In this paper, the class of boundedly approximately lower subdifferentiable functions is defined and shown to be very closely related to the class of continuous and quasiconvex functions. Approximate lower subdifferentiability is studied in which calculus rules are provided. A basic cutting plane algorithm for minimizing an lower subdifferentiable function is constructed and its convergence is discussed. Two algorithms for constrained optimization are proposed where the constraining functions are involved in the construction of cutting planes. The OCP (outer cutting plane) algorithm gives an approximate solution sufficiently close to the feasible set, but not necessarily in the feasible set. On the other hand, the ICP (inner cutting plane) algorithm generates feasible points only, but the solution just gives an approximate value of the objective function over a more restricted constraint set. When combined, these two algorithms give good enough approximate solutions.