Matrix Programming: Basic Theory, Algorithms, and Applications
Variational Analysis and Complementarity System
Matrix Analysis and Computations
Computational Finance: Financial Optimization
Risk Management: Correlation stress test
Teaching
2013/2014, Semester II, MA4254 Discrete Optimization,
19:00--20:00pm, LT22.
Recruitments
PhD Students: I am particularly interested in students who have
solid mathematical foundation and are willing to work hard on challenging problems in
optimization and beyond. Any exceptional student with/without TOEFL/GRE scores will
be considered. Drop me an email to check if
I am qualified to be your supervisor.
For information about my optimization colleagues working at math dept, please visit their websites here
Pang Chin How, Jeffrey ,
Kim Chuan TOH and
Gongyun ZHAO .
Codes for nearest (covariance) correlation matrix problems
CorrelationMatrixNewton.m Computing the
Nearest Correlation Matrix (uploaded in August 2006; last updated on Janaury 22, 2014).
This code should be good enough for most users. However, if you
really need a faster code, you need to download mexeig.m
(for win64 operating system) and if use win32 or Linux system, you need to download
the installmex file installmex.m and the c-file
mexedig.c by running the installmex.m first. For a random 10,000 by 10,000 pseudo correlation matrix,
the faster code needs 15 minutes to reach a solution with the relative duality gap less
than 1.0e-4 after 4 iterations and 24 minutes with the relative duality gap less than 1.0e-12 after 7
iterations
in my Dell Desktop
with Intel (R) Core i7 processor. For practioners, you may set the stopping criterion (relative
duality gap) to stay between 1.0e-1 and 1.0e-3.
. If you need a C/C++ code, download main.c and
main.h, which were written by
Pawel Zaczkowski
under
a summer research project. If you are a client to
The Numerical Algorithms Group(NAG), you may also enjoy their commercialized implementation.
(Updated on January 25, 2014).
CorNewton3.m Computing the
Nearest Correlation Matrix with fixed diagonal and off diagonal elements
(uploaded on September 14, 2009).
CorNewton3_Wnorm.m Computing the
W-norm Nearest Correlation Matrix with fixed diagonal and off diagonal elements
Testing example: testCorMatWnorm.m
(uploaded on September 14, 2009).
CorMatHdm.m Calibrating the
H-weighted Nearest Correlation Matrix
Testing example: testCorMatHdm.m
(uploaded in June 2008; last updated on September 10, 2009)
CorMatHdm_general.m Computing the
H-weighted Nearest Correlation Matrix with fixed elements and lower and upper bounds
[H should not have too many zero elements for better numerical performance; otherwise, see CaliMatHdm]
Testing example: testCorMatHdm_general.m
(uploaded on September 14, 2009).
LagDualNewton.m (this is superseded by CorNewton3.m)
Testing example:
testLagDualNewton.m
(LagDualNewton method for the Band Correlation Stress Testing, "CorNewton1.m" will be called).
CorNewtonSchur.m Testing example:
testCorNewtonSchur.m
(Schur decomposition based method for the Local Correlation Stress Testing,
"CorNewton1.m" will be called).
AugLagNewton.m (this is superseded by CorMatHdm_general.m)
Testing example:
testAugLagNewton.m
(AugLagNewton method for the Band Correlation Stress Testing, "CorNewton1.m" will be called).
(uploaded in March 2007).
CaliMatHdm.zip Calibrating the
H-weighted Nearest Covariance Matrix [H is allowed to have a large number of zero
elements]
(uploaded in April 2010).
Rank_CaliMat.zip Calibrating the
Nearest Correlation Matrix with Rank Constraints
(uploaded in April 2010).
Rank_CaliMatHdm.zip Calibrating the
H-weighted Nearest Correlation Matrix with Rank Constraints
(uploaded in April 2010; last updated in October 2010 by including the refined Major codes).
Codes under the CONvex Matrix Optimization Project (CONMOP)
SDPNAL-0.zip
"A Newton-CG augmented Lagrangian method for semidefinite programming"
(first made publicly available in September 2009 after a number of requests and trials by many
colleagues, for whom we would like to thank for their feedback and suggestions). [This software
solves large scale SDPs with linear constraints plus several SDP cones and nonnegative orthants.
SOCs will be added in the next version. For each SDP block, the matrix dimension n should not be much larger than 2000 though
we did try n larger than 4000. See here for details.]
Logdet-0.zip
"Solving log-determinant optimization problems by a Newton-CG proximal
point algorithm". See the brief user's guide logdet-0-guide.pdf
CorMatHdm_general.m Computing the
H-weighted Nearest Correlation Matrix with fixed
elements and lower and upper bounds
[H should not have too many zero elements for better numerical performance;
otherwise, see CaliMatHdm]
Testing example: testCorMatHdm_general.m
(uploaded on September 14, 2009).
CaliMatHdm.zip Calibrating the
H-weighted Nearest Covariance Matrix [H is allowed to have a large number of zero
elements]
(uploaded in April 2010).
PPApack-0.zip
"Proximal-point algorithms for nuclear norm minimizartion"
See here for details.]
Codes for rank constrainted problems
Rank_CaliMat.zip Calibrating the
Nearest Correlation Matrix with Rank Constraints
(uploaded in April 2010).
Rank_CaliMatHdm.zip Calibrating the
H-weighted Nearest Correlation Matrix with Rank Constraints
(uploaded in April 2010; last updated in October 2010 by including the refined Major codes).
Caihua Chen, Yong-Jin Liu, Defeng Sun, and
Kim Chuan Toh, "A Semismooth Newton-CG Dual Proximal Point Algorithm for Matrix Spectral Norm Approximation Problems",
November 2012,
PDF version SNDPPA-7.pdf.
Weimin Miao, Shaohua Pan, and Defeng Sun, "A rank-corrected procedure for matrix completion with fixed basis coefficients",
November
2012,
PDF version rank_correction.pdf.
Kaifeng Jiang, Defeng Sun, and
Kim Chuan Toh, "A partial proximal point algorithm for nuclear norm regularized matrix least squares problems", January
2012,
PDF version PPA_Smoothing-2.pdf.
Bin Wu, Chao Ding, Defeng Sun, and
Kim Chuan Toh, "On the Moreau-Yosida regularization of the vector k-norm related functions", March
2011,
PDF version k-norm_08Mar11.pdf.
Revised in March 2013; PDF
Maryam Fazel, Ting Kei Pong, Defeng Sun, and
Paul Tseng,
"Hankel matrix rank minimization with applications to system identification and realization",
PDF version Hankelrm23.pdf. SIAM Journal on Matrix Analysis and Applications 34 (2013) XXX-XXX.
Chao Ding, Defeng Sun, and
Kim Chuan Toh, "An introduction to a class of matrix cone programming",
PDF version. Mathematical Programming 13X (201X) XXX-XXX.
Kaifeng Jiang, Defeng Sun, and
Kim Chuan Toh,
"Solving nuclear norm regularized and semidefinite matrix least squares problems with linear equality
constraints",
PDF version PPA_Semismooth-Revision.pdf.Fields Institute Communications Series on Discrete Geometry and Optimization, K. Bezdek, Y. Ye, and A. Deza eds., 2013.
Theses of Students:
"Matrix Completion Models with Fixed Basis Coefficients and Rank Regularized Prbolems with Hard Constraints",
PhDThesis_Miao_Final.pdf (PhD thesis of MIAO Weimin) January 2013.
2011-2012
Kaifeng Jiang, Defeng Sun, and
Kim Chuan Toh, "An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP",
PDF version inexact-APG-QSDP-4.pdf. SIAM Journal on Optimization 22 (2012) 1042--1064.
Houduo Qi and Defeng Sun,
"An augmented Lagrangian dual approach for the H-weighted nearest correlation matrix problem",
PDF version CorrMatHnorm.pdf;
IMA Journal of Numerical Analysis 31 (2011) 491--511.
See the "MATLAB Codes" section for codes in Matlab.
Chengjing Wang, Defeng Sun, and
K. C. Toh, "Solving log-determinant optimization problems by a Newton-CG proximal
point algorithm", September 2009,
PDF version logdet-NAL-29Sep09.pdf;
Revised in March 2010,
PDF version logdet-NAL-12Mar10.pdf;
SIAM Journal on Optimization 20 (2010) 2994--3013.
See the "MATLAB Codes" section for codes in Matlab.
Xinyuan Zhao, Defeng Sun, and
K. C. Toh, "A Newton-CG augmented Lagrangian method for semidefinite programming",
PDF version NewtonCGAugLag.pdf
; SIAM Journal on Optimization 20 (2010) 1737--1765.
See the "MATLAB Codes" section for codes in Matlab.
Houduo Qi and Defeng Sun,
"Correlation stress testing for value-at-risk: an unconstrained convex optimization approach",
PDF version stress_test.pdf;
Computational Optimization and Applications 45 (2010) 427--462.
See the "MATLAB Codes" section for codes in Matlab.
Yan Gao and Defeng Sun,
"Calibrating least squares covariance matrix problems with equality and inequality constraints",
PDF version CaliMat.pdf;
SIAM Journal on Matrix Analysis and Applications 31 (2009) 1432--1457.
See the "MATLAB Codes"
section for codes in Matlab.
Theses of Students:
"Structured Low Rank Matrix Optimization Problems: A Penalized Approach"
PDF version main_gy.pdf (PhD thesis of GAO Yan) August 2010.
"A Semismooth Newton-CG Augmented Lagrangian Method for Large Scale Linear and Convex Quadratic SDPs"
PDF version main_xyz.pdf (PhD thesis of ZHAO Xinyuan) August 2009. [See the "MATLAB Codes" section for the software for solving linear SDPs.
The software for solving convex QSDPs with linear constraints plus several SDP cones, SOCs, and
nonnegative orthants will be
made publicly available shortly after some trials.]
"A Study on Nonsymmetric Matrix-Valued Functions"
PDF version Main_YZ.pdf (Master thesis of YANG Zhe) August 2009.
2007-2008
Jiri Outrata and Defeng Sun,
"On the coderivative of the projection operator onto the second order cone"
Final PDF version singapore4.pdf Set-Valued Analysis 16 (2008) 999--1014.
Zi Xian Chan and Defeng Sun,
"Constraint nondegeneracy, strong regularity, and nonsingularity in
semidefinite programming".
Final PDF version SiamCS07.pdf SIAM Journal on Optimization 19 (2008) 370--396.
J.-S. Chen, Defeng Sun, and
Jie Sun , "The SC^1 property of the squared norm of the SOC Fischer-Burmeister function".
PDF file lipschitz_ORL_10_07.pdf Operations Research Letters 36 (2008) 385--392.
Defeng Sun and
Jie Sun , "Loewner's operator and spectral functions in Euclidean
Jordan algebras".
Final PDF version MOR_SS4.pdf Mathematics of Operations Research 33 (2008) 421--445.
Defeng Sun,
Jie Sun, and Liwei Zhang,
"The rate of convergence of the augmented Lagrangian method for
nonlinear semidefinite programming".
Final PDF version final_SSZ_07.pdf Mathematical Programming 114 (2008) 349--391. Published online: 10 May 2007.
Zheng-Jian Bai, Delin Chu, and Defeng Sun, "A dual optimization approach to inverse quadratic eigenvalue
problems with partial eigenstructure".
PDF version BCS-IQEP_rev.pdf SIAM Journal on Scientific Computing 29 (2007) 2531--2561.
2005-2006
Defeng Sun, "The strong second order sufficient condition and constraint nondegeneracy
in nonlinear semidefinite programming and their implications,"
Final PDF version NLSDP_Final.pdfMathematics of Operations Research 31 (2006) 761--776.
Zheng-Hai Huang, Defeng Sun and
Gongyun Zhao ,
``A smoothing Newton-type algorithm of stronger convergence for the
quadratically
constrained convex quadratic programming,"
Revised PDF version HSZ_Re.pdf Computational Optimization and Applications 35 (2006) 197--237.
Fanwen Meng, D.F. Sun and
Gongyun Zhao ,
``Semismoothness of solutions to generalized equations and
the Moreau-Yosida regularization," Final
PDF version MSZ_May_05.pdf Mathematical Programming 104 (2005) 561--581.
D.F. Sun and
J. Sun , "Nonsmooth Matrix Valued Functions Defined by Singular
Values", December 2002. PDF version SS3.pdf.
Revised with the new title as "Strong semismoothness of Fischer-Burmeister
SDC and SOC functions",
Final PDF version SS3_Rev.pdf Mathematical Programming 103 (2005) 575--581.
D. Han,
Xun Li, D.F. Sun, and
J. Sun
``Bounding option prices of multi-assets:
a semidefinite programming approach,"
PDF version
HLSS.pdfPacific Journal of Optimization
1 (2005) 59--79. (Special issue in honor of the 70th
birthday of R Tyrrell Rockafellar).
Theses of Students:
``Smoothing Approximations for Two Classes of Convex Eigenvalue Optimization Problems"
PDF version Yu_Aug_2005.pdf (Master thesis of Yu Qi)
Z. Huang,
L. Qi and D.F. Sun,
``Sub-Quadratic Convergence of a Smoothing Newton
Algorithm for the P_0-- and Monotone
LCP,''
PDF version
hqs_revised_Feb20.pdf Mathematical Programming,
99 (2004), 423--441.
J. Sun, D.F. Sun
and L. Qi,
``A Smoothing Newton Method for
Nonsmooth Matrix Equations and Its Applications in Semidefinite
Optimization Problems,''
Final version SSQ_Oct15.pdf SIAM Journal on Optimization, 14 (2004), 783--806.
``The Smoothing Function of the Nonsmooth Matrix Valued Function"
PDF version Zhao_July_2004.pdf (Master thesis of Jinye Zhao)
2003
H.-D. Qi, L. Qi and D.F. Sun, ``Solving KKT Systems via the Trust Region and
the Conjugate Gradient Methods," SIAM Journal on
Optimization, 14 (2003) 439--463.
J.S. Pang, D.F. Sun and J. Sun, ``Semismooth Homeomorphisms and
Strong Stability of Semidefinite and Lorentz Cone Complementarity
Problems," PDF version
PSS_03.pdf Mathematics of Operations Research, 28 (2003) 39-63.
X.D. Chen, D. Sun and J. Sun,
``Complementarity Functions and Numerical Experiments for Second-Order-Cone
Complementarity Problems," PDF version coap_03.pdf Computational Optimization and Applications, 25 (2003)
39 -- 56.
G. Zhou,
K. C. Toh and Defeng Sun, ``Semismooth Newton methods for minimizing
a sum of Euclidean norms with linear constraints,''
Postscript version
zts.ps
PDF version zts.pdf.
Journal of Optimization Theory and Applications,
119 (2003), 357--377.
D.F. Sun and
J. Sun, ``Strong Semismoothness of Eigenvalues of Symmetric Matrices
and Its Application to Inverse Eigenvalue Problems,''
SIAM Journal on Numerical Analysis, 40 (2003) 2352--2367.
2002
D.F. Sun,
R.S. Womersley and
H.-D. Qi ,
``A feasible semismooth asymptotically Newton method for
mixed complementarity problems'',
PDF version
SWQ_02.pdf Mathematical Programming, 94 (2002) 167--187.
D.F. Sun and J. Sun, ``Semismooth Matrix Valued Functions,"
PDF version
SS_02.pdf Mathematics of Operations Research, 27 (2002) 150--169.
L. Qi and D. Sun, ``Smoothing Functions and a Smoothing Newton Method
for Complementarity and Variational Inequality Problems,"
Journal of Optimization Theory and Applications, 113 (2002) 121--147.
L. Qi, D. Sun and G. Zhou,
``A primal-dual algorithm for minimizing a sum of Euclidean norms'',
Journal of Computational and Applied Mathematics,
138 (2002) 127--150.
2001
D. Sun, ``A further result on an implicit function
theorem for locally Lipschitz functions'',
PDF version
implicit.pdf Operations Research Letters, 28 (2001) 193--198.
D. Sun and L. Qi,
``Solving variational
inequality problems via smoothing-nonsmooth reformulations'',
PDF version
proj_smooth.pdf Journal of Computational
and Applied Mathematics, 129 (2001) 37--62.
Y.B. Zhao and D. Sun, ``Alternative theorems
for nonlinear projection equations and
their applications to generalized complementarity problems'',
Nonlinear Analysis: Theory, Methods and Applications.
46 (2001) 853--868.
L. Qi and D. Sun, ``Nonsmooth & Smoothing Methods for NCP & VI'',
the Encyclopedia of Optimization ,
C. Floudas and P. Pardalos
(editors),
(Kluwer Academic Publisher, Nowell, MA. USA, 2001) 100-104.
E. Polak, L. Qi and D. Sun, "Second-Order Algorithms for Generalized
Finite and Semi-Infinite Min-Max Problems," SIAM Journal
on Optimization 11 (2001) 937--961.
2000
L. Qi, D. Sun and G. Zhou,
``A new look at
smoothing Newton methods for nonlinear complementarity problems and
box constrained variational inequalities'',
PDF version
QSZ_00.pdf Mathematical Programming, 87 (2000), 1--35.
L. Qi and D. Sun,
``Improving the convergence of non-interior point algorithms
for nonlinear complementarity
problems'',
Mathematics of Computation, 69 (2000), 283--304.
Y. Dai, J. Han, G. Liu, D. Sun, H. Yin and Y. Yuan,
``Convergence properties of nonlinear conjugate gradient methods'',
SIAM Journal on Optimization, 10 (2000), 345--358.
L. Qi
and D. Sun, ``Polyhedral methods for solving three
index assignment problems,''
Nonlinear Assignment Problems: Algorithms and
Applications, P.M. Pardalos and L. Pitsoulis, eds.,
(Kluwer Academic Publisher, Nowell, MA, USA, 2000), 91-107.
1999
R. Mifflin, L. Qi and D. Sun, ``Properties of Moreau-Yosida
regularization of a piecewise $C^2$ convex function'',
Mathematical Programming, Vol. 84, 1999, 269--281.
D. Sun and R. S. Womersley, ''A New Unconstrained Differentiable
Merit Function for Box Constrained Variational Inequality Problems and
a Damped Gauss-Newton Method'',
PDF version
Sun_Womersley_99.pdf SIAM Journal on Optimization, Vol. 9, 1999, pp. 409--434.
E. Polak, L. Qi and D. Sun, ``First-Order Algorithms for Generalized Finite
and Semi-Infinite Min-Max Problems,''
Computational Optimization and Applications,
Vol. 13, pp. 137-161, 1999.
D. Sun and L. Qi, ``On NCP functions'',
PDF version
ncp.pdf Computational Optimization and Applications,
Vol. 13, 1999, 201--220.
D. Sun,
``A regularization Newton method
for solving nonlinear complementarity
problems'',
PDF version
AMO_99.pdf Applied Mathemtics and Optimization, 40 (1999), 315-339.
L. Qi and D. Sun, ``A survey of some
nonsmooth equations and smoothing Newton
methods'',
PDF version
qsreview1.pdf
in Andrew Eberhard,
Barney Glover, Robin Hill and Daniel Ralph eds.,
Progress in
optimization, 121--146, Appl. Optim., 30, Kluwer Acad. Publ., Dordrecht, 1999.
G. Zhou, D. Sun and L. Qi,
``Numerical experiments for a class of
squared smoothing Newton
methods for complementarity
and variational
inequality problems'',
PDF version
zsq_99.pdf
in Reformulation: Nonsmooth, Piecewise Smooth,
Semismooth and Smoothing Methods,
M. Fukushima and L. Qi (eds.), Kluwer Academic Publishers B.V., 421--441,
1999.
1998
F. Potra, L. Qi and D. Sun, ``Secant methods for semismooth
equations'',
Numerische Mathematik, Vol. 80, 1998, 305--324.
X. Chen, L. Qi and D. Sun,
``Global and superlinear convergence of the
smoothing Newton
method and its application to general box constrained variational
inequalities'',
PDF version
CQS_98.pdf Mathematics of Computation, 67 (1998), pp. 519-540.
R. Mifflin, D. Sun and L. Qi,
``Quasi-Newton bundle-type methods
for
nondifferentiable convex optimization'',
SIAM Journal on Optimization, Vol. 8, 1998, 583 - 603.
H. Jiang, M. Fukushima, L. Qi and D. Sun,
``A trust region method for solving generalized complementarity problems'',
SIAM Journal on Optimization, Vol. 8, 1998, pp. 140-157.
J. Han and D. Sun, ``Newton-Type methods for
variational inequalities'',
Advances in Nonlinear Programming, Y. Yuan eds,
Klumer, Boston, 1998, pp. 105 -- 118.
D. Sun and J. Han and Y.B. Zhao, ``On the finite termination of the
damped-Newton
algorithm for the linear complementarity problem'',
Acta Mathematica
Numerica Applicatae, Vol. 21:1, 1998, 148--154.
1997
D. Sun and J. Han, ``Newton and quasi-Newton methods for a
class of nonsmooth equations and related problems'',
PDF version
Sun_Han_97.pdf SIAM Journal on Optimization, 7 (1997) 463--480.
D. Sun, M. Fukushima and L. Qi, ``A computable generalized Hessian of the
D-gap function and Newton-type methods for variational inequality problem'',
PDF version
SFQ_97.pdf
in: M.C. Ferris and J.-S. Pang, eds., Complementarity and Variational
Problems -- State of the Art, SIAM Publications, Philadelphia, 1997,
pp. 452-473.
J. Han and D. Sun, ``Newton and quasi-Newton methods for
normal maps with polyhedral sets'',
Journal of Optimization
Theory and Applications, Vol. 94, No. 3, pp. 659-676,
September 1997.
D. Sun and J. Han, ``On a conjecture in
Moreau-Yosida approximation of a nonsmooth convex function''
Chinese Science Bulletin 42 (1997)
1423--1426.
1996
D. Sun, ``A class of iterative methods for solving nonlinear
projection equations'', PDF version Sun96.pdf Journal of Optimization Theory and Applications,
Vol. 91, No.1, 1996, pp. 123--140.
H. Jiang, L. Qi, X. Chen and D. Sun,
``Semismoothness and Superlinear Convergence
in Nonsmooth Optimization and
Nonsmooth Equations'', Nonlinear Optimization and Applications,
G. Di Pillo and F. Giannessi eds., (Plenum Publishing Corporation,
New York), 1996, 197--212.
1995
G. Liu, J. Han and D. Sun, ``Global convergence
of BFGS method with nonmonotone line search'',
Optimization 34 (1995) 147--159.
D. Sun, ``A new step-size skill for solving a class of
nonlinear projection equations'',
PDF version Sun95.pdf Journal of Computational Mathematics 13:4 (1995), 357--368.
1994
D. Xu and D. Sun, ``A modification of successive
approximation method for nonsmooth equations'',
PDF version Xu_Sun_smoothing_94.pdf
Qufu Shifan Daxue
Xuebao Ziran Kexue Ban 20:3 (1994) 14--20.
D. Sun and J. Wang, ``An approximation method for
stochastic programming with recourse'',
Mathematica Numerica Sinica
16 (1994) 80--92. (In Chinese).
English translation published in Chinese Journal of
Numerical
Mathematics and Applications 16:2 (1994) 70--83.
D. Sun, ``A projection and contraction method for the
nonlinear complementarity problem and its extensions'',
PDF version Sun94.pdf Mathematica
Numerica Sinica 16 (1994) 183--194. (In Chinese).
English translation published
in Chinese
Journal of
Numerical Mathematics and Applications 16:3 (1994) 73--84.
D. Sun, ``An iterative method for solving variational
inequality problems and
complementarity problems'',
Numerical Mathematics A Journal of Chinese
Universities 16 (1994) 145--153. (In Chinese).
1993
D. Sun, ``Projected extragradient method for finding saddle
points of general convex programming'',
Qufu Shifan Daxue
Xuebao Ziran Kexue Ban 19:4 (1993) 10--17.
