1

I'm using a method that is giving satisfactory results in practice, but I have a hard time trying to formulate rigorously what I'm actually computing. I'm solving an optimization problem using Projected Gauss-Seidel algorithm and I would like to write it mathematically as a conic complementary problem or as the dual problem of a quadratic programm. I was not able to find anything related to this in the literature, even though I'm quite sure it exists.

In practice, I have a linear system $A x + b = 0$, where $A$ is positive definite. I know I can solve this problem using Gauss-Seidel $x^{k+1} = L_*^{-1} \left(b - U x^k\right)$ and I know how to prove it converges. However, I want to consider in addition the second-order cone constraint $$ \mathcal{C}_{n+1}=\left\{ x =\begin{bmatrix} y \\ t \end{bmatrix} \Bigg| y \in \mathbb{R}^n, t\in \mathbb{R}, \|y\|_2\leq t \right\}. $$ I'm solving the constrained problem by projecting the elements of $x$ at iteration $k$ of Gauss-Seidel algorithm $y^{k},t^{k}$ on the boundary of $\mathcal{C}_{n+1}$ if necessary. In practice, for iteration $k$, I first update $t^{k}$ following the classical Gauss-Seidel rule, then I project it $t^{k+1} = \max(t^{k+1}, 0)$, and finally I do the same for $y$, $y^{k+1} = y^{k+1} \min(t^{k+1} / \|y^{k+1}\|_2, 1.0)$.

I would like to know to which solution this algorithm is converging, and ideally formulate it as first-order KKT optimality conditions of a quadratic programm if it exists. My intuition is that it should be something like this: $$ \min_x \frac{1}{2} x^T A x + x^T b \\ \text{s.t. } x \in \mathcal{C}_{n+1} $$ But I guess it is not that easy.

duburcqa
  • 139
  • 6
  • In the case of an non-linear hypercube instead of a second-order cone, then I know how to write the solution of PGS as a Non-Linear Complementary Problem (NLCP): $$ s = s^+ - s^- = A x + b \ 0 \leq s^+ \perp x - l(x) \geq 0 \ 0 \leq s^- \perp u(x) - x \geq 0 $$ where $\perp$ is the complementary operator.

    But here it is more tricky since a cannot relate the sign of individual components to a complementary condition. It would be possible for $t$ but not for $y$ ...

     – duburcqa Dec 05 '21 at 17:40

1 Answers1

0

I found the solution. It converges to: $$ r = [r_y^T, r_t]^T = A x + b \\ r_y \cdot (\text{diag}(A)_y x) = - \|r_y\| \|\text{diag}(A)_y x\| \\ 0 \leq r_t \perp t \geq 0 \\ 0 \leq \|r_y\| \perp t - \|y\| \geq 0 \\ $$ Note that it is only valid if the components $y$ are updated in parallel instead of sequentially! But anyway it is the way it should be done.

As far as I know, it is not the dual problem for a quadratic program. But for me it is fine, I'm satisfied with this formulation.

duburcqa
  • 139
  • 6