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

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.

  • $\begingroup$ 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. $\endgroup$
    – gerw
    Aug 18, 2021 at 6:14
  • $\begingroup$ 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? $\endgroup$
    – Amin
    Aug 18, 2021 at 7:01
  • $\begingroup$ 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. $\endgroup$ Aug 18, 2021 at 8:08
  • $\begingroup$ 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. $\endgroup$
    – Amin
    Aug 20, 2021 at 17:40
  • $\begingroup$ Crossposted to OR.SE: How to find the optimal solution of a convex program given all KKT points? $\endgroup$ Oct 25, 2022 at 2:51


You must log in to answer this question.