Cortical circuits have separate excitatory and inhibitory (E-I) populations, operate in the balanced regime, and are able to store and retrieve memories that consist of graded patterns of activity. Previous theoretical studies have fallen short of explaining all these characteristics in a single unified model. Some models only allowed symmetric weight matrices precluding an E-I architecture. Others exploited the saturating part of nonlinear single neuron transfer functions, leading to effectively binary memories and no balance. Yet others remained in the convex, non-saturated regime but stabilized low firing rates via a single inhibitory feedback loop, irrespective of the memory being recalled — but this inhibition could only be calibrated for a single stereotypical level of excitation, thus implying effectively binary memories again. Here we propose a novel framework in which we enforce a balanced regime and the stability of graded attractors by directly optimizing the connectivity of the network under physiological constraints. We formalized memory storage as implying two conditions: that the memorized patterns be fixed points of the dynamics, and that the dynamics be stable around those fixed points. The first objective is easily approached as it maps to a simple form of linear regression, despite the network being nonlinear, where the regressing coefficients are the elements of the synaptic weight matrix and the dependent variable is the required attractor. However, the second objective is a paradigmatic challenge in robust control studying the stabilization of systems with potentially strong positive feedback loops. Thus, we used a recently developed relaxation of the spectral abscissa which provides a smoothly differentiable measure of the stability of an attractor to perturbations. This allowed us to construct functioning E-I circuits that encode graded memories in the balanced regime. This provides the first step towards understanding the basic organizing principles of cortical memories.