Multi-variable non-convex optimization problem where the problem is convex if one variable is fixed

32 Views Asked by At

I have a non-convex optimization problem in the form

$$ \begin{align} & \min{f(x,y)} \\ & \text{s.t. } h(x,y) \le 0 \end{align} $$

I cannot derive a closed form solution. However, if I assume $y$ is constant, then the problem becomes convex and I can derive a closed form solution for $x$ as a function of $y$, i.e,

$$ \begin{align} x^*(y) = \; & \arg \min_{x}{f(x,y)} \\ & \text{s.t. } h(x,y) \le 0 \end{align} $$

Now, let's assume I can find the global optimal solution of the original problem somehow (numerially) and is denoted by $x_\text{opt}$ and $y_\text{opt}$. Are the following statement and the correspodning proof correct?

$$ x_\text{opt} = x^*(y_\text{opt}) $$

Proof:

By definition we have $$ f(x_\text{opt},y_\text{opt}) \le f(x,y) \quad \forall x,y \quad \text{s.t.} \quad h(x,y) \le 0 $$ and therefore, $$ f(x_\text{opt},y_\text{opt}) \le f(x^*(y_\text{opt}),y_\text{opt}). $$ Also, we have $$ f(x^*(y),y) \le f(x,y) \quad \forall x,y \quad \text{s.t.} \quad h(x,y) \le 0 $$ Therefore, we can write $$ f(x^*(y_\text{opt}),y_\text{opt}) \le f(x_\text{opt},y_\text{opt}). $$ Consequently,

$$ f(x^*(y_\text{opt}),y_\text{opt}) = f(x_\text{opt},y_\text{opt}) $$ and $$ x^*(y_\text{opt}) = x_\text{opt}. $$