4
$\begingroup$

For the optimization problem $\underset{\mathbf{x}\in \mathbb{R}^n}{\operatorname{argmin}} f(\mathbf{x})$, we can use the following standard nonlinear conjugate gradient method to find the solution:

  1. $\mathbf{d}_0 = -\nabla f(\mathbf{x}_0),$
  2. $\mathbf{x}_{i+1}=\mathbf{x}_i+\alpha_i\mathbf{d}_i,$ where $\alpha_i$ is found by line search,
  3. $\mathbf{g}_{i+1} = \nabla f(\mathbf{x}_{i+1})$,
  4. $\mathbf{d}_{i+1}= -\mathbf{g}_{i+1} + \beta_i\mathbf{d}_i$.

I wonder for the problem $\underset{\mathbf{x}\in \mathbb{R}^n, \; \mathbf{y}\in \mathbb{R}^n}{\operatorname{argmin}} f(\mathbf{x},\mathbf{y})$, where $f$ is a function of 2 variables, whether the corresponding nonlinear conjugate gradient method is:

  1. $\mathbf{d}_0^x = -\nabla_{\mathbf{x}} f(\mathbf{x}_0, \mathbf{y}_0), \mathbf{d}_0^y = -\nabla_{\mathbf{y}} f(\mathbf{x}_0, \mathbf{y}_0)$, where $\nabla_{\mathbf{x}}f$ and $\nabla_{\mathbf{y}}f$ are the derivatives of $f$ with respect to $\mathbf{x}$ and $\mathbf{y}$,
  2. $\mathbf{x}_{i+1}=\mathbf{x}_i+\alpha_i\mathbf{d}_i^x$, $\mathbf{y}_{i+1}=\mathbf{y}_i+\alpha_i\mathbf{d}_i^y$,
  3. $\mathbf{g}_{i+1}^x = \nabla_{\mathbf{x}} f(\mathbf{x}_{i+1},\mathbf{y}_{i+1})$, $\mathbf{g}_{i+1}^y = \nabla_{\mathbf{y}} f(\mathbf{x}_{i+1},\mathbf{y}_{i+1})$,
  4. $\mathbf{d}_{i+1}^x= - \mathbf{g}_{i+1}^x + \beta_i^x\mathbf{d}_i^x$, $\mathbf{d}_{i+1}^y= - \mathbf{g}_{i+1}^y + \beta_i^y\mathbf{d}_i^y$.

Also, I am not sure how to compute $\beta_i^x$, $\beta_i^y$. If $\beta_i^x,\beta_i^y$ are computed by the Fletcher–Reeves method, is $\beta_i^x=\beta_i^y=\frac{\|\mathbf{g}_{i+1}\|^2}{\|\mathbf{g}_{i}\|^2}$ (where $\mathbf{g}_{i} = [\mathbf{g}_{i}^x, \mathbf{g}_{i}^y]$), or $\beta_i^x=\frac{\|\mathbf{g}_{i+1}^x\|^2}{\|\mathbf{g}_{i}^x\|^2}$, $\beta_i^y=\frac{\|\mathbf{g}_{i+1}^y\|^2}{\|\mathbf{g}_{i}^y\|^2}$?

$\endgroup$
8
$\begingroup$

If you introduce a variable $\mathbf z=(\mathbf x^T, \mathbf y^T)^T \in \mathbb{R}^{2n}$, then you can write $f(\mathbf x, \mathbf y)=f(\mathbf z)$ and it fits the exact format you wrote in your outline of the first method and it will all work as described. You just have to match things like $\nabla_z f(\mathbf z) = (\nabla_x f(\mathbf x,\mathbf y)^T, \nabla_y f(\mathbf x,\mathbf y)^T)^T$ etc.

$\endgroup$
  • 1
    $\begingroup$ Is this equivalent to my second method, where $\beta_i^x=\beta_i^y=\frac{\|\mathbf{g}_{i+1}\|^2}{\|\mathbf{g}_{i}\|^2}$? $\endgroup$ – chaohuang Jan 12 '13 at 4:37
  • 2
    $\begingroup$ Yes. The two betas must be the same (the CG method doesn't know anything about $x,y$, it only knows of one vector $z$). $\endgroup$ – Wolfgang Bangerth Jan 12 '13 at 12:49
1
$\begingroup$

for your two variable case, $\beta_i$ should be same for both $\beta_i^x$ and $\beta_i^y$, it is computed as $\beta_i=\frac{\mathbf{g}_{i+1}^T\mathbf{g}_{i+1}}{\mathbf{g}_{i}^T\mathbf{g}_{i}}$ (where $\mathbf{g}_{i} = [\mathbf{g}_{i}^x; \mathbf{g}_{i}^y]$). The $\mathbf{g}$ is a 2x1 vector, thus $\mathbf{g}^T\mathbf{g}$ gives a single value. It may help to check Subrat Pathak's master thesis "A COMPARATIVE STUDY OF NON LINEAR CONJUGATE GRADIENT METHODS" where he numerically test the two variable nonlinear cg in several nonlinear functions.

$\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.