# How to find the optimal solution of a convex program given all KKT points?

Suppose we have a parametric convex program with some constraints. $$$$\begin{split} \max_{x} \: & f(x,\mathbf{a})\\ & g_1(x,\mathbf{a})\le 0 \\ & g_2(x,\mathbf{a}) \le 0 \end{split}$$$$

where $$\mathbf{a}$$ is a vector of parameters. I can obtain all KKT points and their corresponding Lagrangian multipliers. I am wondering if it is possible to find the optimal solution based on KKT points and multipliers by conditioning on them? I mean, I want to find conditions and then say if condition 1 is true, the optimal solution will be the first KKT point, and so on.

If there is any example, I would be thankful if you can share it.

• If your problem satisfies a constraint qualification (CQ), you know that all solutions are among the KKT points. Hence, you can just take the KKT points with the smallest objective value. If a CQ does not apply, there might be solutions which are not KKT points. In this case, it is not possible to determine the solutions by just looking at the KKT points.
– gerw
Aug 18, 2021 at 6:14
• Thanks. Is there any other method except evaluating all KKT points? I mean based on lagrange multipliers, and solutions, is it possible to define some conditions for optimality of each point?
– Amin
Aug 18, 2021 at 7:01
• I have to point out that all the KKT points for convex program must be optimal solution (without any CQ) and this is the so-called KKT sufficient condition. Aug 18, 2021 at 8:08
• Yeah. I agree. All KKT points can be optimal but not simultaneously. For example, suppose we have $\{\max_x \: ax \: | \: -1\le x\le 1\}$. Here, 1 is optimal if $a>0$ and -1 is optimal if $a<1$. I wanna find some conditions like these ones for the optimality of each KKT point.
– Amin
Aug 20, 2021 at 17:40
• Crossposted to OR.SE: How to find the optimal solution of a convex program given all KKT points? Oct 25, 2022 at 2:51