Class notes
Introduction to Linear Optimization Solution Manual
- Course
- Institution
- Book
Complete Solutions Manual for Introduction to Linear Optimization by Dimitris Bertsimas & John N. Tsitsiklis
[Show more]
Connected book
Book Title:
Author(s):
- Edition:
- ISBN:
- Edition:
Seller
Follow
SolutionsWizard
Reviews received
Content preview
Solution Manual For:Introduction to Linear Optimization
by Dimitris Bertsimas & John N. Tsitsiklis
John L. Weatherwax∗
November 22, 2007
Introduction
Acknowledgements
Special thanks to Dave Monet for helping find and correct various typos in these solutions.
Chapter 1 (Introduction)
Exercise 1.1
Since f (·) is convex we have that
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) . (1)
Since f (·) is concave we also have that
f (λx + (1 − λ)y) ≥ λf (x) + (1 − λ)f (y) . (2)
Combining these two expressions we have that f must satisfy each with equality or
f (λx + (1 − λ)y) = λf (x) + (1 − λ)f (y) . (3)
This implies that f must be linear and the expression given in the book holds.
∗
wax@alum.mit.edu
1
,Exercise 1.2
Part (a): We are told that fi is convex so we have that
fi (λx + (1 − λ)y) ≤ λfi (x) + (1 − λ)fi (y) , (4)
for every i. For our function f (·) we have that
m
X
f (λx + (1 − λ)y) = fi (λx + (1 − λ)y) (5)
i=1
m
X
≤ λfi (x) + (1 − λ)fi (y) (6)
i=1
Xm m
X
= λ fi (x) + (1 − λ) fi (y) (7)
i=1 i=1
= λf (x) + (1 − λ)f (y) (8)
and thus f (·) is convex.
Part (b): The definition of a piecewise linear convex function fi is that is has a represen-
tation given by
fi (x) = Maxj=1,2,...,m (c′j x + dj ) . (9)
So our f (·) function is
n
X
f (x) = Maxj=1,2,...,m (c′j x + dj ) . (10)
i=1
Now for each of the fi (x) piecewise linear convex functions i ∈ 1, 2, 3, . . . , n we are adding
up in the definition of f (·) we will assume that function fi (x) has mi affine/linear functions
to maximize over. Now select a new set of affine values (c̃j , d˜j ) formed by summing elements
from each of the 1, 2, 3, . . . , n sets of coefficients from the individual fi . Each pair of (c̃j , d˜j )
is obtained by summing one of the (cj , dj ) pairs from each of the n sets. The number of
such coefficients can be determined as follows. We have m1 choices to make when selecting
(cj , dj ) from the first piecewise linear convex function, m2 choices for the second piecewise
linear convex function, and so on giving a total of m1 m2 m3 · · · mn total possible sums each
producing a single pair (c̃j , d˜j ). Thus we can see that f (·) can be written as
f (x) = Maxj=1,2,3,...,Qnl=1 ml c̃′j x + d˜j , (11)
since one of the (c̃j , d˜j ) will produce the global maximum. This shows that f (·) can be
written as a piecewise linear convex function.
Exercise 1.3 (minimizing a linear plus linear convex constraint)
We desire to convert the problem min(c′ x + f (x)) subject to the linear constraint Ax ≥ b,
with f (x) given as in the picture to the standard form for linear programming. The f (·)
, given in the picture can be represented as
−ξ + 1 ξ<1
f (ξ) = 0 1<ξ<2 (12)
2(ξ − 2) ξ > 2,
but it is better to recognize this f (·) as a piecewise linear convex function given by the
maximum of three individual linear functions as
f (ξ) = max (−ξ + 1, 0, 2ξ − 4) (13)
Defining z ≡ max (−ξ + 1, 0, 2ξ − 4) we see that or original problem of minimizing over the
term f (x) is equivalent to minimizing over z. This in tern is equivalent to requiring that z
be the smallest value that satisfies
z ≥ −ξ + 1 (14)
z ≥ 0 (15)
z ≥ 2ξ − 4 . (16)
With this definition, our original problem is equivalent to
Minimize (c′ x + z) (17)
subject to the following constraints
Ax ≥ b (18)
z ≥ −d′ x + 1 (19)
z ≥ 0 (20)
z ≥ 2d′ x + 4 (21)
where the variables to minimize over are (x, z). Converting to standard form we have the
problem
Minimize(c′ x + z) (22)
subject to
Ax ≥ b (23)
′
dx+z ≥ 1 (24)
z ≥ 0 (25)
′
−2d x + z ≥ 4 (26)
Exercise 1.4
Our problem is
Minimize(2x1 + 3|x2 − 10|) (27)
subject to
|x1 + 2| + |x2 | ≤ 5 . (28)
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller SolutionsWizard. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $8.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
78121 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now