2
$\begingroup$

I have to solve a set of nonlinear optimization problems in the subspace defined as the orthogonal space to a given vector.

More precisely, $$ \arg\min f(\vec x) \qquad \text{with} \qquad \vec x \cdot \vec n =0 $$

I am thinking of applying the nonlinear conjugate gradient method projecting the direction of descent but I am wondering in which step I should do this projection operation.

One idea is that the projection should take place only in the update of the position like $$ \vec d_k = - \vec \nabla f(\vec x_{k-1}) + \beta \vec d_{k-1} \\ \alpha_k = \arg \min f(\vec x_{k-1} + \alpha \vec d_k) \\ \vec x_{k} = \vec x_{k-1} + (\alpha_k \vec d_k) - [(\alpha_k \vec d_k)\cdot \vec n ]\vec n $$

The other idea is to apply projection directly to the gradient itself such that even the past directions are subjected to the constraint of living in the orthogonal subspace to $\vec n$

$$ \vec g_k = \vec \nabla f(\vec x_{k-1}) - [\vec \nabla f(\vec x_{k-1})\cdot \vec n]\vec n \\ \vec d_k = - \vec g_k + \beta \vec d_{k-1} \\ \alpha_k = \arg \min f(\vec x_{k-1} + \alpha \vec d_k) \\ \vec x_{k} = \vec x_{k-1} + (\alpha_k \vec d_k) $$

What is the best way to solve this problem?

Improve this question
$\endgroup$
5
  • $\begingroup$ I am not so sure projecting will be as good as adding term $+\epsilon \|\vec x \cdot \vec v\|_2^2$, this term will be linear and very nice for conjugate gradient to follow and you get the constraint "baked into the problem" so to speak, so you don't need to worry about altering algorithm in some untested way. $\endgroup$
    – mathreadler
    Apr 20 '19 at 18:42
  • $\begingroup$ Probably you are right, but performing this optimization is just a subroutine of a more complex algorithm such that the directions $\vec n$ are different for each subproblem and they even change in time. So I'd prefer to use projection $\endgroup$
    – skdys
    Apr 21 '19 at 19:09
  • $\begingroup$ Why not simply express your objective function in terms of $n-1$ coordinate vectors perpendicular to $n$? find a basis for this space. $\endgroup$
    – Brian Borchers
    Apr 22 '19 at 1:01
  • $\begingroup$ @BrianBorchers this seems easy said than done. I do not know $n$ before and as I said this is a subroutine of a bigger algorithm. I have just to minimize my function perpendicular to this direction $\vec n$, then this direction changes and again I have to do some minimization steps. The solution you've pointed out seems quite unfeasible in this context. $\endgroup$
    – skdys
    Apr 22 '19 at 10:16
  • $\begingroup$ See @greg answer. $\endgroup$
    – Brian Borchers
    Apr 22 '19 at 13:43
1
$\begingroup$

Let $x = (I-nn^T)y$   then for any vector $y$ the constraint is automatically satisfied.
Let $f_x$ be the gradient of $f$ with respect to $x$, then the gradient wrt to $y$ is $f_y=(I-nn^T)f_x$

Now solve the unconstrained minimization problem for $y$ via conjugate gradients, and calculate the corresponding $x$ afterwards.

$$\eqalign{ y^* &= \arg\min f(y) \cr x^* &= (I-nn^T)y^* \cr }$$

Improve this answer
$\endgroup$
5
  • $\begingroup$ You are basically saying that I should perform unconstrained optimization and then just projecting the solution on the subspace I am interested in? How can I be sure that this solution is the minimum of $f$ in this subspace? $\endgroup$
    – skdys
    Apr 22 '19 at 10:11
  • $\begingroup$ I assumed $n$ was a unit vector, if it's not please adjust the matrix factor to $\Big(I-\frac{nn^T}{n^Tn}\Big)$ $\endgroup$
    – greg
    Apr 22 '19 at 20:32
  • $\begingroup$ Yes, $\vec n$ is a unit vector. However, I don't see why I could be sure that this solution is the minimum of $f$ in this subspace. The projection of the solution in the subspace maybe is not the minimum in that subspace. $\endgroup$
    – skdys
    Apr 22 '19 at 20:54
  • 1
    $\begingroup$ @skdys I think that greg actually meant to write $y^* = \arg \min_{y} f\left( (I - n n^T) y \right)$ since this will actually represent the correct optimization after substituting the expression for $x$. This optimization clearly finds the best value of $f$ along your hyperplane since you’re directly optimizing $f$ along the hyperplane. $\endgroup$
    – spektr
    Apr 27 '19 at 6:45
  • $\begingroup$ The same approach works for any linear constraint $A x = b: \qquad$ min $f( x_0 + $ project $(x))$, project $x$ to the nullspace of $A$, $x_0$ any solution of $A x = b$. $\endgroup$
    – denis
    Dec 20 '19 at 15:38

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.