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's gravatar image

accept rate: 0%

edited 11 Mar '15, 11:09

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%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

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's gravatar image

accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "Title")
  • 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



Asked: 11 Mar '15, 10:41

Seen: 1,057 times

Last updated: 11 Mar '15, 18:49

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