We augment existing generator-side primary frequency control with load-side control that are local, ubiquitous, and continuous. The mechanisms on both the generator and the load sides are decentralized in that their control decisions are functions of locally measurable frequency deviations. These local algorithms interact over the network through nonlinear power flows. We design the local frequency feedback control so that any equilibrium point of the closed-loop system is the solution to an optimization problem that minimizes the total generation cost and user disutility subject to power balance across entire network. With Lyapunov method we derive a sufficient condition for any equilibrium point of the closed-loop system to be asymptotically stable. A simulation demonstrates improvement in both the transient and steady-state performance over the traditional control only on generators, even when the total control capacity remains the same.