12
$\begingroup$

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.

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

1 Answer 1

7
$\begingroup$

In general, nonlinear optimization algorithms implemented in finite precision floating point software don't converge exactly to an optimal solution exactly satisfying the optimality conditions. Therefore, practical criteria are developed and implemented whereby the algorithm is terminated and optimality declared when the optimality conditions (or convergence) are met to within some specified tolerance. How such a tolerance is implemented and the numerical value of tolerance is chosen are among the trickiest, and least documented, aspects of practical nonlinear optimization software.

Similarly, in this case, you will need to implement some practical criterion(a) involving a specified tolerance as to what constitutes "convergence" to an accumulation point. The practical criterion(a) will not be perfect, and can erroneously report convergence which has not really occurred, or not report convergence when it has essentially occurred. Exact convergence will not be achieved.

Unfortunately, there is no clean, simple, answer.

$\endgroup$
5
  • 1
    $\begingroup$ What would you recommend as the definition of convergence to an accumulation point? What bothers me with the statement in the paper is that, convergence of the entire sequence A (refer my post for defn) is not established. As a result, suppose something like taking the a_{MAX} as the approximation to the primal optimal solution, where MAX is the max number of iterations one performs, could be a wrong estimate altogether. $\endgroup$
    – batwing
    Commented Jul 22, 2019 at 17:28
  • 1
    $\begingroup$ Yes, it is tricky, and papers and books usually give short shrift to the subject. You will have to learn how to do it from the school of hard knocks. $\endgroup$ Commented Jul 22, 2019 at 17:40
  • $\begingroup$ @batwing I have been wondering about this exact question. Have you discovered anything you'd like to share? $\endgroup$
    – user56202
    Commented May 19, 2021 at 15:30
  • $\begingroup$ @user56202 - I haven't found any satisfactory answer to the question, better to use other dual methods such as ADMM if we are also interested in recovering the primal solution. $\endgroup$
    – batwing
    Commented May 19, 2021 at 16:22
  • $\begingroup$ @batwing Thanks for the update! $\endgroup$
    – user56202
    Commented May 19, 2021 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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