Tight estimation of the Lipschitz constant for deep neural networks (DNNs) is\nuseful in many applications ranging from robustness certification of\nclassifiers to stability analysis of closed-loop systems with reinforcement\nlearning controllers. Existing methods in the literature for estimating the\nLipschitz constant suffer from either lack of accuracy or poor scalability. In\nthis paper, we present a convex optimization framework to compute guaranteed\nupper bounds on the Lipschitz constant of DNNs both accurately and efficiently.\nOur main idea is to interpret activation functions as gradients of convex\npotential functions. Hence, they satisfy certain properties that can be\ndescribed by quadratic constraints. This particular description allows us to\npose the Lipschitz constant estimation problem as a semidefinite program (SDP).\nThe resulting SDP can be adapted to increase either the estimation accuracy (by\ncapturing the interaction between activation functions of different layers) or\nscalability (by decomposition and parallel implementation). We illustrate the\nutility of our approach with a variety of experiments on randomly generated\nnetworks and on classifiers trained on the MNIST and Iris datasets. In\nparticular, we experimentally demonstrate that our Lipschitz bounds are the\nmost accurate compared to those in the literature. We also study the impact of\nadversarial training methods on the Lipschitz bounds of the resulting\nclassifiers and show that our bounds can be used to efficiently provide\nrobustness guarantees.\n