Optimality and convergence of Alternating Minimization approaches

Question

I have an optimization problem in four variable and fortunately, the problem is convex in each variable while keeping others fixed. I want to use alternating minimization (AM) based algorithm to find the optimal solution.

My optimization problem is given below, $$ \min_{U,V,P,Q} \; \|X-UV\|_{F}^2 + \|K-PQ\|_{F}^2 + \|Y-UQ\|_{F}^2 + \|U\|_{F}^2 + \|V\|_{F}^2 + \|Q\|_{F}^2 $$ and the variables are $U, V, P $ and $Q$, and the norm used in Frobenius norm. There is an additional constraints that $U$ and $Q$ are non-negative. My question is, what are the optimality guarantee and convergence result for AM algorithms when there are more than two variables ?. Anyone can point me to some literature discussing such ?

Answer 1

One specific result that might be relevant is Proposition 2.3.1 (page 151) in D. Bertsekas, Nonlinear Programming, 3rd ed. 2016.

The result is that if there is a unique solution to each of the coordinatewise minimization problems, then any limit point of the sequence of solutions is a stationary point (which could be a minimum or a saddle point.)

If the level sets of $f$ are bounded (and hence compact), you can be assured that there will be at least one limit point- otherwise your sequence of solutions might just drift off to infinity.

Answer 2

There are many works on this topic. For example look at this paper and its references: https://arxiv.org/pdf/1511.02746.pdf