Consider a convex QP of the form $$ \min_x \bigl\{\tfrac12 x^\top Q x + q^\top x : Ax\leq b\bigr\}\tag{P} $$ with dual $$ \min_y \bigl\{\tfrac12 (A^\top y + q)^\top Q^{\dagger} (A^\top y+q) + b^\top y : y\geq0\bigr\}.\tag{D} $$ Suppose that when solving the problem with an iterative method (interior point method, augmented Lagrangian method,...), we have estimates $\|x^\nu\|$ and $\|y^\nu\|$ at iteration $\nu$ as well as primal and dual infeasibilities. I have heard that it is important to try and keep primal and dual infeasibilities to the same order of magnitude. Are there any standard ways to use information from the primal and dual to scale the subproblem (linear system) that needs to be solved to obtain the next iteration $\nu+1$?

One thought might be to "remove" the norm of $y^\nu$ by considering an alternate problem in terms of new variable $\tilde{y} \gets y/\|y^\nu\|$ so that $\|\tilde{y}\|\approx1$, which controls the scale of the dual infeasibility. But this doesn't do anything to ensure that the scale of the primal infeasibility $b-A{x}$ is commensurate with the dual infeasibility. Would it be better to consider a problem in new variables $x'\gets \frac{x}{\sqrt{\|x^\nu\|\|y^\nu\|}}$ and $y'\gets \frac{y}{\sqrt{\|x^\nu\|\|y^\nu\|}}$?

Crosslinked here.



Your Answer

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