ISE 530 Optimization Methods for Analytics
Open-book, open-notes mid-term examination
Wednesday 08:00–09:30 PM October 23, 2019
Instructions. First read through all problems very carefully; you are responsible for solving the
problems as stated. You will receive no credit if you solve the wrong problems, even if you use the
correct approach. You will also receive no credit if you do not follow instructions or if there is no
work shown to support your answer.
Reminder and warning. You are reminded to do your own work and will neither seek nor offer
help from and to any one. You are further reminded that cheating is not tolerated and will receive
the maximum penalty. In particular, I do not expect to see papers with the slightest similarities.
1. Consider the univariate absolute-value regression problem:
minimize
z
| z − 1 |+ 2 | z + 1 |.
(a) Write this problem as a linear program in 2 variables (one nonnegative and the other free) and
4 constraints; call it formulation (A). Solve this formulation graphically.
(b) Write problem (A) in standard form: minimize
x
cTx subject to Ax = b and x ≥ 0 and call it
formulation (B). Clearly identify the variable x, the matrix A and vectors b and c in formulation
(B).
(c) Solve the linear program (B) by the simplex method and verify your solution with the one
obtained by the graphical method obtained in part (a). [Hint: with the correct formulation, you
can get an initial basic feasible solution by inspection and simple tableau manipulation; Phase I is
not needed.]
(d) Derive the dual program of formulation (A). Use complementary slackness on this pair of
programs to verify the optimal solution obtained in part (b).
2. Consider the linear program
minimize
x
2x1 − 3x2 + 2x3 + x4 − 2x5
subject to x1 − x2 + 2x3 + x4 = 2
−2x1 + 3x2 + 2x3 + 3x5 = −2
and x1, x2, x3, x4, x5 ≥ 0.
For the following parts, you will receive no credit if you form any simplex tableau. Parts (b) and
(c) are independent of each other
(a) It is conjectured that x1 and x2 are positive in an optimal solution of the problem. Prove this
conjecture by showing that it is a basic feasible solution and the reduced costs of the nonbasic
variables are all nonnegative.
(b) Suppose that all the coefficients in the objective function are increased by δ (which may be
negative). Find the range of δ within which the primal solution obtained in (c) remains
optimal.
(c) Suppose that the two right-hand constants in the constraints are changed by ±δ, respectively.
Find the range of δ within which the solution in (a) remains optimal.
3. Consider the trivariate function:
f(x, y, z) = ex−y + ey−x + ex
2+2x + x2 + z2 − 2xz − x+ z
Calculate the Hessian matrix ∇2f(x, y, z) and show that it is positive definite for all (x, y, z). Find
a minimizer of the function. Is the minimizer unique?
4. Starting at the point (1, 1), carry out one full iteration of the steepest descent method on the
function f(x1, x2) = x
3
1 − 6x1 x2 + 4x32 using the Armijo line search with backtracking factor
ρ = 0.8 and tilted factor σ = 0.8 to obtain the next iterate with a strictly smaller objective value.
Do the same using the Newton direction with line search and same parameters.
2

欢迎咨询51作业君