Covers All 11 Chapters
SOLUTIONS MANUAL
, TABLE OF CONTENTS
Chapter 1: Introduction..................................................................................................... 1
1.1, 1.2, 1.4, 1.6, 1.10, 1.13
Chapter 2 Convex Sets ................................................................................................. 4
2.1, 2.2, 2.3, 2.7, 2.8, 2.12, 2.15, 2.21, 2.24, 2.31, 2.42, 2.45,
2.47, 2.49, 2.50, 2.51, 2.52, 2.53, 2.57
Chapter 3: Convex Functions and Generalizations ........................................................ 15
3.1, 3.2, 3.3, 3.4, 3.9, 3,10, 3.11, 3.16, 3.18, 3.21, 3.22, 3.26,
3.27, 3.28, 3.31, 3.37, 3.39, 3.40, 3.41, 3.45, 3.48, 3.51, 3.54,
3.56, 3.61, 3.62, 3.63, 3.64, 3.65
Chapter 4: The Fritz John and Karush-Kuhn-Tucker Optimality Conditions .. 29 4.1, 4.4,
4.5, 4.6, 4.7, 4.8, 4.9, 4.10, 4.12, 4.15, 4.27, 4.28, 4.30,
4.31, 4.33, 4.37, 4.41, 4.43
Chapter 5: Constraint Qualifications............................................................................... 46
5.1, 5.12, 5.13, 5.15, 5.20
Chapter 6: Lagrangian Duality and Saddle Point Optimality Conditions ......................... 51
6.2, 6.3, 6.4, 6.5, 6.7, 6.8, 6.9, 6.14, 6.15, 6.21, 6.23, 6.27, 6.29, Chapter 7:
The Concept of an Algorithm......................................................... 64
7.1, 7.2, 7.3, 7.6, 7.7, 7.19
Chapter 8: Unconstrained Optimization ......................................................................... 69
8.10, 8.11, 8.12, 8.18, 8.19, 8.21, 8.23, 8.27, 8.28, 8.32, 8.35,
8.41, 8.47, 8.51, 8.52
Chapter 9: Penalty and Barrier Functions ...................................................................... 88
9.2, 9.7, 9.8, 9.12, 9.13, 9.14, 9.16, 9.19, 9.32
Chapter 10: Methods of Feasible Directions .................................................................. 107
10.3, 10.4, 10.9, 1.012, 10.19, 10.20, 10.25, 10.33, 10.36, 10.41,
10.44, 10.47, 10.52
5
,Chapter 11: Linear Complementary Problem, and Quadratic, Separable, Fractional, and
Geometric Programing.............................................................................. 134
11.1, 11.5, 11.12, 11.18, 11.19, 11.22, 11.23, 11.24, 11.36, 11.41,
11.42, 11.47, 11.48, 11.50, 11.51, 11.52
6
, CHAPTER 1:
INTRODUCTION
1.1 In the figure below, min and max denote optimal solutions for Part (a)
and Part (b), respectively.x
x
2
x
2
(4, 2)
1
−3 −2 −3 0 2 3 4 x
1
2
xmax x
−2 min Feasible region
1.2 a. The total cost per time unit (day) is to be minimized given the storage
limitations, which yields the following model:
d1 Q2 d Q
Minimize f (Q , Q ) k h c +c d
1 k d
2
h
1 2 1Q 1 2 2 Q 2 2 1 1 2 2
subject to s 2 S 1 2
s1Q1 2 Q
Q 0, Q 0.
1 2
Note that the last two terms in the objective function are constant and thus
can be ignored while solving this problem.
b. Let S j denote the lost sales (in each cycle) of product j, j = 1, 2. In
thisQ case,
Q S we S replace
where the
F ( objective
, , , Sfunction
) = 1(in 1Part
, ) +(a) 2with
( , S ),
F ( 1 , 2 , 1 , 2 ), Q1 Q 2 S 1 2 F Q S1 F Q2 2
and where
dj j
Q2
F (Q , S ) (k + c Q − PQ , j
+ S ) 1, 2.
h
j j j Q S j j j j j j j 2(Q + S )
j j j j
, Q S
j j
This follows since the cycle time is , and so over some T
dj
Td j
days, the number of cycles is
. Moreover, for each cycle, the
Qj Sj
fixed setup cost is k j , the variable production cost is c j Qj , the lost
sales cost is j S j , the profit (negative cost) is PQj , and the
hj Qj
inventory carrying cost is Q ( ) . This yields the above total cost
2 j d
j
function on a daily basis.
1.4 Notation: x j : production in period j, j = 1,…,n
d j : demand in period j, j = 1,…,n
I j : inventory at the end of period j, j = 0, 1,…,n.
The production scheduling problem is to:
n
Minimize [ f (x j ) cI j 1 ] j 1
subject to xj d j I j 1 I j
for j = 1,…,n
Ij K for j = 1,…,n–1
In 0
x j 0, I j 0 for j = 1,…,n–1.
1.6 Let X denote the set of feasible portfolios. The task is to find an x X
such that there does not exist an x X for which c t x c t x and
t t , with at least one inequality strict. One way to find
x Vx x Vx
efficient portfolios is to solve:
c t x xt x x X
Maximize { 1 V : }
such
2 that
1 2 1.
for different values of ( 1, 2) 0
1.10 Let x and p denote the demand and production levels, respectively, and let
Z denote a standard normal random variable. Then we need p to be such
that P( p x 5) 0.01, which by the continuity of the normal random
variable is equivalent to P(x p 5) 0.01. Therefore, p must satisfy
2
, P(Z p 5 150
) 0.01,
7
where Z is a standard normal random variable. From tables of the standard
normal distribution we have P(Z 2.3267) 0.01. Thus, we want
p 145
2.3267, or that the chance constraint is equivalent to
7
p 161.2869.
1.13 We need to find a positive number K that minimizes the expected total
cost. The expected total cost is (1 p)P(x K 2)
Therefore, the mathematical programming problem
pP(x K
1).
can be formulated as follows:
K
Minimize (1 p) f (x 2 )dx p f (x
1)dx
0 0
subject to K 0.
are
If the conditional distribution functions F(x 2 ) and F(x )
1
known, then the objective function is simply (1 p)F(K 2 )
p(1 F(K )).
1
3
, CHAPTER 2:
CONVEX SETS
2.1 Let x conv( 1 S2 ) . Then there exists [0,1] and 1, S
such that x S (1 ) . Since and are both in , x xmustx 2be 1S 2
1 2 1 2 1
x x must
in conv( 1 ) . Similarly, bex in conv(S2x ) . Therefore,
x x conv( 1S )
conv(S2 )S. (Alternatively, since 1 conv( 1 ) and 2 S conv(S S
2 ) , we
have S S that
or
1 S2 conv( 1 ) conv(S2 ) conv[ 1 S2 ]
S S S
conv(S ) conv(S ) .)
1
2
An example in which conv( 1 S2 ) conv( 1) conv(S2 ) is given
S S
below:
S1
S2
Here, conv( 1 S2 ) , while conv( 1 ) conv(S2 ) 1 in this case.
S S S
2.2 Let S be of the form S {x : Ax b} in general, where the constraints
might include bound restrictions. Since S is a polytope, it is bounded by
definition. To show that it is convex, let y and z be any points in S, and let
x y (1 )z , for 0 1 . Then we have Ay b and Az b ,
which implies that
Ax Ay (1 ) Az b (1 )b b , or that x S .
Hence, S is convex.
Finally, to show that S is closed, consider any sequence { n } x such
x
that xn S , n . Then we have A n b , n , or by taking limits as
x
n , we get Ax b , i.e., x S as well. Thus S is closed.
2.3 Consider the closed set S shown below along with conv(S) , where
conv(S ) is not closed:
4
, Now, suppose that S p is closed. Toward this end, consider any
sequence {xn} x , where xn conv(S) , n . We must show that
x conv(S). Since xn conv(S) , by definition (using Theorem 2.1.6),
xr S
x p1 xr for
we have that we can write , where
n nr n n
r1
r 1,..., p 1, n , and where p1 1, n , with 0, r, n .
nr
nr
r1
Since the -values as well as thexr -points belong to compact sets,
nr n
K
, r 1,..., p 1 ,
there exists a subsequence K such that { nr } r
and {xr } xr , r 1,..., p 1 . From above, we have taking limits as
n
n , n K , that
p1r p1 1, 0 , r 1,..., p 1 ,
x x , with
r r r
r1 r1
where x r S , r 1,..., p 1 since S is closed. Thus by definition,
x conv(S ) and so conv(S ) is closed.
2.7 a. Let y1 and y2 belong to AS. Thus, y1 Ax1 for some x1 S and
y2 = Ax2 for some x2 S . Consider y y1 (1 ) y2 , for any
0 1. Then y A[ x1 (1 )x 2 ]. Thus, letting
1 2 since S is convex and that
x x (1 )x , we have that x S
y Ax . Thus y AS , and so, AS is convex.
b. If 0 , then S {0}, which is a convex set. Hence, suppose that
0 . Let x1 and x2 S , where x1 S and x2 S . Consider
x x1 (1 ) x2 for any 0 1. Then, x [ x1
(1 )x 2 ] . Since 0 , we have that x x1 (1 )x 2 , or that
x S since S is convex. Hence x S for any 0 1, and
thus S is a convex set.
2.8 S {( 1, ):0 1, 2 3}.
S1 2 x x2 x1 x2
5
, − Sx S x x x
{( 1, 2 ) : 1 0, 2 1}.
1 2 1 2
2.12 Let S 1S S2 . Consider any y, z S , and any (0,1) such that
y y and z z + z , with {y , z } S and {y , z } S .
y 1 2 1 1 1 2 2 2
Then 1 y (12 )z 1 y2 (1 ) 1 (1 )z 2 . Since both sets
y z S , i = 1, 2. Therefore,
S and S are convex, we have y (1 )z
1 2 i i i
y (1 )z is still a sum of a vector from 1 S and a vector from S2 ,
and so it is in S. Thus S is a convex set.
Consider the following example, where 1 and S2 are closed, and convex.
S
S S2
1
sequence {y } sequence {z n}
n
Let n
z , for the sequences {yn } and {zn} shown in the figure,
x {y y}n n
where n 1 , and {zn } S2 . Then { n } 0 where n S , n,
S x x
but 0 S . Thus S is not closed.
Next, we show that if 1 Sis compact and S2 is closed, then S is closed.
Consider a convergent sequence { n } xof points from S, and let x denote its
x y z , where for each n, y S and
limit. By definition, n n n n 1
zn S2 . Since { yn} is a sequence of points from a compact set, it must be
bounded, and hence it has a convergent subsequence. For notational
simplicity and without loss of generality, assume that the sequence {y n}
itself is convergent, and let y denote its limit. Hence, S This result y 1.
taken together with the convergence of the sequence { n} x implies that
{zn} is convergent to z, say. The limit, z, of {zn} must be in S2 , since S2
is a closed set. Thus, x y z , where y S1 and z S2 , and therefore,
x S . This completes the proof.
6
, THOSE WERE PREVIEW PAGES
TO DOWNLOAD THE FULL PDF
CLICK ON THE L.I.N.K
ON THE NEXT PAGE
SOLUTIONS MANUAL
, TABLE OF CONTENTS
Chapter 1: Introduction..................................................................................................... 1
1.1, 1.2, 1.4, 1.6, 1.10, 1.13
Chapter 2 Convex Sets ................................................................................................. 4
2.1, 2.2, 2.3, 2.7, 2.8, 2.12, 2.15, 2.21, 2.24, 2.31, 2.42, 2.45,
2.47, 2.49, 2.50, 2.51, 2.52, 2.53, 2.57
Chapter 3: Convex Functions and Generalizations ........................................................ 15
3.1, 3.2, 3.3, 3.4, 3.9, 3,10, 3.11, 3.16, 3.18, 3.21, 3.22, 3.26,
3.27, 3.28, 3.31, 3.37, 3.39, 3.40, 3.41, 3.45, 3.48, 3.51, 3.54,
3.56, 3.61, 3.62, 3.63, 3.64, 3.65
Chapter 4: The Fritz John and Karush-Kuhn-Tucker Optimality Conditions .. 29 4.1, 4.4,
4.5, 4.6, 4.7, 4.8, 4.9, 4.10, 4.12, 4.15, 4.27, 4.28, 4.30,
4.31, 4.33, 4.37, 4.41, 4.43
Chapter 5: Constraint Qualifications............................................................................... 46
5.1, 5.12, 5.13, 5.15, 5.20
Chapter 6: Lagrangian Duality and Saddle Point Optimality Conditions ......................... 51
6.2, 6.3, 6.4, 6.5, 6.7, 6.8, 6.9, 6.14, 6.15, 6.21, 6.23, 6.27, 6.29, Chapter 7:
The Concept of an Algorithm......................................................... 64
7.1, 7.2, 7.3, 7.6, 7.7, 7.19
Chapter 8: Unconstrained Optimization ......................................................................... 69
8.10, 8.11, 8.12, 8.18, 8.19, 8.21, 8.23, 8.27, 8.28, 8.32, 8.35,
8.41, 8.47, 8.51, 8.52
Chapter 9: Penalty and Barrier Functions ...................................................................... 88
9.2, 9.7, 9.8, 9.12, 9.13, 9.14, 9.16, 9.19, 9.32
Chapter 10: Methods of Feasible Directions .................................................................. 107
10.3, 10.4, 10.9, 1.012, 10.19, 10.20, 10.25, 10.33, 10.36, 10.41,
10.44, 10.47, 10.52
5
,Chapter 11: Linear Complementary Problem, and Quadratic, Separable, Fractional, and
Geometric Programing.............................................................................. 134
11.1, 11.5, 11.12, 11.18, 11.19, 11.22, 11.23, 11.24, 11.36, 11.41,
11.42, 11.47, 11.48, 11.50, 11.51, 11.52
6
, CHAPTER 1:
INTRODUCTION
1.1 In the figure below, min and max denote optimal solutions for Part (a)
and Part (b), respectively.x
x
2
x
2
(4, 2)
1
−3 −2 −3 0 2 3 4 x
1
2
xmax x
−2 min Feasible region
1.2 a. The total cost per time unit (day) is to be minimized given the storage
limitations, which yields the following model:
d1 Q2 d Q
Minimize f (Q , Q ) k h c +c d
1 k d
2
h
1 2 1Q 1 2 2 Q 2 2 1 1 2 2
subject to s 2 S 1 2
s1Q1 2 Q
Q 0, Q 0.
1 2
Note that the last two terms in the objective function are constant and thus
can be ignored while solving this problem.
b. Let S j denote the lost sales (in each cycle) of product j, j = 1, 2. In
thisQ case,
Q S we S replace
where the
F ( objective
, , , Sfunction
) = 1(in 1Part
, ) +(a) 2with
( , S ),
F ( 1 , 2 , 1 , 2 ), Q1 Q 2 S 1 2 F Q S1 F Q2 2
and where
dj j
Q2
F (Q , S ) (k + c Q − PQ , j
+ S ) 1, 2.
h
j j j Q S j j j j j j j 2(Q + S )
j j j j
, Q S
j j
This follows since the cycle time is , and so over some T
dj
Td j
days, the number of cycles is
. Moreover, for each cycle, the
Qj Sj
fixed setup cost is k j , the variable production cost is c j Qj , the lost
sales cost is j S j , the profit (negative cost) is PQj , and the
hj Qj
inventory carrying cost is Q ( ) . This yields the above total cost
2 j d
j
function on a daily basis.
1.4 Notation: x j : production in period j, j = 1,…,n
d j : demand in period j, j = 1,…,n
I j : inventory at the end of period j, j = 0, 1,…,n.
The production scheduling problem is to:
n
Minimize [ f (x j ) cI j 1 ] j 1
subject to xj d j I j 1 I j
for j = 1,…,n
Ij K for j = 1,…,n–1
In 0
x j 0, I j 0 for j = 1,…,n–1.
1.6 Let X denote the set of feasible portfolios. The task is to find an x X
such that there does not exist an x X for which c t x c t x and
t t , with at least one inequality strict. One way to find
x Vx x Vx
efficient portfolios is to solve:
c t x xt x x X
Maximize { 1 V : }
such
2 that
1 2 1.
for different values of ( 1, 2) 0
1.10 Let x and p denote the demand and production levels, respectively, and let
Z denote a standard normal random variable. Then we need p to be such
that P( p x 5) 0.01, which by the continuity of the normal random
variable is equivalent to P(x p 5) 0.01. Therefore, p must satisfy
2
, P(Z p 5 150
) 0.01,
7
where Z is a standard normal random variable. From tables of the standard
normal distribution we have P(Z 2.3267) 0.01. Thus, we want
p 145
2.3267, or that the chance constraint is equivalent to
7
p 161.2869.
1.13 We need to find a positive number K that minimizes the expected total
cost. The expected total cost is (1 p)P(x K 2)
Therefore, the mathematical programming problem
pP(x K
1).
can be formulated as follows:
K
Minimize (1 p) f (x 2 )dx p f (x
1)dx
0 0
subject to K 0.
are
If the conditional distribution functions F(x 2 ) and F(x )
1
known, then the objective function is simply (1 p)F(K 2 )
p(1 F(K )).
1
3
, CHAPTER 2:
CONVEX SETS
2.1 Let x conv( 1 S2 ) . Then there exists [0,1] and 1, S
such that x S (1 ) . Since and are both in , x xmustx 2be 1S 2
1 2 1 2 1
x x must
in conv( 1 ) . Similarly, bex in conv(S2x ) . Therefore,
x x conv( 1S )
conv(S2 )S. (Alternatively, since 1 conv( 1 ) and 2 S conv(S S
2 ) , we
have S S that
or
1 S2 conv( 1 ) conv(S2 ) conv[ 1 S2 ]
S S S
conv(S ) conv(S ) .)
1
2
An example in which conv( 1 S2 ) conv( 1) conv(S2 ) is given
S S
below:
S1
S2
Here, conv( 1 S2 ) , while conv( 1 ) conv(S2 ) 1 in this case.
S S S
2.2 Let S be of the form S {x : Ax b} in general, where the constraints
might include bound restrictions. Since S is a polytope, it is bounded by
definition. To show that it is convex, let y and z be any points in S, and let
x y (1 )z , for 0 1 . Then we have Ay b and Az b ,
which implies that
Ax Ay (1 ) Az b (1 )b b , or that x S .
Hence, S is convex.
Finally, to show that S is closed, consider any sequence { n } x such
x
that xn S , n . Then we have A n b , n , or by taking limits as
x
n , we get Ax b , i.e., x S as well. Thus S is closed.
2.3 Consider the closed set S shown below along with conv(S) , where
conv(S ) is not closed:
4
, Now, suppose that S p is closed. Toward this end, consider any
sequence {xn} x , where xn conv(S) , n . We must show that
x conv(S). Since xn conv(S) , by definition (using Theorem 2.1.6),
xr S
x p1 xr for
we have that we can write , where
n nr n n
r1
r 1,..., p 1, n , and where p1 1, n , with 0, r, n .
nr
nr
r1
Since the -values as well as thexr -points belong to compact sets,
nr n
K
, r 1,..., p 1 ,
there exists a subsequence K such that { nr } r
and {xr } xr , r 1,..., p 1 . From above, we have taking limits as
n
n , n K , that
p1r p1 1, 0 , r 1,..., p 1 ,
x x , with
r r r
r1 r1
where x r S , r 1,..., p 1 since S is closed. Thus by definition,
x conv(S ) and so conv(S ) is closed.
2.7 a. Let y1 and y2 belong to AS. Thus, y1 Ax1 for some x1 S and
y2 = Ax2 for some x2 S . Consider y y1 (1 ) y2 , for any
0 1. Then y A[ x1 (1 )x 2 ]. Thus, letting
1 2 since S is convex and that
x x (1 )x , we have that x S
y Ax . Thus y AS , and so, AS is convex.
b. If 0 , then S {0}, which is a convex set. Hence, suppose that
0 . Let x1 and x2 S , where x1 S and x2 S . Consider
x x1 (1 ) x2 for any 0 1. Then, x [ x1
(1 )x 2 ] . Since 0 , we have that x x1 (1 )x 2 , or that
x S since S is convex. Hence x S for any 0 1, and
thus S is a convex set.
2.8 S {( 1, ):0 1, 2 3}.
S1 2 x x2 x1 x2
5
, − Sx S x x x
{( 1, 2 ) : 1 0, 2 1}.
1 2 1 2
2.12 Let S 1S S2 . Consider any y, z S , and any (0,1) such that
y y and z z + z , with {y , z } S and {y , z } S .
y 1 2 1 1 1 2 2 2
Then 1 y (12 )z 1 y2 (1 ) 1 (1 )z 2 . Since both sets
y z S , i = 1, 2. Therefore,
S and S are convex, we have y (1 )z
1 2 i i i
y (1 )z is still a sum of a vector from 1 S and a vector from S2 ,
and so it is in S. Thus S is a convex set.
Consider the following example, where 1 and S2 are closed, and convex.
S
S S2
1
sequence {y } sequence {z n}
n
Let n
z , for the sequences {yn } and {zn} shown in the figure,
x {y y}n n
where n 1 , and {zn } S2 . Then { n } 0 where n S , n,
S x x
but 0 S . Thus S is not closed.
Next, we show that if 1 Sis compact and S2 is closed, then S is closed.
Consider a convergent sequence { n } xof points from S, and let x denote its
x y z , where for each n, y S and
limit. By definition, n n n n 1
zn S2 . Since { yn} is a sequence of points from a compact set, it must be
bounded, and hence it has a convergent subsequence. For notational
simplicity and without loss of generality, assume that the sequence {y n}
itself is convergent, and let y denote its limit. Hence, S This result y 1.
taken together with the convergence of the sequence { n} x implies that
{zn} is convergent to z, say. The limit, z, of {zn} must be in S2 , since S2
is a closed set. Thus, x y z , where y S1 and z S2 , and therefore,
x S . This completes the proof.
6
, THOSE WERE PREVIEW PAGES
TO DOWNLOAD THE FULL PDF
CLICK ON THE L.I.N.K
ON THE NEXT PAGE
