Theory and methods for problems arising in robust stability, optimization and quantization
Theory and methods for problems arising in robust stability, optimization and quantization
复制标题
鲁棒稳定性、优化和量化问题的理论与方法
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
M. Gürbüzbalaban
中科院分区：
文献类型：
--
作者：
M. Overton;C. Gunturk;M. Gürbüzbalaban
本论文由三个独立的部分组成：
第一部分涉及线性动力系统的谱和伪谱鲁棒稳定性测量。常用的度量有 H ∞ 范数、不稳定距离、数值半径、谱横坐标、伪谱横坐标和伪谱半径。首先，我们开发并分析了一种新算法的收敛性，以逼近大型稀疏系统的 H∞ 范数。其次，我们解决静态输出反馈问题，该问题与最小化一族多项式的横坐标（根的最大实部）密切相关。我们证明，当一元多项式的系数只有一个仿射约束时，这个问题是容易处理的，当优化器存在时，推导优化器的显式公式，否则推导近似优化器，并给出一种有效计算它的方法。第三，我们开发了一种新的基于牛顿的算法来计算离散不稳定性距离，并证明对于泛型矩阵，该算法是局部二次收敛的。对于数值半径，我们证明了Mengi-Overton算法总是二次收敛的。最后给出了伪谱、伪谱横坐标和伪谱半径的一些规律性结果。这些结果肯定地回答了 Lewis 和 Pang 在 2008 年提出的猜想。
第二部分涉及非光滑优化。我们研究了 Nesterov 引入的两个有趣的非光滑函数。我们描述了这些函数的 Clarke 平稳点和 Mordukhovich 平稳点。非平滑优化算法在第二个函数上有一个有趣的行为，经常收敛到非最小化 Clarke 驻点，该驻点不是 Mordukhovich 驻点。
第三部分涉及一位 sigma-delta 量化和最近基于优化的半色调方法之间的等效性。 Sigma-Delta 量化是一种流行的信号模数转换量化方法，而半色调是控制大多数数字印刷和许多显示设备的核心过程，通过该过程将连续色调图像转换为双层图像。半色调问题最近被表述为全局优化问题，我们表明相同的目标函数在一位 sigma-delta 量化中被最小化。
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.