Introduction to Convex Optimization - Primal problem to Dual problem

Consider an optimization problem in the standard form (we call this a primal problem):

We denote the optimal value of this as $p^{\star }$. We don’t assume the problem is convex.

The Lagrange dual function

We define the Lagrangian $L$ associated with the problem as $$L(x,\lambda ,v)=f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{i=1}^p{v}_i{h}_i(x)$$ We call vectors $\lambda$ and $v$ the dual variables or Lagrange multiplier vectors associated with the problem (1).

We define the Lagrange dual function (or just dual function) $g$ as the minimum value of the Lagrangian over $x$: for $\lambda \in {\mathbf{R}}^m,v\in {\mathbf{R}}^p$, $$g(\lambda ,v)=\underset{x\in \mathcal{D}}{\inf }L(x,\lambda ,v)=\underset{x\in \mathcal{D}}{\inf }(f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{i=1}^p{v}_i{h}_i(x))$$

Note that once we choose an $x$, $f_i(x)$ and $h_i(x)$ are fixed and therefore the dual function is a family of affine functions of ($\lambda$, $v$), which is concave even the problem (1) is not convex.

Lower bound property

The dual function yields lower bounds on the optimal value $p^{\star }$ of the problem (1): For any $\lambda ⪰0$ and any $v$ we have $$g(\lambda ,v)\le p^{\star }$$

Suppose $\tilde{x}$ is a feasible point for the problem (1), i.e., $f_i(\tilde{x})\le 0$ and $h_i(\tilde{x})=0$, and $\lambda ⪰0$. Then we have

$$L(\tilde{x},\lambda ,v)=f_0(\tilde{x})+\sum _{i=1}^m{\lambda }_i{f}_i(\tilde{x})+\sum _{i=1}^p{v}_i{h}_i(\tilde{x})\le f_0(\tilde{x})$$

Hence $$g(\lambda ,v)=\underset{x\in \mathcal{D}}{\inf }L(x,\lambda ,v)\le L(\tilde{x},\lambda ,v)\le f_0(\tilde{x})$$

Since $g(\lambda ,v)\le f_0(\tilde{x})$ holds for every feasible point $\tilde{x}$, the inequality $g(\lambda ,v)\le p$ follows. The inequality holds, but is vacuous, when $g(\lambda ,v)=-\mathrm{\infty }$. The dual function gives a nontrivial lower bound on $p^{\star }$ only when $\lambda ⪰0$ and $(\lambda ,v)\in \mathbf{\text{dom}},g$, i.e., $g(\lambda ,v)>-\mathrm{\infty }$. We refer to a pair $(\lambda ,v)$ with $\lambda ⪰0$ and $(\lambda ,v)\in \mathbf{\text{dom}},g$ as dual feasible.

Derive an analytical expression for the Lagrange dual function

Practice problem 1: Least-squares solution of linear equations

The Lagrangian is $L(x,v)=x^{\mathrm{\top }}x+v^{\mathrm{\top }}(Ax-b)$. The dual function is given by $g(v)={\text{inf}}_{x}L(x,v)$. Since $L(x,v)$ is a convex quadratic function of $x$, we can find the minimizing $x$ from the optimality condition

$${\mathrm{\nabla }}_{x}L(x,v)=2x+A^{\mathrm{\top }}v=0$$

which yields $x=-(1/2)A^{\mathrm{\top }}v$. Therefore the dual function is

$$g(v)=L(-(1/2)A^{\mathrm{\top }}v,v)=-(1/4)v^{\mathrm{\top }}A{A}^{\mathrm{\top }}v-b^{\mathrm{\top }}v$$

Therefore, $p^{\star }\ge -(1/4)v^{\mathrm{\top }}A{A}^{\mathrm{\top }}v-b^{\mathrm{\top }}v$. The next step is to maximize $-(1/4)v^{\mathrm{\top }}A{A}^{\mathrm{\top }}v-b^{\mathrm{\top }}v$.

Practice problem 2: Standard form Linear Programming

The Lagrangian is $$L(x,\lambda ,v)=c^{\mathrm{\top }}x-\sum _{i=1}^n{\lambda }_i{x}_i+v^{\mathrm{\top }}(Ax-b)=-b^{\mathrm{\top }}v+(c+A^{\mathrm{\top }}v-\lambda {)}^{\mathrm{\top }}x$$

The dual function is $$g(\lambda ,v)=\underset{x}{\inf }L(x,\lambda ,v)=-b^{\mathrm{\top }}v+\underset{x}{\inf },(c+A^{\mathrm{\top }}v-\lambda {)}^{\mathrm{\top }}x$$

We see that $g(\lambda ,v)$ is a linear function. Since a linear function is bounded below only when it is zero. Thus, $g(\lambda ,v)=-\mathrm{\infty }$ except when $c+A^{\mathrm{\top }}v-\lambda =0$. Therefore,

The lower bound property is nontrivial only when $\lambda$ and $v$ satisfy $\lambda ⪰0$ and $c+A^{\mathrm{\top }}v-\lambda$. When this occurs, $-b^{\mathrm{\top }}v$ is a lower bound on the optimal value of the LP. We can form an equivalent dual problem by making these equality constraints explicit:

This problem, in turn, can be expressed as

The Lagrange dual problem

For each pair $(\lambda ,v)$ with $\lambda ⪰0$, the Lagrange dual function gives us a lower bound on the optimal value $p^{\star }$ of the optimization problem (1). Thus we have a lower bound that depends on some parameters $\lambda ,v$.

This leads to the optimization problem

This problem is called the Lagrange dual problem associated with the problem (1). In this context the original problem (1) is sometimes called the primal problem. We refer to $({\lambda }^{\star },v^{\star })$ as dual optimal or optimal Lagrange multipliers if they are optimal for the problem (2). The Lagrange dual problem (2) is a convex optimization problem, since the objective to be maximized is concave and the constraint is convex. This is the case whether or not the primal problem (5.1) is convex.

Note: the dual problem is always convex.

Weak/ Strong duality

The optimal value of the Lagrange dual problem, which we denote $d^{\star }$, is, by definition, the best lower bound on $p^{\star }$ that can be obtained from the Lagrange dual function. The inequality

$$d^{\star }\le p^{\star }$$

which holds even if the original problem is not convex. This property is called weak duality.

We refer to the difference $p^{\star }-d^{\star }$ as the optimal duality gap of the original problem. Note that th optimal duality gap is always nonnegative.

We say that strong duality holds if

$$d^{\star }=p^{\star }$$

Note that strong duality does not hold in general. But if the primal problem (11) is convex with $f_1,\dots ,f_k$ convex, we usually (but not always) have strong duality.

Slater’s condition

Slater’s condition: There exists an $x\in \mathbf{relint},D$ such that $$f_i(x)<0,i=1,\dots ,m,Ax=b$$

Such a point is called strictly feasible.

Slater’s theorem: If Slater’s condition holds for a convex problem, then the strong duality holds.

Complementary slackness

Suppose the strong duality holds. Let $x^{\star }$ be a primal optimal and $({\lambda }^{\star },v^{\star })$ be a dual optimal point. This means that

We conclude that the two inequalities in this chain hold with equality. Since the inequality in the third line is an equality, we conclude that $x^{\star }$ minimizes $L(x,{\lambda }^{\star },v^{\star })$ over $x$.

Another important conclusion is

$${\lambda }_i^{\star }{f}_i(x^{\star })=0,i=1,\dots ,m$$

KKT optimality conditions

We now assume that the functions $f_0,\dots ,f_m,h_1,\dots ,h_p$ are differentiable, but we make no assumptions yet about convexity.

KKT conditions for nonconvex problems

Suppose the strong duality holds. Let $x^{\star }$ be a primal optimal and $({\lambda }^{\star },v^{\star })$ be a dual optimal point. Since $x^{\star }$ minimizes $L(x,{\lambda }^{\star },v^{\star })$ over $x$, it follows that its gradient must vanish at $x^{\star }$, i.e.,

$$\mathrm{\nabla }{f}_0(x^{\star })+\sum _{i=1}^m{\lambda }_i^{\star }\mathrm{\nabla }{f}_i(x^{\star })+\sum _{i=1}^p{v}_i^{\star }\mathrm{\nabla }{h}_i(x^{\star })=0$$

The KKT conditions are the following:

For any optimization problem with differentiable objective and constraint functions for which strong duality obtains, any pair of primal and dual optimal points must satisfy the KKT conditions.

KKT conditions for convex problems

When the primal problem is convex, the KKT conditions are also sufficient for the points to be primal and dual optimal. That is, if $f_i$ are convex and $h_i$ are affine, and $\tilde{x},\tilde{\lambda },\tilde{v}$ are any points that satisfy the KKT conditions

then $\tilde{x}$ and $(\widetilde{{\lambda }_i},\widetilde{v_i})$ are primal and dual optimal, with zero duality gap. To see this, note that the first two conditions state that $\tilde{x}$ is primal feasible. Since $\widetilde{{\lambda }_i}$ ≥ 0, $L(x,\tilde{\lambda },\tilde{v})$ is convex in $x$; the last KKT condition states that its gradient with respect to $x$ vanishes at $x=\tilde{x}$, so it follows that $\tilde{x}$ minimizes $L(x,\tilde{\lambda },\tilde{v})$ over $x$. From this we conclude that

This shows that $\tilde{x}$ and $(\tilde{\lambda },\tilde{v})$ have zero duality gap, and therefore are primal and dual optimal.

We conclude the following:

• For any convex optimization problem with differentiable objective and constraint functions, any points that satisfy the KKT conditions are primal and dual optimal, and have zero duality gap.
• If a convex optimization problem with differentiable objective and constraint functions satisfies Slater’s condition, then the KKT conditions provide necessary and sufficient conditions for optimality: Slater’s condition implies that the optimal duality gap is zero and the dual optimum is attained, so $x$ is optimal iff there are $(\lambda ,v)$ that, together with $x$, satisfy the KKT conditions.

Solving the primal problem via the dual

Note that if strong duality holds and a dual optimal solution $({\lambda }^{\star },v^{\star })$ exists, then any primal optimal point is also a minimizer of $L(x,{\lambda }^{\star },v^{\star })$. This fact sometimes allows us to compute a primal optimal solution from a dual optimal solution.

More precisely, suppose we have strong duality and an optimal $({\lambda }^{\star },v^{\star })$ is known. Suppose that the minimizer of $L(x,{\lambda }^{\star },v^{\star })$, i.e., the solution of

is unique (For a convex problem this occurs). Then if the solution is primal feasible, it must be primal optimal; if it is not primal feasible, then no primal optimal point can exist, i.e., we can conclude that the primal optimum is not attained.

---

Reference:

• Convex Optimization* by Stephen Boyd and Lieven Vandenberghe.