I think my questions are about conjugate function since I am really not familiar with it. I really hope someone can recommand some materials about this topic.

Consider the problem

min f(x)

s.t. Ax = b, $x \in \chi $

Then, the dual of augmented lagrangian is

$d_{\gamma}(\lambda) = min_{x \in \chi} f(x) + \lambda ^T (Ax - b) + \frac{\gamma}{2}||Ax - b||^2$.

(1) we want to show that $d_{\gamma}(\lambda)$ is differentiable

(2) we want to show that $||\nabla d_{\gamma}(\lambda) - \nabla d_{\gamma}(\lambda^{\prime})|| \leq \frac{1}{\gamma} ||\lambda - \lambda^{\prime}||$.

Here are proofs from my professor's slides for these two questions. But I still have some questions about the proof and conditions of the conclusions.

enter image description here enter image description here

Here are my questions:

(1) To prove that $d_{\gamma}(\lambda)$ is differentiable, we use the conditions that f(x) is differentiable and convex. But what if f(x) is not differentiable? I mean, with augmented lagrandian, what we want to do is to transform the objective which is not differentiable to a more differentiable one. But I cannot find such transformation from this proof.

(2) we know the objection function $d_{\gamma}(\lambda)$ is related to the conjugate function of f(x)(maybe, I am not sure). But for conjugate function, we have the following conclusions.

  • if f is convex and closed, then $(f^*)^* = f$
  • if f is $\gamma$ strongly convex, then $||\nabla f^*(x) - \nabla f^*(y)|| \leq \frac{1}{\gamma} ||x - y||$

I think for the proof, we use such ideas, but I am not familiar with conjugate function, I do not know how to use such conclusions to get the proof. Can anyone help me figure it out?

(3) We can find the constraints is affine function. What if the problem bebecomes general nonlinear problem

min f(x)

s.t. g(x) $\leq 0$

h(x) = 0

I think we can get the same conclusions(differentiability and lipschitz continuous), but I am confused about the conjugate function of such problem. Can anyone give the conjugate function of such general nonlinear problem and give some hits about how to prove the differentiability and lipschitz continuous?


Your Answer

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

Browse other questions tagged or ask your own question.