Our concern is with optimal design of photonic crystals with large band-gaps, thereby enabling a wide variety of prescribed interaction with and control of mechanical and electromagnetic waves. We present and use an algorithm based on convex conic optimization to design two-dimensional photonic crystals with large absolute band gaps. Our modeling methodology yields a series of finite-dimensional eigenvalue optimization problems that are large-scale and non-convex, with low regularity and non-differentiable objective. By restricting to appropriate eigen-subspaces, we reduce the problem to a sequence of small-scale convex semidefinite programs (SDPs) for which modern SDP solvers can be efficiently applied. Among several illustrations we show that it is possible to design photonic crystals which exhibit multiple absolute band gaps for the combined transverse electric and magnetic modes. The optimized crystals show complicated patterns which are far different from existing photonic crystal designs. We employ subspace approximation and mesh adaptivity to enhance computational efficiency. The resulting optimized structures are not necessarily fabricable, due to lack of connectedness of the materials and/or complicated boundary structure. We introduce new modeling methods to address the issue of optimizing designs that yield tractable models and yet are robust in the context of fabricability.