# How to use the KKT-conditions for a not-differentiable function using subdifferentials.

First some notation. Let $$\dfrac{\partial}{\partial \textbf{x}} f(\textbf{x})$$ determine the gradient for a funcion $$f:\textbf{R}^n \rightarrow \textbf{R}$$, and let the subdifferential be determined by $$\dfrac{\partial_s}{\partial_s \textbf{x}} f(\textbf{x})$$. Remark that the subdifferential is the set of all subgradients.

Now imagine we are in an optimization setting, where $$f$$ is the objective function, $$g_i$$ is an inequality constraint function for $$i = 1, \ ..., m_1$$ and $$h_i$$ is an equality constraint function for $$i = 1, \ ..., m_2$$. Let $$\textbf{k}$$ be the vector of lagrange-multipliers for the inequality constraints, and let $$\textbf{l}$$ be the ditto for the equality constraints. Then if all the functions are differentiable, This wikipedia site gives the following KKT-conditions:

\begin{align} && &\dfrac{\partial}{\partial \textbf{x}} f(\tilde{\textbf{x}}) + \sum_{i=1}^{m_1}k_i\dfrac{\partial}{\partial \textbf{x}}g_i(\tilde{\textbf{x}}) + \sum_{j=1}^{m_2}l_j \dfrac{\partial}{\partial \textbf{x}}h_j(\tilde{\textbf{x}}) = 0. && \text{Stationarity condition}\\ && &g_i(\tilde{\textbf{x}}) \leq 0, \qquad i = 1, \ ..., m_1. && \text{Primal feasibility condition I}\\ && &h_j(\tilde{\textbf{x}}) = 0, \qquad j = 1, \ ..., m_2. && \text{Primal feasibility condition II}\\ && &k_i \geq 0, \qquad i = 1, \ ..., m_1. && \text{Dual feasibility condition}\\ && &k_ig_i(\tilde{\textbf{x}}) = 0, \qquad i = 1, \ ..., m_1. && \text{Complementary slackness condition}\\ \end{align} The wiki-article then goes on to make the following remark:

If some of the functions are non-differentiable, subdifferential versions of Karush–Kuhn–Tucker (KKT) conditions are available

I imagine that means if either one of $$f$$, the $$g_i$$'s and the $$h_i$$ are not differentiable, we exchange the stationarity condition with: \begin{align} && &0 \in \dfrac{\partial_s}{\partial_s \textbf{x}} f(\tilde{\textbf{x}}) + \sum_{i=1}^{m_1}k_i\dfrac{\partial_s}{\partial_s \textbf{x}}g_i(\tilde{\textbf{x}}) + \sum_{j=1}^{m_2}l_j \dfrac{\partial_s}{\partial_s \textbf{x}}h_j(\tilde{\textbf{x}}), && \end{align} where the subgradients are uniquely determined by the gradient, for the functions who are still differentiable. However I have a very hard time verifying this. I have looked in my usual nonlinear-programming go-to books (Bertsekas "Nonlinear Programming" and "Convex Optimization" by Boyd and Vanderberghe) without any luck, since these books only deal with differentiable functions. The wikipage links to the following source:

Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. ISBN 978-0691119151. MR 2199043.

However, I do not have acces to this book.

So my question is this: First of all, is my understanding of the comment on the wikipedia-page correct? Secondly, does anyone have a source where I can read a proof for this?

Context: I am asking this question, since I am writing an assignment about constrained estimation of the LASSO-estimator whose error function is not differentiable in parts of it's domain.