Secant Approximation Methods for Convex Optimization

Abstract

The methods discussed are based on local piecewise-linear secant approximations to continuous convex objective functions. Such approximations are easily constructed and require only function evaluations rather than derivatives. Several related iterative procedures are considered for the minimization of separable objectives over bounded closed convex sets. Computationally, the piecewise-linear approximation of the objective is helpful in the case that the original problem has only linear constraints, since the subproblems in this case will be linear programs. At each iteration, upper and lower bounds on the optimal value are derived from the piecewise-linear approximations. Convergence to the optimal value of the given problem is established under mild hypotheses. The method has been successfully tested on a variety of problems, including a water supply problem with more than 900 variables and 600 constraints.