0
$\begingroup$

I am stucked at a detail in a constrained optimization problem:

Question

Assume that the objective function is continuous on its domain $D$, but at some points $Z \subseteq D$ it is not differentiable. Further assume that the constraints implicitly force some or all feasible and optimal solutions to take values in $Z$. Doesn't this contradict somehow the Lagrangian approach? How to deal with this?

Example

Think of the following optimization problem (with the continuous extension $0 \cdot \log 0 := 0$) on $n$ variables $x_1, \ldots, x_n$:

minimize $\sum_i x_i \cdot \log x_i$

subject to $A~x = b$ and all $x_i \geq 0$

for some given matrix $A \in \{0,1\}^{n \times n}$ and some positive vector $b$. It has a unique optimum (if any) because the objective is strictly convex with convex constraints.

The Lagrangian $\Lambda(x, \mathbf{\lambda}) = \sum_i~ x_i \cdot \log x_i - \lambda^T ( A~x - b)$ provides the derivatives

$\nabla_{x_i}\Lambda(x,\alpha) = \log x_i + 1 - \sum_k \lambda_k a_{ki}$

and

$\nabla_{\lambda_i}\Lambda(X,\lambda) = (\sum_k a_{ik} x_k) - b_i$.

Probably one should not simply continue calculations and just ignore the fact that the derivatives are not defined for $x_i=0$? Indeed the entries in $A$ may be such that every feasible solution $f$ forces some of the $x_i$'s to $0$, that is, it determines some index set $I(f) \subseteq \{1, \ldots, n\}$ with $x_i = 0$ for all $i \in I(f)$. For any such $x_i$ the derivative is $\nabla_{x_i}\Lambda(x,\alpha) = -\infty$. Hence for each feasible solution separately, "in retrospective" we could set all the $x_i$'s from $I(f)$ to zero already from the beginning and then define $\nabla_{x_i}\Lambda(x,\alpha) := 0$ for them). But this seems to be a painful argument and somehow contradicts the clear formulation of the Lagrangian as a function in the free variables $x_i$. So what is the right approach here?

Some rough ideas: Can one for example argue somehow by the continuity of the derivatives? Or should one study all the optimization problems on every index subspace $S \subseteq \{1, \ldots, n\}$ separately constrained to $x_i > 0$ on $S$, in order to then find the optimum among all of them? Or can one extend the Lagrangian approach to a weaker notion of derivatives? Or are there related techniques that directly work on the KKT conditions without explicitly taking the derivatives?

$\endgroup$
0
$\begingroup$

The class of problems you refer to is called "nonsmooth optimization problems" in the field. Specifically, nonsmoothness refers to the presence of functions for which either the second or the first derivatives do not exist or may not be computable/available. Techniques to solve them vary based on problem class, but there are extensions of first order conditions to certain classes of such problems. For instance, there is the idea of Clarke stationarity based on generalized gradients.

This is pretty active research area in optimization and lots of people are working on it especially since a lot of machine learning problems (such as those involving l1 norms) fall into this category. If you want a starting reference I'd go with Clarke's book.

Hope that helps.

$\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.