In this paper, the problem of finding optimal success probabilities of static linear optics quantum gates is linked to the theory of convex optimization. It is shown that by exploiting this link, upper bounds for the success probability of networks realizing single-mode gates can be derived, which hold in generality for linear optical networks followed by postselection, i.e., for networks of arbitrary size, any number of auxiliary modes, and arbitrary photon numbers. As a corollary, the previously formulated conjecture is proven that the optimal success probability of a postselected non-linear sign shift gate without feed-forward is 1/4, a gate playing the central role in the scheme of Knill-Laflamme-Milburn for quantum computation with linear optics. The concept of Lagrange duality is shown to be applicable to provide rigorous proofs for such bounds for elementary gates without feed-forward, although the original problem is a difficult non-convex problem in infinitely many objective variables. Similar applications of this method in finding optimal linear optical schemes are outlined.