Topics in global optimization: Ellipsoidal bisection, graph partitioning and sparse reconstruction.

摘要

In this dissertation, we develop theories and practical algorithms for optimization problems which arise from science, economics and engineering.;First, an ellipsoidal branch and bound algorithm is developed for global optimization. The algorithm starts with a known ellipsoid containing the feasible set. Branching in the algorithm is accomplished by subdividing the feasible set using ellipses. Lower bounds are obtained by replacing the concave part of the objective function by an affine underestimate. A ball approximation algorithm, obtained by generalizing of a scheme of Lin and Han, is used to solve the convex relaxation of the original problem. Numerical experiments are given for a randomly generated quadratic objective function and randomly generated convex, quadratic constraints.;Second, we propose an exact algorithm for solving the graph partitioning problem with upper and lower bounds on the size of each set in the partition. The algorithm is based on a branch and bound method applied to a continuous quadratic programming formulation of the problem. Lower bounds are achieved by decomposing the objective function into convex and concave parts and replacing the concave part by the best affine underestimate. It is shown that the best affine underestimate can be expressed in terms of the center and the radius of the smallest sphere containing the feasible set. The concave term is obtained either by a constant diagonal shift associated with the smallest eigenvalue of the objective function Hessian, or by a diagonal shift obtained by solving a semidefinite programming problem. Numerical results show that the proposed algorithm is competitive with state-of-the-art graph partitioning codes.;Finally, the convergence rate is analyzed for the SpaSRA algorithm (Sparse Reconstruction by Separable Approximation) of Wright, Nowak and Figueiredo for minimizing a sum f(x)+psi( x) where f is smooth and psi is convex, but possibly nonsmooth. We prove that if f is convex, then the error in the objective function at iteration k, for k sufficiently large, is bounded by a/(b + k) for suitable choices of a and b. Moreover, if the objective function is strongly convex, then the convergence is R-linear. An improved version of the algorithm based on a cycle version of the Barzilai-Borwein iteration and an adaptive line search is given. The performance of the algorithm is investigated using applications in the areas of signal processing and image reconstruction.