I'm new to Convex Optimization and I'm reading chapter 5 (DUALITY) in Boyd's book. From my point of view, the most complicated step is how can we find the Lagrange dual function from Primal function, which is given by $ g(λ,v)=\inf L(x,λ,v) $
I tried to enlist several methods to find the Lagrange dual function for each cases as following:
If the primal function is Linear Programming, or Quadratic, basically we can use the gradient $\Delta_{L} = 0$ to find $\inf L$
If the primal function is Norm, $\log{x}$, $\log{\det{x}}$, exponential $e^x$, entropy $x\log(x)$....it is suggested to apply the conjugate function by using $\inf(f) = -\sup(-f)$ then $f^*(y) = \sup (y^{T}x - f(x))$
If the primal function has more than one variable, i.e. $x_{1}, x_{2}$ we need to find the $\inf$ over each variable
In some cases, if the primal function is Quadratic, we can also use the Pseudo Inverse to find the $inf$
I know these mentioned-above cases are not enough, hence, please help to enlist some other cases and how to find the dual function. Appreciate.
Given an optimization problem: $\min\limits_{x\in \mathbb{R}^n} f(x)$ with some constraints (I will choose some for sake of example): $Ax=b\in\mathbb{R}^m$ and $g(x) \leq c\in\mathbb{R}$ we can find the dual in the following way.
First write all constraints with the right hand side being $0$, e.g.
$$Ax=b \rightarrow Ax-b=0,$$
and
$$g(x) \leq c \rightarrow g(x) - c \leq 0.$$
Next, we give a Lagrange multiplier to each constraint. Inequality constraints will get a nonnegative multiplier and equality constraints will get a multiplier which can take any real value (since an equality is really inequality in both directions). We add this to our original objective:
$$ L(x,\lambda,\mu) = f(x) + \langle \lambda, Ax-b\rangle + \mu (g(x)-c)$$
This is called the Lagrangian of our problem, here $\lambda$ is a vector in $\mathbb{R}^m$ and $\mu$ is a scalar in $\mathbb{R}$ but together they make up our Lagrange multipliers. So, the problem we started with was to minimize $f$ subject to the constraints, however this is equivalent to the following problem:
$$\min\limits_{x\in\mathbb{R}^n}\max\limits_{\lambda\in\mathbb{R}^m, \mu\geq 0}L(x,\lambda,\mu)$$
Since as we let the components of $\lambda$ and $\mu$ grow to infinity we are basically requiring the constraints to be satsified. This is still a tough problem to solve but we can switch the order of the min and the max in our problem to get,
$$\max\limits_{\lambda\in\mathbb{R}^m, \mu\geq 0}\min\limits_{x\in\mathbb{R}^n}L(x,\lambda,\mu) = \max\limits_{\lambda\in\mathbb{R}^m, \mu\geq 0} J(\lambda,\mu)$$
which we call the dual problem, and $J$ is the dual function. Now, you might wonder why your dual function is written as a minimization problem and the one I have presented in maximization. Recall that $\max S = -\min -S$, making this change we can rewrite the dual problem as a minimization problem.
This pdf was really helpful when I was trying to understand this stuff and is the source for my answer: https://cs.stanford.edu/people/davidknowles/lagrangian_duality.pdf