2
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

In Hastie, Tibshirani and Wainwright "Statistical Learning with Sparsity" page 99 equation (5.11) in section 5.2.2 they use the generalized KKT-conditions in the special case of the Lasso-estimator. I am going to refer to this in my assignment, even though it isn't proved in this book.

If anyone stumbles across this question and know a place, where it is proved, please do let me know.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.