Mert Gurbuzbalaban
Theory and methods for problems arising in robust stability, optimization and quantization M Gurbuzbalaban - PhD Thesis, New York University 2012.
Publication year: 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 and radius, pseudospectral abscissa and 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
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. The halftoning problem
was recently formulated as a global optimization problem. We prove that the same
objective function is minimized in one-bit sigma-delta quantization