Solve Primal Dual Problems: Understand Convex Function & Lagrangian

[OhMyMarkov]

Hello everyone!

I got this topic confusing me:

Suppose we would like minimize a convex function such that a given constraint is satisfied, mathematically, we would solve:

$arg min _x f(x)$ such that $c(x) \in S$ where $c(x)$ is the constraint function and $S$ is the allowable set of values $c(x)$ can have (I don't know if this is correct in mathematical notation...)

The dual of this problem would be solving the Lagrangian, that is: $arg min _x f(x) + \lambda c(x)$ where $\lambda > 0$. But they say that the two problems are not equivelent in a sense that there is what is called a duality gap between the two results, but that this gap is zero for linear programs and second order cone programs. What I want ask is that, how are the two problems different and why do they yield different results, we've been using Lagrange multipliers for a while and it is shocking that the result it produces may not be correct.Any help is appreciated!

 

[jvicens]

Hello there,

Thank you for bringing up this interesting topic. I am a scientist who specializes in optimization and I would be happy to provide some clarification on the differences between the two problems and why they yield different results.

Firstly, you are correct in your mathematical notation for the minimization problem with a constraint. The constraint function, $c(x)$, represents a set of conditions that the solution, $x$, must satisfy. The allowable set of values for $c(x)$, denoted by $S$, is often referred to as the feasible region.

Now, let's talk about the dual problem. The Lagrangian, which is obtained by adding the product of the constraint function and a Lagrange multiplier, is a way to convert the constrained optimization problem into an unconstrained one. The dual problem is essentially finding the minimum of this unconstrained function, which is equivalent to finding the maximum of the original function subject to the constraint.

The reason why the two problems may yield different results is because the dual problem involves maximizing over the Lagrange multipliers, while the original problem involves minimizing over the decision variables. In some cases, the optimal solutions for the two problems may not be the same, resulting in a duality gap. This gap can be thought of as the difference between the optimal values of the two problems.

As you mentioned, for linear programs and second order cone programs, the duality gap is zero. This is because these types of problems have special properties that allow the optimal solutions for the two problems to be equal. However, for more general convex functions, the duality gap may not be zero and the two problems may yield different results.

I hope this helps to clarify the differences between the two problems and why they may yield different results. If you have any further questions, please don't hesitate to ask. Good luck with your research!