Whether $g(y) = \min\limits_{x} f(x, y)$ is convex under some conditions

68 Views Asked by At

Denote a convex function $f(x,y)$. Suppose that $f$ is convex with respect to $y$, and is a strongly convex quadratic function with respect to $x$.

Let $$ d(y)=\arg\min_x f(x,y). $$

Let $$g(y)=f(d(y),y).$$ Is function $g$ convex?

Due to the comment provided by River Li, function $g$ is not convex.

What if we add a condition: $f$ is further strongly convex with respect to $(x^T,y^T)^T$?

1

There are 1 best solutions below

2
On

If $f$ is convex with respect to $y$ then for every $x$, we have for $t\in(0,1)$ $$f(x,ty_1+(1-t)y_2) \leq tf(x,y_1) + (1-t)f(x,y_2)$$ Surely that means that whenever $x=d(y), y=ty_1+(1-t)y_2$ for any arbitrary function $d$ (including the one you provided), we should still have $$f(d(y),ty_1+(1-t)y_2) \leq tf(d(y),y_1) + (1-t)f(d(y),y_2)$$ Which means (Edited to use convexity with respect to $x$ in line $3$) $$g(ty_1+(1-t)y_2) = f(d(ty_1 + (1-t)y_2),ty_1 + (1-t)y_2)\\ = f(d(y),ty_1+(1-t)y_2) \leq tf(d(y),y_1) + (1-t)f(d(y),y_2) \\ < t^2f(d(y_1),y_1)+t(1-t)f(d(y_2),y_1)+t(1-t)f(d(y_1),y_2) + (1-t)^2f(d(y_2),y_2) \\ < tg(y_1) + (1-t)g(y_2) + t(1-t)\left(f(d(y_2),y_1) + f(d(y_1),y_2)\right)$$ So if $f$ is positive then $g$ is convex.