0

Is there a systematic way of going about solving \begin{align} {\text{maximize}} &\hspace{3mm}& \frac{|\mathbf{Ax}|}{N} \\ \text{subject to} &\hspace{3mm}& \mathbf{x} = [0,1] \end{align} where $N$ is the number of non-zero elements in $\mathbf{x}$? For simplicity, we can assume the values of $\mathbf{A}$ are positive real numbers.

  • In case the notation wasn't clear, the elements of $\mathbf{x}$ are either 0 or 1, i.e. $\mathbf{x}$ is a binary vector. –  Apr 15 '16 at 00:56
  • Indeed the notation might need some explanation. Is $A$ a matrix? What are the dimensions of $A$ and $x$? And then what does the absolute value in $|Ax|$ mean? – Josse van Dobben de Bruyn Apr 15 '16 at 00:59
  • $\mathbf{A}$ is a matrix, and could have arbitrary dimensions, as long as it has the same number of columns as rows of $\mathbf{x}$. $|\mathbf{Ax}|$ can be any norm, but for simplicity we can say that it is the $l-1$ norm, i.e., sum of absolute values of its elements. –  Apr 15 '16 at 03:49
  • Okay. One more question: is $A$ a square matrix or not necessarily? – Josse van Dobben de Bruyn Apr 15 '16 at 15:03
  • I suspect you just can select the column $j$ with the largest column sum (and thus N=1). Note that with $A$ positive we can drop the absolute values. Also this can be reformulated as a linear Mixed Integer Program. – Erwin Kalvelagen Apr 15 '16 at 16:34
  • Thanks for the comments. $\mathbf{A}$ does not have to be a square matrix. –  Apr 16 '16 at 23:57
  • @Kalvelagen If we select the column $j$ of $\mathbf{A}$ with the largest column sum, that may not guarantee that the result is maximized? Also, a LMIP is NP-hard, and if $\mathbf{x}$ is binary it is NP-complete? –  Apr 17 '16 at 00:18

0 Answers0