3

My objective function is quadratic in $\mathbf{a}$, which is vector version of matrix $\mathbf{A}$. But a rank-1 constrain i-e $\mathbf{A}=\mathbf{p}\mathbf{q}^{T}$ makes the problem nonconvex.

However if I fix $\mathbf{p}$, the remaining problem becomes an unconstrained minimization problem in $\mathbf{q}$. I solve for $\hat{\mathbf{q}}$, update $\mathbf{q}$, and then repeat to get $\hat{\mathbf{p}}$. This way I was able to split original problem into two unconstrained minimization problem wrt two vectors $\mathbf{p}$ and $\mathbf{q}$. I iterate till a stopping criterion is met.

Now I am looking into convergence issue of this approach.To be specific I want to be able to say that

  1. Regardless of how I initialize, my algorithm always returns $\hat{\mathbf{p}}$ and $\hat{\mathbf{q}}$.
  2. Let $\mathbf{p^*}$ and $\mathbf{q^*}$ denote the OPTIMAL solution. Under what conditions can we guarantee that $\hat{\mathbf{p}}=\mathbf{p^*}$ and $\hat{\mathbf{q}}=\mathbf{q^*}$.

Note that (1) holds true if (2) is true but (1) does not necessarily imply (2). Can someone please suggest some reference material or give some insight into how to approach such an analysis.

NAASI
  • 997
  • What do you mean "iterate till a stopping criterion is met" -- what do you do at each iterate? If one problem only uses $p$ and one only uses $q$, why do you need to iterate? – LarrySnyder610 Apr 30 '19 at 01:34
  • I fix $\mathbf{p}$ and minimize wrt to $\mathbf{q}$ to get $\hat{\mathbf{q}}$. Then update $\mathbf{q}=\hat{\mathbf{q}}$ and minimize wrt to $\mathbf{p}$ to get $\hat{\mathbf{p}}$. and so on – NAASI Apr 30 '19 at 01:42
  • In that case I think you are describing coordinate descent: https://en.wikipedia.org/wiki/Coordinate_descent – LarrySnyder610 Apr 30 '19 at 01:46
  • Thanks. Here https://www.cs.cmu.edu/~ggordon/10725-F12/slides/25-coord-desc.pdf, it says that one-by-one update is critical for success of coordinate descent. In my case I am doing all-at-once this i-e computing $\hat{\mathbf{p}}$ instead of $p_1,p_2\cdots,p_n$ separately. Does it mean that there is no guarantee for (2) to be true? – NAASI Apr 30 '19 at 02:21
  • That I don't know. You might try changing the title of the question to something like "Does coordinate descent converge to optimal solution if we don't optimize one-by-one?" (or something shorter :) ) -- that might catch the eye of some folks who are more expert than I in this topic. As a side note, there is an effort underway to launch a SE site for OR; you might consider committing to it here: https://area51.stackexchange.com/proposals/121892/operations-research?referrer=TsiyOTmVGMXPhrwHTdj1zw2 – LarrySnyder610 Apr 30 '19 at 13:26

0 Answers0