Theory and methods for problems arising in robust stability, optimization and quantization
Michael L. Overton, C. Si̇nan Güntürk, Mert Gürbüzbalaban · 2012
This thesis is composed of three independent parts: Part I concerns spectral and pseudospectral robust stability measures for linear dynamical systems. Popular measures are the H ∞ norm, the distance to instability, numerical radius, spectral abscissa, pseudospectral abscissa and pseudospectral radius. Firstly, we develop and analyze the convergence of a new algorithm to approximate the H∞ norm of large sparse systems. Secondly, we tackle the static output feedback problem, a problem closely related to minimizing the abscissa (largest real part of the roots) over a family of monic polynomials. We show that when there is just one affine constraint on the coefficients of the monic polynomials, this problem is tractable, deriving an explicit formula for the optimizer when it exists and an approximate optimizer otherwise, and giving a method to compute it efficiently. Thirdly, we develop a new Newton-based algorithm for the calculation of the distance to discrete instability and prove that for generic matrices the algorithm is locally quadratically convergent. For the numerical radius, we give a proof of the fact that the Mengi-Overton algorithm is always quadratically convergent. Finally, we give some regularity results on pseudospectra, the pseudospectral abscissa and the pseudospectral radius. These results answer affirmatively a conjecture raised by Lewis & Pang in 2008. Part II concerns nonsmooth optimization. We study two interesting nonsmooth functions introduced by Nesterov. We characterize Clarke stationary and Mordukhovich stationary points of these functions. Nonsmooth optimization algorithms have an interesting behavior on the second function, converging very often to a nonminimizing Clarke stationary point that is not Mordukhovich stationary. Part III concerns the equivalence between one-bit sigma-delta quantization and a recent optimization-based halftoning method. Sigma-delta quantization is a popular quantization method for the analog to digital conversion of signals, whereas halftoning is a core process governing most digital printing and many display devices, by which continuous tone images are converted to bi-level images. Halftoning problem is recently formulated as a global optimization problem, we show that the same objective function is minimized in the one-bit sigma-delta quantization.