An Improved Self-Adaptive Inertial Projection and Contraction Algorithm for Mixed-Cell-Height Circuit Legalization

In advanced technology nodes, mixed-cell-height circuit designs have become increasingly prevalent, posing significant challenges for legalization. We first formulate the legalization as a class of variational inequality (VI) problems defined over convex sets and then employ an existing self-adaptive inertial projection and contraction algorithm (SIPCA) to solve it. Building upon this framework, we further propose an improved self-adaptive inertial projection and contraction algorithm (SIPCAIP) by incorporating the subgradient extragradient technique to enhance convergence efficiency and numerical stability. The proposed method preserves the advantages of projection and contraction schemes for handling VIs with nonsymmetric positive semidefinite system matrices while demonstrating faster convergence and improved robustness compared with the baseline SIPCA. Moreover, a rigorous convergence analysis is established to provide theoretical guarantees for the effectiveness of the proposed method. Numerical experiments demonstrate that the proposed method effectively addresses the mixed-cell-height legalization problem and provides a rigorous and extensible framework for solving related quadratic optimization problems.