Skip to main content
eScholarship
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Electronic Theses and Dissertations bannerUC Berkeley

Quasi-Newton Algorithms for Non-smooth Online Strongly Convex Optimization

Abstract

The growing prevalence of networked systems with local sensing and computational capability will result in an increasing array of online and large scale optimization problems. We adopt the framework of online convex optimization that allows for the optimization of an arbitrary sequence of convex functions subject to a single convex constraint set. We identify quasi-Newton algorithms as a promising class of algorithms to solve online strongly convex optimization problems. We first examine the relationships between several known algorithms for convex functions that satisfy a α-exp-concave assumption. Next we present two new quasi-Newton algorithms for non-smooth strongly convex functions and show how these algorithms can be parallelized given a summed objective function. Our new algorithms require fewer parameters and have provably tighter bounds then similar known algorithms. Also, our bounds are not a function of the number of iterations, but instead a function of the sequence of strongly convex parameters that correspond to a sequence of strongly convex functions. We then extend these algorithms to use a block diagonal hessian approximation. An algorithm with a fully diagonal hessian approximation results in a large scale quasi-Newton algorithm for online convex optimization. Our results can be translated to convergence bounds and optimization algorithms that solve non-smooth strongly convex functions. We perform numerical experiments on test functions of different dimension and compare our algorithms to similar known algorithms. These experiments show our algorithms perform well in the majority of test cases we consider. We apply our algorithms to online portfolio optimization with a l2-norm regularized constant-rebalanced portfolio model and compare our algorithm to known methods. In addition, a heuristic algorithm for online vehicle routing is presented. Although online vehicle routing does not fit within the framework of online convex optimization, the work provided significant insight into online optimization and provides a future source of ideas and motivation. Finally, we provide conclusions and discuss future research directions.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View