I have the following optimization problem (like the LASSO problem but with maximization instead of minimization):

$\mathbf{maximize}_{\boldsymbol{\alpha}} \|\mathbf{x} -\mathbf{A}\boldsymbol{\alpha}\|^2$ s.t. $\|\boldsymbol{\alpha}\|_0 \leq k$

with $\alpha$ a sparse vector with no more than $k$ non-zero elements.

We can notice I have a maximization problem instead of a minimization one. To solve this problem, I have first converted into a minimization problem:

$\mathbf{minimize}_{\boldsymbol{\alpha}} -\|\mathbf{x} -\mathbf{A}\boldsymbol{\alpha}\|^2$ s.t. $\|\boldsymbol{\alpha}\|_0 \leq k$

>What I want first to know is if my above minimization problem is correct or not?

I also would like to know if it is possible to solve directly the maximization problem without converting it into a minimization one? If it is possible, so please can you provide me the detailed calculation?

Then, I can proceed as follows:

$\mathbf{minimize}_{\boldsymbol{\alpha}} -\|\mathbf{x} -\mathbf{A}\boldsymbol{\alpha}\|^2  + \lambda \|\boldsymbol{\alpha}\|_1$.

This problem can be simply solved via alternating direction method of multipliers. For example by introducing an auxiliary vector $\boldsymbol{\beta}$ such that $\boldsymbol{\alpha} = \boldsymbol{\beta}$:

$\mathbf{minimize}_{\boldsymbol{\alpha}, \boldsymbol{\beta}} -\|\mathbf{x} -\mathbf{A}\boldsymbol{\alpha}\|^2  + \lambda \|\boldsymbol{\beta}\|_1$ s.t. $\boldsymbol{\alpha} = \boldsymbol{\beta}$.

>Is that correct? Do I have some special trick to solve the above maximization problem?