# Iterative scheme for a nonlinear optimization problem

Let $\mathbb{PD}_3 \subset \mathbb{R}^{3 \times 3}$ be the set of the positive-definite $3 \times 3$ real matrices.

For given $v \in \mathbb{R}^{3 \times 1}$, consider the function $f_v: \mathbb{PD}_3 \times \mathbb{R}^{3} \rightarrow \mathbb{R}_{\geq 0}$ defined as

$$f_v(X,y) := y^\top X y + 2 y^\top X v + v^\top X v$$

We notice that $f_v$ is quadratic in $y$ (for fixed $X$) and linear in $X$ (for fixed $y$).

For given $F \in \mathbb{R}_{>0}$, consider the nonlinear optimization problem:

$$\min_{X,y} \ \left\| \left( \begin{array}{c} f_{v_1}(X,y)\\f_{v_2}(X,y) \\ \vdots\\ f_{v_N}(X,y) \end{array} \right) - \left( \begin{array}{c} F \\ F \\ \vdots \\ F \end{array} \right) \right\|.$$

To solve it, we have the following iterative scheme.

1. $X^{(1)} := I_3$ (identity matrix).

2. Fix $X \equiv X^{(1)}$ and compute $y^{(1)}$ as solution of the optimization problem (say in the only variable $y$).

3. Fix $y \equiv y^{(1)}$ and compute $X^{(2)}$ as solution of the optimization problem (say in the only variable $X$).

4. Iterate this ping-pong.

Q1. What can we claim about $X^{(\infty)}$ and $y^{(\infty)}$? Are we getting at least a local minimum?

Q2. Assume that the vectors $v_1,...,v:N$ are such that the optimal $X^*$ is "close" to be the identity, say $||X^∗ − I_3|| \leq \delta$ for some $\delta > 0$.

For what values of $\delta$ we can eventually get $(X^{(n)},y^{(n)}) \rightarrow (X^∗,y^∗)$?

-
I haven't analyzed this, but it is basically a coordinate descent method, so I would expect it to converge (albeit slowly), or at least that any accumulation point of the solutions satisfies a 1st order optimality condition. –  copper.hat Jul 31 '12 at 16:13
How can this be proved? –  Adam Jul 31 '12 at 16:28
$X^{(i)}$ might only positive semidefinite, rather than positive definite. –  Robert Israel Jul 31 '12 at 16:32
This question is also interesting. Assume that the vectors $v_1,...,v_N$ are such that the optimal $X^*$ is "close" to be the identity, say $||X^* - I_3|| \leq \delta$ for some $\delta>0$. For what values of $\delta$ we get that $(X^{(n)},y^{(n)}) \rightarrow (X^*,y^*)$? –  Adam Jul 31 '12 at 16:37
In the case of $P_1$, for any $F > 0$ and any positive definite $X$ the solutions of $f_v(X,y) = F$ form a nonempty ellipsoid, so the problem is trivial. –  Robert Israel Jul 31 '12 at 16:37
show 12 more comments