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)$.

  • $\begingroup$ 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.. $\endgroup$ – independentvariable May 15 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.