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$ should be a sparse vector with no more than $k$ non-zero elements.

So 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?

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?