Disciplined Multi-Convex Programming

X. Shen, S. Diamond, M. Udell, Y. Gu, and S. Boyd

Working draft, September 2016. Shorter version appeared in Proceedings 29th Chinese Control and Decision Conference (CCDC), pages 895–900, May 2017.

A multi-convex optimization problem is one in which the variables can be partitioned into sets over which the problem is convex when the other variables are fixed. Multi-convex problems are generally solved approximately using variations on alternating or cyclic minimization. Multi-convex problems arise in many applications, such as nonnegative matrix factorization, generalized low rank models, and structured control synthesis, to name just a few. In most applications to date the multi-convexity is simple to verify by hand. In this paper we study the automatic detection and verification of multi-convexity using the ideas of disciplined convex programming. We describe an implementation of our proposed method that detects and verifies multi-convexity, and then invokes one of the general solution methods.