6
$\begingroup$

We all know the 2nd derivative test in its original form, if $f'(x)=0$, then if $f''(x)<0$ the point is max, and if $f''(x)>0$ the point is min. We also know the generalization for the case is inconclusive with one variable: (I) https://en.wikipedia.org/wiki/Derivative_test#Higher-order_derivative_test

We also know the generalization for multi variable:(II) https://en.wikipedia.org/wiki/Second_partial_derivative_test#Functions_of_many_variables

The question is if there is a generalization of the two, say for multivariable if none of the conditions are met, then we can take the next derivative until we find a derivative which is not zero and use the conditions in (II) to decide whether it's a max or min.

So prove or disprove, one can just take nth derivative and check using the II conditions, that if an extremum is a max or min, or disprove via a counterexample .

$\endgroup$
2
  • $\begingroup$ The following example, which I learned from Walter Rudin, might be relevant. The fourth-degree polynomial $(y-x^2)^2+y^4$ has a strict minimum at the origin. But if you modify it by subtracting a suitable higher-degree term like $2x^8$, the result no longer has a local minimum at the origin. $\endgroup$ Oct 21 '21 at 23:42
  • $\begingroup$ @AndreasBlass I'm not quite sure what do you mean by that. $\endgroup$ Oct 22 '21 at 15:49
1
+50
$\begingroup$

There cannot be such algorithm in general (As long as NP!=P) Suppose there was, let's call it A. the number of condition is constant. calculating matrix multiplication is polynomial. So A is polynomial. calculating n-th derivative is polynomial. Now use the algorithm A to find the if it is the minimum or not. so our algo is in P. But according to https://arxiv.org/abs/1012.0729 and other papers, finding local minimum is NP hard. so one of the following:

  1. you prove P=NP or
  2. A doesn't exist.
$\endgroup$
0
$\begingroup$

Sure! The general form of the Taylor's Theorem can be written as

$$\begin{aligned} f(x)= &f(x_0) +𝐃f(x_0)β‹…(x-x_0) +\tfrac{1}{2}𝐃^2 f(x_0)β‹…(x-x_0)^{βŠ—2}+β‹― \\&β‹―+\tfrac{1}{k!}𝐃^k f(x_0)β‹…(x-x_0)^{βŠ—k} +\tfrac{1}{(k+1)!}R_{k+1}(x)β‹…(x-x_0)^{βŠ— (k+1)} \end{aligned}$$

In the case when $f\colon H→ℝ$ is scalar, we may even express it as

$$\begin{aligned} f(x)= &⟨f(x_0)∣(x-x_0)^{βŠ—0}⟩_{H^{βŠ—0}} \\&+βŸ¨πƒf(x_0)∣(x-x_0)⟩_{H^{βŠ—1}} \\&+\tfrac{1}{2}βŸ¨πƒ^2 f(x_0)∣(x-x_0)^{βŠ—2}⟩_{H^{βŠ—2}} \\&+β‹― \\&+\tfrac{1}{k!}βŸ¨πƒ^k f(x_0)∣(x-x_0)^{βŠ—k}⟩_{H^{βŠ—k}} \\&+\tfrac{1}{(k+1)!}⟨R_{k+1}(x)∣(x-x_0)^{βŠ— (k+1)}⟩_{H^{βŠ—(k+1)}} \end{aligned}$$

Using the induced inner product of the tensor product of Hilbert spaces. For example: the Frobenius inner product for $mΓ—n$ matrices is the induces inner product on $ℝ^m βŠ— ℝ^n$. Convince yourself that the standard Hessian term $xᡀ𝐇f(x_0)x$ is identical to $βŸ¨πƒ^2f(x_0), x^{βŠ—2}⟩_{ℝ^nβŠ—β„^n}$

We say a tensor $π“βˆˆH^{βŠ—2n}$ is positive definite if and only if $βŸ¨π“βˆ£x^{βŠ—2n}⟩_{H^{βŠ—2n}}β‰₯0$ for all $x$ with equality if and only if $x=0$.

Theorem Assume $f\colon ℝ^n →ℝ$ is $2n$ times continuously differentiable and $𝐃^kf(x_0)=0$ for $k=1…(2n-1)$ and $𝐃^{2n}f(x_0)$ is positive definite. Then $f$ has a strict local minimum at $x_0$.

Proof: It is more or less a replication of the regular proof. By Taylors formula:

$$\begin{aligned} f(x) - f(x_0)= \tfrac{1}{(2n)!}𝐃^{2n} f(x_0)β‹…(x-x_0)^{βŠ—2n} +\tfrac{1}{(2n+1)!}R_{2n+1}(x)β‹…(x-x_0)^{βŠ— (2n+1)} \end{aligned}$$

Since $𝐃^{2n} f(x_0)$ is positive definite, the first term is always positive for $xβ‰ x_0$. But it also dominates $R$ asymptotically as $xβ†’x_0$. Hence, there must be an Ξ΅-ball $U_Ξ΅(x_0)$ around $x_0$ for which the RHS is positive for all $xβ‰ x_0$. Hence $f(x)>f(x_0)$ locally.

$\endgroup$
1
  • 2
    $\begingroup$ This is certainly true, but a proper generalization of the derivative test would have to address what happens in the following situation: suppose $x_0$ is a point where $Df(x_0)=0$ (so we have a critical point), but $D^2f(x_0)$ is non-zero, but say $D^2f(x_0)$ is not positive definite (and not negative-definite). In one-dimension of course this is impossible, but in higher dimensions it is. $\endgroup$
    – peek-a-boo
    Oct 22 '21 at 0:15

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.