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\}\}$?


1 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}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.