Final Project of MATP6610/4820
(Due at mid-night of May-01-2020 to [email protected])
Instructions: Choose one of the three topics below. You should write a report by LaTex
to show how you derive your solver (include all gradient formulas if any gradient is used), all
results you obtain, and all observations you make. To earn full credit, you need make your
report well-written, include in your report all results required below each topic, and also,
you need make sure your code works in a right way and produce correct solutions. Please
pack your report and code in a single zip file. Do NOT zip the provided data file. Send a
pdf file of your report and the zip file to [email protected]. Your pdf and zip
files should both be named in the format “MATP4820 FinalProject FirstName LastName”
or “MATP6610 FinalProject FirstName LastName”, depending on if you are a 4820 or 6610
student. If you work with one another student, include the names of both students in the
name of your files.
Team work: You can work individually or with at most one other student. A 4820
student can only work with another 4820 student in a group, and a 6610 student can only
work with another 6610 student in a group.
Submission: Each group only needs to make one submission. If you work with another
student, write both names in the report, and explain how you collaborate and the contribu-
tion from each one. Both students in a group will get the same grade, but I want to know
each one’s contribution.
Bonus: if you do two topics, you can earn up to 40/number of group member percent
extra credit, and if you do all three topics, you can earn up to 50/number of group member
percent extra credit.
Topic I: Portfolio optimization
Assume that we have one unit of capital and n assets to invest on. The ith asset has an
expected return rate ξi ∈ R for each i. Our goal is to find a portfolio with the maximum
expected return such that the risk is controlled. This problem can be formulated as
max
x∈Rn
ξ>x, s.t.
n∑
i=1
xi ≤ 1, x>Qx ≤ α, xi ≥ 0, i = 1, . . . , n, (1)
1
where ξ = [ξ1, ξ2, . . . , ξn]
> denotes the vector of expected return rate, and Q is the covariance
matrix of the return.
Requirements
Include every item below and your code in a single report. Use the provided datasets to test
your code.
1. Develop a solver for (1) by the augmented Lagrangian method (ALM). You can put the
two inequality constraints
∑n
i=1 xi ≤ 1 and x>Qx ≤ α into the augmented Lagrangian
function, and then to solve the ALM subproblem, you need the projection onto the
nonnegativity constraint set {x ∈ Rn : xi ≥ 0, i = 1, . . . , n}. Alternatively, you can
just put the inequality constraint x>Qx ≤ α into the augmented Lagrangian function,
and then you will need the projection onto the set {x ∈ Rn : ∑ni=1 xi ≤ 1, xi ≥ 0, i =
1, . . . , n}. The latter projection is doable but not simple, so you will need first figure
out how to do the projection.
2. In either way described above, you will need an iterative method to solve the ALM
subproblem. Develop a subroutine for the ALM subproblems by the projected gradient
method or its accelerated version. Report the update you perform and the stopping
condition you adopt.
3. Write down the update of your ALM solver and also the stopping condition you use to
terminate your ALM solver.
4. Test your solver using the provided data set. Report the violation of the primal fea-
sibility, the dual feasibility, and the complementarity condition at all outer iterates.
You can tune the parameter α > 0 and report a few sets of results corresponding to
different α > 0.
Topic II: Robust principal component analysis
Let X be composed of a sparse matrix S and a low-rank matrix L. The robust PCA [2]
aims at finding S and L, given X. Using `1 norm to promote sparsity and nuclear norm to
promote low-rankness, robust PCA can be modeled as
min
L,S
‖L‖∗ + λ‖S‖1, s.t. L + S = X. (2)
Here, ‖L‖∗ denotes the nuclear norm of L and equals the summation of its singular values,
and ‖S‖1 =
∑
i,j |sij|, where sij denotes the (i, j)-th entry of S.
2
Requirements
Include every item below in a single report and attach your code. Use the provided datasets
to test your code.
1. Develop two solvers for (2): one is by the quadratic penalty method or the augmented
Lagrangian method (ALM), and another is by the alternating direction method of
multipliers (ADMM). [Do NOT do both quadratic penalty and ALM, just one
of them.]
2. For the quadratic penalty method or the ALM, you will need to approximately solve
subproblems in the form of
min
L,S
‖L‖∗ + λ‖S‖1 + β
2
‖L + S− Z‖2F , (3)
where β > 0 is the penalty parameter. In the above, Z = X for the quadratic penalty
method, and Z will include X and also the Lagrangian multiplier for the ALM. Develop
a subroutine by the proximal gradient method. Report how you do the proximal map-
ping of non-differentiable terms, the update you perform, and the stopping condition
you adopt. Refer to [1, Theorem 2.1] for the proximal mapping of the nuclear norm.
The paper is included in LMS for your convenience.
3. For the ADMM, you will update L and S separately. Formulate each subproblem
and report how you solve the subproblems (you should have a closed-form solution for
each subproblem). Give the iterative update of the ADMM and report the stopping
condition you use.
4. Compare the two solvers that you develop by using the provided synthetic data and
also Escalator video Dataset. Note that the video dataset is in 3D format. It contains
200 frames of size 130×160. You will need first reshape each frame into a column vector
and form a 20800 × 200 matrix X. Plot the objective value and constraint violation
at all iterates by the two solvers. For each solver, after you obtain the solution (L,S),
reshape each column of L and S into a 130× 160 image and use imshow to show a few
selected columns of L and S. You can also use implay to see how the foreground and
background of the video are separated. Report what you observe.
Topic III: Neyman-Pearson Classification
Given data points {(xi, yi)}Ni=1 with xi ∈ Rp and yi ∈ {+1,−1} for each i, let N+ = {i ∈
[N ] : yi = 1} and N− = {i ∈ [N ] : yi = −1} be the positive and negative sets of points
3
respectively. The Neyman-Pearson classification (NPC) [3] minimizes the false negative error
while controlling the level α > 0 of false positive error through solving the problem:
minimize
w,b
1
N+
∑
i∈N+
`(w, b; xi, yi), s.t.
1
N−
∑
i∈N−
`(w, b; xi, yi) ≤ α, (4)
where N+ and N− denote the cardinalities of N+ and N−, and ` is a certain error function.
For this project, we let ` be the error function used in logistic regression, i.e.,
`(w, b; xi, yi) = log
(
1 + exp
(− yi(w>xi + b))) . (5)
Requirements
1. Develop a solver for (4) with ` given in (5) by the augmented Lagrangian method
(ALM). Your solver should be able to accept (X,y, α) and also a few optional param-
eters (z0, tol,maxit) as the input. Here, X ∈ Rp×N and y ∈ RN with the i-th column
of X being the i-th data point, and z0 is the initial iterate.
2. In your report, explicitly formulate the subproblem that is solved within each outer
iteration and explain how you solve the subproblem, including the optimization method
you choose, the iterative update formula, and the stopping condition.
3. Report the stopping condition you use to terminate your ALM solver.
4. For the training data sets provided by the instructor, run your ALM solver. Save and
report (by figure or table) the violation of primal feasibility and also dual feasibility at
each outer iteration.
5. Based on the output solution, do the classification on the testing data and report the
false positive and false negative errors you obtain. You can tune the model parameter
α. You should report the errors and the corresponding value of α you use.
References
[1] J.-F. Cai, E. J. Cande`s, and Z. Shen. A singular value thresholding algorithm for matrix
completion. SIAM Journal on optimization, 20(4):1956–1982, 2010.
[2] E. J. Cande`s, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? Journal
of the ACM (JACM), 58(3):1–37, 2011.
[3] P. Rigollet and X. Tong. Neyman-pearson classification, convexity and stochastic con-
straints. Journal of Machine Learning Research, 12(Oct):2831–2855, 2011.
4