Vector conjugate of a linear mapping

Question

As we know, if $f:X \to \mathbf R$ is given by $f(x)=\langle a^*,x\rangle$, where $a^*\in X^*$ then the (Fenchel) conjugate of $f$ is given by $f^*(x^*)=0$ for $x^*=a^*$ and $f^*(x^*)=+\infty$ else.

Now let $f:\mathbf R^n \to \mathbf R^m$ be a given mapping and $K\subset \mathbf R^m$ a proper, closed, convex, pointed and solid cone. The (weak) vector conjugate $f^*$ is now defined by the following relation, where $V\in \mathbf R^{m\times n}$: $Vx-f(x) \in f^*(V)$ if and only if $Vx-f(x) \not\leq_{\operatorname{int} K} Vy-f(y)$ for every $y\in \mathbf R^n$. Here, $a \not\leq_{\operatorname{int} K} b$ if and only if $b-a \notin \operatorname{int} K$.

I would like to calculate the vector conjugate of $f:\mathbf R^n \to \mathbf R^m$, given by $f(x)=Ax$, where $A \in \mathbf R^{m\times n}$ is a given matrix.

It is easy to check, that $f^*(A)= \{0 \}$. Of course, this follows from the relation $Ax-f(x)=Ax-Ax=0$ and the fact that $0 \not\leq_{\operatorname{int} K} 0$.

But how can I calculate $f^*(V)$ for $V\neq A$?

If needed, we can take the cone $$K:= \Big\{ y\in \mathbf R^m \mid \displaystyle\sum_{j=1}^{m} y_j \geq 0 \text{ and } y_j \geq 0 \text{ for } j=1, \dotsc, m-1 \Big\}.$$

Answer 1

By definition, $Vx-Ax \in f^*(V)$ if and only if $(V-A)(y-x) \not\in{\operatorname{int} K}$ for every $y\in \mathbf R^n$. Note that this condition is independent of $x$! Let us therefore replace $y-x$ with $y$ for convenience, and let us look at the opposite condition: there exists $y\in \mathbf R^n$ such that $(V-A)y \in{\operatorname{int} K}$. For your cone, this opposite condition holds if and only if there exists a $y\in \mathbf R^n$ and an $\varepsilon \in \mathbf R$ such that $$\begin{pmatrix}1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots \\0 & 0 & \cdots & 1 & 0 \\ 1 & 1 & \cdots & 1 & 1 \end{pmatrix} (V-A)y \geq \varepsilon e, \varepsilon > 0,$$ or $$\begin{pmatrix}\begin{pmatrix}1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots \\0 & 0 & \cdots & 1 & 0 \\ 1 & 1 & \cdots & 1 & 1 \end{pmatrix} (V-A) & -e\end{pmatrix}\begin{pmatrix}y \\ \varepsilon\end{pmatrix} \geq 0, \quad \begin{pmatrix}0 \\ \vdots \\ 0 \\ -1 \end{pmatrix}^T \begin{pmatrix}y \\ \varepsilon\end{pmatrix} < 0,$$

We now invoke Farkas' lemma:

Exactly one of the following statements is true:

1. The system $Az = b$ has a solution $z \geq 0$

2. The system $A^Ty \geq 0$, $b^Ty < 0$ has a solution $y\in \mathbf R^m$

We recognize the second statement in our linear system above. That was the opposite condition. Therefore, $Vx-Ax \in f^*(V)$ if and only if there exists a $z \geq 0$ such that

$$(V^T-A^T) \begin{pmatrix}1 & 0 & \cdots & 0 & 1 \\ 0 & 1 & \cdots & 0 & 1 \\ \vdots \\0 & 0 & \cdots & 1 & 1 \\ 0 & 0 & \cdots & 0 & 1 \end{pmatrix} z = 0, \quad e^Tz = 1.$$ You can always rescale a nonzero $z$ such that $e^Tz = 1$, so all you need to know is whether $$(V^T-A^T) \begin{pmatrix}1 & 0 & \cdots & 0 & 1 \\ 0 & 1 & \cdots & 0 & 1 \\ \vdots \\0 & 0 & \cdots & 1 & 1 \\ 0 & 0 & \cdots & 0 & 1 \end{pmatrix}$$ has full rank. If it has, there is no such $z$ and $f^*(V) = \emptyset$. Otherwise, $f^*(V) = \{(V-A)x : x \in \mathbb R^n \}$ (which is the column space of $V-A$).