Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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?
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.
