ConvexFit: an optimal minimum-error convex fitting and smoothing algorithm with application to gate-sizing

Convex optimization has gained popularity due to its capability to reach global optimum in a reasonable amount of time. Convexity is often ensured by fitting the table data into analytically convex forms such as posynomials. However, fitting the look-up tables into the posynomial forms with minimum error itself may not be a convex optimization problem and hence excessive fitting errors may be introduced. In this paper, we propose to directly adjust the look-up table values into a numerically convex look-up table without explicit analytical form. We show that numerically "convexifying" the table data with minimum perturbation can be formulated as a convex semidefinite optimization problem and hence optimality can be reached in polynomial time. Without an explicit form limitation, we find that the fitting error is significantly reduced while the convexity is still ensured. As a result, convex optimization algorithms can still be applied. Furthermore, we also develop a "smoothing" algorithm to make the table data smooth and convex to facilitate the optimization process. Results from extensive experiments on industrial cell libraries demonstrate that our method reduces 30× fitting error over a well-developed posynomial fitting algorithm. Its application to circuit tuning is also presented.