Finding a feasible solution with negative objective function value

 1 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 11 Mar '15, 10:41 Long 19●1●5 accept rate: 0%

 0 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 11 Mar '15, 15:36 Paul Rubin ♦♦ 14.6k●4●12 accept rate: 19%
 0 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 11 Mar '15, 18:49 Long 19●1●5 accept rate: 0%
 toggle preview community wiki

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

Asked: 11 Mar '15, 10:41

Seen: 984 times

Last updated: 11 Mar '15, 18:49

Related questions

OR-Exchange! Your site for questions, answers, and announcements about operations research.