# Why are $\nabla f(x^*)+A^T\nu^*=0$ called the "dual feasibility equations"?

For the following convex minimization problem:

$$\begin{array}{rl} \textrm{minimize} & f(x)\\ \textrm{subject to} & Ax=b, \end{array}$$

where $f$ is differentiable, the optimality conditions are: $$Ax^*=b, \qquad \nabla f(x^*)+A^T\nu^*=0.$$

In Boyd & Vandenberghe's "Convex Optimization" (p521), $Ax^*=b$ are called primal feasibility equations, and $\nabla f(x^*)+A^T\nu^*=0$ are called dual feasibility equations. The naming of the former makes perfect sense to me, since $Ax=b$ is a set of equations that define the feasible set of the primal problem (within the domain).

However, I'm not so sure why $\nabla f(x^*)+A^T\nu^*=0$ are called the "dual feasibility equations"? Isn't the dual problem an unconstrained concave maximization:

$$\sup_{\nu} \left[\inf_{x\in \mathcal D} f(x)+\nu^T(Ax-b)\right]?$$

Is it because we view the attainability of the infimum within the square brackets for a given $\nu$ as the feasibility condition for the dual problem? (This just defines the domain of the dual problem, doesn't it?)

• Your reasoning seems to be correct Commented Jan 16, 2017 at 6:37
• It is not about attainability, but about value. If the infimum is $-\infty$, we say the corresponding $\nu$ is infeasible. Commented Jan 16, 2017 at 8:33
• @LinAlg Thanks for pointing out this subtlety! Indeed, $\nabla f(x^*)+A^T\nu^*=0$ does not define the domain or feasible set of the dual problem. It is only a sufficient condition for a $\nu$ to be in the domain (and hence feasible). In light of this, I wonder if there's some better reason why we call $\nabla f(x^*)+A^T\nu^*=0$ the dual feasibility equations. Or is it simply because it's a sufficient condition for feasibility of the dual problem? Commented Jan 16, 2017 at 14:17
• I'm not sure I understand your last statement. If $\nabla f(x)+A^Tv\neq 0$, then the inner infimum has not been attained, so that's not the minimizing value of $x$. And in practice, it is often the case that the infimum is $-\infty$ for many particular values of $\nu$---which means those values of $\nu$ are not in the domain of the dual function. So that condition does define the domain of the dual function, and therefore its feasible set. Commented Jan 16, 2017 at 14:53
• I was thinking about the dual of a problem with $f(x) = 1/x$, $x\geq 1$, where the infimum is not attained. However, in the context of optimality conditions for the primal, I can see why these are called dual feasibility equations. Commented Jan 16, 2017 at 15:00

Based on our discussions, I would say this. Using an extended-real convention, the domain $\mathcal{D}$ is absorbed by $f$ itself, and the Lagrange dual is \begin{array}{ll} \text{maximize} & g(\nu) \triangleq \inf_x L(x,\nu) = \inf_x f(x) + \nu^T ( Ax - b ) \\ \end{array} There is no explicit dual constraint for this problem, because the Lagrange multiplier for an equality constraint is itself unconstrained. In contrast, for an inequality constraint $Ax\leq b$, the dual problem would have an explicit constraint $\nu \geq 0$.

However, we know that in practice, there are often values of $\nu$ such that $\inf_x L(x,\nu) = -\infty$. These serve as an implicit constraint on $\nu$ reflected in the domain of $g$. It is common practice to identify those implicit constraints and make them explicit. (Indeed, this is necessary if one does not wish to adopt an extended-real convention.) So the dual becomes \begin{array}{ll} \text{maximize} & g(\nu) \triangleq \inf_x f(x) + \nu^T ( Ax - b ) \\ \text{subject to} & -\infty < \inf_x f(x) + \nu^TAx \end{array} This is true even if $f$ is not differentiable. If $f$ is differentiable on all of $\mathbb{R}^n$, then this is equivalent to \begin{array}{ll} \text{maximize} & g(\nu) \triangleq \inf_x f(x) + \nu^T ( Ax - b ) \\ \text{subject to} & \exists x ~ \nabla f(x) + A^T \nu = 0 \end{array} [EDIT: as the OP points out, there are cases where it is not truly equivalent; rather, it is a sufficient condition.] This will also hold if $f(x)$ is differentiable in an extended-real sense. That is, if:

• $\mathop{\textrm{dom}} f$ is open;
• $f$ is differentiable on its domain;
• $f$ serves as a barrier for its domain; that is, $f(x)\rightarrow +\infty$ as $x\rightarrow\mathop{\textrm{Bd}} \mathop{\textrm{dom}} f$.

Note that this specifically excludes cases where the domain of $f$ is "artificially" constrained, like the case we considered in the comments.

Anyway, subject to these assumptions, it is reasonable to call $\nabla f(x) +A^T\nu=0$ a "dual feasibility constraint". [EDIT: I still maintain that this is reasonable in practice, despite the exceptions found by the OP.] It may seem a bit restrictive to require this assumption at first. But I would suggest that if artificial domain constraints are replaced with explicit equality and inequality constraints instead, these restrictions are somewhat light.

• Thanks a lot for writing up an answer for this question. However, I'm still stuck at one point: It appears that the problem isn't just the artificial constraint we impose on the domain of $f$. For example, consider $\mathrm{minimize } f(x)=e^{x_1}+e^{x_2}-x_1$, subject to $x_1=1$. $f(x)$ is strictly convex and differentiable on $\mathbb R^2$. Its dual function is $g(\nu)=\inf_{x} e^{x_1}+e^{x_2}-x_1+\nu(x_1-1)$. So again $g(1)=-1$ and $\nu=1$ is in the domain of $g$. But the infimum is not attained, and $\nabla f(x)+A^T\nu=[e^{x_1}+\nu-1, e^{x_2}]^T\ne 0$. Commented Jan 17, 2017 at 2:54
• I'm not sure if I follow you. For $\nu=1$, we have $g(1)=\inf_{x} e^{x_1}+e^{x_2}-1=-1,$ isn't it? So the $\nu=1$ is in the domain of $g$. But for $\nu=1$, $\nabla f(x)+A^T\nu=[e^{x_1}, e^{x_2}]^T$ is never zero on the entire $\mathbb R^2,$ isn't it? Commented Jan 17, 2017 at 3:07
• OK. We have $g(\nu) = \inf_x e^{x_1} + e^{x_2} - x_1 + \nu( x_1 - 1)$. Indeed, for $\nu=1$, we have $g(\nu)=\inf_x e^{x_1} + e^{x_2} - 1$ as you indicated, so $g(\nu)=-1$. This is certainly an interesting wrinkle, and yet it still satisfies the condition that $-\infty < \inf_x L(x,\nu)$. Commented Jan 17, 2017 at 3:09
• So it does look like there's a technical detail remaining that I've missed in my answer above. I'll edit to state that it's not a perfect equivalence. Commented Jan 17, 2017 at 3:11
• Remember, the dual function and its effect on the dual feasibility set hold even if $f$ is not differentiable. And as a result, we already knew that the gradient condition is sufficient, but not necessary. So I think we're spending too much time on exceptions like these. I think it's fair to say that this constitutes an error in Boyd & Vandenberghe, though. Commented Jan 17, 2017 at 3:13