Fixed point iteration on symmetric biconvex function

Question

Suppose $X\subseteq\mathbb{R}^n$ is a convex set and that a function $g(x,y):X\times X\rightarrow\mathbb{R}_+$ is smooth, "strictly biconvex" (strictly convex in $x$ and $y$ independently but not jointly), and satisfies $g(x,y)=g(y,x)$.

Alternating optimization on $g$ in this case takes a nice form: $x_{i+1}\gets \arg\min_x g(x,x_i).$

I know alternating optimization doesn't have to converge in general. But, is there any chance to prove that $x_i\rightarrow x^\ast$ that under the symmetry and biconvexity assumptions?

Answer 1

The paper cited in my answer here provides a detailed proof of the two-block case of alternating minimization (block coordinate descent). In particular, as mentioned in my comment, the convergence follows thanks ultimately to having unique subproblem solutions.

Answer 2

This problem, in its general form (without requiring any convex properties), is very popular since 1950s. Look around the technique "Block Coordinate Descent" method to take a generic idea.

Your problem, that has these "partial"-convex properties is also popular. You can find a very good tutorial in [1] about such problems. In this tutorial, it is analytically explained that in principle it is difficult to optimally minimize such a problem. A very nice technique that guarantees the global optima is suggested in [2].

[1] Jochen Gorski , Frank Pfeuffer, Kathrin Klamroth, Biconvex sets and optimization with biconvex functions: a survey and extensions, 2007.

[2] C.A. Floudas, and V. Visweswaran, A Global Optimization Algorithm (GOP) For Certain Classes of Nonconvex NLPs : I. Theory, 1990.