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.

   $\min_{x_1,x_2} x_1^2+x_2^2 -2 x_1x_2+x_1+x_2$

   subject to $(x_1-x_2)^2+ 4x_1x_2 + e^{x_2-x_1} \leq 0$, and $5x_1-7x_2=0$.

Linear program and standard form

2. Consider the following linear program:

   $\max \quad x_2-x_1$

   $\textrm{subject to:} \quad 2x_1 +x_2 \geq 3,\quad 3x_1-x_2 \leq 7,\quad x_1 \geq 0.$

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

Simplex method

3. Simulate the simplex method one step for the following LP (note that $(x_1,x_2,x_3)=(0,0,0)$ is feasible):

   $\max \quad x_1+4x_2+5x_3$

   $\text{subject to:}\quad x_1+2x_2+3x_3\leq 2, \quad 3x_1+x_2+2x_3\leq 2, \quad 2x_1+3x_2+x_3\leq 4, \quad x_1,x_2,x_3\geq 0$.

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

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

   $\max\quad 3x_1+x_2$

   $\text{subject to:} \quad x_1-x_2 \leq -1, \quad -x_1-x_2\leq -3, \quad 2x_1+x_2\leq 4, \quad x_1, x_2\geq 0$.

   The first step should be to find a feasible solution by simplex method, since $(x_1,x_2)=(0,0)$ 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.)

Duality

5. Write the dual to

   $\min\quad 5x_1 + 7x_2 + 9x_3 + 11x_4 + 13x_5$

   $\text{subject to:}\quad 15x_1 + 14x_2 + 45x_3 + 44x_4 + 13x_5 = 2022, \quad x_1, x_2, x_3, x_4, x_5 \geq 0$.

   and solve it by solving its dual.

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

   $\min\quad c^{\mathsf{T}} x$

   $\text{subject to:} \quad Ax = b$.