Applications

MERIT has potential applications in a wide range of mathematical optimization problems. We note that the case-dependent sub-optimality guarantees can be viewed as trust certificates provided along with the approximate solutions, and hence, are of practical importance in decision making scenarios.

To provide an example of MERIT's derivation, in the following, we consider unimodular quadratic programming (UQP), also known as complex quadratic programming. Interestingly, using MERIT one may obtain better performance guarantees for UQP compared to the analytical worst-case guarantees (such as gamma=pi /4

associated with SDR).

Unimodular Quadratic Programming (UQP)

The NP-hard problem of optimizing a quadratic form over the unimodular vector set arises in a variety of active sensing and communication applications, such as receiver signal-to-noise ratio (SNR) optimization, synthesizing cross ambiguity functions, steering vector estimation, and maximum likelihood (ML) detection. Namely, we study the problem

where $mathbf{R} in mathcal{C}^{n times n}$ is a given Hermitian matrix, and Omega

represents the unit circle, i.e. Omega={s in mathcal{C} : ~| s | =1 }

MERIT for UQP

To help the formulation of MERIT, Theorem 1 presents a bijection among the set of matrices leading to the same solution.

Theorem 1. Let mathcal{K}(mathbf{s}) represent the set of matrices mathbf{R} for which a given $mathbf{s} in Omega^n$ is the global optimizer of UQP. Then

is a convex cone.
For any two vectors $mathbf{s}_1,mathbf{s}_2 in Omega^n$ , the one-to-one mapping

$mathbf{R} in mathcal{K}(mathbf{s}_1) Longleftrightarrow mathbf{R} odot (mathbf{s}_0 mathbf{s}_0^H) in mathcal{K}(mathbf{s}_2)$

(where $mathbf{s}_0=mathbf{s}_1^* odot mathbf{s}_2$ ) holds among the matrices in $mathcal{K}(mathbf{s}_1)$ and $mathcal{K}(mathbf{s}_2)$ .

It is interesting to note that in light of the above result, the characterization of the cone mathcal{K}(mathbf{s})

for any given mathbf{s}=widetilde{mathbf{s}}

leads to a complete characterization of all mathcal{K}(mathbf{s})

, $mathbf{s} in Omega^n$ , and thus solving any UQP. While a complete tractable characterization of mathcal{K}(mathbf{s})

cannot be expected (due to the NP-hardness of UQP), approximate characterizations of mathcal{K}(mathbf{s})

are possible. In the following, our goal is to provide an approximate characterization of the cone mathcal{K}(mathbf{s})

which can be used to tackle the UQP problem.

Theorem 2. For any given $mathbf{s}= ( e^{j phi_1}, cdots , e^{j phi_n} )^T in Omega^n$ , let $mathcal{C}(mathbf{V}_mathbf{s})$ represent the convex cone of matrices $mathbf{V}_mathbf{s}= mathbf{D} odot (mathbf{s} mathbf{s}^H)$ where is any real-valued symmetric matrix with non-negative off-diagonal entries. Also let $mathcal{C}_mathbf{s}$ represent the convex cone of matrices with being their dominant eigenvector (i.e the eigenvector corresponding to the maximal eigenvalue). Then for any mathbf{R} in mathcal{K}(mathbf{s}) , there exists alpha_0 geq 0 such that for all alpha geq alpha_0 ,

$mathbf{R}+ alpha mathbf{s} mathbf{s}^H in mathcal{C}(mathbf{V}_mathbf{s}) oplus mathcal{C}_mathbf{s}$

where oplus stands for the Minkowski sum of the two sets.

An intuitive illustration of the result in Theorem 2 is shown in Fig. 1. Indeed, it can be shown that Theorem 2 is valid even when mathbf{s}

is a local optimum of the UQP associated with mathbf{R}

Finally, one can use $mathcal{C}(mathbf{V}_mathbf{s}) oplus mathcal{C}_mathbf{s}$ as an approximate characterization of mathcal{K}(mathbf{s})

noting that the accuracy of such a characterization can be measured by the minimal value of alpha_0

. Hereafter, we study a computational method to obtain an alpha_0

which is as small as possible. We also formulate the sub-optimality guarantee for a solution of UQP based on the above mathcal{K}(mathbf{s})

approximation.

Using the previous results, we build a sequence of matrices (for which the UQP global optima are known) whose distance from the given matrix mathbf{R}

is decreasing. The proposed iterative approach can be used to solve for the global optimum of UQP or at least to obtain a local optimum (with an upper bound on the sub-optimality of the solution). We know from Theorem 2 that if mathbf{s}

is a stable point of the UQP associated with mathbf{R}

then there exist matrices $mathbf{Q}_mathbf{s} in mathcal{C}_mathbf{s}$ , $mathbf{P}_mathbf{s} in mathcal{C}(mathbf{V}_mathbf{s})$ and a scalar alpha_0 geq 0

such that $mathbf{R}+ alpha_0 mathbf{s} mathbf{s}^H = mathbf{Q}_mathbf{s}+ mathbf{P}_mathbf{s}$ . The latter equation can be rewritten as

where $mathbf{Q}_mathbf{1} in mathcal{C}_mathbf{1}$ , and $mathbf{P}_mathbf{1} in mathcal{C}(mathbf{V}_mathbf{1})$ .

We first consider the case of alpha_0=0

which corresponds to the global optimality of mathbf{s}

. Consider the optimization problem:

$min_{mathbf{s} in Omega^n, mathbf{Q}_mathbf{1} in mathcal{C}_mathbf{1}, mathbf{P}_mathbf{1} in mathcal{C}(mathbf{V}_mathbf{1})} | mathbf{R} - (mathbf{Q}_mathbf{1}+ mathbf{P}_mathbf{1}) odot (mathbf{s} mathbf{s}^H) |_F$

Note that, as $mathcal{C}_mathbf{1} oplus mathcal{C}(mathbf{V}_mathbf{1})$ is a convex cone, the global optimizers $mathbf{Q}_mathbf{1}$ and $mathbf{P}_mathbf{1}$ for any given mathbf{s}

can be easily found. On the other hand, the problem of finding an optimal mathbf{s}

for fixed $mathbf{R}_mathbf{1} =mathbf{Q}_mathbf{1}+ mathbf{P}_mathbf{1}$ is non-convex and hence more difficult to solve globally.

Note that there exist examples for which the above objective function does not converge to zero. As a result, the proposed method cannot obtain a global optimum of UQP in such cases. However, it is still possible to obtain a local optimum of UQP for some alpha_0>0

. To do so, we solve the optimization problem,

$min_{mathbf{s} in Omega, mathbf{Q}_mathbf{1} in mathcal{C}_mathbf{1}, mathbf{P}_mathbf{1} in mathcal{C}(mathbf{V}_mathbf{1})} | mathbf{R}' - (mathbf{Q}_mathbf{1}+ mathbf{P}_mathbf{1}) odot (mathbf{s} mathbf{s}^H) |_F$

with $mathbf{R}' = mathbf{R} + alpha_0 mathbf{s} mathbf{s}^H$ , for increasing alpha_0

Sub-Optimality Analysis

We show how MERIT can provide real-time sub-optimality guarantees and bounds during its iterations. Let alpha_0=0

(as a result mathbf{R}'=mathbf{R}

) and define

where $mathbf{Q}_mathbf{1} in mathcal{C}_mathbf{1}$ and $mathbf{P}_mathbf{1} in mathcal{C}(mathbf{V}_mathbf{1})$ . By construction, the global optimum of the UQP associated with $mathbf{R}_mathbf{s}$ is

. We have that

$begin{array}{ll} max_{mathbf{s}' in Omega^n} mathbf{s}'^H mathbf{R} mathbf{s}' & leq max_{mathbf{s}' in Omega^n} mathbf{s}'^H mathbf{R}_mathbf{s} mathbf{s}' + max_{mathbf{s}' in Omega^n} mathbf{s}'^H mathbf{E} mathbf{s}' & leq max_{mathbf{s}' in Omega^n} mathbf{s}'^H mathbf{R}_mathbf{s} mathbf{s}' + n sigma_1(mathbf{E}) & = mathbf{s}^H mathbf{R}_mathbf{s} mathbf{s} + n sigma_1(mathbf{E}) end{array}$

$begin{array}{ll} max_{mathbf{s}' in Omega^n} mathbf{s}'^H mathbf{R} mathbf{s}' & geq max_{mathbf{s}' in Omega^n} mathbf{s}'^H mathbf{R}_mathbf{s} mathbf{s}' + min_{mathbf{s}' in Omega^n} mathbf{s}'^H mathbf{E} mathbf{s}' & geq max_{mathbf{s}' in Omega^n} mathbf{s}'^H mathbf{R}_mathbf{s} mathbf{s}' + n sigma_n(mathbf{E}) & = mathbf{s}^H mathbf{R}_mathbf{s} mathbf{s} + n sigma_n(mathbf{E}) end{array}$

As a result, an upper bound and a lower bound on the objective function for the global optimum of UQP can be obtained at each iteration. Next, suppose that we have to increase alpha_0

in order to obtain the convergence of $| mathbf{E} |_F$ to zero. In such a case, we have that

$max_{mathbf{s}' in Omega^n} mathbf{s}'^H mathbf{R}_mathbf{s} mathbf{s}' - alpha_0 n^2 leq max_{mathbf{s}' in Omega^n} mathbf{s}'^H mathbf{R} mathbf{s}' leq max_{mathbf{s}' in Omega^n} mathbf{s}'^H mathbf{R}_mathbf{s} mathbf{s}'$

$mathbf{s}^H mathbf{R}_mathbf{s} mathbf{s} - alpha_0 n^2 leq max_{mathbf{s}' in Omega^n} mathbf{s}'^H mathbf{R} mathbf{s}' leq mathbf{s}^H mathbf{R}_mathbf{s} mathbf{s}.$

$gamma= frac{mathbf{s}^H mathbf{R} mathbf{s}}{mathbf{s}^H mathbf{R}_mathbf{s} mathbf{s}} = 1- frac{alpha_0 n^2}{mathbf{s}^H mathbf{R}_mathbf{s} mathbf{s}}= frac{mathbf{s}^H mathbf{R} mathbf{s}}{mathbf{s}^H mathbf{R} mathbf{s} + alpha_0 n^2}.$

Numerical Examples and Discussion

We use the power method-like iterations, and MERIT, as well as the curvilinear search of with Barzilai-Borwein (BB) step size, to solve an UQP (with n=10

) based on the same initialization. The resultant UQP objectives along with required times (in sec) versus iteration number are plotted in Fig. 2.

It can be observed that the power method-like iterations approximate the UQP solution much faster than the employed curvilinear search. On the other hand, both methods are much faster than MERIT. This type of behavior, which is not unexpected, is due to the fact that MERIT is not designed solely for local optimization; indeed, MERIT relies on a considerable over-parametrization in its formulation which is the cost paid for easily derivable sub-optimality guarantees. In general, one may employ the power method-like iterations to obtain a fast approximation of the UQP solution (e.g. by using several initializations), whereas for obtaining sub-optimality guarantees one can resort to MERIT.

Next, we approximate the UQP solutions for

full-rank random positive definite matrices of sizes n in { 8,16 }

. Inspired by some previous works, we also consider rank-deficient matrices mathbf{R}

with rank

. The performance of MERIT for different values of

is shown in Table 1. Note that, in general, the provided sub-optimality guarantees gamma

are considerably larger than pi/4

of SDR. We also employ SDR to solve the same UQPs. In this example, we continue the randomization procedure of SDR until reaching the same UQP objective as for MERIT. A comparison of the computation times of SDR and MERIT can also be found in Table 1.

Fig. 3. Application of MERIT for designing cross ambiguity functions (CAFs). The normalized CAF modulus for (a) the Bj"orck code of length n =53

(i.e. the initial CAF), and (b) the CAF obtained by MERIT. See the Related Publications for more details.