3
$\begingroup$

I have a parameterised optimization problem: \begin{align} \boldsymbol{S}(p)= &\arg \min_{ \boldsymbol{x}} g( \boldsymbol{x})\\ \text{s.t. } & \boldsymbol{A}(p) \textbf{x} = \boldsymbol{b}(p)\\ \end{align} Where we have the following assumptions:

$ \boldsymbol{g}(x) $ is strongly convex, $ \boldsymbol{A}(p) $ is full row-rank. $ \boldsymbol{A}(p) $ and $ \boldsymbol{b}(p) $ is $ C_1 $ continous.

I now want to proove continuity of $\boldsymbol{S}(p)$.


I think I have a working solution strategy (I am not sure if it is precise enough yet)

1: Due to strict convexity, for a fixed p, a unique solution to the KKT conditions exists (which also is the minimum): \begin{equation}\label{key} \boldsymbol{R}( \boldsymbol{z}) = {\left[\begin{matrix}\nabla_{ \boldsymbol{x}} \boldsymbol{g} (x) + \boldsymbol{A}^T \boldsymbol{\lambda} \\ \boldsymbol{A} \textbf{x} - \boldsymbol{b} \end{matrix} \right]}= \boldsymbol{0 } \end{equation} For $ \boldsymbol{z} ={\left[\begin{matrix}\boldsymbol{x }^T & \boldsymbol{\lambda}^T \end{matrix} \right]} ^T $

Using the implicit function theorem to express $ \frac{\partial \boldsymbol{z}}{\partial p} $ : \begin{equation} \frac{\partial \boldsymbol{R} }{\partial \boldsymbol{z} } \frac{\partial \boldsymbol{z}}{\partial p} + \frac{\partial \boldsymbol{R}}{\partial p} =0 \end{equation} Thus: \begin{equation}\label{SENSITIIVITY} \frac{\partial \boldsymbol{z}}{\partial p} = - \left( \frac{\partial \boldsymbol{R} }{\partial \boldsymbol{z} } \right)^{-1} \frac{\partial \boldsymbol{R}}{\partial p} \end{equation} '

The first term: \begin{equation} \frac{\partial \boldsymbol{R} }{\partial \boldsymbol{z} } = {\left[\begin{matrix}\nabla_x^2 ( g(x)) & \boldsymbol{A}^T \\ \boldsymbol{A} & \boldsymbol{0} \end{matrix} \right]} \end{equation} Is invertible if g is strictly convex, and A full row-rank.

Secondly $ \frac{\partial \boldsymbol{R}}{\partial p} $ exists if $ \boldsymbol{A}(p) $ and $ \boldsymbol{b}(p)$ is $C_1$.

Which appearantly shows continuity of $ \boldsymbol{z} $ (and $ \boldsymbol{x} $).

I am unsure if this is precise enough or if I need extra conditions. Can anyone verify?.(or point out what I am missing if it does not hold) Any references or guidelines would be helpful.

Bonus question: By the above, then it seems that $\boldsymbol{z}$ is also $ C_1 $ continous, or do I need any new conditions to state this?.

$\endgroup$
1
  • 1
    $\begingroup$ Do you assume that the minimum always exists or could it also be an infimum? $\endgroup$
    – jarauh
    Feb 8, 2019 at 13:56

1 Answer 1

1
$\begingroup$

The underlying principle in obtaining continuity (even continuous differentiability) for $S$ with the IFT is correct. Personally, I would write things a bit differently/more precisely and in a different order and have done so below, but there is a gap:

Before you talk about continuity of $S$, you should prove that $S$ is actually well defined, so that there indeed exists a (unique) solution to your optimization problem for every parameter $p$. Due to strict convexity of $g$ and linearity of the constraints w.r.t. $x$, it is clear that if a solution exists, then it is unique. But in fact, I think there are instances of your setup where there is no solution, such as $g(x_1,x_2) = e^{-x_1} + e^{-x_2}$, this is strictly convex, $A = (1,0)$ and $b = 1$.

If you can (under more assumptions, such as $A$ invertible, or properties of $g$ on the kernel of $A$, e.g. coercivity) prove that, then you can indeed proceed as you sketched. I think it should be done roughly as follows:

  1. The function $R$ should depend on $z$ and $p$. Then you note that the first component $x$ in $z$ is the unique solution to your optimization problem with parameter $p$, so $x = S(p)$, if and only if there is $\lambda$, the second component of $z$, such that $R(z,p) = 0$. This is due to (strong) convexity; the second component $\lambda$ in $z$ is then the associated Lagrange multiplier.
  2. Planning to use the implicit function theorem, you need to verify two things: that $R$ is Frechet-differentiable, and that the partial derivative $\partial R/\partial z$ is continuously invertible. (Look up the assumptions of the theorem!) You basically have already written down the argument for the latter.
  3. Now the implicit function theorem tells you that for every pair $(\bar z,\bar p)$ satisfying $R(\bar z,\bar p) = 0$, there is a continuously differentiable mapping $\varphi$ defined on some open set surrounding $\bar p$ such that $R(\varphi(p),p) = 0$ for all $p$ from that open set. Unwinding all the notation shows that in fact $S$ and $\varphi$ must coincide, so $S$ is also continuously differentiable. Note how the implicit function theorem requires to have a solution at hand first!
$\endgroup$

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.