Suppose we are given a differentiable function $f(x,y)$ such that $\forall$ $t \in \mathbb{R}$, $f = t$ yields strictly convex level curves. If we are given a line equation $L:y = mx + c$ such that it always intersects two points of a level curve or is tangent to it or does not intersect at all, will it mean that a level curve tangent to $y = mx + c$ always exists?
This is required for a different (convex optimization) problem that I am trying to solve. I am not sure if this holds, but intuitively it feels like that, although I don't have a solid intuition to solve this. Using the Mean Value Theorem, one can say that a tangent with slope $m$ exists that will intersect a given level curve. But I can't extend this to prove that the line $y = mx + c$ itself will be tangent to some level curve.
Update: The problem is almost solved (thanks to @copper.hat), but there's a case that I can rule out. Please see my last comment below this post.
Best Answer
Why is the graph below impossible?
Let $\displaystyle m_1=\min_{p\in[p_1,p_2]}f(p)$ and $\displaystyle m_2=\max_{p\in[p_1,p_2]}f(p)$. WLOG, let the two outer intersection points in the graph be $p_1$ and $p_2$ from left to right, i.e., $f(p_1)=f(p_2)=m_2$. Let the inner two points be $A$ and $B$ from left to right, i.e., $f(A)=f(B)=m_1$. We have $m_1<m_2$; otherwise, the line intersects the level curve $f(x,y)=m_1$ at those four points.
Let $E$ be the midpoint between $A$ and $B$.
However, any strictly convex curve intersects with any line at no more than $2$ points. Hence, the graph above is impossible.
Please see a complete proof below, anyway, if you read the graph differently.
A complete proof
Given point $A\in\mathbb R^2$, let its coordinate be $(A_x, A_y)$ and $f(A)=f(A_x,A_y)$ by slight abuse of $f$. Let $\mathcal C_A$ be the level curve of $f$ that passes $A$, i.e. the curve defined by the equation $f(x,y)=f(A)$.
Pick an abitrary point $P\in \mathcal L$. Since $P\in \mathcal L\cap \mathcal C_P$, by assumption, $|\mathcal L\cap \mathcal C_P|=2$ or $\mathcal L$ is tangent to $\mathcal C_P$. If it is the latter case, we are done.
Otherwise, $|\mathcal L\cap \mathcal C_P|=2$. Let $Q\in \mathcal L\cap \mathcal C_P$, $Q\not=P$. WLOG, suppose $P_x<Q_x$; otherwise, just switch $P$ and $Q$.
$f$ on line segment $\overline{PQ}$ cannot be constant; otherwise, $\mathcal L\cap\mathcal C_P$ would contain infinitely many points. There are two cases.
The minimum value of $f$ on $\overline{PQ}$ is smaller than $f(P)$.
Suppose the minimum value is reached at $S$ for some $S\in\overline{PQ}$. Then $f(S)\lt f(P)$, $S\not=P$ and $S\not=Q$.
Claim. Let $B\in \mathcal L$, $B\not=S$. Then $f(S)\lt f(B)$.
Proof. Let $g(x):x\to \mathbb R$, $g(x)=f(\text{the point on $\mathcal L$ with first coordinate }x)$. $g(P_x)=f(P)=f(Q)=g(Q_x)$.
Suppose $f(S)\ge f(B)$ for the sake of contradiction. There are several cases of $B_x$.
$B_x<P_x$.
$\quad\quad\begin{matrix}\mathcal L:\ \\\ \end{matrix} \overline{\quad\quad B\quad\quad P\quad\quad\phantom{B}\quad\phantom{D}\quad S\quad \quad\quad Q\quad\quad\quad}$
Since $g$ is continuous, $g(x)=\frac{f(S)+f(P)}2$ as an equation in $x$ has one root in interval $(B_x, P_x)$, a root in interval $(P_x, S_x)$ and a root in interval $(S_x, Q_x)$. That means $\mathcal L$ intersects the level curve $f(x,y)=\frac{f(S)+f(P)}2$ at three points, which cannot be true.
$B_x = P_x$, which is not possible since $f(S)<f(P)$.
$P_x<B_x<S_x$. Since $g(S_x)$ is the minimum value of $g$ on $[P_x, Q_x]$, $f(S)\le f(B)$. Hence $f(S)=f(B)$.
Let $D$ be the midpoint of $B$ and $S$.
$\quad\quad\begin{matrix}\mathcal L:\ \\\ \end{matrix} \overline{\quad\quad\phantom{B}\quad\quad P\quad\quad B\quad D\quad S\quad\quad\quad Q\quad\quad\quad}$
The remaining cases are symmetric to the cases above. $\quad\checkmark$
The claims says $\mathcal L$ intersects $\mathcal C_S$ only at $S$. That means $\mathcal L$ is tangent to $\mathcal C_S$.
The minimum value of $f$ on $\overline{PQ}$ is bigger than $f(P)$.
This case is symmetric to the case above.
Proof is completed.