Difficulties with Finding a Proper Penalty Value for the Progressive Hedging Algorithm

Recently, I've been working on some two-stage stochastic programming problems. Due to the presence of integer second-stage variables in the model, I've preferred to use the Progressive Hedging Algorithm (PHA). I've implemented my algorithms in GAMS and run them successfully. However, a common issue between all problems was that occasionally PHA underestimated the optimal solution of the original problem (obtained via solving the deterministic equivalent problem).

I've found out that on some problems the method is highly sensitive to the penalty term, $$r$$, in the objective function depicted below (i.e., the one penalizing the distance between the current solution from the previous nonanticipative solution). Please note that $$\rho$$ and $$\hat{x}$$ are parameters determined iteratively within the PHA. Also, $$c^Tx_k$$ and $$q^T_ky_k$$ are the first-stage and second-stage costs, respectively.

\begin{align}\min\qquad&\sum_{k=1}^{K} p_{k}\left[c^Tx_k+q^T_ky_k+\rho^{v,T}_{k}(x_k-\hat{x}_k)+\dfrac{r}{2}\lVert x_k-\hat{x}_k\rVert^2\right]\\\text{s.t.}\qquad&Ax_k = b,\\\qquad&Wy_k=h_k-T_kx_x,\\\qquad&x_k \ge 0,\,\exists x_k\in \mathbb{Z}^+,\\\qquad&y_k \ge 0, \,\exists y_k\in \mathbb{Z}^+.\end{align}

Unfortunately, tuning $$r$$ could take considerable time and be a pain. I was wondering if there is any way to tune $$r$$ and find the optimal or near-optimal solutions with less hassle. I would really appreciate it if you could share your experience and tricks to overcome this difficulty.

Update #1: The problems under study are completely linear. In other words, they are two-stage stochastic mixed-integer programming (with integer first- and second-stage variables).

Update #2: As my first-stage variables are binary, I'm able to completely linearize the term $$\lVert x_k-\hat{x}_k\rVert^2$$. Therefore, the problem solved in each iteration of PHA is completely linear. In addition, it is separable under index $$k$$ for different scenarios.

Update #3: The progressive hedging algorithm was implemented as discussed here on page 257.

Step 0. Suppose some nonanticipative $$x_0$$, some initial multiplier $$\rho_0$$, and $$r > 0$$ . Let $$ν = 0$$. Go to Step 1.

Step 1. Let $$(x_k^{v+1},y_k^{v+1}) \; \forall k = 1,...,K$$ solve the problem above. Let $$\hat{x}^{v+1} = (\hat{x}^{v+1,1},...,\hat{x}^{v+1,K})^T$$ where $$\hat{x}^{v+1,k} = \sum_{l=1}^{K} p_lx^{v+1,l} \; \forall k = 1,...,K$$.

Step 2. Let $$\rho^{v+1}=\rho^{v} + r(x^{v+1,k}-\hat{x}^{v+1})$$. If $$\hat{x}^{v+1}=\hat{x}^{v}$$ and $$\rho^{v+1}=\rho^{v}$$, then, stop; $$\hat{x}^{v}$$ and $$\rho^{v}$$ are optimal. Otherwise, let $$v = v+1$$ and go to Step 1.

• I had the same issue when setting the penalty value for ADMM. I dont think I gave it much thought back then, but I think it will help to look at the convergence results for the convex minimization problem i.e. look at how the convergence results depend on Q (condition number of Q), r. If there is some relationship there, then you may want to set r based on Q. Aug 27, 2019 at 15:39
• Thanks, @batwing. In my case, $Q$ is a linear function in terms of $x_k$ and $y_k$. I'm not sure but I think that should not cause such problems. Aug 27, 2019 at 16:13
• Are pages 407+408 applicable?, calculate quadratic $r$ for each.
– Rob
Aug 27, 2019 at 18:35
• @Rob: Thanks, this seems promising. I'll try it and report back. Aug 27, 2019 at 19:21
• Ehsan, I do not have that book. The penalty only converges when a small number of nonanticipativity constraints (NACs) are to be satisfied. Finding a nonanticipative solution becomes particularly difficult when the input scenarios differ drastically.
– Rob
Aug 28, 2019 at 14:25

1 Answer

This problem is addressed in some detail in Section 2.1 of the paper Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems by Watson and Woodruff (a non-paywall version is given here). In general, proper selection can be quite tricky and is highly problem-specific. I recommend trying some of the tricks in the linked paper.

• Thanks for the reference. I'll try implementing the idea discussed in the paper and report back. Although, an interesting observation is that in the literature, usually the issue of convergence is discussed and not underestimation. Aug 30, 2019 at 18:29
• Thanks again for the reference. Implementing some of its ideas helped with finding an error in my codes that caused the underestimation problem. Also, the ideas helped with speeding up the convergence. Sep 19, 2019 at 19:12