3
$\begingroup$

Let $F:\mathbb{R}^{n}\rightarrow \mathbb{R}$ be differentiable. For every affine subset $L$ of $\mathbb{R}^{n}$ of the form \begin{eqnarray} L=\{{x}\in \mathbb{R}^{n}:A{x}=b\} \end{eqnarray} for some $m\times n$ matrix $A$ having full rank and $b\in \mathbb{R}^{m}$, with $m\leq n$, it is known that $F$ attains a $\textbf{unique minimum}$ (let's call it $x^{*}$) over $L$. Further, it is known that $F$ attains a unique minimum on $\mathbb{R}^{n}$ itself. Let's call this point as $x^{0}$.

Given $L\subset \mathbb{R}^{n}$ of the above form satisfying

  1. $x^{0}\notin L$, and
  2. $x^{*}\in L$ is the unique point where $F$ attains a minimum in $L$,

we know, from Lagrange's theorem, that there exists $\lambda^{*}\in \mathbb{R}^{m}$ such that \begin{eqnarray} \nabla F(x^{*})=A^{T}\lambda^{*}. \end{eqnarray}

Is it possible to argue that $\nabla F(x^{*})=A^{T}\lambda^{*}\neq \textbf{0}$, the all-zero vector? If so, can someone provide a proof of the same?

Since $F$ attains a global minimum at $x^{0}$, it is clear that \begin{eqnarray} \nabla F(x^{0})=\textbf{0}. \end{eqnarray}

Since $x^{0}$ is the global minimum, my question is if it is possible that $\nabla F(x^{*})=\textbf{0}$ for $x^{*}\neq x^{0}$ that is the unique point of minimum in $L$.

Nothing more is known about the function $F$, except that it is differentiable. Can imposing more constraints on $F$ (such as requiring $F$ to be strictly convex) pave way for arguing that $\nabla F(x^{*})$ should be a non-zero vector?


Add 1: If we are told that $\nabla F(x^{*})=\textbf{0}$ for some $x^{*}\in \mathbb{R}^{n}$, then we may not be able to conclude if $x^{*}$ is a point of minimum or maximum (or even saddle). However, knowing apriori the fact that $x^{*}$ is the unique point in $L$ where $F$ attains a minimum, and that $x^{0}$ is the unique point in $\mathbb{R}^{n}$ where $F$ attains a minimum, isn't it reasonable to say $\nabla F(x^{*})\neq \textbf{0}$? For, if it were $\textbf{0}$, there would be two points (namely $x^{*}$ and $x^{0}$) where $F$ attains minima in $\mathbb{R}^{n}$? This is just a thought.

$\endgroup$
18
  • $\begingroup$ If it is true, the key property here must be that $F$ attains a unique minimum on each hyperplane. Otherwise it need not be true. $\endgroup$
    – Surb
    Mar 27, 2017 at 11:31
  • $\begingroup$ @Surb yes I too feel this is the point that must be exploited to the fullest. But I do not find a way to argue to my satisfaction. $\endgroup$ Mar 27, 2017 at 11:32
  • 2
    $\begingroup$ @DhanviSreenivasan There is no complementary slackness for equalities. $\endgroup$
    – A.Γ.
    Mar 27, 2017 at 12:12
  • 1
    $\begingroup$ @A.G. good point, but can't every equality be rewritten as a pair of inequalities? $\endgroup$
    – Surb
    Mar 27, 2017 at 14:27
  • 1
    $\begingroup$ @Surb It is always a bad thing to do, because the inequality gradients are going to violate the constraint qualification for sure, and the KKT theory is not valid. $\endgroup$
    – A.Γ.
    Mar 27, 2017 at 15:06

1 Answer 1

1
$\begingroup$

It is possible that $\nabla F(\mathbf x^*)=0$ for $\mathbf x^*\ne \mathbf x^0$.

Example: take $f(t)=(t-1)^3$ and consider $F(x,y)=f(x^2+y^2)$. Basically, the graph of $F$ is the rotation of the following curve

enter image description here

The level sets of $F$ are circles, hence, the minimum on any line is unique (intersections of circles and tangent lines are unique). However, the equation $$ \nabla F(x,y)=2 f'(x^2+y^2)\begin{bmatrix}x\\y\end{bmatrix}=0 $$ has several solutions: the origin (the global minimum of $F$) and the circle $x^2+y^2=1$ where $f'=0$. Hence, taking $L=\{y=1\}$, for example, will give $\mathbf x^*=(0,1)\ne \mathbf x^0=(0,0)$ with $\nabla F(\mathbf x^*)=0$.

The condition that $F$ attains unique minimum on all linear manifolds is equivalent to the level subsets $\{F(\mathbf x)\le C\}$ being strictly convex, that makes $F$ necessarily strictly quasiconvex. If we strengthen it to be pseudoconvex (or, in particular, convex) then $$ \nabla F(a)=0\quad\Rightarrow\quad a\text{ is the global minimum} $$ and by uniqueness it can happen only at $x^0$.

$\endgroup$
4
  • $\begingroup$ Wow!! This is a great answer! Thanks a lot. $\endgroup$ Mar 30, 2017 at 3:30
  • $\begingroup$ Can you please elaborate more on "The condition that F attains unique minimum on all linear manifolds is equivalent to the level subsets {F(x)≤C} being strictly convex, that makes F necessarily strictly quasiconvex"? Any hints on how I can prove this to myself by merely using the fact that F attains a unique minimum on every linear (affine) manifold? $\endgroup$ Mar 30, 2017 at 3:35
  • $\begingroup$ @Karthik I do not have a short proof, just idea: if the minimum is unique then the level subsets $\{F(x)\le \min+\epsilon\}$ should be homotopy equivalent to a point (aka contractible). If such a set is not convex then the convex hull is not strictly convex, and there is a supporting hyperplane that meets it at more than one point which contradicts the uniqueness of minimum. If a level subset $\{F(x)\le C\}$ for an arbitrary $C$ is not contractible then as $C\to\min$ it should bifurcate to a contractible set, and when the bifurcation happens we get again the same contradiction as above. $\endgroup$
    – A.Γ.
    Mar 31, 2017 at 6:07
  • $\begingroup$ Oh I see... Thank you so much $\endgroup$ Mar 31, 2017 at 8:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .