UC Santa Barbara

This thesis consists of three parts focusing on three different problems. All of these problems have optimization at heart yet they are related to different branches of optimization.

Our first problem is on the convergence rate of two moment based methods, Polyak's Heavy Ball and Nesterov's Accelerated Gradient, employing adaptive restart. We introduce two criteria and show that under such criteria these methods have linear convergence. Strongly convex functions satisfy these criteria hence the results are valid for such functions. To the best of our knowledge, our result is the first convergence result for the adaptive restart scheme. We then introduce a novel restarting criteria which are highly tunable and also satisfies linear convergence.

Our second problem is on computation of the sparsest solution to an underdetermined system of linear equations. We introduce an extrapolation procedure which computes the sparsest solution from a penalized relaxation of the problem via Huber function. This extrapolation procedure uses a condition called sign constancy and we show that if one works with extreme points this can be removed. We present necessary and sufficient conditions for the recovery of the sparsest solution by penalized Huber loss function and ties among different solutions.

Our last problem of concern is on Network flows. In this work in progress, we investigate existence and computation of the equilibrium in trade networks with constraints. To the best of our knowledge, these networks are only investigated under simple capacity constraints on each link. Here we first start with a negative result where we give a counterexample where the link capacities live in a polymatroid yet there is no integer equilibrium point in the feasible region. We then move on to investigate the cases where the constraints are less restrictive.