Consider the following convex continuous optimization problem: min \(f(x)=\sqrt{(x'Qx)}-c'x\) s.t. \(e'x \leq 1\) \(x \geq 0,\) where Q is positive definite, \(c\geq 0\) and \(e=(1,...,1)\). I'm interested in any feasible point \(y\) satisfying \(f(y) < 0\). Assuming the \(f(z) < 0\) for the optimal solution \(z\). Is it true that there exists a vertex \(e_i\), such that \(f(e_i) < 0\)? For sure if this would not be true, there is a convex combination of the vertices with a negative objective function value, but how to find it?
asked
Long |

It is possible that \(f\) is strictly positive at every vertex but negative somewhere in the interior. For instance, try two dimensions with \(Q=I\) and \(c = (0.9, 0.9)\). Since your objective function is differentiable (other than at the origin), you could apply a gradient projection method and just stop iterating as soon as you got an objective value less than zero (by more than rounding tolerance).
answered
Paul Rubin ♦♦ |

Hi Paul, i was aware of taking this method. But actually this might be even be to costly. Is there a way to find 'any' descent direction in 0? I was reading about the steepest descent and computing it would result in the solution of a trust region subproblem. But actually any descent direction would be sufficient to decrease the objective function value below zero in one iteration, right? Unfortunately i'm not aware of any method to determine one.
answered
Long |