Scribd Logo
Upload

Welcome to Scribd!

  • 26 views

    Homework #2 Solutions

    Uploaded by

    Rajeshwar Singh
    The document summarizes the solutions to homework problems about convex sets and linear programming. It proves that a hyperplane, the intersection of two convex sets, and the intersection of any finite number of convex sets are convex. It also proves that the set of vectors satisfying a system of linear equations Ax=b is convex, and finds the extreme points and optimal solution for a linear program.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Homework #2 Solutions

    Uploaded by

    Rajeshwar Singh
    26 views2 pages
    The document summarizes the solutions to homework problems about convex sets and linear programming. It proves that a hyperplane, the intersection of two convex sets, and the intersection of any finite number of convex sets are convex. It also proves that the set of vectors satisfying a system of linear equations Ax=b is convex, and finds the extreme points and optimal solution for a linear program.

    Original Description:

    Maths

    Original Title

    354hw2soln

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document summarizes the solutions to homework problems about convex sets and linear programming. It proves that a hyperplane, the intersection of two convex sets, and the intersection of any finite number of convex sets are convex. It also proves that the set of vectors satisfying a system of linear equations Ax=b is convex, and finds the extreme points and optimal solution for a linear program.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    26 views2 pages

    Homework #2 Solutions

    Uploaded by

    Rajeshwar Singh
    The document summarizes the solutions to homework problems about convex sets and linear programming. It proves that a hyperplane, the intersection of two convex sets, and the intersection of any finite number of convex sets are convex. It also proves that the set of vectors satisfying a system of linear equations Ax=b is convex, and finds the extreme points and optimal solution for a linear program.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    Math 354 Summer 2004

    Homework #2 Solutions
    1 Sketch the set of feasible solutions to the following set of inequalities

    −x + y ≤ 2,
    2x + y ≤ 2,
    x ≥ 0,
    y ≤ 1.

    Answer: You all got it right, and besides, graphs are hard to draw.

    2 Prove that a hyperplane (defined on page 72, a hyperplane is a set of the form {x : aT x = b}
    for some vector a and real number b) is a convex set (defined on page 79).
    Proof: Let H be a hyperplane. We know that H is of the form {x : aT x = b} for some a and
    b. We want to show that H is convex, i.e., for any two points x1 and x2 in H and any point x
    on the line segment between x1 and x2 , we want to show that x also lies in H. Now take two
    points x1 and x2 in H and let x lie on the line segment between x1 and x2 . We know that
    x = λx1 + (1 − λ)x2 for some λ between 0 and 1. Now we just check the hyperplane condition
    for x:

    aT x = aT (λx1 + (1 − λ)x2 ) ,
    = λaT x1 + (1 − λ)aT x2 ,
    = λb + (1 − λ)b,
    = b,

    and this shows that x does indeed lie on the hyperplane, proving the claim.

    3 Prove that the intersection of two convex sets is a convex set.


    Proof: Let A and B be convex sets. We want to show that A ∩ B is also convex. Take
    x1 , x2 ∈ A ∩ B, and let x lie on the line segment between these two points. Then x ∈ A
    because A is convex, and similarly, x ∈ B because B is convex. Therefore x ∈ A ∩ B, as
    desired.

    4 Prove that the intersection of any finite number of convex sets is a convex set. Hint: this
    should follow from the previous problem; for example, to show that A1 ∩ A2 ∩ A3 is convex,
    write it as (A1 ∩ A2 ) ∩ A3 .
    Proof: Let A1 , A2 , . . . , An be convex sets. Then

    A1 ∩ A2 ∩ . . . ∩ An = (. . . ((A1 ∩ A2 ) ∩ A3 ) . . .) ∩ An ).

    By the previous problem, A1 ∩ A2 is convex, so ((A1 ∩ A2 ) ∩ A3 ) is also convex, etc.


    To write up a more formal proof, use induction.
    Math 354 Summer 2004
    5 Let A be an m × n matrix and let b be a vector in Rm . Prove that the set of vectors x in Rn
    satisfying Ax = b is a convex set. Hints: note that the empty set, ∅, is trivially a convex set
    (at least according to me; whether or not our book agrees on this is unclear), and try to use
    the previous three problems.
    Proof: First, sorry about the misleading hint. You can certainly do it that way, but the
    easier way is just to copy the proof from 2:
    Choose x1 and x2 that satisfy Ax1 = b and Ax2 = b. Let x lie on the line segment between
    x1 and x2 , we want to show that x also satisfies Ax = b. We know that x = λx1 + (1 − λ)x2
    for some λ between 0 and 1. Now we have

    Ax = A (λx1 + (1 − λ)x2 ) ,
    = λAx1 + (1 − λ)Ax2 ,
    = λb + (1 − λ)b,
    = b,

    and this shows that x also lies in this set, proving the claim.

    6 Find the extreme points of the set of feasible solutions for the following optimization problem
    and then find the optimal solution(s).

    Maximize z = 2x + 3y
    subject to
    3x + y ≤ 6,
    x + y ≤ 4,
    x + 2y ≤ 6,
    x ≥ 0,
    y ≥ 0.

    Answer: Once again, graphs are a pain, so I’ll skip that part. Here’s a table:

    extreme points z = 2x + 3y
    (0, 0) 0
    (0, 3) 9
    (2, 0) 4
    ( 65 , 12
    5
    ) 48
    5
    = 9.6

    So, the optimal solution is (6/5, 12/5).

    You might also like