We are interested in minimizing a quadratic function, which is not convex. The feasible set is a polyhedron. We know that the global minimum is at a vertex when the function is concave.
Also, there is a paper which says for this type of problem "KKT conditions are necessary for global optimality", which I will cite asap.
My questions are:
- is a KKT point local minimum, or local extremum?
- under what case all the vertices are local minimum?
Best Answer
Unless there is more known about this specific problem than you say, you can not conclude that the global minimum is at a vertex. If the feasible set is bounded and the objective function is concave, you can conclude that the global minimum is at a vertex. But you can not reach that conclusion knowing only that the objective function is non-convex, because it could be indefinite (i.e., neither convex nor concave).
KKT conditions are necessary for global optimality, but they are not sufficient. If the Hessian of the objective function is indefinite, a point satisfying the KKT conditions could be any of 1) global minimum 2) local minimum, which is not global minimum 3) saddle point 4) global maximum 5) local maximum, which is not global maximum
If the Hessian of the objective function is positive semidefinite, there are no saddle points, and every local minimum is a global minimum. If the Hessian of the objective function is negative semidefinite, there are no saddle points, and every local maximum is a global maximum.
A point satisfying the KKT conditions (actually, you presumably mean the first order KKT conditions, can be determined to be a local minimum, saddle point, or local maximum, according to the 2nd order conditions. Specifically, a point satisfying the 1st order KKT conditions is a {local minimum, saddle point, local maximum} if the Hessian of the objective function projected into the null space of the Jacobian of active constraints (i.e., equality constraints and those inequalities which hold with equality at that point) is respectively {positive semidefinite, indefinite, negative semidefinite}. Note that the Jacobian (matrix), is as defined at https://en.wikipedia.org/wiki/Jacobian_matrix_and_determinant#Jacobian_matrix .