 Forum index » Science and Technology » Math » num-analysis
Author Message
Fan
science forum beginner

Joined: 31 Dec 2005
Posts: 7 Posted: Tue Jul 11, 2006 7:05 pm    Post subject: How to solve the linear objective function with max function, and linear constraints? 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 Robert B. Israel
science forum Guru

Joined: 24 Mar 2005
Posts: 2151 Posted: Wed Jul 12, 2006 8:47 pm    Post subject: Re: How to solve the linear objective function with max function, and linear constraints? 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 C W

Joined: 25 May 2005
Posts: 64 Posted: Wed Jul 12, 2006 11:53 pm    Post subject: Re: How to solve the linear objective function with max function, and linear constraints? 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  Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 The time now is Tue Mar 26, 2019 3:52 am | All times are GMT Forum index » Science and Technology » Math » num-analysis
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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