Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

is there a way to convert this linear functional optimization problem into linear programming?

0 views
Skip to first unread message

LunaMoon

unread,
Oct 19, 2009, 11:07:28 PM10/19/09
to
max a'*x / b'*x

w.r.t x,

s.t. x>=0, 1'*x=1

Here a and b are given vectors, " ' " denotes the vector
transposition, x is our search variable which is a vector, 1 is also a
vector above. It means the element of x should sum up to 1.

Any thoughts?

Thanks a lot!

edadk

unread,
Oct 20, 2009, 1:06:40 AM10/20/09
to
Hi

There is an old idea by Charnes and Cooper that can be used on this
problem I think. However, I would take a look at

S. Boyd and L. Vanderberghe, Convex Optimization, page 151.

which tell you how to convert your problem to an LP.

Erling

mra...@gmail.com

unread,
Oct 21, 2009, 2:09:26 PM10/21/09
to

if you make Xi=1 for the max ai/bi that will do(?)
if you still want to do an LP may be you can max sum((ai/bi)*Xi), with
the same constraints

Michael Hennebry

unread,
Nov 1, 2009, 12:27:47 PM11/1/09
to
On Oct 19, 9:07 pm, LunaMoon <lunamoonm...@gmail.com> wrote:
> max a'*x / b'*x
>
> w.r.t x,
>
> s.t. x>=0, 1'*x=1

Assuming b'*x> 0:
Given any feasible solution with objective value z,
max a'*x - z*b'*x
If the new objective function is greater than 0,
the new x is an improved solution to the original problem.

0 new messages