I am trying to study how to get the Lagrangian dual of a standard function quadratic programming problem $\min_x \frac{1}{2} x^T Q x –c^T x$, subject to $A x \le b$. Using the regular Fenchel duality, I know that the result we get is the Lagrangian function $L(x,z)=\frac{1}{2} x^T Q x – z^T (Ax-b)$ (as shown in the link https://en.wikipedia.org/wiki/Quadratic_programming#Lagrangian_duality ).

I want to understand how we get this using the perturbation that is typically done in Fenchel duality. Fenchel duality, as I understand it, starts with a convex function, let’s call it $f(x)$, and makes a perturbation like so: $F(x,y) = f(x) +g(Ax-y)$.

As I understand it, the requirements are:

  • $F(x,y)$ must be jointly convex in $x$ and $y$

  • $A$ must be a linear operator

  • The perturbation must be such that when $y=0$, the original function is returned

So now I’m wondering if I can arbitrarily choose a perturbation for $A$ and $y$ here. And, if so, then why would there be any reason to choose a perturbation other than $A=I$ (identity matrix), and $y=0$? I do not understand this perturbation here and I’m hoping someone can tell me how it relates to the getting the Lagrangian. Thanks.

Resources: https://en.wikipedia.org/wiki/Quadratic_programming#Lagrangian_duality https://en.wikipedia.org/wiki/Duality_(optimization)


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.