So, today I've encountered the article and there was the speed of convergence of CG compared for primal and dual problem.
The point is, up today I've only briefly heard about "primal" and "dual" problems and I'm not even very experienced generally in optimizations.
So, could you, please, help me to understand this with some simple example?
My attempt
Let's try to use the example from Wikipedia:
We want to solve following problem: $$ A\textbf{x} = \begin{bmatrix} 4 & 1\\ 1 & 3 \end{bmatrix} \textbf{x} = \begin{bmatrix} 1 \\ 2 \end{bmatrix} = \textbf{b}\\ x_* = \begin{bmatrix} \frac{1}{11}\\ \frac{7}{11} \end{bmatrix} $$
Matrix $A$ is symmetrical and positive-definite, so we know, that the solution is the minimum of the quadratic form. And so we can solve this system by finding its minimum with CG.
$x_*$ is the analytical solution of the system.
I presume, that the primal problem is the minimization of the quadratic function given by my system of equations,so it's something like this:
$$ f(x) = \frac{1}{2}\textbf{x}^TA\textbf{x} - \textbf{x}^T\textbf{b}\\ x_* = \inf\limits_{x} f(x) $$
Could you, please, show me, how can I deduce and solve dual problem from this?
You need at least one constraint to derive the dual. Let's use the Cholesky decomposition of $A$ to write the problem as: $$\inf_x \frac{1}{2}x^TU^TUx - x^Tb$$ The constraint can now be introduced by taking $y=Ux$: $$\inf_{x,y} \left\{ \frac{1}{2}y^Ty - x^Tb : Ux=y\right\}$$ The dual is typically derived via the Lagrangian: $$L(x,y,z) = \frac{1}{2}y^Ty - x^Tb + z^T(Ux-y) \}$$ The dual is now: $$\sup_z \inf_{x,y} L(x,z)$$ To find $\inf_{x,y} L(x,z)$, set the derivatives to zero to obtain $-b+U^Tz = 0$ and $y-z=0$. The dual is therefore: $$\sup_z \left\{ -\frac{1}{2} z^T z : U^T z = b \right\}$$ The dual problem is a constrained problem and can therefore not be solved with "pure" CG. However, there are "projected" CG algorithms that can cope with linear equality constraints, see, e.g., https://www.math.uwaterloo.ca/~tfcolema/articles/Linearly%20Constrained%20Optimization%20and%20Projected%20Preconditioned%20Conjugate%20Gradients.pdf
Note that the solution to the unconstrained problem $\sup_y -\frac{1}{2}y^Ty$ solves $-y=0$, so you really need a projected CG to make any sense of this.