LASSO problem but with a maximization instead of minimization

Question

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?

Answer 1

That problem does not have a maximum. Unless $A$ or $k$ are zero, you can take $\alpha = Me_j$, where $e_j$ is a vector of the canonical basis, and then the objective function diverges when $M \to \infty$.