1
$\begingroup$

Suppose I have the following optimization problem

$$ \min\limits_{\mathbf{x},\mathbf{y}} f(\mathbf{x},\mathbf{y}) \tag{1} $$

It is already known that the target function $f$ is continuous and differentiable, which has a unique stationary point, and this stationary point is also a global minimum. However, $f$ is not convex. Here, I guess that $f$ is a strict quasi-convex function, and my question is based on this.

From the KKT condition, I find that the necessary condition for the optimal point is $ \mathbf x=g(\mathbf y) $.

  1. Is my guess about this function correctly (just based on the properties discussed above)? If it is, then, we can use convex optimization algorithms to find a global optimal point of $f$ since $f$ is strictly quasi-convex.

  2. Can we substitute $\mathbf x=g(\mathbf y)$ into the target function and solve the consequent optimization problem. In words, is the solution to the following optimization problem equivalent to the original optimization problem in $(1)$?

$$ \min\limits_{\mathbf{y}} f(g(\mathbf y),\mathbf{y}) $$

Any helpful comments are appreciated! ^_^

$\endgroup$
2

2 Answers 2

1
$\begingroup$

Suppose you have the optimization problem

$$ \min_{x,y} f(x,y),\quad (x,y)\in X\subset\mathbb{R}^n\times \mathbb{R}^m \tag{1} $$

Suppose also that the function $f$ is continuous and differentiable, which has a unique stationary point, and this stationary point is also a global minimum.

Since $f$ is diferentiable you can find that $$\frac{\partial f(x,y)}{\partial x}=0$$ gives the necessary condition for the optimal point. Sometimes it gives you one function $ x=g( y)$. But it can gives you more the one implicit functions.

If you have only one function $x=g(y)$, you can substitute into the function and solve the problem $(1)$ as $$ \min_{y} \phi(y),\qquad \phi(y)=f(g( y),{y}),$$ (please see this topic on math.stackexchange).

You can find more related discussions searching for "\(\min_yf(x^*(y),y)\) " on SearchOnMath, like this topic on math.stackexchange.

Note:

  1. Theorem. Let $f:X\to \mathbb{R}$ be differentiable on the open convex set $X\subset \mathbb{R}^n\times \mathbb{R}^m$. Then $f$ is quasiconvex on $X$ if and only if $$u,v\in X,\,f(u)\leq f(v)\Longrightarrow \nabla f(v)\cdot(u-v)\leq 0. $$

a) If you can verify the previous theorem then $f$ is a quasi-convex function.

b) If $f$ was a quasi-convex function. It is not clear why shoud be $\phi(y)=f(g( y),{y})$ convex.

$\endgroup$
1
  • $\begingroup$ Thanks for your time! I understand the sequential optimization procedure now. So in my problem, I can substitute $x=g(y)$ into the original problem, but the subsequent problem may not be equivalent to the original one. This depends on my problem and the structure of $x=g(y)$. $\endgroup$
    – HiNull
    May 6 at 3:14
0
$\begingroup$

The function $$ f(\mathbf{x},\mathbf{y})=-\cos(\mathbf{x}^2+\mathbf{y}^2)\,e^{-\mathbf{x}^2-\mathbf{y}^2} $$ has a global minimum at $\mathbf{x}=\mathbf{y}=0$ but is not strictly quasi-convex because it is not even quasi convex. For $c\in(-1,+1)$ the set $\{f\le c\}$ is a union of sets of the form $\{\mathbf{x}^2+\mathbf{y}^2<R\}\setminus\{\mathbf{x}^2+\mathbf{y}^2<r\}\,.$

$\endgroup$
1
  • $\begingroup$ Thanks for your comment. Yes, the function you write is not quasi-convex, but it does not have a unique stationary point. The point x=y=0 is the global minimizer, but there are also other stationary points. In my function, the stationary point is unique. $\endgroup$
    – HiNull
    Apr 14 at 13:58

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.