# Recovering primal optimal solutions from dual sub gradient ascent using ergodic primal sequences

My question concerns recovering a primal optimal solution while performing dual sub gradient ascent. Denoting by $$y_i$$ the dual multiplier in the $$i^{\text{th}}$$ iteration, let $$\begin{equation} x_i = \underset{x \in X}{\operatorname{arg\,min}} \,L(x, y_i) \end{equation}$$ where $$L(x, y_i) = f(x) + y_i^T g(x)$$ is the Lagrangian, where $$f, g$$ are convex functions and $$X$$ is a convex set. The following papers:

1. Two “well-known” properties of sub-gradient optimization, Kurt M. Anstreicher, Laurence A. Wolsey (https://link.springer.com/article/10.1007/s10107-007-0148-y)
2. Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs, Sherali and Choi (https://www.sciencedirect.com/science/article/pii/0167637796000193)

propose to recover the primal optimal solution by constructing an auxiliary sequence $$A = \left( a_i \right)$$, where $$a_i$$ is a convex combination of points in the set $$\lbrace{x_k \rbrace}_{k=1}^{i}$$. These papers prove that any accumulation point of the sequence $$A$$ converges to the optimal primal solution of the problem $$\begin{equation} \underset{\substack{ x \in X,\\ g(x) \leq 0}}{\min} f(x) \end{equation}$$ My question, how does one compute such an accumulation point in practice (code) given that often we only perform a finite number of dual sub gradient iterations?

The construction scheme for primal optimal solution has been applied to practical problems in many papers, but none of them provide any detail as to how they compute such an accumulation point.

• Perhaps you can provide complete references, and links if available, to the relevant papers. Jul 22, 2019 at 16:32