In this article, we propose a new performance bound analysis of analog circuits considering process variations. We model the variations of component values as intervals measured from tested chips and manufacture processes. The new method first applies a graph-based analysis approach to generate the symbolic transfer function of a linear(ized) analog circuit. Then the frequency response bounds (maximum and minimum) are obtained by performing nonlinear constrained optimization in which magnitude or phase of the transfer function is the objective function to be optimized subject to the ranges of process variational parameters. The response bounds given by the optimization-based method are very accurate and do not have the overconservativeness issues of existing methods. Based on the frequency-domain bounds, we further develop a method to calculate the time-domain response bounds for any arbitrary input stimulus. Experimental results from several analog benchmark circuits show that the proposed method gives the correct bounds verified by Monte Carlo analysis while it delivers one order of magnitude speedup over Monte Carlo for both frequency-domain and time-domain bound analyses. We also show analog circuit yield analysis as an application of the frequency-domain variational bound analysis.