NAG CL Interface
g02akc (corrmat_nearest_rank)
1
Purpose
g02akc computes the nearest correlation matrix of maximum prescribed rank, in the Frobenius norm, to a given square, input matrix.
2
Specification
void |
g02akc (double g[],
Integer pdg,
Integer n,
Integer rank,
double errtol,
double ranktol,
Integer maxits,
Integer maxit,
double x[],
Integer pdx,
double *f,
double *rankerr,
Integer *nsub,
NagError *fail) |
|
The function may be called by the names: g02akc or nag_correg_corrmat_nearest_rank.
3
Description
g02akc finds the nearest correlation matrix of maximum prescribed rank to an approximate correlation matrix in the Frobenius norm.
The solver is based on the Majorized Penalty Approach (MPA) proposed by
Gao and Sun (2010). One of the key elements in this type of method is that the subproblems are similar to the nearest correlation matrix problem without rank constraint, and can be solved efficiently by
g02aac. The total number of subproblems solved is controlled by the arguments
maxit and
maxits. The algorithm behaviour and solver accuracy can be modified by these and other input arguments. The default values for these arguments are chosen to work well in the general case but it is recommended that you tune them to your particular problem. For a detailed description of the algorithm see
Section 11.
4
References
Bai S, Qi H–D and Xiu N (2015) Constrained best Euclidean distance embedding on a sphere: A matrix optimization approach SIAM J. Optim. 25(1) 439–467
Gao Y and Sun D (2010) A majorized penalty approach for calibrating rank constrained correlation matrix problems Technical report Department of Mathematics, National University of Singapore
Qi H–D and Yuan X (2014) Computing the nearest Euclidean distance matrix with low embedding dimensions Mathematical Programming 147(1–2) 351–389
5
Arguments
-
1:
– double
Input/Output
-
On entry: , the initial matrix.
On exit: a symmetric matrix with diagonal elements set to .
-
2:
– Integer
Input
On entry: the stride separating column elements of the matrix
in the array
g.
Constraint:
.
-
3:
– Integer
Input
-
On entry: the order of the matrix .
Constraint:
.
-
4:
– Integer
Input
-
On entry: , the upper bound for the rank of .
Constraint:
.
-
5:
– double
Input
-
On entry: the termination tolerance for the convergence measure of the objective function value.
If
, then a value of
is used. See
Section 11 for further details.
-
6:
– double
Input
-
On entry: the feasibility tolerance for the rank constraint.
If
,
is used. See
Section 11 for further details.
-
7:
– Integer
Input
-
On entry: specifies the maximum number of iterations used for the majorization approach to solve penalized problems at each level of penalty parameter.
If , then a value of is used.
-
8:
– Integer
Input
-
On entry: specifies the maximum number of iterations for the penalty method, i.e., the maximum level of penalty parameter.
If , then a value of is used.
-
9:
– double
Output
-
On exit: , the nearest correlation matrix of rank .
-
10:
– Integer
Input
On entry: the stride separating column elements of the matrix
in the array
x.
Constraint:
.
-
11:
– double *
Output
-
On exit: the difference between and given by .
-
12:
– double *
Output
-
On exit: the rank error of , defined as , given that denote eigenvalues of sorted in non-increasing order.
-
13:
– Integer *
Output
-
On exit: the total number of majorized problems that have been solved, i.e., the total number of calls for
g02aac.
-
14:
– NagError *
Input/Output
-
The NAG error argument (see
Section 7 in the Introduction to the NAG Library CL Interface).
6
Error Indicators and Warnings
- NE_ALLOC_FAIL
-
Dynamic memory allocation failed.
See
Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
- NE_BAD_PARAM
-
On entry, argument had an illegal value.
- NE_CONVERGENCE
-
Convergence is limited by
machine precision. The objective function value or rank is decreasing very slowly.
The array returned in
x may still be of interest.
Majorized penalty approach fails to converge in
maxit level of penalty iterations.
- NE_INT
-
On entry, .
Constraint: .
- NE_INT_2
-
On entry, and .
Constraint: .
On entry, and .
Constraint: .
On entry, and .
Constraint: .
- NE_INTERNAL_ERROR
-
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact
NAG for assistance.
See
Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
- NE_NO_LICENCE
-
Your licence key may have expired or may not have been installed correctly.
See
Section 8 in the Introduction to the NAG Library CL Interface for further information.
7
Accuracy
The returned accuracy is controlled by
errtol and
ranktol, and is limited by
machine precision.
8
Parallelism and Performance
g02akc is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
g02akc makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.
Please consult the
X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this function. Please also consult the
Users' Note for your implementation for any additional implementation-specific information.
Arrays are internally allocated by g02akc. The total size of these arrays is real elements and integer elements.
10
Example
This example finds the nearest correlation matrix with target rank
to:
10.1
Program Text
10.2
Program Data
10.3
Program Results
11
Algorithmic Details
g02akc is aimed at solving the rank constrained nearest correlation matrix problem formulated as follows:
where
is the input approximate correlation matrix,
is the upper bound of rank of the output nearest correlation matrix
, the expression
stands for a constraint on eigenvalues of
in the space of
by
symmetric matrices
, namely, all the eigenvalues should be non-negative, i.e., the matrix should be positive semidefinite,
denotes the Frobenius norm. Note that the rank constraint is given as an inequality, which means if the intrinsic rank of the input matrix is already less than or equal to
, the solver will calculate a nearest correlation matrix without increasing the rank.
This section contains a short description of the algorithm used in
g02akc which is based on the Majorized Penalty Approach (MPA) by
Gao and Sun (2010). Further details on accuracy and stopping criterion are also included.
11.1
Penalty approach
Let
be the vector of the eigenvalues of
(arranged in the non-increasing order) and
be the corresponding matrix of orthonormal eigenvectors of
. The equivalent relationship for a positive semidefinite matrix
is as follows.
Therefore, problem
(1) can be equivalently written as
Introducing the penalty parameter
, we can obtain the following penalized problem by taking a trade-off between the rank constraint and the least square distance
.
Define
where
is the identity matrix,
is the standard trace inner product in
. We can rewrite problem
(3) as
The penalty parameter
is updated according to the progress of rank reduction. The input argument
maxit controls the maximum number of updates of
.
The penalized problem
(4) is not equivalent to the original problem
(1) and the relationship can be described as follows. If the rank of the minimizer
to problem
(4) is not larger than
, then
is a global optimal solution to problem
(1), otherwise an
-optimal solution to problem
(1) is guaranteed given that parameter
satisfies some bound constraint. Please see
Gao and Sun (2010) for more details.
11.2
Majorization approach
The focus now is on solving the penalty problem
(4). Since
is nonsmooth and concave, we majorize it by the linear function defined by its subgradient. For given
(the current iteration) and
, we have
Now, instead of solving the nonconvex problem
(4), we solve the following convex model:
The framework combines ideas of a penalty method with majorization, it can be described as follows:
Majorized Penalty Algorithm (MPA) |
-
1.Select a penalty parameter and a feasible point , set .
-
2.Solve subproblem (5) to get .
-
3.If , stop; otherwise, update penalty parameter , set and go to step 2.
|
Let
, the subproblem
(5) is actually a nearest correlation matrix problem with input
without rank constraint, which can be solved efficiently by
g02aac. Input
maxits controls the maximum number of iterations used in solving one problem
(5) with fixed
.
For the convergence result of the algorithm, see
Gao and Sun (2010). For other implementations as well as parameter setting strategies, see
Qi and Yuan (2014) and
Bai et al. (2015).
11.3
Stopping criteria
The algorithm shown in
Table 1 is stopped when all the stopping criteria are satisfied to the requested accuracy, these are:
Here
and
may be set by arguments
errtol and
ranktol respectively in order to achieve various returned accuracy. The above quantity to measure rank feasibility does not scale well with the magnitude of
. To rectify this drawback, we also build in the third stopping criterion to control the percentage of the first
eigenvalues of
out of all the eigenvalues: