# Sum of squares optimization with a cut-off (Quadratic programming problem)

I recently asked about an optimization problem, which turned out to be a quadratic programming problem. Specifically, I wanted to minimize the objective function $$-\mathbf{w^{\top}XX^{\top}w}$$ with the constraint $$||\mathbf{w}|| = 1$$. For this problem the optimal solution is proportional to the left singular vector corresponding to the largest singular value.

After analyzing the problem for two weeks, and learning a lot about quadratic programming, I came to the conclusion that I must modify my original problem. Specifically, I would like to maximize

$$f(\mathbf{y}) = \begin{cases}\sum_{i}y_{i}^{2}, \quad &y_{i}^{2} < c\\ 0,\quad &y_{i}^{2} \geq c\end{cases}$$

where $$\mathbf{y} = \mathbf{w^{\top}}\mathbf{X}$$ and $$c$$ is some constant value. So, unlike previously, there is a cut-off in the function.

Is it still possible to solve this via SVD (or find other closed-form solution)? Alternatively, could I rewrite the problem so that the piecewise part becomes a constraint to the problem?

The previous question is available here, which might be helpful for context.

• You are using $i$ in two different ways. I think you meant $$f(\mathbf{y})=\sum\limits_{i: y_i^2<c} y_i^2.$$ Feb 20, 2020 at 23:59
• Are you sure about the discontinuity? A more typical setup would be that the quadratic function saturates, i.e. the function value is $c^2$ for $y_i^2\geq c$. Feb 21, 2020 at 7:25
• @RobPratt, Yes, indeed, that is what I meant.
– mmh
Feb 21, 2020 at 10:30
• @JohanLöfberg That might actually work as well! Would it be easier to solve? Though, I am fairly sure about the cut-off, at least based on everything I have done on this problem so far.
– mmh
Feb 21, 2020 at 10:30
• An epsilon change in $y_i$ cause the objective term to go from $c$ to 0 Feb 21, 2020 at 19:24