# How to divide the original optimization problem into several suproblems?

$$\begin{array}{ll} \text{minimize} & \| \mathbf{X} - \mathbf{A} \|_F^2\\ \text{subject to} & {\mathbf{X}}\mathbb{1} = \mathbb{1}, \quad \mathbf{X} \geq 0\\ & \mathbf{X} = \mathbf{X}^T, \quad Tr(\mathbf{X}) = k \end{array}$$

in which $\mathbf{X},\mathbf{M}$ is the matrix. $\mathbb{1}$ is the vector consist all ones. $Tr()$ is the matrix trace.

I saw the paper (their Eq.(19)): http://www.kdd.org/kdd2016/papers/files/rfp1162-wangA.pdf

They solve above problem in two subproblems

$$\begin{array}{ll} \text{minimize} & \| \mathbf{X} - \mathbf{A} \|_F^2\\ \text{subject to} & {\mathbf{X}}\mathbb{1} = \mathbb{1}, \quad \mathbf{X} \geq 0 \end{array}$$ and

$$\begin{array}{ll} \text{minimize} & \| \mathbf{X} - \mathbf{A} \|_F^2\\ \text{subject to} & \mathbf{X} = \mathbf{X}^T, \quad Tr(\mathbf{X}) = k \end{array}$$

My concerns are belows

(1) Why it is correct ? What is the logical behind this decompose the original optimization into two subproblems?

(2) Finally, How to get the final solution $X$ from those two subproblems?

It is explained on p. 4 of the paper linked in the question. The strategy is to iteratively solve the 2 subproblems, which are each easier to solve than the original problem. When the subproblems have converged to a value of $X$, that is the solution (i.e., $X$ wouldn't further change by more than a small convergence tolerance if further iterations were taken).

Our strategy is to solve two subproblems, Problem (20) and Problem (21) alternately, and let their solutions project mutually. In each iteration, we solve Problem (20) first and let its solution M 1 to be the T matrix in Problem (21), afterwards we solve Problem (21) and let its solution M 2 play the role of matrix T in Problem (20). We solve these two problems alternately and iteratively until M converges.

According to Von Neumann’s successive projection lemma [16], this mutual projection strategy we use will converge to the cross of two subspaces formed by Problems (20) and (21). The lemma theoretically ensures that the solution of the alternate projection strategy ultimately converges onto the global optimal solution of Problem (19)

• I don't quite understand: "we solve Problem (20) first and let its solution M 1 to be the T matrix in Problem (21), afterwards we solve Problem (21) and let its solution M 2 play the role of matrix T in Problem (20)." why the solution of M become matrix T for subproblems each other? some other reference about this? – jason Jun 7 '18 at 22:03
• I know of no other reference for this. The proof of convergence is provided in the paper. – Mark L. Stone Jun 7 '18 at 22:14
• Is it possible directly optimizing the original problem instead of splitting into two sub problems? – jason Jun 7 '18 at 22:31
• I check their proofs. Appendix A is to get the solution of M, which is clear. But I am confuse of Appendix B. what is the goal of $M=T_+$? From their idea: $T = M$ should be the case. Appendix mainly focus on finding the solutions. The convergence is not provided for this problem. They talk about the convergence of the whole Augmented Lagrange Multiplier (ALM) algorithm – jason Jun 7 '18 at 22:38
• Go back to problems 16 and 17. Then you will see that T in 19 is not a constant (input data), but is tied to the L, and ultimately the M. So really T is a function of M (that is kind of hidden in 20 and 21). That's why the alternating iterative process was introduced. But you could go back to 16 or 17 and solve by some general method .. The point of this algorithm is that it is specialized for this problem, and the authors show it converges to the global optimum. Presumably, it's a fast method for solving this problem. – Mark L. Stone Jun 7 '18 at 22:56

Maybe I will give an explanation from a different viewpoint. A projection of $a$ onto the set $S$ is the closest point'' to $a$, that is, it is the solution of $$\min_{x} \|x - a\| \text{ subject to } x \in S$$

Now, suppose you have two sets $S_1$ and $S_2$ for which you have good projection algorithms. A well-known method for projecting onto $S = S_1 \cap S_2$ is alternatively projecting onto $S_1$ and then $S_2$ (and then $S_1$ and so on...), until convergence. That is, we generate the sequence $$X_{k+1} = P_{S_2}(P_{S_1}(X_k))$$ It is well known (Newmann's alternating projection Lemma) that if both sets are convex, the algorithm converges to the projection onto $S$.

Your given problem is indeed a projection of $A$ onto the set defined by the constraints. The authors claim that they have an efficient algorithm for projecting onto the set $S_1$ defined by the first two constraints, and onto the set $S_2$ defined by the second two constraints. What they suggest is simply using the alternating projection method. Nothing more, nothing less.

• Cool, How this process works? for example, you can get the solution $X_1$ from the first subproblem under set $S_1$. How to use this solution $X_1$ from the first to solve the second subproblem over set $S_2$? In the paper, they say just relpace $A = X_1$ to solve the second subporblem. Did I missing something. – jason Jun 8 '18 at 16:54
• It seems that those two subproblem can be solved independently, Let say $X_1$ from first subpproblem, $X_2$ from the second subproblem. How to project them each other by Newmann's alternating projection? I know little about this algorithm. – jason Jun 8 '18 at 16:56