FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » num-analysis
How to solve the linear objective function with max function, and linear constraints?
Post new topic   Reply to topic Page 1 of 1 [3 Posts] View previous topic :: View next topic
Author Message
Fan
science forum beginner


Joined: 31 Dec 2005
Posts: 7

PostPosted: Tue Jul 11, 2006 7:05 pm    Post subject: How to solve the linear objective function with max function, and linear constraints? Reply with quote

Consider the following problem: a piece-wise linear objective function

with max function, and linear constraints.

Is this still a linear program? What solver can find the solution
quickly?


E.g., x belongs to R_3. Define the max function [y]_+ = max {0,y}.


min [5x_1 - 4x_2]_+ + [3x_3 - x_1]_+


s.t. x >= 0,
x_1 + 3x_2 > 4


Thanks,


Fan
Back to top
Robert B. Israel
science forum Guru


Joined: 24 Mar 2005
Posts: 2151

PostPosted: Wed Jul 12, 2006 8:47 pm    Post subject: Re: How to solve the linear objective function with max function, and linear constraints? Reply with quote

In article <1152644735.439243.76610@s13g2000cwa.googlegroups.com>,
Fan <fyanguw@gmail.com> wrote:
Quote:
Consider the following problem: a piece-wise linear objective function

with max function, and linear constraints.

Is this still a linear program? What solver can find the solution
quickly?

It is not a linear programming problem. In some cases
(minimizing a convex piecewise linear objective, or maximizing
a concave one) it can be written as one.

Quote:

E.g., x belongs to R_3. Define the max function [y]_+ = max {0,y}.


min [5x_1 - 4x_2]_+ + [3x_3 - x_1]_+


Since the max of linear functions is convex, this is OK. You can
write it as

min p_1 + p_2

s.t. p_1 >= 5 x_1 - 4 x_2
p_1 >= 0
p_2 >= 3 x_3 - x_1
p_2 >= 0
(and your other constraints)

Quote:

s.t. x >= 0,
x_1 + 3x_2 > 4

I hope you mean >=. Strict inequality constraints, when
they aren't redundant, mean there won't be any optimal solutions.

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
Back to top
C W
science forum addict


Joined: 25 May 2005
Posts: 64

PostPosted: Wed Jul 12, 2006 11:53 pm    Post subject: Re: How to solve the linear objective function with max function, and linear constraints? Reply with quote

Fan wrote:
Quote:

Consider the following problem: a piece-wise linear objective function

with max function, and linear constraints.

Is this still a linear program? What solver can find the solution
quickly?

E.g., x belongs to R_3. Define the max function [y]_+ = max {0,y}.

min [5x_1 - 4x_2]_+ + [3x_3 - x_1]_+

s.t. x >= 0,
x_1 + 3x_2 > 4


If the conmstraints read :

x_1>=0,x_2>0,x_3>=0,x_1 + 3x_2 >= 4

then min [5x_1 - 4x_2]_+ + [3x_3 - x_1]_+ = 0 at [x_1,x_2,x_3] = [16/19, 20/19,
0] is the minimum.

Quote:
Thanks,

Fan
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [3 Posts] View previous topic :: View next topic
The time now is Thu Dec 14, 2017 5:00 pm | All times are GMT
Forum index » Science and Technology » Math » num-analysis
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Linear operator and determinant aline Math 0 Wed Nov 29, 2006 2:37 am
No new posts Generating function for Mathieu functions cosmicstring@gmail.com Math 1 Fri Jul 21, 2006 8:39 am
No new posts Choice function over finite sets Peter Webb Math 5 Fri Jul 21, 2006 3:28 am
No new posts Function from Taylor series? Nathan Urban Research 1 Thu Jul 20, 2006 12:48 am
No new posts Function not in L_1 {[0,1]}, but satisfies ...? atkrunner@hotmail.com Math 12 Thu Jul 20, 2006 12:46 am

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0203s ][ Queries: 16 (0.0050s) ][ GZIP on - Debug on ]