1
$\begingroup$

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}$

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

The sum of a convex function and a strongly convex function is again strongly-convex. This is a direct application of the definition of strong-convexity.

On the other hand, it should be clear that $u \mapsto u^TP_iu$ is strongly convex if $P_i$ is positive definite.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Tony.Wu Jul 13 '16 at 5:00
  • $\begingroup$ 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 ? $\endgroup$ – dohmatob Jul 13 '16 at 7:53
  • $\begingroup$ I don't know that what is the difference between "penalty term" in equation(2.6) in web.stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf and "proximal term" in Algorithm 4 in ftp.math.ucla.edu/pub/camreport/cam13-64.pdf why the penalty term can be shown to be differentiable under rather mild conditions on the original problem and proximal term can make the subproblem strictly or strongly convex? $\endgroup$ – Tony.Wu Jul 13 '16 at 8:49
  • $\begingroup$ 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. $\endgroup$ – dohmatob Jul 13 '16 at 8:58
  • $\begingroup$ Sorry for another question, I don't clearly know the explanation of meaning in "penalty term" in equation(2.6) in web.stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf why this term can be shown to be differentiable under rather mild conditions on the original problem. $\endgroup$ – Tony.Wu Jul 13 '16 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.