# Convex Conjugate of sum-of-max terms

Let $$f: \mathbb{R}^n \mapsto \mathbb{R}$$ be a sum-of-max linear terms function:

$$f(x) = \sum_{k=1}^K \max_i\{a_{k,i}^\top x\}$$ where $$a$$ are the linear coefficients.

I am interested in the convex conjugate $$f^*(w)$$ of this function, then I will use a constraint $$f^*(w) \leq 0$$ in a convex optimization problem.

Recall the convex conjugate definition: $$f^*(w) = \underset{x \in dom f}{\sup} w^\top x - f(x)$$

I try: \begin{align} & \underset{x \in dom f}{\sup} w^\top x - f(x) \leq 0 \\ \iff & \sup \{ w^\top x - \sum_{k=1}^K \max_i\{a_{k,i}^\top x\} \} \leq 0\\ \iff & \sup \{ w^\top x + \sum_{k=1}^K \min_i\{-a_{k,i}^\top x\} \} \leq 0 \\ \iff & \sup \{ w^\top x + \sum_{k=1}^K y_k \ | \ y_k \leq \min_i \{ -a_{k,i}^\top x \}, \forall k\} \leq 0 \\ \iff & \begin{cases} w^\top x + \sum_{k=1}^K y_k \leq 0 \\ y_k \leq -a_{k,i}^\top x \quad \forall i,k \end{cases} \end{align}

Obviously, the last steps are incorrect since $$y_k \rightarrow - \infty$$ will always hold the equation. This trick usually works for the $$f(x) \leq 0$$ kind of constraints, but I don't know how to linearize ths conjugate when we have $$\sup$$ of $$-f(x)$$.

• okay, so $f(x)$ is not the correct way to formulate this. All the $a_{k,i}$ coefficients should be in the function input, and $f(z) = \sum_{k=1}^K \max_{i \subseteq {1,\ldots,n}} z_i$ is the better version. Then, we can say $f(Az + b)$, and so on.. – independentvariable May 15 at 0:05