[SOLVED] Si152 homework 1 to 4 solutions

Problem i. Write the gradient and Heissan matrix of the following formula. [10pts]
x
TAx + b
Tx + c (A ∈ Rn∗n
, b ∈ Rn
, c ∈ R)Problem ii. Write the gradient and Heissan matrix of the following formula. [10pts]
∥Ax − b∥
2
2
(A ∈ Rm∗n
, b ∈ Rm)Problem iii. Convert the following problem to linear programming. [10pts]
min
x∈Rn
∥Ax − b∥1 + ∥x∥∞ (A ∈ Rm∗n
, b ∈ Rm)Problem vi. Proof the convergence rates of the following point sequences. [30pts]
x
k =
1
k
x
k =
1
k!
x
k =
1
2
2
k
(Hint: Given two iterates x
k+1 and x
k
, and its limit point x
∗
, there exists real number q > 0,
satisfies
lim
k→∞x
k+1 − x
∗∥xk − x∗∥
= q
if 0 < q < 1, then the point sequence Q-linear convergence; if q = 1, then the point sequence
Q-sublinear convergence; if q = 0, then the point sequence Q-superlinear convergence)Problem v. Select the Haverly Pool Problem or the Horse Racing Problem in the courseware, compile the program using AMPL model language and submit it to https://neos-server.
org/neos/solvers/index.html.(Hint: both AMPL solver and NEOS solver can be used,
please indicate the type of solver used in the submitted job, show the solution results (eg:
screenshots attached to the PDF file), and submit the source code together with the submitted job, please package as .zip file, including your PDF and source code.) [40pts]Convert the following problem to a linear program in standard form. [20pts]
max
x∈R4
2×1 − x3 + x4
s.t. x1 + x2 ≥ 5
x1 − x3 ≤ 2
4×2 + 3×3 − x4 ≤ 10
x1 ≥ 0
(1)Use the two-phase simplex procedure to solve the following problem. [40pts]
min
x∈R4
− 3×1 + x2 + 3×3 − x4
s.t. x1 + 2×2 − x3 + x4 = 0
2×1 − 2×2 + 3×3 + 3×4 = 9
x1 − x2 + 2×3 − x4 = 6
x1, x2, x3, x4 ≥ 0
(2)3.1 Q1
Prove that the extreme points of the following two sets are in one-to-one correspondence. [20pts]
S1 = {x ∈ R
n
: Ax ≤ b, x ≥ 0}
S2 = {(x, y) ∈ R
n × R
m : Ax + y = b, x ≥ 0, y ≥ 0}
(3)
, where A ∈ R
m×n, b ∈ R
m.
1
3.2 Q2
Does the set P = {x ∈ R
2
: 0 ≤ x1 ≤ 1} have extreme points? What is its standard form? Does it have extreme
points in its standard form? If so, give a extreme point and explain why it is a extreme point. [20pts]Problem 1. Prove the dual of the dual of a linear programming (standard form) is itself.[25pts]Problem 2. Prove the dual objective increases after a pivot of the dual simplex method.[25pts]Problem 3. Let L(x,λ) be the Lagrangian of a linear programming problem, and (x
∗
,λ
∗
) be the optimal primaldual solution. Prove that
L(x,λ
∗
) ≥ L(x
∗
,λ
∗
) ≥ L(x
∗
,λ),
for any primal feasible x and dual feasible λ.[25pts]Problem 4. Construct a linear programming problem for which both the primal and the dual problem has no feasible
solution.[25pts]Problem 1. f is a positive definite quadratic function
f(x) = 1
2
x
TAx + b
Tx, A ∈ S
n
++, b ∈ R
n
,
x
k
is the current iteration point, d
k
is the descent direction. Derive the step size of exact linear search [20pts]
α
k = arg min
α>0
f(x
k + αdk
).Problem 2. Prove that f : R
n → R is affine if and only if f is both convex and concave. [20pts]Problem 3. Solve the optimal solution of the Rosenbrock function
f(x, y) = (1 − x)
2 + 100(y − x
2
)
2
,
using MATLAB programming to implement three algorithms (each 20pts): gradient descent (GD) method, Newton’s
method, and Quasi-Newton methods (either rank-1, DFP or BFGS).You are required to print iteration information of
last 10 steps: including objective, step size, residual of gradient. Technical implementation: explain how to choose
the step size, how to set the termination criteria, how to choose the initial point, the value of the required parameters,
converge or not and convergence rate. (paste the code in the pdf to submit it, no need to submit the source code)
[60pts]