2
$\begingroup$

Assume you have the following simple constrained optimization problem:

$$ \begin{equation} \begin{split} &\min_x f(x) \\ & s.t \quad g(x) = c \end{split} \end{equation} $$ where $f,g$ are both differentiable.

What are the standard way to show that the problem solution (here I am referring to the objective minimum, and not the decision variable) is/is not differentiable with respect to $c$? I have run a few concrete examples and found that numerically the solution seems to be differentiable, but I have no idea how to show it more formally.

$\endgroup$
4
  • 1
    $\begingroup$ What do you mean by: "solution is/is not differentiable with respect to $c$"? $\endgroup$ Jan 10 at 11:43
  • 1
    $\begingroup$ Note that " $f,g$ are both differentiable for a given $c$" should be "$f,g$ are both differentiable" since neither depends on $c.$ $\endgroup$
    – prubin
    Jan 10 at 16:36
  • 1
    $\begingroup$ @MatheusDiógenesAndrade i mean the objective minimum (i.e solution of the problem; note that I am not referring to the decision variable here) of this optimization problem would change w.r.t $c$, thus one can also define a certain notion of differentiability for the minimum with respect to $c$. $\endgroup$
    – c zl
    Jan 15 at 5:12
  • 1
    $\begingroup$ @prubin thanks for pointing it out, i edited that phrase away. $\endgroup$
    – c zl
    Jan 15 at 5:12

2 Answers 2

0
$\begingroup$

There is a rich literature on parametric optimization, which deals with questions of when the optimal value/solution of an optimization problem is (sub)differentiable with respect to its parameters.

Classical references are:

  1. Fiacco's book "Introduction to Sensitivity and Stability Analysis in Nonlinear Programming", available for purchase here
  2. Bonnans and Shapiro's book "Perturbation Analysis of Optimization Problems", available for download/purchase here

A more approachable reference is:

  1. Still's "Lectures on Parametric Optimization: An Introduction", which can be downloaded for free here

In particular, Theorem 4.4 in Still's lecture notes provides general conditions under which the optimal value function of your problem is differentiable with respect to the parameter $c$.

$\endgroup$
1
$\begingroup$

In general, the optimization problem you have stated may not have a unique optimum, i.e, there may exist multiple optimal solutions. Consider, for instance, $\min_{x,y} \{ x | x=c, 0 \leq y \leq 1\}$: any solution $(c,y)$ is optimal.

In that case, the mapping from $c$ to an optimal solution of the problem is one-to-many, and is therefore not differentiable. This is often the case when $f$ and/or $g$ are non-convex: the optimum may not be unique, or it may jump to a distant point even under small perturbation.

There is a rich literature in the machine learning community on differentiating through an optimization problem. As far as I know, they all rely (in some form or the other) on the KKT conditions. One of the most famous paper is this NeurIPS 2019 paper for the convex case.

$\endgroup$
1
  • $\begingroup$ Sorry, but i am actually referring to the objective minimum (not the decision variable) of the optimization problem. Thus the issue of one-to-many seems to not be an issue right? $\endgroup$
    – c zl
    Jan 15 at 5:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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