Homework 5

Due: Nov. 11, 22:00:00

Optimization problems

  1. Determine whether the following optimization problem is a convex optimization or not. Give your reasons.

    subject to , and .

Linear program and standard form

  1. Consider the following linear program:

    • Sketch the feasible set.
    • Solve it by geometric method.

Simplex method

  1. Simulate the simplex method one step for the following LP (note that is feasible):


    You only need to simulate one step, namely, choose some to increase and then shift the coordinates.

  2. We would like to use two-phase simplex method to solve the following linear program.


    The first step should be to find a feasible solution by simplex method, since is not feasible. What linear program should we solve at the first step (in order to find a feasible solution)?

    (You only need to write the linear program. No need to solve it.)


  1. Write the dual to


    and solve it by solving its dual.

  2. What is the dual to the following form of linear program?