11
$\begingroup$

I'm reading Boyd's notes on forming the dual problem in order to decompose the primal problem. On page 4, right before the start of the next section, he talks about how given the optimal dual solution, finding the optimal primal solution is non-trivial. At the end, he says "There are also some standard tricks for regularizing the subproblems that work very well in practice."

Does anyone know what he means and how to go about regularizing the subproblems?

$\endgroup$
2
  • $\begingroup$ Any progress on this? I have been looking for my copy of Convex Optimization (to read the reference made in the notes). What are you looking for to clarify what Boyd means? $\endgroup$
    – Wesley Dyk
    Commented Aug 6, 2020 at 17:17
  • $\begingroup$ Perhaps he is referring to the method of multipliers or ADMM (which both by the way are dual methods regularized using the constraints in the problem). Check out this reference (web.stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf). I think at the end of chapter 2 (Precursors) you may find some useful information. $\endgroup$
    – batwing
    Commented Oct 22, 2020 at 5:44

1 Answer 1

1
$\begingroup$

When Boyd refers to "regularizing the subproblems," he is likely referring to techniques that improve the numerical stability and convergence properties of the subproblem solvers in the context of dual decomposition. Dual decomposition involves solving a series of subproblems, each of which involves optimizing a subset of the variables in the original problem while holding the others fixed. These subproblems can sometimes be ill-conditioned, which can lead to numerical instability and slow convergence.

One common technique for regularizing subproblems is to add a regularization term to the objective function that penalizes large values of the variables. This can help to improve the conditioning of the problem and prevent numerical issues such as overflow or underflow. The choice of regularization term depends on the specific problem and the structure of the subproblem.

Another technique is to use preconditioning to improve the conditioning of the subproblem. Preconditioning involves transforming the subproblem into an equivalent form that has better conditioning properties, such as by scaling the variables or adding a diagonal matrix to the constraints. Again, the choice of preconditioning technique depends on the specific problem and the structure of the subproblem.

Finally, it is also possible to choose the decomposition variables in such a way as to improve the conditioning of the subproblems. For example, if the original problem has a block diagonal structure, it may be beneficial to choose the decomposition variables to correspond to the blocks in the matrix.

Overall, the choice of regularization technique depends on the specific problem and the structure of the subproblem. It is often a matter of trial and error to find the technique that works best for a given problem.

$\endgroup$

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.