I have a nonlinear bi-variate optimization problem like $\max \: f(x,y)$ where $f(x,y)$ is a nonlinear and differentiable function of both variables, and $0\le x\le 1$, $\:0\le y \le ub$. In order to find the optimal solution, can I find the stationary points, $\nabla f(x,y)=0$, and boundary points and evaluate the objective function at the corners, such as $(0,0), (0,ub), (1,0),(1,ub)$ points and stationary points $\nabla f(x,y)=0$ (KKT points)? The highest order in the function is 3 and in form of $xy^2$ or $yx^2$?
3
-
$\begingroup$ Is the function $f$ concave? $\endgroup$– joniJul 14, 2021 at 7:34
-
$\begingroup$ Stationary points (gradient = 0) and KKT points are two different things. Which do you mean? $\endgroup$– prubin ♦Jul 14, 2021 at 17:53
-
$\begingroup$ Yes, you are right. I mean aggregation of KKT points and 4 vertices of the feasible space. The function is not concave, and the objective function it is bounded $\endgroup$– AminJul 15, 2021 at 1:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
The KKT conditions are necessary conditions for an optimum to your problem, so if you can find all feasible points satisfying them, the one with the best objective function will be your optimum. There is no need to consider the corners of the feasible region explicitly. If any of them is optimal, it will also be a KKT point.
-
$\begingroup$ Thank you so much. Do you mean that checking all KKT points is enough regardless of the concavity of the objective function? $\endgroup$– AminJul 15, 2021 at 19:52
-
$\begingroup$ +1, but actually for KKT to be necessary, the objective function $f$ must be continuously differentiable (which it would be if $f$ is a polynomial, as the OP might be suggesting) it is), not just differentiable as stated in the question. $\endgroup$ Jul 15, 2021 at 20:02
-
$\begingroup$ @Katatonia Yes. Convexity (or pseudoconvexity) comes into play when looking for sufficient conditions, but the KKT conditions are necessary without any convexity assumption. $\endgroup$– prubin ♦Jul 16, 2021 at 16:56
-
$\begingroup$ @MarkL.Stone Being rusty w.r.t. NLP, I was going by section 4.3.6 of Bazaraa & Shetty. For the necessary conditions part, they only make the following rather eclectic mix of assumptions (at the local optimum): the objective is differentiable; the binding inequality constraints are differentiable; the nonbinding inequality constraints are continuous; and the equality constraints are continuously differentiable. $\endgroup$– prubin ♦Jul 16, 2021 at 17:01
-