# Properties on proximal term

If the equation $x_i$-subproblem showed below is not strictly convex

$\arg \min_{x_i}=f_i(x_i)+\frac{\rho}{2}\|A_ix_i+\sum_{j\neq i}A_jx_j^k-c-\frac{\lambda^k}{\rho}\|_2^2$

Why adding the proximal term $\frac{1}{2}\|x_i-x_i^k\|^2_{P_i}$ showed below can make the subproblem strictly or strongly convex?

$arg \min_{x_i} f_i(x_i)+\frac{\rho}{2}\|A_ix_i+\sum_{j\neq i}A_jx_j^k-c-\frac{\lambda^k}{\rho}\|_2^2+\frac{1}{2}\|x_i-x_i^k\|^2_{P_i}$

• Possible typo in your formula. Did you mean $x_i - x_j$ ? – dohmatob Jul 12 '16 at 14:40
• sorry for wrong typing, make corrections $\frac{1}{2}\|x_i-x_i^k\|^2_{P_i}$ – Tony.Wu Jul 13 '16 at 5:06

On the other hand, it should be clear that $u \mapsto u^TP_iu$ is strongly convex if $P_i$ is positive definite.
• but the term $\frac{\rho}{2}\|A_ix_i+\sum_{j\neq i}A_jx_j^k-c-\frac{\lambda^k}{\rho}\|_2^2$ is strongly convex, why add another strongly convex term $\frac{1}{2}\|x_i-x_i^k\|^2_{P_i}$ in this updating formulation? – Tony.Wu Jul 13 '16 at 5:00
• That term is strongly-convex iff $A_i^TA_i$ is positive definite (i.e iff $A_i$ has full rank). Is this the case ? If so, then add it as a hypothesis in you question. Please take some time to write down your problem / question as neatly and completely as you can. Or maybe you could provide a link to the paper you're trying to understand ? – dohmatob Jul 13 '16 at 7:53
• OK, it appears the authors use language which is not very rigorous. They say in the introduction that the $A_i$ have full column-rank. Thus by virtue of my comments above, the $x_i$ sub-problem is already strongly convex. However, $A_i^TA_i$ may be very ill-conditioned (i.e the smallest eigenvalue of $A_i^TA_i$ though strictly positive, may be terribly smaller than the largest). A judicious choice for the $P_i$'s may then repair this ill-conditioning. – dohmatob Jul 13 '16 at 8:58