Proving the existence of KKT points

Question

Let a function $f:\mathbb{R}^d \rightarrow \mathbb{R}$ an index set $I$, and inequality constraints $g_i(x)\leq 0, ~\forall i \in I $.

How do we prove the existence of KKT points for $f$ subject to $g_i, ~i \in I$ without using e.g the existence of a minimum of $f$ (through Weierstrass for example) in conjunction with a constraint qualification?

I have a feeling that it could be a fixed point theorem.

PS: In an optimization problem, we implicitly prove that the set of KKT points is nonempty through evoking some constraint qualification for feasible local optima of the problem.

i.e., Since local optima must be KKT points then the set of KKT points is nonempty.

Can we use a straightforward argument for the existence of KKT points irregardless of local optima and constraint qualifications?

Answer 1

You said: “When we evoke a constraint qualification, we implicitly prove that the set of KKT points is nonempty -- it must include the local optima of an objective function”. This is not true in general if I correctly understood what you said. Constraint qualifications have nothing to do with KKT points. As the name suggests, constraint qualifications (CQ) are assumptions on the algebraic description of the feasible set of an optimization problem that ensure that the KKT conditions hold at any local minimum. So, if the problem does not assume minimum, and it satisfies an CQ at all feasible points, KKT points might not exist.

On the other hand, up to my knowledge, there is no such unified way of guaranteeing the KKT conditions at feasible points. Depending on the problem, finding a KKT point is the same as proving the existence of a solution. Hence, proving one thing must not be easier than guaranteeing the other. In my opinion, finding such a general and practical method/algorithm to find a KKT point whenever they exist is a dream. For me, such an issue seems as hard as any of the Millennium problems.

Despite that, I will give you an insight into why asking for constraint qualifications is not as bad for the fulfillment of the KKT conditions as you might think. What will be discussed is not optimal as your “dream scenario”, but it is optimal in the “practical scenario”. First, when the KKT conditions hold, the basic first-order conditions for optimality hold, see Theorem 6.12 in the variational analysis book written by R. Tyrrell Rockafellar to see what is the definition of such a condition. Hence, there is no way of guaranteeing the KKT conditions without the basic first-order conditions for optimality. Proving that is just an easy exercise. On the other hand, we also have an interesting result that almost follows by definition:

Result: Given a set described by equality and inequality constraints, say $\Omega$ and a feasible point ${x} \in \Omega$, and if, for every differentiable function $f$, we can ensure the KKT conditions at ${x}$ for $f$ whenever it satisfies the basic first-order conditions at ${x}$, this means that the Guignard constraint qualification holds, see Definition 2.2.

Discussion: The idea of proving such a statement is quite easy. Indeed, let us suppose that we can ensure the KKT conditions for every function that satisfies the basic first-order conditions. Given an ${v}$ in the polar of the tangent cone at ${x}$, defining the linear function $f( {h}) = -{v}^{T} {h}$, for all ${h}$, we have that $-\nabla f({x})^{T} {h} = {v}^{T} {h} \leq 0$, for every ${h}$ in the tangent cone, see Definition 2.2.. Hence, the basic first-order conditions hold at ${x}$ for such a function $f$. Thus, the KKT conditions hold at ${x}$ for that function, by the hypothesis. Therefore, ${v} \in \mathcal{L}({x})^{*}$. Hence, the Guignard constraint qualification holds.

The discussion means that proving the KKT conditions at a point whenever they exist, and regardless of the objective function, implies the Guignard constraint qualification holds at ${x}$. This means that, without constraint qualification, there will be objective functions that satisfy the KKT conditions at some point, but some others don't at the same point. Hence, such a general analysis inspired by your “dream scenario” must be even more precise and stronger than guaranteeing that the KKT conditions hold when Guignard constraint qualification holds (which is the weakest constraint qualification known). That's why it must be as hard as any of the Millennium problems to guarantee what you want in a nonobvious manner. I'm not saying that such a condition does not exist, but I'm saying that finding a practical algorithm or even a nonobvious mathematical result that decides whether “there is an ${x}$ that is a KKT point" is true or false is what might be harder than any of the Millennium problems. Up to my knowledge, there is no such algorithm, and it would be incredible to find one.