1
$\begingroup$

Consider the strictly convex unconstrained optimization problem $\mathcal{O} := \min_{x \in \mathbb{R}^n} f(x).$ Let $x_\text{opt}$ denote its unique minima and $x_0$ be a given initial approximation to $x_\text{opt}.$We will call a vector $x$ an $\epsilon-$ close solution of $\mathcal{O}$ if \begin{equation} \frac{||x - x_{\text{opt}}||_2}{||x_0 - x_\text{opt}||_2} \leq \epsilon. \end{equation}

Suppose that there exists two iterative algorithms $\mathcal{A}_1$ and $\mathcal{A}_2$ to find an $\epsilon-$ close solution of $\mathcal{O}$ with the following properties:

  1. For any $\epsilon > 0,$ the total computational effort, i.e. effort required per iteration $\times$ total number of iterations, to find an $\epsilon-$ close solution is same for both the algorithms.
  2. The per iteration effort for $\mathcal{A}_1$ is $O(n),$ say, while that of $\mathcal{A}_2$ is $O(n^2).$

Are there situations, where one would prefer one algorithm over the other? Why?

$\endgroup$
1
$\begingroup$

Yes. Consider these other criteria:

  • What are the memory constraints of each algorithm?

Given the size of the problem, this can be an important determinant of which algorithm to use. The problem might exceed the memory capacity of your computer. Newton and quasi-Newton methods rely on computing or approximating the Hessian matrix. This matrix must be stored. However, algorithms like non-linear conjugate gradient do not require computation of the Hessian (and thus, not the storage of it). To compare this to the two algorithms that you mention, notice that "Newton based methods - Newton-Raphson Algorithm, Quasi-Newton methods (e.g., BFGS method) - tend to converge in fewer iterations, although each iteration typically requires more computation than a conjugate gradient iteration as Newton-like methods require computing the Hessian (matrix of second derivatives) in addition to the gradient. Quasi-Newton methods also require more memory to operate (see also the limited memory L-BFGS method)." (https://en.wikipedia.org/wiki/Nonlinear_conjugate_gradient)

  • Is the algorithm parallelizable?

Not all algorithms are as scalable as others. A classic example in linear algebra is to compare SOR and Gauss-Seidel to the Jacobi method. SOR is usually the preferred methods, although it is not as parallelizable (scalable) as the Jacobi method. (https://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.