Linearize objective function in MILP

Question

I have an objective function that I want to linearize but want to confirm that I'm doing it correctly. There are some constraints that are linear in $x$ but they're unimportant for the problem. The objective is: $$\max_{x}p^Tx-\rho\|Ax\|_q$$ Subject to: $$A\in \mathbf{R}^{nxn}$$ $$p\in \mathbf{R}^n$$ $$x\in\{0,1\}^n$$ $$\rho\in\mathbf{R}^+$$

I'm investigating the cases where $q=1$ and $q=\infty$. This is what I've simplified $q=1$ to: $$\max_{x, z}p^Tx-\rho \sum_{i=1}^{n} z_i$$ Subject to: $$A\in \mathbf{R}^{nxn}$$ $$-z\leq Ax \leq z $$ $$z\in \mathbf{R}^n$$ $$x\in\{0,1\}^n$$ $$\rho\in\mathbf{R}^+$$

This feels straight forward from standard LP but just want to confirm this would hold for MILP as well. I may be missing something where this doesn't extend to MILP.

For the $q=\infty$ case, the objective is: $$\max_{}\{p^Tx-\rho*\max_{}\{|Ax|\}\}$$

I've simplified this to: $$\max_{x, z}p^Tx-\rho z$$ Subject to: $$z\geq (Ax)_i \hspace{0.5cm} \forall i \; in \;1 \;to \;n$$ $$z\geq -(Ax)_i \hspace{0.5cm} \forall i \; in \;1 \;to \;n$$ $$A\in \mathbf{R}^{nxn}$$ $$z\in \mathbf{R}$$ $$x\in\{0,1\}^n$$ $$\rho\in\mathbf{R}^+$$

I'm not sure I can transform the inner maximization like that. I know this works for $\min\{\max\{Ax\}\}$ or $\max\{\min\{Ax\}\}$ but does this follow for $\max\{-\max\{Ax\}\}$?

Answer 1

Both linearizations are correct. Here's a derivation for $\max\{-\max\{\}\}$: \begin{align} \max_x\left\{-\max_i f_i(x)\right\} &= \max_x\left\{\min_i \{-f_i(x)\}\right\} \\ &= \max_x\left\{y: y \le -f_i(x) \text{ for all $i$}\right\} \\ &= \max_x\left\{y: -y \ge f_i(x) \text{ for all $i$}\right\} \\ &= \max_x\left\{-z: z \ge f_i(x) \text{ for all $i$}\right\} &&\text{[take $z=-y$]} \end{align}