Consider the optimization problem
$$
\min_{x\in X} f(x)
$$
where $X\subset\mathbb{R}^n$ is a nonempty closed convex set. $f$ is continuous everywhere on $X$. I can show that $f$ is convex on the interior of $X$. I don't have a proof that $f$ is convex on the boundary of $X$. Are the Karush-Kuhn-Tucker conditions sufficient to characterize a solution to this optimization problem in this case?
[Math] Sufficiency of KKT conditions when the objective function is convex on the interior of feasible set
convex optimizationconvex-analysisoptimization
Best Answer
Yes, Indeed we have $$\text{Set of optimal solutions} = \text{Set of KKT points} $$ If $f$ is continuous on $X$ while convex on $\text{int} X$, then $f$ has to be Convex on whole $X$. Also we know that $\text{int} X \neq \emptyset$ this shows the slater QC holds , therefore aevery optimal point is indeed KKT point. we show that also each KKT point is indeed optimal. To this end, take $\bar{x} \in X$ which satisfies KKT system i.e., $$ 0 \in \partial f( \bar{x} ) + N(\bar{x}; X)$$ Where $N(\bar{x}; X)$ and $\partial f(x)$ are the convex normal cone of $X$ at $\bar{x},$ and convex subdifferential of $f$ at $\bar {x}$ respectively. Depending on the structure of constraints $N(\bar{x}; X)$ can be reduced to the a system containing Lagrange multipliers. From KKT condition we could find vectors $u \in \partial f(\bar{x})$ and $ v \in N(\bar{x}; X)$ such that$$u + v =0$$
Now take $x \in X$, Since $u \in \partial f(\bar {x})$ we have
\begin{align*} \langle u , x -\bar {x} \rangle \leq f(x ) - f(\bar{x}) \\ \Rightarrow \langle v , x -\bar {x} \rangle \ge f(\bar{x}) - f(x ) \end{align*}
And that the left side is negative due to $v \in N(\bar{x} ; X)$, Hence $f(x) \ge f(\bar{x}).$ Therefore $\bar{x} \in X$ is optimal.
Note that the continuity of $f$ on boundary of $X$ is an essential assumption!
For example take $X=[0,1]$ and $f=1$ on $\text{int}X = (0,1)$ and $f(x) = 0$ for $x \in \{0, 1\}$ Then all point living on $(0,1)$ are KKT points, Since for $\bar{x} \in (0,1)$we have $f' (\bar{x}) =0 $ (note that in interior points all Lagrange multipliers are zero, that's why KKT system is reduced to $f' = 0.$ On the other hand, clearly none of these points are optimal!
P.S:
Actually what I mentioned here as Slater QC is not the well-known Slater's Constraint's Qualification (of course $X$ has not been represented by inequalities and equalities), Maybe I should delete that word to avoid confusion. It is a slater type qualification condition (QC) which guarantees Sum Rule i.e, $$ \partial (f+g) (x) = \partial f(x) + \partial g (x) $$ Where $g$ is the indicator function of $X$, so $\partial g(\bar{x}) = N(\bar{x} ; X)$. And note that the constrained problem is equivalent to unconstrained problem with new objective $f+g$. That's why we have the implication $ Optimal \to KKT $. In general Somehow all constraint qualifications can be seen as conditions guarantee Sum rule between objective function and the indicator function of Constraint set. I used sum rule under condition made in Moreu-Rockafellar theorem, which corresponds to Slater's constraint qualification. There are also some other conditions for calculus rules which somehow they have counter part in Constraint Qualification and vice versa!