- Main
Quasi-Newton Algorithms for Non-smooth Online Strongly Convex Optimization
- Godwin, Mark Franklin
- Advisor(s): Borrelli, Francesco
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
Enter the password to open this PDF file:
-
-
-
-
-
-
-
-
-
-
-
-
-
-