3
$\begingroup$

Consider the optimisation problem $$\begin{array}{cl} \displaystyle \underset{\mathbf{x}_{1}, \ldots, \mathbf{x}_{N}}{\mathrm{minimize}} & f(\mathbf{x}_{1}, \ldots, \mathbf{x}_{N}) \\ \mathrm{subject~to} & \mathbf{x}_{1} \in \mathcal{X}_{n}, \quad \forall n \end{array}$$ where $f$ is not convex (nor pseudo-convex or quasi-convex) in any of the variables $\mathbf{x}_{n}$. Suppose that the minimum over each variable $\mathbf{x}_{n}$ given the other variables $\{ \mathbf{x}_{i} \}_{i \neq n}$, i.e., $$\underset{\mathbf{y} \in \mathcal{X}_{n}}{\min} \ f(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}, \mathbf{y}, \mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N})$$ is uniquely attained in closed form, i.e., without the need of a search algorithm.

A well-known convergence result [Bertsekas, Nonlinear Programming - Prop. 2.7.1]. Assume that:

  1. The set $\mathcal{X} = \prod_{n} \mathcal{X}_{n}$ is closed and convex;

  2. $f$ is continuously differentiable over $\mathcal{X}$;

  3. The minimum over each variable $\mathbf{x}_{n}$ given the other variables $\{ \mathbf{x}_{i} \}_{i \neq n}$ is uniquely attained.

Then, every limit point of the sequence generated by the block coordinate descent (BCD) method is a stationary point of the original problem.

Question. What can we say about the convergence of the block coordinate descent algorithm if either the first or the second conditions above are not satisfied? That is, does BCD still converge if $f$ is continuously differentiable over a nonconvex set $\mathcal{X}$ or if $f$ is not continuously differentiable over a convex set $\mathcal{X}$? My intuition is that, since the solution of each subproblem is uniquely attained in closed form (without the need of a search algorithm), BCD should still converge. I also found some [lecture slides][1] (see slide 10) that do not assume any convexity of the set $\mathcal{X}$, but no reference is included.

Some specific details of my problem. Suppose that each subproblem can be written as $$\underset{\mathbf{x}_{n} \, : \, \| \mathbf{x}_{n} \| = 1}{\mathrm{minimize}} \ \frac{\mathbf{x}_{n}^{\mathrm{T}} \mathbf{A} (\{\mathbf{x}_{i}\}_{i \neq n}) \mathbf{x}_{n}}{\mathbf{x}_{n}^{\mathrm{T}} \mathbf{B} (\{\mathbf{x}_{i}\}_{i \neq n}) \mathbf{x}_{n}}.$$ Here, the objective (in the form of generalised Rayeigh quotient) is continuously differentiable over the nonconvex set $\mathcal{X}_{n} = \{ \mathbf{x}_{n} : \| \mathbf{x}_{n} \| = 1 \}$ and the closed-form solution is given by the minimum eigenvector of $\big( \mathbf{B} (\{\mathbf{x}_{i}\}_{i \neq n}) \big)^{-1} \mathbf{A} (\{\mathbf{x}_{i}\}_{i \neq n})$. Now, I would obtain the same solution by relaxing the nonconvex set above as $\mathcal{X}_{n} = \{ \mathbf{x}_{n} : \| \mathbf{x}_{n} \| \leq 1 \}$: however, in this case, the objective would not be differentiable in $\mathbf{x}_{n} = \mathbf{0}$ (although this point is not attained by the solution).

$\endgroup$

2 Answers 2

1
$\begingroup$

For a non-convex feasible region, there's no guarantee of convergence. Consider a function $f$ on the discrete feasible set

$X=\left\{ (1,1), (1,-1), (-1,1), (-1,-1) \right\}$

With

$f((1,1))=15$

$f(-1,1)=12$

$f(-1,-1)=13$

$f(1,-1)=10$

Clearly, the minimum is at $(1,-1)$. Furthermore, from any one of the four points and in either of the two coordinates $x_{1}$, or $x_{2}$, there is a unique component wise minimum. However, if we start at $(1,1)$, then in the first iteration we move to $(-1,1)$, and then stay there forever.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. I understand that convergence to the global minimum, i.e., $(1,-1)$, cannot be guaranteed. What I need is convergence to a stationary point of the original problem: in your example, $(-1,1)$ is a (kind of) local minimum. What can we say in the general case? $\endgroup$
    – TheDon
    Commented Jun 1, 2021 at 5:12
0
$\begingroup$

As an example of a non-differentiable function over a convex set, consider $f(x,y)=x+y+2|x-y|$ on $x,y\in [0,1]$. The function satisfies 1 and 3 and it's even convex but $\arg\min_x x + y_0 + 2|x-y_0|$ is $y_0$, then $\arg\min_y y_0 + y + 2|y_0-y|$ is again $y_0$ and the algorithm gets stuck at $(y_0,y_0)$ rather than converging to $(0,0)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .