1
$\begingroup$

I'm reading the section on Linear Programming in Barbu and Precupanu's Convexity and Optimization in Banach Spaces (p. 206 in the 4th edition), and had a couple of questions concerning their derivation of the dual problem for the infinite dimensional linear program: $$ (\mathscr{P}) \quad \min\{(x_0^*,x): x\in P, \hspace{.1cm} y_0 - Ax\in Q\}$$ where $X$ and $Y$ are two Banach spaces, $P \subset X$, $Q\subset Y$ are closed convex cones, $A: X\to Y$ is a linear continuous operator, and $x_0^*\in X^*$ and $y_0\in Y$. They note that $\mathscr{P}$ can be obtained from $$ (\mathscr{P}_1) \quad \min\{f(x)-g(Ax) \}$$ in which the perturbations are generated by translations, where $X$, and $Y$ are, again, real Banach spaces, $f: X\to ]-\infty, +\infty]$ is a proper, convex, and lower-semicontinuous function, $g: Y\to [-\infty, +\infty[$ is a proper, concave, and upper-semicontinuous function, and $A:X\to Y$ is a linear continuous operator. They take $f=x_0^*+I_P$ and $g = -I_{y_0-Q}$, and proceed to calculate conjugate functionals as follows: $$\begin{aligned} f^*(x^*) &= \sup\{(x^*-x_0^*,x): x\in P \} = I_{P^0}(x^*-x_0^*), \\ g^*(y^*) &= \{(y^*,y): y\in y_0-Q\} = (y^*,y_0)-\sup\{(y^*,y); y\in Q\}\\ &= (y^*,y_0) - I_{Q^0}(y^*) \end{aligned}$$ Arriving at a dual problem associated with $\mathscr{P}_2$: $$ (\mathscr{P}^*) \quad \max\{(y^*,y_0): y^*\in Q^0, A^*y^*-x_0^*\in P^0 \}$$ My questions about the derivation are as follows:

  • Why did they choose $f$ and $g$ as they did for this derivation? I'm having trouble relating it to the choices of $f$ and $g$ for the derivation of the dual problem for an LP in $\mathbb{R}^n$. That is to say for the canonical form of the finite dimensional problem, $$(\mathscr{P}_c)\quad \min\{\langle x,b\rangle _n:x\in\mathbb{R}^n,x\geq 0,Ax\geq c\}$$ they take $f(x) = \langle x,b\rangle _n $ for $x\geq 0$, and $+\infty$ otherwise, and $g(y)=0$ if $y\geq c$, and $-\infty $ otherwise.

  • Why is $\sup\{(x^*-x_0^*,x): x\in P \} = I_{P^0}(x^*-x_0^*)$? I believe $I_{P^0}(x^*-x_0^*)$ is the indicator function on the polar of the set $P$, but it seems as if this should be the support functional of $P^0$, since by definition for a subset $A$ of $X$: $I^*_A(x^*)=\sup\{(x,x^*); x\in A\}$ represents the equation of a supporting hyperplane of $A$, which in this case I believe is $P^0$. This would make sense to me since the basic idea behind duality and constructing the dual problem is recovering a closed convex set from its supporting hyperplanes.

  • In calculating the convex conjugate of $g$, why is $g^*(y^*) = \{(y^*,y): y\in y_0-Q\}$, and not $g^*(y^*) = \sup\{(y^*,y)-g(y): y\in y_0-Q\}$? I thought that for any function $f:X\to\overline{\mathbb{R}}$, we had that its convex conjugate was defined as $f^*(x^*) = \sup\{(x,x^*)-f(x); \quad x\in X\}, x^*\in X^*$. Again, my understanding of this geometrically, in terms of why we care about convex conjugate functionals, and relating to the construction of the dual was that we are in some sense picking the "smallest" slope for a hyperplane that is tangent to the convex function. Is there some simplification or assumption that I'm missing?

  • Lastly, why is $\{(y^*,y): y\in y_0-Q\} = (y^*,y_0)-\sup\{(y^*,y); y\in Q\}$? Without the introduction of $\sup$ as I imagine there should be, I don't see how they made that jump.

    I suspect that I'm missing something painfully obvious. Any help addressing my above questions would really help my understanding and be greatly appreciated :)

$\endgroup$

1 Answer 1

1
+50
$\begingroup$
  1. 'Because it works'. If you pick a different $f$ and $g$ I am sure you can also make it work, but the structure of $\mathscr{P}_1$ makes it easy to derive the dual.

  2. The indicator function $I_{P^0}(x^*-x_0^*)$ takes values $0$ and $\infty$: it takes the value $0$ if $(x^*-x_0^*, x) \leq 1$ for all $x \in P$, which is the same as requiring $(x^*-x_0^*, x) \leq 0$ for all $x \in P$ (because $P$ is a cone). The expression $\sup\{(x^*-x_0^*,x): x\in P \}$ also takes values $0$ and $\infty$ (since $P$ is a cone): it takes the value $0$ if $(x^*-x_0^*,x)\leq 0$ for all $x\in P$. Therefore, the functions are identical.

  3. You have $g(y) = -I_Q(y_0 - y)$ , so $g^*(y^*) = \inf_y \{ (y^*,y) + I_Q(y_0 - y \}$. Substituting $z = y_0 - y$ gives: $g^*(y^*) = (y^*,y_0) - \sup_z \{ (y^*,z) - I_Q(z) \}$. For the last term you can use the same reformulation as in 2 to relate the support function of $Q$ to the indicator of the polar of $Q$.

$\endgroup$
6
  • $\begingroup$ This was relatively helpful, so thank you for putting the time in to answer! Two quick things that I would appreciate an edit on before I accept: First, how is $g(y) = I_Q(y_0 - y)$, when I thought $g(y) = -I_{y_0-Q}(y)$ for some $y\in Y$; I tried looking at the definitions and working out a similar argument as you but got stuck since I've never formally studied cones and such, so sorry for that lack of knowledge. However everything after that assertion in $3$ makes sense. $\endgroup$
    – teddy
    Commented Apr 30, 2020 at 16:51
  • $\begingroup$ Second, their formulation is for the canonical form, but how would i proceed if it were a problem in standard form? Would I take $y_0=0$ and derive it for another set of inequality constraints where $A$ takes the opposite sign, since $Ax=0 \iff 0\leq Ax\leq 0$? I imagine taking $y_0=0$ would force the objective function of the dual to be $0$ since it's the linear functional $y^*$ evaluated at $y_0$, so that can't be correct? Any guidance would be appreciated, thank you so much again @LinAlg ! $\endgroup$
    – teddy
    Commented Apr 30, 2020 at 16:52
  • 1
    $\begingroup$ @teddy You are right about the minus sign in $g$, I fixed that. Since the constraint is $y_0 - Ax \in Q$, you add the term $I(y_0 - Ax|Q)$ to the objective (or subtract $-I(y_0 - y|Q)$ with $y=Ax$). If the constraint is $Ax=0$, $g(y) = 0$ if $y=0$ ($g(y)=-\infty$ otherwise), so $g^*(y^*) = \inf_y \{ (y^*,y) - g(y) \} = 0$. $\endgroup$
    – LinAlg
    Commented Apr 30, 2020 at 18:50
  • $\begingroup$ Great, that makes more sense now! Sorry one last question came up reading your response, I promise: when they derive the dual, they take the difference of the convex conjugates, corresponding to the maximum vertical separation of the corresponding separating hyperplanes, but if $g^*(y^*)=0$, and the conjugate functional of $f$ is either $0$ or $\infty$, then the dual objective function is $0$ everywhere? I can't imagine this would be correct, since the formulation for the dual in finite dimensions is so similar between canonical and standard form, can you please help with my misunderstanding? $\endgroup$
    – teddy
    Commented Apr 30, 2020 at 19:47
  • 1
    $\begingroup$ @teddy if the only finite value of the conjugate of $f$ is $0$, then the optimal value of the primal problem (if it is feasible) is $0$ (compare the primal formulation with the definition of the conjugate of $f$), so it is not surprising that the dual problem also has an optimal value of $0$ $\endgroup$
    – LinAlg
    Commented Apr 30, 2020 at 22:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .