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