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

9733450 Vandenberge该项目致力于计算机辅助设计和电气工程优化领域的研究和教学。研究部分集中于非线性凸优化的最新内点方法，以及它们在超大规模集成电路和控制系统设计中的应用。这些新的优化方法推广了80年代发展起来并在实践中获得巨大成功的类似线性规划(LP)的内点方法。它们最近扩展到非线性凸优化，特别是半定规划(SDP)问题，在几个领域产生了直接的实际和理论影响，特别是控制理论和组合优化。在控制中，已经观察到各种分析和综合问题可以被描述为半定规划问题，因此数值求解效率很高。在确定可被视为SDP的控制问题方面进行了密集的研究，并在解决这些问题的内点方法领域取得了快速进展。作为这项活动的结果，已有几个软件实现可用，事实证明，这些软件对中小型问题很有用。这项研究旨在开发更强大的通用代码，利用控制中遇到的SDP中的问题结构，并能够解决大规模问题。这将大大扩展线性矩阵不等式技术在计算机辅助控制系统设计中的实际应用。这里的目标是开发、实现和测试一种新的电路大小调整方法，而基于Elmore延迟的传统延迟优化技术不适用于该方法。这包括具有非树形拓扑的电路，例如时钟分布网络，以及具有耦合电容的电路，例如由于互连线之间的耦合。通过非线性凸优化的布局，特别是定时驱动布局和与栅极大小相结合的布局。用于非线性凸优化的新方法使使用更复杂的代价函数和处理新类型的约束成为可能，其代价与现有技术相当。这里的目的是分析和测试半定规划在各种NP-Hard电路划分问题的谱划分方法中的使用。谱分割方法是启发式方法，它使用通过与电路相关联的拉普拉斯矩阵的特征值分解来求解的松弛。内点方法使得在一族矩阵上有效地优化这一特殊的界成为可能，从而获得更好的启发式。该项目的教育部分包括为工程专业学生开发一系列优化的研究生课程，包括线性规划和凸规划、大规模和组合优化、动态规划和图形优化。

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.***