Consider the following primal LP problem.

Question

Consider the following primal LP problem.

Max 𝑍=2𝑥1+5𝑥2+7𝑥3 s.t. 𝑥1+2𝑥2=6,and 𝑥1≥0, 𝑥2≥0,𝑥3≥0.
(a) Graph the feasible region. [4]
(b) Find the gradient of the objective function, and then find the projected gradient onto the feasible region. [6]
(c) Starting from the initial trial solution (𝑥1,𝑥2, 𝑥3)=(1,1,1), perform two iterations of the interior-point algorithm. [20]

Answer 1

(a) To graph the feasible region, we need to plot the constraints 𝑥1+2𝑥2=6, 𝑥1≥0, 𝑥2≥0, and 𝑥3≥0.

First, let's solve the equation 𝑥1+2𝑥2=6 for 𝑥2:

𝑥1 + 2𝑥2 = 6
2𝑥2 = 6 - 𝑥1
𝑥2 = (6 - 𝑥1)/2

Now we can draw the graph.

For 𝑥1 = 0, 𝑥2 = (6 - 0)/2 = 3.
For 𝑥2 = 0, 𝑥1 = 6 - 0 = 6.

So we have the points (0, 3), (6, 0), and the origin (0, 0).

Finally, we draw a line passing through these points.

```
|
| /
| /
| /
| /
|/
------------------
0 3 6
```

(b) The gradient of the objective function is the vector of coefficients of the decision variables, which is (2, 5, 7).

To find the projected gradient onto the feasible region, we need to calculate the normal vector to the feasible region's boundary at the current trial solution (𝑥1,𝑥2)=(1,1).

From the constraint 𝑥1+2𝑥2=6, we can rewrite it as 𝑥2=(6-𝑥1)/2. Taking the derivative of 𝑥2 with respect to 𝑥1, we get 𝑑𝑥2/𝑑𝑥1= -1/2.

Therefore, the normal vector to the feasible region's boundary is (1, -1/2).

(c) To perform two iterations of the interior-point algorithm, we need to update the trial solution based on the Newton direction and update the barrier parameter (μ).

Step 1: Initialize the trial solution and barrier parameter.
𝑥1 = 1, 𝑥2 = 1, 𝑥3 = 1, μ = 1

Iteration 1:
Step 2: Calculate the gradient and Hessian matrix.
The gradient of the objective function is (2, 5, 7).

𝐻essian matrix:
[0 0 0]
[0 0 0]
[0 0 0]

Step 3: Calculate the Newton direction.
Direction = -𝐻essian^-1 * gradient = (0, 0, 0)

Step 4: Determine the step size (α).
Since the direction is zero, α is calculated as infinity.

Step 5: Update the trial solution.
𝑥1 = 𝑥1 + α * Direction = 1 + ∞ * 0 = 1
𝑥2 = 𝑥2 + α * Direction = 1 + ∞ * 0 = 1
𝑥3 = 𝑥3 + α * Direction = 1 + ∞ * 0 = 1

Step 6: Update the barrier parameter.
μ = μ/10 = 1/10 = 0.1

Iteration 2:
Step 2: Calculate the gradient and Hessian matrix.
The gradient of the objective function is (2, 5, 7).

𝐻essian matrix:
[0 0 0]
[0 0 0]
[0 0 0]

Step 3: Calculate the Newton direction.
Direction = -𝐻essian^-1 * gradient = (0, 0, 0)

Step 4: Determine the step size (α).
Since the direction is zero, α is calculated as infinity.

Step 5: Update the trial solution.
𝑥1 = 𝑥1 + α * Direction = 1 + ∞ * 0 = 1
𝑥2 = 𝑥2 + α * Direction = 1 + ∞ * 0 = 1
𝑥3 = 𝑥3 + α * Direction = 1 + ∞ * 0 = 1

Step 6: Update the barrier parameter.
μ = μ/10 = 0.1/10 = 0.01

After two iterations of the interior-point algorithm, the trial solution remains unchanged at (𝑥1,𝑥2,𝑥3)=(1,1,1), and the barrier parameter μ is updated to 0.01.

Answer 2

(a) To graph the feasible region, we need to plot the constraints of the linear programming problem.

The first constraint is 𝑥1 + 2𝑥2 = 6. We can rewrite this equation in terms of 𝑥1:
𝑥1 = 6 - 2𝑥2

Next, we plot the region where 𝑥1 ≥ 0, 𝑥2 ≥ 0, and 𝑥3 ≥ 0. Since 𝑥3 is not present in any constraint, it can take any non-negative value. Therefore, we don't need to plot it on the graph.

To graph the feasible region, we can use a coordinate system with 𝑥1 on the x-axis and 𝑥2 on the y-axis.

1. Start by plotting the line 𝑥1 + 2𝑥2 = 6. To do this, find two points that satisfy the equation. For example, when 𝑥2 = 0, 𝑥1 = 6, and when 𝑥2 = 3, 𝑥1 = 0. Plot these two points and draw a straight line connecting them.

2. Next, shade the region below the line since 𝑥1 + 2𝑥2 is less than or equal to 6.

3. Finally, shade the region to the right of the y-axis since 𝑥1 is greater than or equal to 0.

The shaded region represents the feasible region for this linear programming problem.

(b) To find the gradient of the objective function, we will take the partial derivatives with respect to 𝑥1, 𝑥2, and 𝑥3.

∇𝑍 = (∂𝑍/∂𝑥1, ∂𝑍/∂𝑥2, ∂𝑍/∂𝑥3)
= (2, 5, 7)

The projected gradient onto the feasible region is the projection of ∇𝑍 onto the tangent space of the feasible region at the current point.

(c) To perform two iterations of the interior-point algorithm starting from the initial trial solution (𝑥1, 𝑥2, 𝑥3) = (1, 1, 1), we'll update the trial solution and iterate twice using the interior-point algorithm.

Iteration 1:
1. Compute the Newton step, which is the solution to the linear system (∇²𝑍 + 𝑍𝑅)𝑆 = -∇𝑍, where ∇²𝑍 is the Hessian matrix of second partial derivatives and 𝑅 is a diagonal matrix with 𝑅_𝑖𝑖 = 𝑥_𝑖/𝑠_𝑖.

2. Update the trial solution using the Newton step: (𝑥1, 𝑥2, 𝑥3) = (𝑥1, 𝑥2, 𝑥3) + 𝑆.

3. Go to step 1 until convergence.

Repeat the above steps for Iteration 2.