0
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ 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.$$ $\endgroup$
    – RobPratt
    Feb 20, 2020 at 23:59
  • 1
    $\begingroup$ 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$. $\endgroup$ Feb 21, 2020 at 7:25
  • $\begingroup$ @RobPratt, Yes, indeed, that is what I meant. $\endgroup$
    – mmh
    Feb 21, 2020 at 10:30
  • $\begingroup$ @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. $\endgroup$
    – mmh
    Feb 21, 2020 at 10:30
  • 1
    $\begingroup$ An epsilon change in $y_i$ cause the objective term to go from $c$ to 0 $\endgroup$ Feb 21, 2020 at 19:24

0

You must log in to answer this question.