What if we found many points satisfying KKT conditions

Question

I have the following convex optimization problem: \begin{equation} \begin{aligned} \max_{x} & \quad f(X)\\ s.t. &\quad \sum\limits_{j=1}^N A_{ij}X_{ij} - \sum\limits_{j=1}^N A_{ji}X_{ji}= 0, \forall i\\ & \quad 0 \leq X_{ij} \leq 1, \forall i, j =1, 2, \cdots, n \end{aligned} \end{equation}

Since we have infinite points satisfying $\sum\limits_{j=1}^N A_{ij}X_{ij} - \sum\limits_{j=1}^N A_{ji}X_{ji}= 0$, then I got many points (cannot enumerate all points) satisfying KKT conditions.

Here for this problem, it satisfies Slater’s condition and thus we have strong duality. So I am wondering if this case happens and then should I say all of these points are optimal???

---

Re-edit: $f(X)$ is concave.

Actually, I can find one feasible solution from the linear system $\sum\limits_{j=1}^N A_{ij}X_{ij} - \sum\limits_{j=1}^N A_{ji}X_{ji}= 0$ and it satisfies all of the KKT conditions.

I am just wondering if I can take this solution as the optimal one due to the strong duality. If that’s true, I do not need to verify other solutions from $\sum\limits_{j=1}^N A_{ij}X_{ij} - \sum\limits_{j=1}^N A_{ji}X_{ji}= 0$.

Answer 1

If you have found a point that satisfies the KKT conditions, then it is an optimal solution. It will be the unique optimal solution when $f$ is strictly concave; otherwise, it's possible that there are multiple equally good optimal solutions.

Some fine print about the properties we're using:

• We need to be looking at a convex program in order to draw this conclusion from the KKT conditions in gradient form. But if you have a point that satisfies the KKT conditions in saddle point form, you don't need convexity. Admittedly, verifying the KKT conditions in saddle point form is less practical.
• The Slater condition on convex programs isn't necessary for this direction. Its purpose is to rule out cases in which no point satisfies the KKT conditions, but a degenerate optimal solution exists. (So if the KKT conditions have no solution, you need something like the Slater condition to conclude that there is no optimal solution. But for a bounded convex program, that's impossible anyway.)