CAREER: Large-scale convex optimization with applications to VLSI and control systems design

9733450 Vandenberghe该项目致力于计算机辅助设计和电气工程优化领域的研究和教学。 研究部分集中在最近的非线性凸优化的邻域点方法，以及它们在超大规模集成电路和控制系统设计中的应用。 这些新的优化方法推广了类似的边界点法线性规划（LP），在八十年代开发的，并已在实践中取得了巨大的成功。 它们最近扩展到非线性凸优化，特别是半定规划（SDP）问题，在控制理论和组合优化等领域产生了直接的实际和理论影响。在控制中，人们已经观察到各种分析和综合问题都可以用半定规划问题表示，因此可以高效地数值求解。 已经有了深入的研究，以确定控制问题，可以铸造为SDP，以及在该地区的快速进展，在解决这些问题的邻域点的方法。 由于这项活动，已经有几个软件实现，这已被证明是有用的小型和中型的问题。 拟议的研究旨在开发更强大的通用代码，利用在控制中遇到的SDP的问题结构，并能够解决大规模的问题。 这将极大地扩展线性矩阵不等式技术在计算机辅助控制系统设计中的实际应用。 这里的目标是开发，实施和测试一种新的方法，用于调整电路的传统的延迟优化技术，这是基于埃尔默延迟，不适用。 这包括具有非树形拓扑的电路，例如，时钟分配网和具有耦合电容器的电路，例如，通过非线性凸优化来优化布局，特别是时序驱动布局和结合栅极尺寸的布局。 非线性凸优化的新方法使得使用更复杂的成本函数和处理新类型的约束成为可能，其成本与现有技术相当。 在这里，我们的目标是分析和测试使用半定规划的频谱划分方法的各种NP难电路划分问题。 频谱划分方法是使用松弛的算法，该松弛通过与电路相关联的拉普拉斯矩阵的特征值分解来求解。 内点法可以有效地优化矩阵族上的这个特殊界，从而获得更好的启发式。该项目的教育部分包括为工程专业学生开发一系列优化研究生课程，涵盖线性和凸规划、大规模和组合优化、动态规划和图优化。

9733450VandenbergheThe project is devoted to research and teaching in the area of optimization applied to computer-aided design and electrical engineering. The research component focuses on recent interior-point methods for nonlinear convex optimization, and their application to VLSI and control systems design. These new optimization methods generalize similar interior-point methods for linear programming (LP) that were developed in the eighties and that have been used with great success in practice. Their recent extension to nonlinear convex optimization, and to the semidefinite programming (SDP) problem in particular, has had immediate practical and theoretical impact in several fields, notably control theory and combinatorial optimization.In control, it has been observed that various analysis and synthesis problems can be formulated as semidefinite programming problems, and hence numerically solved with great efficiency. There has been intensive research on identifying control problems that can be cast as SDPs, as well as rapid progress in the area of interior-point methods for solving those problems. As a result of this activity, several software implementations have become available, which have proven useful for small and medium-sized problems. The proposed research aims at developing more powerful general-purpose codes that exploit the problems structure in the SDPs encountered in control, and are capable of solving large-sclale problems. This would significantly extend the practical use of linear matrix inequality techniques in computer-aided control system design.À Wire and gate sizing via semidefinite programming. The objective here is to develop, implement, and test a new method for sizing circuits to which the conventional delay optimization techniques, which are based on the Elmore delay, do not apply. This includes circuits with a non-tree topology, e.g., clock distribution meshes, and circuits with coupling capacitors, e.g., due to coupling between interconnect wires.À Placement via nonlinear convex optimization, in particular timing-driven placement and placement combined with gate sizing. New methods for nonlinear convex optimization make it possible to use more complex cost functions and to handle new types of constraints, at a cost comparable to existing techniques.À Circuit partitioning via semidefinite programming. Here the objective is to analyze and test the use of semidefinite programming in spectral partitioning methods for various NP-hard circuit partitioning problems. Spectral partitioning methods are heuristics that use a relaxation solved via the eigenvalue decomposition of the Laplacian matrix associated with the circuit. Interior-point methods make it possible to efficiently optimize this special bound over a family of matrices, and hence to obtain a better heuristic.The education component of the project involves the development of a sequence of graduate courses in optimization for engineering students, covering linear and convex programming, large-scale and combinatorial optimization, dynamic programming, and graph optimization.***