# Control of a Wind-Turbine via Machine Learning techniques

L. Schena1 E. Gillyns1 W. Munters1 S. Buckingham1 M. A. Mendez1 1 von Karman
Institute for Fluid Dynamics
Waterloose Steenweg 72, 1640 Sint-Genesius-Rode, Belgium
e-mail<EMAIL_ADDRESS>
###### Abstract

This article presents two _model-free_ controllers for wind-turbine torque and
pitch control. These controllers are based on reinforcement learning (RL) and
Bayesian optimization (BO) and do not rely on any mathematical model of the
wind-turbine dynamics, in contrast to classical approaches designed on
linearized models. The model-free controllers were benchmarked against a
proportional-integral-derivative (PID) regulator in a numerical environment
using Blade Element Momentum theory for computing the aerodynamic torque and
the blade loads. The results showed that the model-free approaches could
increase power harvesting while reducing wind turbine loads.

###### keywords:

Wind-turbine control, Reinforcement Learning, Loads mitigation

L. Schena, E. Gillyns, W. Munters, S. Buckingham, M. A. Mendez

##  1 INTRODUCTION

The control of wind turbines is a grand challenge in wind energy [1], and it
is crucial to its viability [2]. Currently, most wind turbines operate in
variable-speed or variable-pitch (VS-VP) conditions [3, 4] depending on the
wind speed. Figure 1 shows the ideal power curve for a reference NREL 5-MW [5]
wind turbine considered in this study. This is designed for rated power of
$P_{R}=5$ [MW] at a rated wind speed of $u_{R}=11.4$ [m s-1]. A standard
controller [6] acts on the generator torque at a wind speed
$u_{\infty}<u_{R}$, holding the blades fine-pitched to the optimal pitch
angle, and on the pitch angle at $u_{\infty}>u_{R}$, keeping the nominal
torque. This aims to maximize the power production in regions 2 and 2.5 and
limit the loads in regions 2.5 and 3. This work focuses on pitch and torque
control in region 2.5, which is particularly critical in balancing the
conflicting objectives of power maximization and load mitigation. Gusts or
lulls in this region might cause undesired switches from pitch to torque
control, leading to sub-optimal power production or excessive loads. Standard
controllers based on PI (Proportional and Integral) formulations might offer
enough flexibility in the control law to handle these conditions optimally [7,
8]. These controllers rely on linearized models of the wind turbine dynamics,
but no linearization can handle the switch between the two operating
conditions. In this work, we investigate the application of machine learning
algorithms that learn directly from data without relying on any model of the
underlying dynamics, and we benchmark their performances against classical PID
controllers. Section 2 overviews the simulation environment and the algorithms
employed. Next, Sect. 3 details the test cases on which the controllers are
compared. Sect. 4 discusses the results and Sect. 5 outlines the conclusions
and future work.

Figure 1: Steady power response as a function of wind-speed for the NREL 5-MW
[5] considered in this work. The round markers indicate the investigated
conditions.

##  2 METHODOLOGY

###  2.1 Simulation environment

The numerical environment considered in this work relies on a first-order
model of the wind-turbine dynamics:

$\dot{\omega}=\frac{N_{g}}{J}(\tau_{a}-N_{g}\tau_{g}\eta_{gb})\,,$ (1)

where $\dot{\omega}$ [rad s-2] is the rotor acceleration, $N_{g}$ [-] the
efficiency of the generator, $J$ is the rotor inertia [kg m-2], $\eta_{gb}$[-]
is the gearbox ratio, and $\tau_{a}$ and $\tau_{g}$ are the aerodynamic and
generator torque respectively. In a first approximation, the aerodynamic
torque is a function of the tip speed ratio $\lambda=\omega R/u_{\infty}$ and
the blade pitch angle $\beta$ [deg]:

$\tau_{a}=\frac{1}{2}\rho\pi
R^{2}\frac{C_{p}(\lambda,\beta)}{\omega}u_{\infty}^{3}=\frac{1}{2}\rho\pi
R^{2}C_{Q}(\lambda,\beta)u_{\infty}^{3}\,,$ (2)

where $C_{p}(\lambda,\beta)$ is the power coefficient and
$C_{Q}=C_{Q}(\lambda,\beta)$ is the torque coefficient. Equation (1) and (2)
provide the simplest model for the wind turbine dynamics under the assumption
of rigid blades and uniform wind over the rotor’s swept area. Although these
assumptions are rather restrictive (especially for large turbines), this model
is commonly used by control engineers in wind applications [9, 10] and is thus
considered appropriate for a first comparative analysis of model-free versus
classic controllers.

(a)

(b)

Figure 2: (a) Schematic of the blade, approximated with 12 twelve nodes and
reference frame used in the BEM simulation for the test cases considered in
this work. b) Contour of the resulting $C_{p}$ coefficient as a function of
$\lambda$ and $\beta$.

In order to integrate (1) and (2), the power coefficient was computed using
the Blade Element Momentum (BEM) formulation using the WISDEM CCBlade [14]
Python package, whereas the loads have been computed using AeroDyn [15]. This
formulation couples the momentum equation with the blade element theory to
compute the forces per unit length acting at different nodes (see Fig. 2(a))
along each blade. The wind velocity and the (instantaneous) rotational speed
constitute the _state_ $\mathbf{s}=[u_{\infty}\quad\omega]^{T}$ vector for the
dynamical system to be controlled. In order to make the system physically
realistic, the controller _action_ /_actuation_ is given in terms of rate-of-
change for the pitch angle ($\dot{\beta}$) and torque ($\dot{\tau}$), that is
$\mathbf{a}=[\dot{\beta}\quad\dot{\tau}]^{T}$. Therefore, within the time
integration of (1), the update on the $\beta$ and $\tau$ under the action of
the controller is:

$\displaystyle\beta(t+\Delta t)=\beta(t)+\dot{\beta}\Delta t$ (3)
$\displaystyle\tau(t+\Delta t)=\tau(t)+\dot{\tau}\Delta t$

where $\Delta t$ is the time step in the integration. The rates are clipped in
a range $\dot{\beta}\in[-\dot{\beta}_{max},\dot{\beta}_{max}]$ [deg s-1] and
$\dot{\tau}\in[-\dot{\tau}_{max},\dot{\tau}_{max}]$ [Nm s-1] (see Table 1).

The goal of the optimal controller is to find the _policy_ /_actuation_ law
$\pi:\mathcal{S}\rightarrow\mathcal{A}$, with
$\mathcal{S}\subseteq\mathbb{R}^{2}$ the space of admissible states and
$\mathcal{A}\subseteq\mathbb{R}^{2}$ the set of admissible actions, such that
a _reward_ function is maximized. The definition of this reward function
depends on the control objectives and is described in Sect. 3. First, we
briefly introduce the investigated control strategies in Sect. 2.2.

1 begin

2 Initialize a possible control law $\mathbf{a}=\pi(\mathbf{s};\mathbf{w})$ of
the controller;

3 Initialize the inflow velocity $u_{\infty}$ and add random noise, such that:
$u_{\infty}=u_{\infty,*}+\mathcal{W}(\mu=0,\sigma)$;

4 for  _$n$ in (1, $N_{episodes}$)_ do

5 for  _$t$ in (1,$T$)_ do

6 Initialize wind-turbine at initial conditions;

7 Feed the current state $\mathbf{S}=(u_{\infty,t},\omega_{t})$ to the
controller;

8 Get action(s) $\mathbf{a}=(\beta_{t+1},\tau_{load,t+1})$ following current
policy $\pi$;

9 Evolve the wind-turbine state $\mathbf{s}_{t}\rightarrow\mathbf{s}_{t+1}$,
evaluating the look-up-tables to get the aerodynamic coefficients
$C_{p},C_{Q}$;

10 if  _AeroDyn coupling is active_ then

11 Compute loads $F_{x},F_{y},F_{z}$ (in the hub reference frame) acting on
the wind-turbine blades, and their rate of change $F_{xt},F_{yt},F_{zt}$ via
BEM simulation;

12

13 end if

14 Compute the reward $r_{t}$ associated with the change of state
$\mathbf{s}_{t}\rightarrow\mathbf{s}_{t+1}$ and current action
$\mathbf{a}_{t}$;

15 Update policy weights $\mathbf{w}_{k}$ (for DDPG);

16

17 end for

18 Update policy weights $\mathbf{w}_{k}$ (for BO);

19

20 end for

21

22 end

23

Algorithm 1 Algorithmic Approach for the Optimal Control Law Derivation

###  2.2 Algorithms

Algorithm 1 details the implementation of the control evaluation and training
processes for the different controllers. For training purposes, the algorithm
begins with random initialization of the parameters (line 2) and ends with an
update of the parameters at each episode (line 14).

The performance evaluation (whether used for training or not) is carried out
within _episodes_ of duration $T=100$ [s]. This also defines the duration of
the simulation. This time scale is deemed adequate because it corresponds to
roughly twenty blade rotations in rated conditions. Running the simulations
with a time-step of $\Delta t=0.025$ [s] and considering that the controller
interacts with the system at every iteration, one episode produces 4000
agent/environment interactions per episode. The wind-flow field is generated
such that the time average is $\bar{u}_{\infty}=10.5$ [m s-1] (hence the
turbine operates in Region 2.5, cf. Fig. 1), via TurbSim [18]. This software
constructs realistic wind data from its spectral characteristic. White noise
with zero mean and standard deviation $\sigma=0.1$[m s-1] is also added to
mimic measurement noise and avoid overfitting (line 3). As suggested by [5],
the velocity signal is low-pass filtered at one-quarter of the first edgewise
natural frequency of the blade (corresponding to $f\approx 1$ Hz) to avoid the
high-frequency excitation of these control systems. The corner frequency of
the filter (that is the -3dB attenuation) is thus set to $f_{c}=0.25$ Hz. The
implemented filter is a 5-th order Butterworth filter with cut-off frequency
$f_{co}=1.571/(f_{s}/2)$ Hz, and $f_{s}=40$ Hz is the sampling frequency.
Thus, at each timestep, the agent receives the current (filtered) state
$\mathbf{s}$ and outputs an action $\mathbf{a}$ which makes the environment
(plant) evolve to its next state: $\mathbf{s}_{t}\rightarrow\mathbf{s}_{t+1}$.
An instantaneous reward signal $r(t)$ is produced at each state transition,
and a cumulative reward signal $R=\sum_{t}r(t)$ is produced at the end of the
episode. Both measure the controller performances and are maximum when the
control law is optimal. The reward function definition is discussed in 3. The
‘black-box’ optimization (Section 2.3) updates the control law at the end of
the episodes (line 17) while the reinforcement learning algorithm (Section
2.4) updates at each episode. Before introducing the model-free approaches,
Sect. 2.2.1 briefly recalls the fundamentals of the PID controllers used as
reference.

####  2.2.1 PI (or PID) controllers

This is a classic control approach and serves as a reference controller in
this work. The general multi-input-multi output (MIMO) formulation for the
problem described in Eq. (4)

$\mathbf{a}(\mathbf{s})=\begin{bmatrix}k_{P1}&0\\\
0&k_{P2}\end{bmatrix}\mathbf{e}(\mathbf{s}(t))+\begin{bmatrix}k_{I1}&0\\\
0&k_{I2}\end{bmatrix}\int_{0}^{t}\mathbf{e}(\mathbf{s}(\tau))d\tau+\begin{bmatrix}k_{D1}&0\\\
0&k_{D2}\end{bmatrix}\frac{d\mathbf{e}(\mathbf{s}(t))}{dt}\,,$ (4)

where $\mathbf{e}=\mathbf{s}-\mathbf{s}_{ref}$ is the error between the
current state and the reference state while the coefficients $k_{P},k_{I}$ and
$k_{D}$ are the proportional, integral and derivative gains respectively. The
diagonal form of the matrices involved makes the controllers for each action
independent from the others but one could include more general formulations
with off-diagonal terms.

Considering that in this work we do not control the first state (the wind
speed), Eq. (4) becomes a scalar equation ($k_{P1}=k_{I1}=k_{D1}=0$). The
remaining coefficients can be tuned from data or from dynamic considerations
of the system at hand. In this work, we consider the second approach and we
used the Reference Open Source COntroller (ROSCO, [9]) for determining
$k_{P2}$ and $k_{I2}$. As it is common practice for utility-scale wind
turbines, the coefficient $k_{D2}$ is set to zero to limit the control
sensitivity to measurement noise. The final controller is thus a PI
controller.

The reader is referred to [9] for more details on how the coefficients are
derived. Briefly, these are computed from a linearized model of the wind
turbine and designed to ensure that the (linear) closed loop system has a
prescribed transfer function.

###  2.3 Bayesian Optimization (BO)

The BO is a classic surrogate based approach to minimize a ‘black-box’
function [11]. As done in [12], the training of a model-free controller is
converted into a black-box optimization problem by prescribing the parametric
form of the control law. In this work, we consider a linear law
$\mathbf{a}=\mathbf{W}\mathbf{s}$ with $\mathbf{W}\in\mathbb{R}^{2\times 2}$
collecting the four coefficients to be identified. For a given choice of
parameters, the environment can be simulated for one episode and the global
cumulative reward $R(\mathbf{W})$ is the cost function that needs to be
optimized.

The BO formulation used in this work is the classic combination of Gaussian
Process Regression (GPR) for the surrogate model and Lower Confidence Bound
(LCB) for the acquisition function. The GPR was carried out using a Matern
kernel with $\nu=1.5$ and length scale $l=1.0$ (see [13] for more details).

###  2.4 Reinforcement Learning (RL)

Reinforcement Learning (RL) is the machine learning paradigm in which the
agent (controller) learns how to interact with the environment (plant) to
maximize a reward signal [16]. The conceptual architecture of the RL agent is
the same as for the BO agent: this is simply a different way of converting the
problem of training a model-free controller into a black-box optimization. In
modern RL approaches, based on Deep Neural Networks (also known as Deep RL),
the policy $\mathbf{a}=\pi(\mathbf{s};\mathbf{w})$ is encoded in an Artificial
Neural Network (ANN), and the training is performed using stochastic gradient
ascent approaches. This allows for deriving a general (nonlinear) control law
without the need to prescribe a specific form (like in the linear policy
trained by the BO formulation). In this work, an in-house customized
implementation of the Deep Deterministic Policy Gradient (DDPG, [17]) is
employed (see also [12]). Two ANNs are employed, one to map states to actions,
the _actor_ and another one that approximates the long-term consequences of
the applied actions - or _value function_ -, the _critic_. The former consists
in a 32$\times$32 network plus a concatenation of the input layer to allow
linear control parametrizations, whereas the latter concatenates two networks.
The first, from the action taken by the agent composed as 2$\times$64\. The
states are elaborated in two layers of size 2$\times$32$\times$32\. These are
concatenated and expanded by means of two layers with 32$\times$32$\times$1 ,
neurons, from which the output is the value estimated. Both the network
architecture and the learning approach are the same as in [12], with 2 neurons
in the first (inputs) and the last (actuation) layers. The total number of
parameters to be trained is 6750.

Finally, it is noted that, while the problem has been posed as a minimization
problem for the BO optimization and a maximization one for the RL approach,
following the relative literature practice, the two are de facto identical, as
the fitness functions have been modified of sign accordingly.

##  3 TEST CASES

All the test cases investigated in this work consider the reference wind
turbine NREL-5 MW with all technical details available in open-source [5]. The
relevant characteristics are reported listed in Tab. 1.

Rotor radius, $R$ | [m] | 63
---|---|---
Peak power coefficient, $C_{P,max}$ | [-] | 0.482
Tip-Speed ratio at peak power coefficient, $\lambda_{*}$ | [-] | 7.55
Rated mechanical power $P_{r}$ | [MW] | 5.296
Rated generator torque $\tau_{r}$ | [N $\cdot$ m] | 43,093.55
Maximum generator torque $\tau_{max}$ | [N $\cdot$ m] | 47,402.91
Maximum generator torque rate $\dot{\tau}_{max}$ | [N $\cdot$ m s-1] | 15,000
Proportional gain $K_{P}$ at minimum blade-pitch setting, | [s] | 0.01882
Integral gain $K_{I}$ at minimum blade-pitch setting, | [-] | 0.0086
Minimum blade-pitch setting, $\beta_{min}$ | [deg] | 0
Maximum blade-pitch setting, $\beta_{max}$ | [deg] | 90
Maximum absolute blade-pitch rate, $\dot{\beta}_{max}$ | [deg s-1] | 8
Table 1: NREL 5-MW wind-turbine main characteristics, [5]

Two control problems are considered. The first is that of tracking the optimal
Tip-speed Ratio (TSR, $\lambda$) regardless of the turbine loads. The second
is that of balancing the power production with the wind blade loads. The
settings for these two problems are described in Section 3.1 and 3.2
respectively.

###  3.1 TSR tracking on synthetic wind data (Test Case A)

This test case aims at maximizing the harvested power and the power
coefficients regardless of the wind loads. Therefore, the instantaneous reward
function is

$r_{1}(t)=-\frac{|\lambda-\lambda_{*}|}{\lambda_{*}}-\frac{|P_{g}-P_{*,g}|}{P_{*,g}}\,,$
(5)

were $\lambda(t)$ is the instantaneous TSR, $\lambda_{*}=7.55$ is the TSR
maximizing the power coefficient $C_{p}$ at the optimal pitch angle
$\beta_{*}=0^{\circ}$ (cfr. figure 2(b)), $P_{g}(t)$ is the instantaneous
extracted power and $P_{r}$ is the rated power.

It is worth recalling that the optimality of $\lambda_{*}$ is valid in steady
conditions but not dynamic ones. In real conditions, where $C_{p}$ could be
measured, the combination of the two terms could allow the controller to
explore the action space departing from $\lambda^{*}$ if the associated loss
in the first term is out-weighted by a gain in the second.

###  3.2 Loads mitigation (Test Case B)

The goal in this test case is to minimize the overall loads met by the wind
turbine. It is recalled that to compute the loads, the augmented framework
embedding BEM simulations is employed, as presented in Sect. 2. The
instantaneous reward in this second test case is

$r_{2}(t)=\langle\tilde{P}_{g}\rangle_{T}-||\tilde{F}||_{1}$ (6)

where the $\langle\tilde{P}_{g}\rangle=P_{g,t}/P_{rated}$ weights the
extracted power ($P_{g,t}$) on the rated power $(P_{r})$, while
$||\tilde{F}||_{1}$ is the $l_{1}$ norm of the aerodynamic load in the hub
reference system, as illustrated in Fig. 2(a). The $\tilde{}$ denotes
normalization of the forces with respect to the average values produced by a
PI controller over an episode.

##  4 RESULTS

We analyze the performances of the model-free controllers over a training
period of $40$ episodes, corresponding to $4000$ s of physical time. We here
focus on the best results achieved at the end of the training and we postpone
the analysis of the learning curves to the extended version of this work.

###  4.1 TSR tracking on synthetic wind data

The numerical results of Test case A (reward function in Eq. (5)) are listed
in Tab. 2. The table collects the relative gain/increase in the power
extracted, defined as $\Delta P_{g}=(\langle P\rangle_{PI}-\langle
P\rangle_{ML})/\langle P\rangle_{PI}$, where $\langle P\rangle_{ML}$
represents the mean power extracted in the simulation time by the control
parametrization at hand, and the relative TSR tracking error, defined as
$\Delta\langle\lambda\rangle=(\langle\lambda\rangle_{PI}-\langle\lambda\rangle_{ML})/\langle\lambda\rangle_{PI}$.
Both quantities are averaged within an episode.

The two machine learning methods increase greatly the power extraction with
respect to the PI controller while maintaining the rotational speed of the
turbine closer to its rated value $\omega_{r}=1.33$ rad s-1. Interestingly,
the results shows that the second term in Eq. (5) is more important than the
first. Figs. 3(a),3(b), 3(c) and 3(d) show the system trajectory in the state
plane $\mathbf{s}=(u_{\infty},\omega)$ during an episode. For plotting
purposes, only one every fifty time steps is included. The markers are colored
by the controller actions at the corresponding states. The figures on the top
show the pitch actuation ($\beta$), while the figures one the bottom show the
torque actuation ($\tau$).

Method |  $\langle{P}_{g}\rangle$ [MW] |  $\langle\lambda\rangle$ [-] |  $\langle\omega\rangle$ [rad s-1] |  $\Delta P_{g}$% |  $\Delta\langle\lambda\rangle$%
---|---|---|---|---|---
PI | 4.05 | 7.28 | 1.22 | - | -
Linear Controller (BO) | 4.80 | 7.61 | 1.32 | +18.1 % | \- 70.21 %
RL (DDPG) | 4.95 | 7.85 | 1.36 | \+ 22.22 % | +11.1 %
Table 2: Results testcase A. Method indicates the parametrization of the
control-law, $\langle P_{g}\rangle$ [MW] is the generated power and $\omega$
[rad s-1] is the mean rotational speed. The last two columns compare the
performances with the baseline (PID).

(a) BO pitching policy

(b) RL (DDPG) pitching policy

(c) BO generator torque policy

(d) RL (DDPG) generator torque policy

Figure 3: System trajectory and controller policy for the BO (on the left) and
DDPG (on the right) algorithms. The first row refers to the pitch rate
actuation while the second refers to the torque rate actuation.

Interestingly, both controllers opt for a pitch angle between
$-1^{\circ}\leq\beta\leq 1^{\circ}$, even though they are not constrained to
do so. This is the pitch angle corresponding to the highest $C_{p}$, for the
$\lambda$ met by the operative trajectories. Concerning the BO torque
actuation, the controller seeks to slow down the wind turbine when the tip
speed ratio is greater than the rated value, whereas it reduces its actuation
in the lower-right part of the plot, where $\lambda\approx 5.25$, to speed the
rotor up. The RL acts similarly, but it surprisingly acts less in the upper
part of the trajectory (corresponding to a larger tip-speed ratio than the
rated value). This behaviour, which might be due to poor state space sampling,
will be further investigated in future works.

###  4.2 Load mitigation

The numerical results of Test case B (reward function in (6)) are listed in
Tab. 3. Both model-free controllers significantly reduce the loads, albeit at
the cost of a significant reduction in the extracted power. This result is due
to the relative weights introduced in the reward function– one could change
these to set different priorities for the two objectives. By repeating the
training with different relative weights between the terms in (6), one could
identify an approximation of the Pareto front in the action space [19].

Remarkably, the linear control driven by the BO achieves better performances
in terms of load reduction for a nearly equal power reduction. Although a more
in-depth analysis is needed to assess the learning performances of both
agents, this result shows that the larger model capacity (and complexity) of
the DDPG agent might not pay off over a more straightforward linear control
law (at least within the 40 episodes considered for the training).

Method |  $P_{g}$ [MW] |  $F_{x}$ [kN] |  $F_{y}$ [N] |  $F_{z}$ [N] |  $\Delta F_{x}$ % |  $\Delta F_{y}$ % | $\Delta F_{z}$
---|---|---|---|---|---|---|---
PI | 4.05 | 295.162 | 5.1E-02 | 3.0E-02 | - | - | -
Linear Controller (BO) | 2.8 | 81.82 | 4.8E-02 | 2.1E-02 | -73% | -7% | -31%
RL (DDPG) | 2.78 | 142.245 | -2.8E-02 | 2.8E-02 | -53.81 % | -44.38% | -8%
Table 3: Results Testcase B. Method indicates the parametrization of the
control-law, $\langle P_{g}\rangle$ [MW] is the generated power, $F_{x},F_{y}$
and $F_{z}$ are the forces met by the wind-turbine in the respective
directions (in the hub frame of reference cfr. Fig. 2(a)), whereas the last
three columns represent their variation against the baseline.

Finally, Figure 4 shows the loads in each node (averaged over an episode) per
unit length. The node numbering increases from the hub to the tip (cf. Figure
2(a)). The load distribution in the absence of control is shown for
comparison, and it is clear that this increase from left to right (i.e. at a
larger distance from the hub). In the absence of control, the load re-
partition is extremely non-uniform, with most of the loads acting on the tip
while the PI controllers introduces a nearly triangular distribution. On the
other hand, the non-monotonic trend for the controlled conditions is due to a
complex interplay between the time-varying accelerations produced by the
controllers and the time-varying deflections of the blades. In the future, the
reward function could be crafted to prescribe a specific load distribution and
thus tailor the loadings to the structural design of the blades.

Figure 4: Loads per unit length on each blade node in case of no control
(blue), baseline PI control (orange), linear BO controller (green) and
nonlinear (DDPG) controller

##  5 CONCLUSIONS AND OUTLOOKS

This work presents two black-box machine learning strategies for the control
of a wind turbine. These have been benchmarked against a classic PI controller
in a numerical environment that reproduces the main features of the wind
turbine power production and loading. The results show that these methods can
outperform baseline (piecewise linearized) approaches and handle multiple
objectives with minimal tuning. Because these controllers learn by trial and
error and do not rely on (necessarily simplified) wind turbine models, they
could offer new avenues for optimal wind energy extraction.
In the future, hybrid approaches will be considered as proposed in [12]. These
could consist of two agents cooperating on two similar problems: (1) learning
the control function and (2) identifying and tuning simplified models online.
The controller could thus decide to operate in a model-based or a model-free
approach and use one of the methods to improve the other. Both the proposed
model-free and the hybrid methods will be implemented in a scaled wind turbine
model in an experimental campaign in the L1 wind tunnel at the von Karman
Institute.

## Acknowledgements

This work has received funding from the Flemish Government through the Agency
for Innovation and Entrepreneurship (Vlaams Agentschap Innoveren en
Ondernemen, VLAIO) through the ICON project RAINBOW in the context of the
cluster on Strategic Initiative for Materials in Flanders (SIM) and the
Blauwer cluster.

## References

  * [1] Veers, P., Dykes, K., Lantz, E., Barth, S., Bottasso, C. L., Carlson, O., Clifton, A., Green, J., Green, P., Holttinen, H., Laird, D., Lehtomäki, V., Lundquist, J. K., Manwell, J., Marquis, M., Meneveau, C., Moriarty, P., Munduate, X., Muskulus, M., … Wiser, R. (2019). Grand challenges in the science of wind energy. Science, 366(6464). https://doi.org/10.1126/science.aau2027.
  * [2] van Kuik G A, et al. 2016 Long-term research challenges in wind energy - A research agenda by the European Academy of Wind Energy Wind Energy Science 1 1-39.
  * [3] Ackermann, T. and Soder, L. (2002). An overview of wind energy-status 2002. Renewable and Sustainable Energy Reviews 6(1-2), 67–127.
  * [4] Gardner, P., Garrad, A., Jamieson, P., Snodin, H., and Tindal, A. (2003). Wind energy. The facts. Technical report, European Wind Energy Association (EWEA), Brussels, Belgium.
  * [5] Jonkman, J., Butterfield, S., Musial, W., Scott, G. (2009). Definition of a 5-MW reference wind turbine for offshore system development. Contract, February, 1–75.
  * [6] Fernando D. Bianchi, Ricardo J. Mantz, Hernán Battista. Wind Turbine Control Systems, Principles, Modelling and Gain Scheduling Design. Springer London (2007).
  * [7] Lio, W. H., Rossiter, J. A., Jones, B. L. (2014). A review on applications of model predictive control to wind turbines. 2014 UKACC International Conference on Control, CONTROL 2014 - Proceedings, July, 673–678. https://doi.org/10.1109/CONTROL.2014.6915220
  * [8] Laks, J. H., Pao, L. Y., Wright, A. D. (2009). Control of wind turbines: Past, present, and future. Proceedings of the American Control Conference, July, 2096–2103. https://doi.org/10.1109/ACC.2009.5160590.
  * [9] Abbas, N. J., Zalkind, D. S., Pao, L., Wright, A. (2022). A reference open-source controller for fixed and floating offshore wind turbines. Wind Energy Science, 7(1), 53–73.
  * [10] Johnson, K. E., Fingersh, L. J., Balas, M. J., Pao, L. Y. (2004). Methods for increasing region 2 power capture on a variable speed hawt. Collection of ASME Wind Energy Symposium Technical Papers AIAA Aerospace Sciences Meeting and Exhibit, January 2014, 103–113.
  * [11] Archetti, Francesco and Candelieri, Antonio. Bayesian optimization and data science. Springer (2019).
  * [12] Pino, F., Schena, L., Rabault, J., Kuhnle, A., Mendez, M. (2022). Comparative analysis of machine learning methods for active flow control. arXiv preprint arXiv:2202.11664.
  * [13] Rasmussen, Carl Edward. Gaussian processes in machine learning. Summer school on machine learning. Springer (2003).
  * [14] Dykes, Katherine L and Damiani, Rick R and Graf, Peter A and Scott, George N and King, Ryan N and Guo, Yi and Quick, Julian and Sethuraman, Latha and Veers, Paul S and Ning, Andrew (2018). Wind Turbine Optimization with WISDEM.
  * [15] Jonkman, J. M., Hayman, G. J., Jonkman, B. J., Damiani, R. R. (2015). AeroDyn v15 User’s Guide and Theory Manual. Renewable Energy, March, 46.
  * [16] Sutton, Richard S. and Barto, Andrew. Reinforcement Learning: An Introduction (2018). A Bradford Book.
  * [17] Lillicrap, Timothy P. and Hunt, Jonathan J. and Pritzel, Alexander and Heess, Nicolas and Erez, Tom and Tassa, Yuval and Silver, David and Wierstra, Daan. Continuous control with deep reinforcement learning (2016). 4th International Conference on Learning Representations, ICLR 2016 - Conference Track Proceedings.
  * [18] Jonkman, B. J., M. L. Buhl, J. (2006). NWTC Information Portal (TurbSim). NREL/TP-500-39797, 1–32.
  * [19] Costa, N. R., Lourenço, J. A., ”Exploring Pareto Frontiers in the Response Surface Methodology”, in G.-C. Yang, S.-I. Ao, L. Gelman, eds., Transactions on Engineering Technologies: World Congress on Engineering 2014 (Berlin/Heidelberg: Springer, 2015), pp. 399–412.


∎

11institutetext: Yingzhe Xu 22institutetext: School of Economics and
Management, North China Electric Power University, Beijing 102206, China
22email<EMAIL_ADDRESS>33institutetext: Cheng Lu 44institutetext: School
of Economics and Management, North China Electric Power University, Beijing
102206, China
44email<EMAIL_ADDRESS>55institutetext: Zhibin Deng 66institutetext:
School of Economics and Management, University of Chinese Academy of Sciences;
MOE Social Science Laboratory of Digital Economic Forecasts and Policy
Simulation at UCAS, Beijing, 100190, China
66email<EMAIL_ADDRESS>77institutetext: Ya-Feng Liu 88institutetext:
State Key Laboratory of Scientific and Engineering Computing, Institute of
Computational Mathematics and Scientific/Engineering Computing, Academy of
Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100190,
China
88email<EMAIL_ADDRESS>
# New semidefinite relaxations for a class of complex quadratic programming
problems††thanks: This preprint has not undergone peer review (when
applicable) or any post-submission improvements or corrections. The Version of
Record of this article is published in Journal of Global Optimization, and is
available online at https://doi.org/10.1007/s10898-023-01290-z.

Yingzhe Xu  Cheng Lu  Zhibin Deng  Ya-Feng Liu

(Received: date / Accepted: date)

###### Abstract

In this paper, we propose some new semidefinite relaxations for a class of
nonconvex complex quadratic programming problems, which widely appear in the
areas of signal processing and power system. By deriving new valid constraints
to the matrix variables in the lifted space, we derive some enhanced
semidefinite relaxations of the complex quadratic programming problems. Then,
we compare the proposed semidefinite relaxations with existing ones, and show
that the newly proposed semidefinite relaxations could be strictly tighter
than the previous ones. Moreover, the proposed semidefinite relaxations can be
applied to more general cases of complex quadratic programming problems,
whereas the previous ones are only designed for special cases. Numerical
results indicate that the proposed semidefinite relaxations not only provide
tighter relaxation bounds, but also improve some existing approximation
algorithms by finding better sub-optimal solutions.

###### Keywords:

Quadratic optimization Semidefinite relaxation Approximation algorithm Phase
quantized waveform design Discrete transmit beamforming

##  1 Introduction

In this paper, we consider the following complex quadratic programming
problem:

$\displaystyle\min{}$ $\displaystyle x^{{\dagger}}Q_{0}x$ (CQP) s.t.
$\displaystyle x^{{\dagger}}Q_{i}x\leq b_{i},~{}i=1,\ldots,m,$ $\displaystyle
l_{i}\leq{|}x_{i}{|}\leq u_{i},~{}i=1,\ldots,n,$
$\displaystyle\arg(x_{i}{x_{j}}^{{\dagger}})\in\mathcal{A}_{ij},\\{i,j\\}\in\mathcal{E},$

where $Q_{0},Q_{1},\ldots,Q_{m}\in\mathbb{C}^{n\times n}$ are Hermitian
matrices, $b_{1},\ldots,b_{m}\in\mathbb{R}$, and $l_{i}$ and $u_{i}$ are the
lower and upper bounds of the modulus of $x_{i}\in\mathbb{C}$ for
$i=1,\ldots,n$. The set $\mathcal{E}$ is a subset of $\\{\\{i,j\\}\,|\,1\leq
i<j\leq n\\}$. For each $\\{i,j\\}\in\mathcal{E}$, $\mathcal{A}_{ij}$ is
either an interval of the form $[\underline{\theta}_{ij},\bar{\theta}_{ij}]$,
or a set of discrete points of the form
$\\{\theta_{ij}^{1},\ldots,\theta_{ij}^{M}\\}\subseteq\mathbb{R}$. We use
$\arg(\cdot)$ to denote the argument of a complex variable, and
$(\cdot)^{\dagger}$ to denote the conjugate transpose of a matrix/vector.

Problem (CQP) arises in many important applications in signal processing,
communication and power system. For example, the radar waveform design problem
Maio2011 , the transmit beamforming problem Demir2014 ; Demir2015 , and the
optimal power flow problem Low2014a ; Low2014b , can all be formulated as
special cases of (CQP). Besides, when $l_{i}=u_{i}=1$ for $i=1,\ldots,n$,
(CQP) degenerates to the unit-modulus constrained quadratic programming
problem, which arises in applications including the MIMO detection problem
Ma2004 , the radar phase code design problem Maio2009 , the angular
synchronization problem Bandeira , and the max-3-cut problem Goemans . In some
applications arising in network problems, such as the optimal power flow
problem in the electricity network Chen2016 ; Coffrin , the set $\mathcal{E}$
can be seen as an edge set that represents the network structure. Besides, the
constraint $\arg(x_{i}{x_{j}}^{{\dagger}})\in\mathcal{A}_{ij}$ in (CQP), which
bounds the difference of phase angles, has some physical meanings in power
systems and other related applications. One may refer to Coffrin  for further
discussions on the physical meaning of this constraint.

Problem (CQP) is NP-hard in general, since some of its special cases are
already known to be NP-hard Zhang2006 . Hence, it is not possible to solve
(CQP) globally in polynomial-time complexity, unless P=NP. Instead, we are
interested in designing efficient algorithms to find sub-optimal solutions of
(CQP). In the literature, most existing sub-optimal algorithms for solving
(CQP) or its subclass problems are approximation algorithms, local-
optimization algorithms, or heuristic algorithms Demir2014 ; Demir2015 ;
Goemans ; Maio2009 ; Maio2011 ; So2007 ; Waldspurger ; Zhang2006 ; Zhao .
Among different sub-optimal algorithms, the semidefinite relaxation based
approximation algorithms have attracted great attention since the pioneering
work of Goemans and Williamson Goemans1995 . One may refer to Luo2010  for a
comprehensive survey on the applications of semidefinite relaxation in signal
processing, and Low2014a ; Low2014b  for the applications in power system. For
certain type of (CQP) which arises in real applications, it has been proven
that under some practical conditions, the probability of obtaining the global
solution of the problem using the semidefinite relaxation based approximation
algorithms can be very high Bandeira ; Low2014b ; Lu2019 .

However, when the phase angle constraints
$\arg(x_{i}{x_{j}}^{{\dagger}})\in\mathcal{A}_{ij}$ are presented in (CQP),
the current existing semidefinite relaxations are generally not tight,
especially when $\mathcal{A}_{ij}$ is a discrete set. The reason is that these
phase angle constraints are usually dropped when deriving semidefinite
relaxations of (CQP). Indeed, by exploiting the phase angle constraints, we
may derive some new valid constraints to enhance the semidefinite relaxation.
A theoretical result has been presented in Lu2019 , which shows that by
introducing new valid constraints derived from the phase angle constraints, we
may design an improved semidefinite relaxation for the MIMO detection problem.
The tightness of the improved semidefinite relaxation can be guaranteed under
certain conditions. Similar enhanced semidefinite relaxations have also been
designed for other types of complex quadratic programming problems that appear
in signal processing Lu2018 ; Lu2020 .

In Lu2018  and Lu2020 , Lu et al. have proposed a method of representing a
complex variable by its polar coordinate form to derive tight semidefinite
relaxations. The main idea behind the method is that some valid constraints
can be easily derived in terms of polar coordinate variables, while it is hard
to discover them in the complex coordinate variables. Based on this method, Lu
et al. have proposed some improved semidefinite relaxations for several
classes of complex quadratic optimization problems in Lu2018 ; Lu2020 .
However, for problem (CQP) that contains the constraints
$\arg(x_{i}{x_{j}}^{{\dagger}})\in\mathcal{A}_{ij}$, the previous semidefinite
relaxations proposed in Lu2018 ; Lu2020  are not always applicable.

In this paper, we propose a new semidefinite relaxation, which is tighter and
more flexible than the existing ones in Lu2018 ; Lu2020 . Our main idea is to
lift the variable $x$ to a matrix $X=xx^{\dagger}$, and exploit the valid
inequalities on the matrix entries $X_{ii}$, $X_{jj}$ and $X_{ij}$ to enhance
the tightness of a semidefinite relaxation. The contributions of this paper
are two folds:

  * •

From the theoretical aspect, we exactly describe the convex hull of the set

$\mathcal{J}^{x}_{ij}:=\\{(x_{i}x^{\dagger}_{i},x_{j}x^{\dagger}_{j},x_{i}x^{\dagger}_{j})\,|\,~{}l_{i}\leq{|}x_{i}{|}\leq
u_{i},l_{j}\leq{|}x_{j}{|}\leq
u_{j},\arg(x_{i}{x_{j}}^{{\dagger}})\in\mathcal{A}_{ij}\\}.$

It turns out that the convex hull of $\mathcal{J}^{x}_{ij}$ can be represented
as a finite number of linear constraints and no more than two second-order
cone constraints. Our theoretical result can be applied to general cases of
(CQP), including the case of $\mathcal{A}_{ij}$ being an interval, and the
case of being a finite set. This new result generalizes the previous one in
Chen2016 , in which the convex hull of $\mathcal{J}^{x}_{ij}$ is described
only for the case $\mathcal{A}_{ij}$ being an interval contained in
$(-\pi/2,\pi/2)$.

  * •

From the computational aspect, based on the formulation of the convex hull of
$\mathcal{J}^{x}_{ij}$, we introduce new valid inequalities on variables
$X_{ii}$, $X_{jj}$ and $X_{ij}$ to design some enhanced semidefinite
relaxations. Our results show that the enhanced semidefinite relaxations can
be tighter than the existing semidefinite relaxations in the literature.
Moreover, by adopting the enhanced semidefinite relaxations, some previous
approximation algorithms can be improved to find better sub-optimal solutions.

The remaining parts of this paper are organized as follows: Section 2
introduces the first enhanced semidefinite relaxation, and analyzes some basic
properties of the proposed semidefinite relaxation. Section 3 compares the
proposed enhanced semidefinite relaxation with existing ones in the
literature. Section 4 proposes the second enhanced semidefinite relaxation
which is further enhanced from the one proposed in Section 2, and shows that
the new semidefinite relaxation can be strictly tighter than the one proposed
in Chen2016 . Section 5 presents the numerical results to show the performance
of the proposed semidefinite relaxations.

The following notations will be adopted throughout the paper: For a given
matrix $X\in\mathbb{C}^{n\times n}$, $\texttt{Re}(X)$ and $\texttt{Im}(X)$
denote its component-wise real part and imaginary part, respectively. For a
given Hermitian matrix $A\in\mathbb{C}^{n\times n}$, $A\succeq 0$ means $A$ is
positive semidefinite. For two given Hermitian matrices $A$ and $B$, $A\succeq
B$ means $A-B\succeq 0$. Moreover, $\texttt{Trace}(A)$ denotes the trace of
$A$, $\texttt{rank}(A)$ denotes the rank of $A$, and $A\cdot B$ denotes
$\texttt{Trace}(A^{{\dagger}}B)$. For a set $\mathcal{S}$ in some vector
space, we use $\textsf{Conv}(\mathcal{S})$ to represent the convex hull of
$\mathcal{S}$. We use

$\mathcal{A}^{M}:=\left\\{0,\frac{1}{M}2\pi,\ldots,\frac{M-1}{M}2\pi\right\\}$

to represent the uniformly discretized phase angle set for $M\geq 2$. Besides,
with a slight abuse of notations, for a nonzero complex variable $z$ and a set
$\mathcal{A}\subset\mathbb{R}$, the notation $\arg(z)\in\mathcal{A}$ means
that there exists a $k\in\mathbb{Z}$ such that $\arg(z)+2k\pi$ is contained in
$\mathcal{A}$.

##  2 A new semidefinite relaxation

In this section, we first present a classical semidefinite relaxation for
problem (CQP), and then enhance it by introducing some new valid constraints.
Letting $X=xx^{{\dagger}}$, problem (CQP) can be reformulated as follows:

$\displaystyle\min{}$ $\displaystyle Q_{0}\cdot X$ (CQP2) s.t. $\displaystyle
Q_{i}\cdot X\leq b_{i},~{}i=1,\ldots,m,$ $\displaystyle l_{i}^{2}\leq
X_{ii}\leq u^{2}_{i},~{}i=1,\ldots,n,$
$\displaystyle\arg(X_{ij})\in\mathcal{A}_{ij},\\{i,j\\}\in\mathcal{E},$
$\displaystyle\texttt{rank}(X)=1.$

Dropping the constraints $\arg(X_{ij})\in\mathcal{A}_{ij}$ for
$\\{i,j\\}\in\mathcal{E}$ and relaxing $\texttt{rank}(X)=1$ to $X\succeq 0$,
we have the following classical semidefinite relaxation:

$\displaystyle\min{}$ $\displaystyle Q_{0}\cdot X$ (CSDP) s.t. $\displaystyle
Q_{i}\cdot X\leq b_{i},~{}i=1,\ldots,m,$ $\displaystyle l_{i}^{2}\leq
X_{ii}\leq u^{2}_{i},~{}i=1,\ldots,n,$ $\displaystyle X\succeq 0.$

(CSDP) has been widely used to design approximation algorithms in the
literature. For example, Maio et al. have applied (CSDP) to design an
approximation algorithm for solving the radar waveform design problem Maio2011
. Zhang and Huang Zhang2006 , and So et al. So2007 , have applied (CSDP) in
the special case, where $l_{i}=u_{i}=1$ for $i=1,\ldots,n$, to design
approximation algorithms for the unit-modulus constrained complex quadratic
optimization.

However, since the constraints $\arg(X_{ij})\in\mathcal{A}_{ij}$ are dropped
directly, the bound provided by (CSDP) may not be tight enough for some
classes of (CQP). As discussed in Lu2018 ; Lu2019 ; Lu2020 , by exploiting the
structure of the phase angle constraints, we may derive new valid inequalities
to enhance the semidefinite relaxation.

For this purpose, we introduce the polar coordinate form for each complex
variable $x_{i}=r_{i}e^{\texttt{i}\theta_{i}}$. Then, we introduce two lifted
matrices, including $X=xx^{{\dagger}}\in\mathbb{C}^{n\times n}$, and
$R=rr^{{\dagger}}\in\mathbb{R}^{n\times n}$. For each
$\\{i,j\\}\in\mathcal{E}$, we have the following equations:

$R_{ij}=r_{i}r_{j},~{}X_{ij}=r_{i}r_{j}e^{\texttt{i}(\theta_{i}-\theta_{j})}=R_{ij}e^{\texttt{i}(\theta_{i}-\theta_{j})}.$
(1)

Based on (1), we may further derive the following equations:

$R_{ii}R_{jj}=R^{2}_{ij},~{}|X_{ij}|=R_{ij}.$ (2)

Adding (2) into (CSDP), we have the following problem:

$\displaystyle\min{}$ $\displaystyle Q_{0}\cdot X$ (CQP3) s.t. $\displaystyle
Q_{i}\cdot X\leq b_{i},~{}i=1,\ldots,m,$ $\displaystyle l_{i}^{2}\leq
X_{ii}=R_{ii}\leq u^{2}_{i},~{}i=1,\ldots,n,$
$\displaystyle\arg(X_{ij})\in\mathcal{A}_{ij},~{}|X_{ij}|=R_{ij},~{}R_{ij}^{2}=R_{ii}R_{jj},~{}\\{i,j\\}\in\mathcal{E},$
$\displaystyle X\succeq 0.$

Notice that constraints $|X_{ij}|=R_{ij}$ and $R_{ij}^{2}=R_{ii}R_{jj}$ are
nonconvex in (CQP3). Hence, we need to relax these nonconvex constraints in
order to obtain a convex relaxation. To do this, we define the following set
for each $\\{i,j\\}\in\mathcal{E}$:

$\mathcal{H}_{ij}=\\{(R_{ii},R_{jj},R_{ij})\mid l_{i}^{2}\leq R_{ii}\leq
u^{2}_{i},l_{j}^{2}\leq R_{jj}\leq u^{2}_{j},R_{ij}^{2}=R_{ii}R_{jj}\\}.$ (3)

We have the following theorem, which is cited from Corollary 5 in Chen2016 ,
with some modifications on notations.

######  Theorem 2.1 (Chen2016 )

The following two linear inequalities are valid for $\mathcal{H}_{ij}$:

$\displaystyle(l_{i}+u_{i})(l_{j}+u_{j})R_{ij}\geq(l_{j}^{2}+l_{j}u_{j})R_{ii}+(l_{i}^{2}+l_{i}u_{i})R_{jj}+l_{i}l_{j}u_{i}u_{j}-l_{i}^{2}l_{j}^{2},$
(4)
$\displaystyle(l_{i}+u_{i})(l_{j}+u_{j})R_{ij}\geq(u_{j}^{2}+l_{j}u_{j})R_{ii}+(u_{i}^{2}+l_{i}u_{i})R_{jj}+l_{i}l_{j}u_{i}u_{j}-u_{i}^{2}u_{j}^{2}.$
(5)

Moreover, the convex hull of $\mathcal{H}_{ij}$ can be represented as follows:

$\displaystyle\textsf{Conv}(\mathcal{H}_{ij})=\left\\{(R_{ii},R_{jj},R_{ij})\,\left|\,\begin{array}[]{@{}lll}l_{i}^{2}\leq
R_{ii}\leq u^{2}_{i},l_{j}^{2}\leq R_{jj}\leq u^{2}_{j}\\\ R_{ij}^{2}\leq
R_{ii}R_{jj}\\\ (R_{ii},R_{jj},R_{ij})~{}\textrm{satisfies \eqref{eq1} and
\eqref{eq2}}\end{array}\right.\right\\}.$ (9)

The inequality $R_{ij}^{2}\leq R_{ii}R_{jj}$ can be transformed to
$(2R_{ij}^{2}+R_{ii}^{2}+R_{jj}^{2})^{1/2}\leq R_{ii}+R_{jj}$. Hence, the
constraint $(R_{ii},R_{jj},R_{ij})\in\textsf{Conv}(\mathcal{H}_{ij})$ can be
formulated as a set of linear constraints and a second-order cone constraint.

Next, for any given $R_{ij}\geq 0$, we consider the nonconvex set

$\mathcal{G}_{ij}(R_{ij}):=\\{X_{ij}\mid
R_{ij}=|X_{ij}|,~{}\arg(X_{ij})\in\mathcal{A}_{ij}\\}$

and its convex hull. When $R_{ij}=0$, we simply define
$\mathcal{G}_{ij}(R_{ij})=\\{0\\}$. When $R_{ij}>0$, by using the similar
arguments in Lu2018 , we have the next two propositions to describe the convex
hull of the set $\mathcal{G}_{ij}(R_{ij})$.

###### Proposition 1

For the case of $\mathcal{A}_{ij}=[\underline{\theta}_{ij},\bar{\theta}_{ij}]$
where $\bar{\theta}_{ij}-\underline{\theta}_{ij}<2\pi,$ we have

$\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))=\left\\{X_{ij}\,|\,a_{ij}\mathrm{Re}\left(X_{ij}\right)+b_{ij}\mathrm{Im}\left(X_{ij}\right)\geq
c_{ij}R_{ij},~{}|X_{ij}|\leq R_{ij}\right\\},$ (10)

where

$a_{ij}=\cos\left(\frac{\underline{\theta}_{ij}+\bar{\theta}_{ij}}{2}\right),~{}b_{ij}=\sin\left(\frac{\underline{\theta}_{ij}+\bar{\theta}_{ij}}{2}\right),\textrm{and}~{}c_{ij}=\cos\left(\frac{\bar{\theta}_{ij}-\underline{\theta}_{ij}}{2}\right).$
(11)

###### Proposition 2

For the case of
$\mathcal{A}_{ij}=\\{\theta_{ij}^{1},\theta_{ij}^{2},\ldots,\theta_{ij}^{M}\\}$
where

$0\leq\theta_{ij}^{1}<\theta_{ij}^{2}<\cdots<\theta_{ij}^{M}<2\pi,$

we have

$\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))=\left\\{X_{ij}\,\left|\,\begin{array}[]{@{}ll}&a_{ij}^{t}\mathtt{Re}\left(X_{ij}\right)+b_{ij}^{t}\mathtt{Im}\left(X_{ij}\right)\leq
c_{ij}^{t}R_{ij},\\\ &t=1,2,\ldots,M\end{array}\right.\right\\},$ (12)

where $\theta_{ij}^{M+1}:=\theta_{ij}^{1}+2\pi$ and

$\displaystyle
a_{ij}^{t}=\cos\left(\frac{\theta_{ij}^{t}+\theta_{ij}^{t+1}}{2}\right),~{}b_{ij}^{t}=\sin\left(\frac{\theta_{ij}^{t}+\theta_{ij}^{t+1}}{2}\right),$
(13) $\displaystyle
c_{ij}^{t}=\cos\left(\frac{\theta_{ij}^{t+1}-\theta_{ij}^{t}}{2}\right).$

The proof of the above two propositions are straightforward, and thus are
omitted here. We illustrate the two propositions in Figure 1. As illustrated
in the left-hand side of Figure 1, for the case
$\mathcal{A}_{ij}=[\underline{\theta}_{ij},\bar{\theta}_{ij}]$ where
$\bar{\theta}_{ij}-\underline{\theta}_{ij}<2\pi$, the set
$\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))$ is defined by the set enclosed by
the straight line passing through points $A$ and $B$, and the arc connecting
the two points. Similarly, as illustrated in the right-hand side of Figure 1,
$\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))$ can be represented by $M$
inequalities when
$\mathcal{A}_{ij}=\\{\theta_{ij}^{1},\theta_{ij}^{2},\ldots,\theta_{ij}^{M}\\}$.

Figure 1: An illustration of the set $\mathcal{G}_{ij}(R_{ij})$ for the case
$R_{ij}=1$.

Based on Propositions 1 and 2, the constraint
$X_{ij}\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))$ can be formulated as a
linear inequality constraint and a second-order cone constraint of the form
$(\texttt{Re}^{2}(X_{ij})+\texttt{Im}^{2}(X_{ij}))^{1/2}\leq R_{ij}$ for the
continuous case, or formulated as $M$ linear inequality constraints for the
discrete case.

Based on Theorems 2.1, Propositions 1 and 2, we can relax (CQP3) to the
following convex problem:

$\displaystyle\min{}$ $\displaystyle Q_{0}\cdot X$ (ECSDP1) s.t.
$\displaystyle Q_{i}\cdot X\leq b_{i},~{}i=1,\ldots,m,$ $\displaystyle
l_{i}^{2}\leq R_{ii}=X_{ii}\leq u^{2}_{i},~{}i=1,\ldots,n,$ $\displaystyle
X_{ij}\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij})),~{}\\{i,j\\}\in\mathcal{E},$
$\displaystyle(R_{ii},R_{jj},R_{ij})\in\textsf{Conv}(\mathcal{H}_{ij}),~{}\\{i,j\\}\in\mathcal{E},$
$\displaystyle X\succeq 0.$

In order to study the tightness of (ECSDP1), we further define the set

$\mathcal{F}_{ij}=\left\\{(X_{ii},X_{jj},R_{ij},X_{ij})\,\left|\,\begin{array}[]{@{}lll}l_{i}^{2}\leq
X_{ii}\leq u^{2}_{i}\\\ l_{j}^{2}\leq X_{jj}\leq u^{2}_{j}\\\
X_{ii}X_{jj}=R^{2}_{ij}=|X_{ij}|^{2}\\\
\arg(X_{ij})\in\mathcal{A}_{ij}\end{array}\right.\right\\}.$ (14)

We have the following theorem.

###### Theorem 2.2

Let $(X,R)$ be a feasible solution of (ECSDP1), then we have
$(X_{ii},X_{jj},R_{ij},X_{ij})\in\textsf{Conv}(\mathcal{F}_{ij})$ for any
$\\{i,j\\}\in\mathcal{E}$.

###### Proof

Since $(X_{ii},X_{jj},R_{ij})\in\textsf{Conv}(\mathcal{H}_{ij})$, there exist
a sequence of points

$(X^{t}_{ii},X^{t}_{jj},R^{t}_{ij})\in\mathcal{H}_{ij},~{}t=1,\ldots,r,$ (15)

such that

$(X_{ii},X_{jj},R_{ij})=\sum_{t=1}^{r}\lambda_{t}(X^{t}_{ii},X^{t}_{jj},R^{t}_{ij}),$
(16)

where $\lambda_{1},\ldots,\lambda_{r}\geq 0$ and
$\sum_{i=1}^{r}\lambda_{t}=1$. Similarly, since
$X_{ij}\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))$, there exist a sequence of
points

$X^{s}_{ij}\in\mathcal{G}_{ij}(R_{ij}),~{}s=1,\ldots,k,$ (17)

such that

$X_{ij}=\sum_{s=1}^{k}\alpha_{s}X^{s}_{ij},$ (18)

where $\alpha_{1},\ldots,\alpha_{k}\geq 0$ and $\sum_{s=1}^{k}\alpha_{s}=1$.
For each $s\in\\{1,\ldots,k\\}$, denote $\arg(X^{s}_{ij})$ by
$\theta^{s}_{ij}$, then we have $X^{s}_{ij}=R_{ij}e^{\texttt{i}\theta_{ij}}$.
Now, we construct the following points:

$(X^{t}_{ii},X^{t}_{jj},R^{t}_{ij},R^{t}_{ij}e^{\texttt{i}\theta^{s}_{ij}})\in\mathcal{F}_{ij},~{}s=1,\ldots,k,~{}t=1,\ldots,r.$
(19)

Then, we have that

$\sum_{t=1}^{r}\sum_{s=1}^{k}\lambda_{t}\alpha_{s}(X^{t}_{ii},X^{t}_{jj},R^{t}_{ij})=\sum_{t=1}^{r}\lambda_{t}(X^{t}_{ii},X^{t}_{jj},R^{t}_{ij})=(X_{ii},X_{jj},R_{ij}),$
(20)

and

$\sum_{s=1}^{k}\sum_{t=1}^{r}\lambda_{t}\alpha_{s}R^{t}_{ij}e^{\texttt{i}\theta^{s}_{ij}}=\sum_{s=1}^{k}\alpha_{s}\left(\sum_{t=1}^{r}\lambda_{t}R^{t}_{ij}\right)e^{\texttt{i}\theta^{s}_{ij}}=\sum_{s=1}^{k}\alpha_{s}R_{ij}e^{\texttt{i}\theta^{s}_{ij}}=X_{ij}.$
(21)

Following from (20) and (21), we have

$(X_{ii},X_{jj},R_{ij},X_{ij})=\sum_{s=1}^{k}\sum_{t=1}^{r}\lambda_{t}\alpha_{s}(X^{t}_{ii},X^{t}_{jj},R^{t}_{ij},R^{t}_{ij}e^{\texttt{i}\theta^{s}_{ij}}).$
(22)

Since

$\sum_{s=1}^{k}\sum_{t=1}^{r}\lambda_{t}\alpha_{s}=\sum_{s=1}^{k}\left(\sum_{t=1}^{r}\lambda_{t}\right)\alpha_{s}=\sum_{s=1}^{k}\alpha_{s}=1,$
(23)

Equation (22) implies that $(X_{ii},X_{jj},R_{ij},X_{ij})$ is the convex
combination of the $k\cdot r$ points defined in (19), thus
$(X_{ii},X_{jj},R_{ij},X_{ij})\in\textsf{Conv}(\mathcal{F}_{ij})$. ∎

In (ECSDP1), the variables $(R_{ii},R_{jj},R_{ij})$ are introduced to link the
connections between $(X_{ii},X_{jj})$ and $X_{ij}$ by the following
constraints:

$\displaystyle X_{ii}=R_{ii},~{}X_{jj}=R_{jj},$ (24) $\displaystyle
X_{ij}\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij})),$
$\displaystyle(R_{ii},R_{jj},R_{ij})\in\textsf{Conv}(\mathcal{H}_{ij}).$

In order to analyze whether the constraints in (24) can bridge a strong
connection between $(X_{ii},X_{jj})$ and $X_{ij}$, we project the set
$\mathcal{F}_{ij}$ onto the space of variables $(X_{ii},X_{jj},X_{ij})$ and
define the following set:

$\mathcal{J}_{ij}=\left\\{(X_{ii},X_{jj},X_{ij})\,\left|\,\begin{array}[]{@{}lll}l_{i}^{2}\leq
X_{ii}\leq u^{2}_{i}\\\ l_{j}^{2}\leq X_{jj}\leq u^{2}_{j}\\\
X_{ii}X_{jj}=|X_{ij}|^{2}\\\
\arg(X_{ij})\in\mathcal{A}_{ij}\end{array}\right.\right\\}.$ (25)

A direct consequence of Theorem 2.2 is the following theorem.

###### Theorem 2.3

Let $(X,R)$ be a feasible solution of (ECSDP1), then for any
$\\{i,j\\}\in\mathcal{E}$, we have

$(X_{ii},X_{jj},X_{ij})\in\textsf{Conv}(\mathcal{J}_{ij}).$ (26)

###### Proof

Based on equation (22) in the proof of Theorem 2.2, we can derive the equation
on the projected space of variables $(X_{ii},X_{jj},X_{ij})$ as follows:

$(X_{ii},X_{jj},X_{ij})=\sum_{s=1}^{k}\sum_{t=1}^{r}\lambda_{t}\alpha_{s}(X^{t}_{ii},X^{t}_{jj},R^{t}_{ij}e^{\texttt{i}\theta^{s}_{ij}}),$
(27)

where

$(X^{t}_{ii},X^{t}_{jj},R^{t}_{ij}e^{\texttt{i}\theta^{s}_{ij}})\in\mathcal{J}_{ij},~{}s=1,\ldots,k,~{}t=1,\ldots,r.$
(28)

Thus we have

$(X_{ii},X_{jj},X_{ij})\in\textsf{Conv}(\mathcal{J}_{ij}).$

∎

Theorem 2.3 shows that by introducing the constraints in (24) into (ECSDP1),
the variables $(X_{ii},X_{jj})$ and $X_{ij}$ are strongly connected, in the
sense that for any feasible solution $(X,R)$ of (ECSDP1), we have
$(X_{ii},X_{jj},X_{ij})\in\textsf{Conv}(\mathcal{J}_{ij})$ for any
$\\{i,j\\}\in\mathcal{E}$. Thus, the convex hull of $\mathcal{J}_{ij}$ is
described by the constraints in (ECSDP1) exactly. Based on the above analysis,
we may expect that (ECSDP1) can be tighter than (CSDP). Note that
$\mathcal{J}_{ij}$ is equivalent to the set $\mathcal{J}_{ij}^{x}$ defined in
Section 1. The convex hull of $\mathcal{J}_{ij}^{x}$ is described exactly for
general cases of (CQP) with different types of $\mathcal{A}_{ij}$.

##  3 Comparisons with existing semidefinite relaxations

Besides of the proposed semidefinite relaxation (ECSDP1), some previous papers
including Chen2016 ; Lu2018 ; Lu2020  have also discussed how to exploit the
structure of the phase angle constraints in (CQP) to derive tight semidefinite
relaxations. In this section, we discuss the relationship between (ECSDP1) and
the existing ones in Chen2016 ; Lu2018 ; Lu2020 .

###  3.1 Comparison with the semidefinite relaxation in Chen2016

We first discuss the connections between (ECSDP1) and the semidefinite
relaxation proposed in Chen2016 . Consider the following continuous case of
(CQP):

$\displaystyle\min{}$ $\displaystyle x^{{\dagger}}Q_{0}x$ (29) s.t.
$\displaystyle x^{{\dagger}}Q_{i}x\leq b_{i},~{}i=1,\ldots,m,$ $\displaystyle
l_{i}\leq{|}x_{i}{|}\leq u_{i},~{}i=1,\ldots,n,$
$\displaystyle\arg(x_{i}{x_{j}}^{{\dagger}})\in[\underline{\theta}_{ij},\bar{\theta}_{ij}],~{}\\{i,j\\}\in\mathcal{E},$

where $-\pi/2<\underline{\theta}_{ij}<\bar{\theta}_{ij}<\pi/2$. Using the
notations in Chen2016 , the lifted matrix $X$ is represented as
$X=W+\texttt{i}T$, and the following set is defined:

$\mathcal{J}_{C}=\left\\{(W_{ii},W_{jj},W_{ij},T_{ij})\,\left|\,\begin{array}[]{@{}lll}&l_{i}^{2}\leq
W_{ii}\leq u^{2}_{i}\\\ &l_{j}^{2}\leq W_{jj}\leq u^{2}_{j}\\\
&L_{ij}W_{ij}\leq T_{ij}\leq U_{ij}W_{ij}\\\
&W_{ii}W_{jj}=W^{2}_{ij}+T^{2}_{ij}\end{array}\right.\right\\},$ (30)

where $L_{ij}=\tan\underline{\theta}_{ij}$ and $U_{ij}=\tan\bar{\theta}_{ij}$.
It is easy to check that the set $\mathcal{J}_{ij}$ defined in (25) is
equivalent to the set $\mathcal{J}_{C}$ under the relationship

$(X_{ii},X_{jj},X_{ij})=(W_{ii},W_{jj},W_{ij}+\texttt{i}T_{ij}).$

In order to describe the convex hull of $\mathcal{J}_{C}$, Chen et al. first
relax $\mathcal{J}_{C}$ to the set defined by the following inequalities:

$\displaystyle l_{i}^{2}\leq W_{ii}\leq u^{2}_{i},$ (31) $\displaystyle
l_{j}^{2}\leq W_{jj}\leq u^{2}_{j},$ $\displaystyle L_{ij}W_{ij}\leq
T_{ij}\leq U_{ij}W_{ij},$ $\displaystyle W_{ii}W_{jj}\geq
W^{2}_{ij}+T^{2}_{ij}.$

Then, they derive the following valid inequalities for $\mathcal{J}_{C}$:

$\displaystyle\pi^{3}_{ij}W_{ij}+\pi^{4}_{ij}T_{ij}\geq(l_{j}^{2}+l_{j}u_{j})W_{ii}+(l_{i}^{2}+l_{i}u_{i})W_{jj}+l_{i}l_{j}u_{i}u_{j}-l_{i}^{2}l_{j}^{2},$
(32)
$\displaystyle\pi^{3}_{ij}W_{ij}+\pi^{4}_{ij}T_{ij}\geq(u_{j}^{2}+l_{j}u_{j})W_{ii}+(u_{i}^{2}+l_{i}u_{i})W_{jj}+l_{i}l_{j}u_{i}u_{j}-u_{i}^{2}u_{j}^{2},$

where

$\displaystyle\pi_{ij}^{3}=(l_{i}+u_{i})(l_{j}+u_{j})\frac{1-f(L_{ij})f(U_{ij})}{1+f(L_{ij})f(U_{ij})},$
(33)
$\displaystyle\pi_{ij}^{4}=(l_{i}+u_{i})(l_{j}+u_{j})\frac{f(L_{ij})+f(U_{ij})}{1+f(L_{ij})f(U_{ij})},$

and $f(\cdot)$ is defined as

$\displaystyle
f(t):=\left\\{\begin{array}[]{@{}ll}(\sqrt{1+t^{2}}-1)/t,{}&\textrm{if}~{}t\neq
0,\\\ 0,{}&\textrm{if}~{}t=0.\end{array}\right.$ (34)

We cite the following results from Chen2016  (see Propositions 2 and 3 in
Chen2016 ).

######  Theorem 3.1 (Chen2016 )

For any $\\{i,j\\}\in\mathcal{E}$, the system of inequalities in (32) is valid
for $\mathcal{J}_{C}$. Moreover, we have

$\textsf{Conv}(\mathcal{J}_{C})=\\{(W_{ii},W_{jj},W_{ij},T_{ij})\,|\,(W_{ii},W_{jj},W_{ij},T_{ij})\textrm{~{}satisfies
}\eqref{eq3}~{}\textrm{and}~{}\eqref{eq4}\\}.$

Based on Theorem 3.1, Chen et al. have proposed the following semidefinite
relaxation (named as SDP+complex valid inequalities (3a) and (3b) in Chen2016
):

$\displaystyle\min{}$ $\displaystyle Q_{0}\cdot X$ (ECSDP2) s.t.
$\displaystyle Q_{i}\cdot X\leq b_{i},~{}i=1,\ldots,m,$ $\displaystyle
l_{i}^{2}\leq W_{ii}\leq u^{2}_{i},~{}i=1,\ldots,n,$
$\displaystyle(W_{ii},W_{jj},W_{ij},T_{ij})\textrm{~{}satisfies
}\eqref{eq4},~{}\\{i,j\\}\in\mathcal{E},$ $\displaystyle L_{ij}W_{ij}\leq
T_{ij}\leq U_{ij}W_{ij},~{}\\{i,j\\}\in\mathcal{E},$ $\displaystyle
X=W+\texttt{i}T\succeq 0.$

We have the next theorem.

###### Theorem 3.2

The two semidefinite relaxations (ECSDP1) and (ECSDP2) are equivalent under
the assumptions that
$\mathcal{A}_{ij}=[\underline{\theta}_{ij},\bar{\theta}_{ij}]$ and
$-\pi/2<\underline{\theta}_{ij}<\bar{\theta}_{ij}<\pi/2$ for all
$\\{i,j\\}\in\mathcal{E}$.

###### Proof

We first assume that $(X,R)$ is a feasible solution of (ECSDP1). Letting
$W=\texttt{Re}(X)$ and $T=\texttt{Im}(X)$. Then based on Theorem 2.3, for any
$\\{i,j\\}\in\mathcal{E}$, we have
$(X_{ii},X_{jj},X_{ij})\in\textsf{Conv}(\mathcal{J}_{ij})$, which implies
$(W_{ii},W_{jj},W_{ij},T_{ij})\in\textsf{Conv}(\mathcal{J}_{C})$. Thus
$(W_{ii},W_{jj},W_{ij},T_{ij})$ satisfies (31) and (32) for
$\\{i,j\\}\in\mathcal{E}$, and $X=W+\texttt{i}T$ is feasible to (ECSDP2).

Next, we assume that $X=W+\texttt{i}T$ is a feasible solution to (ECSDP2).
Then for any $\\{i,j\\}\in\mathcal{E}$, based on Theorem 3.1, we have
$(W_{ii},W_{jj},W_{ij},T_{ij})\in\textsf{Conv}(\mathcal{J}_{C})$, which
implies $(X_{ii},X_{jj},X_{ij})\in\textsf{Conv}(\mathcal{J}_{ij})$. Then,
there exist a sequence of points

$(X^{t}_{ii},X^{t}_{jj},X^{t}_{ij})\in\mathcal{J}_{ij},~{}t=1,\ldots,k,$ (35)

such that

$(X_{ii},X_{jj},X_{ij})=\sum_{t=1}^{k}\lambda_{t}(X^{t}_{ii},X^{t}_{jj},X^{t}_{ij}),$
(36)

where $\lambda_{t}\geq 0$ for $t=1,\ldots,k$ and
$\sum_{t=1}^{k}\lambda_{t}=1$. We expand the feasible solution $X$ to a
feasible solution $(X,R)$ to (ECSDP1) as follows: For each
$i\in\\{1,\ldots,n\\}$, let $R^{t}_{ii}=|X^{t}_{ii}|$ for $t=1,\ldots,k$, and
$R_{ii}=\sum_{t=1}^{k}\lambda_{t}R^{t}_{ii}$. Similarly, for each
$\\{i,j\\}\in\mathcal{E}$, we assign
$R_{ij}=\sum_{t=1}^{k}\lambda_{t}R^{t}_{ij}$, where $R^{t}_{ij}=|X^{t}_{ij}|$.
Based on the above constructions, we can check that
$(R^{t}_{ii},R^{t}_{jj},R^{t}_{ij})\in\mathcal{H}_{ij}$ for all
$t=1,\ldots,k$, so we have

$(R_{ii},R_{jj},R_{ij})=\sum_{t=1}^{k}\lambda_{t}(R^{t}_{ii},R^{t}_{jj},R^{t}_{ij})\in\textsf{Conv}(\mathcal{H}_{ij}).$
(37)

Meanwhile, we have

$X_{ij}=\sum_{t=1}^{k}\lambda_{t}X^{t}_{ij}=\sum_{t=1}^{k}\frac{\lambda_{t}R^{t}_{ij}}{R_{ij}}R_{ij}e^{\texttt{i}\arg(X^{t}_{ij})}.$
(38)

Since

$\sum_{t=1}^{k}\frac{\lambda_{t}R^{t}_{ij}}{R_{ij}}=1,$ (39)

Equations (38) and (39) together imply that $X_{ij}$ is a convex combination
of the points
$R_{ij}e^{\texttt{i}\arg(X^{t}_{ij})}\in\mathcal{G}_{ij}(R_{ij})$, thus

$X_{ij}\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij})).$ (40)

Then, the feasibility of $X$ to (ECSDP2), together with (37) and (40), implies
that $(X,R)$ is feasible to (ECSDP1).

Based on the above discussions, we conclude that $X=W+\texttt{i}T$ is feasible
to (ECSDP2) if and only if there exists a matrix $R$ such that $(X,R)$ is
feasible to (ECSDP1), and the two feasible solutions have the same objective
value. Thus the two problems are equivalent. ∎

Theorem 3.2 shows that when
$\mathcal{A}_{ij}=[\underline{\theta}_{ij},\bar{\theta}_{ij}]\subseteq(-\pi/2,\pi/2)$
for all $\\{i,j\\}\in\mathcal{E}$, the two relaxations (ECSDP1) and (ECSDP2)
are equivalent. The main difference between the two relaxations is that the
convex hull of $\mathcal{J}_{C}$ in (ECSDP2) does not introduce the matrix $R$
to link variables $(X_{ii},X_{jj})$ and $X_{ij}$, so that (ECSDP2) can be more
compact than (ECSDP1). However, for general cases of $\mathcal{A}_{ij}$, it is
not easy to derive the convex hull of $\mathcal{J}_{ij}$ directly. In these
cases, it is very meaningful to introduce the matrix $R$ to link the
connections between $(X_{ii},X_{jj})$ and $X_{ij}$, from which we may derive
the convex hull of $\mathcal{J}_{ij}$ easily. Hence, (ECSDP1) is more general
than (ECSDP2), in the sense that it can be applied to general cases of (CQP)
with different types of $\mathcal{A}_{ij}$. Moreover, even for the case in
which $\mathcal{A}_{ij}\subseteq(-\pi/2,\pi/2)$ for all
$\\{i,j\\}\in\mathcal{E}$, introducing the real matrix $R$ is also helpful,
since we may further enhance (ECSDP1) by adding a new constraint $R\succeq 0$.
We will discuss the effects of adding $R\succeq 0$ to (ECSDP1) in the next
section.

###  3.2 Comparison with the semidefinite relaxation in Lu2020

Next, we analyze the relationship between (ECSDP1) and the enhanced
semidefinite relaxation proposed in Lu2020 , which includes the semidefinite
relaxation proposed in Lu2018  as a special case. In Lu2020 , Lu et al. have
studied the following nonhomogeneous quadratic programming problem:

$\displaystyle\min{}$
$\displaystyle\frac{1}{2}x^{{\dagger}}Q_{0}x+\texttt{Re}(c^{\dagger}x)$ (41)
$\displaystyle l_{i}\leq{|}x_{i}{|}\leq u_{i},~{}i=1,\ldots,n,$
$\displaystyle\arg(x_{i})\in\mathcal{A}_{i}\subseteq[0,2\pi],~{}i=1,\ldots,n.$

The enhanced semidefinite relaxation introduced in Lu2020  is defined as
follows:

$\displaystyle\min{}$ $\displaystyle\frac{1}{2}Q_{0}\cdot
X+\texttt{Re}(c^{\dagger}x)$ (ECSDP3) $\displaystyle l_{i}\leq r_{i}\leq
u_{i},~{}i=1,\ldots,n,$ $\displaystyle
x_{i}\in\textsf{Conv}(\mathcal{G}_{i}(r_{i})),~{}i=1,\ldots,n,$ $\displaystyle
X_{ii}\geq r_{i}^{2},~{}X_{ii}-(l_{i}+u_{i})r_{i}+l_{i}u_{i}\leq
0,~{}i=1,\ldots,n,$ $\displaystyle X\succeq xx^{\dagger},$

where
$\mathcal{G}_{i}(r_{i}):=\\{x_{i}\,|\,r_{i}=|x_{i}|,\arg(x_{i})\in\mathcal{A}_{i}\\}$
for $r_{i}>0$ and $\mathcal{G}_{i}(0)=\\{0\\}$. To show the connections
between (ECSDP3) and (ECSDP1), we first transform (41) to a homogeneous
problem by appending $x_{n+1}=1$ to the vector $x\in\mathbb{C}^{n}$ to
construct an $(n+1)$-dimensional vector $y$, and derive the following problem:

$\displaystyle\min{}$ $\displaystyle\frac{1}{2}y^{{\dagger}}\tilde{Q}_{0}y$
(42) $\displaystyle l_{i}\leq{|}y_{i}{|}\leq u_{i},~{}i=1,\ldots,n,$
$\displaystyle\arg(y_{i}y_{n+1}^{\dagger})\in\mathcal{A}_{i},~{}i=1,\ldots,n,$
$\displaystyle y_{n+1}=1,$

where

$\displaystyle\tilde{Q}_{0}=\begin{bmatrix}Q_{0}~{}&c\\\ c^{{\dagger}}~{}&0\\\
\end{bmatrix}\in\mathbb{C}^{(n+1)\times(n+1)}.$

Then, (ECSDP1) for (42) is formulated as follows:

$\displaystyle\min{}$ $\displaystyle\frac{1}{2}\tilde{Q}_{0}\cdot Y$ (ECSDP4)
$\displaystyle l^{2}_{i}\leq Y_{ii}\leq u^{2}_{i},~{}i=1,\ldots,n,$
$\displaystyle Y_{i,n+1}\in\textsf{Conv}(\mathcal{G}_{i,n+1}(R_{i,n+1})),$
$\displaystyle Y_{ii}\geq
R_{i,n+1}^{2},~{}Y_{i,i}-(l_{i}+u_{i})R_{i,n+1}+l_{i}u_{i}\leq
0,~{}i=1,\ldots,n,$ $\displaystyle Y_{n+1,n+1}=1,~{}Y\succeq 0,$

where the inequality $Y_{i,i}-(l_{i}+u_{i})R_{i,n+1}+l_{i}u_{i}\leq 0$ is
derived from (4) and (5) with $l_{n+1}=u_{n+1}=1$. Then we have the next
theorem.

###### Theorem 3.3

Problem (ECSDP4) is equivalent to (ECSDP3).

###### Proof

Consider the following correspondence relationship between the solutions of
(ECSDP3) and (ECSDP4):

$\displaystyle Y=\begin{bmatrix}X~{}&x\\\ x^{{\dagger}}~{}&1\\\
\end{bmatrix},$ (43) $\displaystyle r_{i}=R_{i,n+1},~{}i=1,\ldots,n.$

It is easy to check that $(Y,R)$ is feasible to (ECSDP4) if and only if the
corresponding solution $(X,x,r)$ is feasible to (ECSDP3), and the two
solutions have the same objective value. Thus, the two problems are
equivalent. ∎

Theorem 3.3 shows the equivalence between (ECSDP3) and (ECSDP4). Moreover, the
following theorem shows that (ECSDP3) is also equivalent to (CSDP) on certain
cases of (41).

###### Theorem 3.4

For problem (41), under the assumptions that $c=0$ and
$0\in\textsf{Conv}(\mathcal{G}_{i}(r_{i}))$ for any $r_{i}\geq 0$, (ECSDP3) is
equivalent to (CSDP).

###### Proof

Since (ECSDP3) is equivalent to (ECSDP4), it is at least as tight as (CSDP).
On the other hand, under the given assumptions, let $X^{*}$ be the optimal
solution of (CSDP), we can always extend it to a solution
$(X^{*},x^{*},r^{*})$ of (ECSDP3) by assigning $x_{i}^{*}=0$ and
$r^{*}_{i}=(X^{*}_{ii})^{1/2}$ for $i=1,\ldots,n$, and the two solutions have
the same objective value when $c=0$. Thus (ECSDP3) is equivalent to (CSDP). ∎

Theorem 3.4 shows that for certain types of homogeneous quadratic programming
problems, both the semidefinite relaxations (ECSDP3) and (ECSDP4) can not be
tighter than the conventional semidefinite relaxation (CSDP). In many
applications in signal processing Demir2014 ; Demir2015 ; Maio2009 , the
problem is just the case that satisfies the assumptions in Theorem 3.4.
However, (ECSDP4) is only a special case of (ECSDP1) for which the set
$\mathcal{E}$ is predefined as

$\mathcal{E}=\\{\\{1,n+1\\},\ldots,\\{n,n+1\\}\\}.$

In fact, we may select some other sets $\mathcal{E}$ to define (ECSDP1), by
which it is possible to derive a semidefinite relaxation that is tighter than
(ECSDP4). For example, for the case that $\mathcal{A}_{i}=\mathcal{A}^{M}$ for
all $i=1,\ldots,n$, where $M\geq 3$, the constraints
$\arg(x_{i})\in\mathcal{A}^{M}$ for $i=1,\ldots,n$ imply that
$\arg(x_{i}x_{j}^{\dagger})\in\mathcal{A}^{M}$ for any $1\leq i<j\leq n$.
Hence, we may select $\mathcal{E}$ as any subset of $\\{\\{i,j\\}\,|\,1\leq
i<j\leq n+1\\}$ to define (ECSDP1). As will be illustrated in the numerical
experiments in Section 5, (ECSDP1) can still be much tighter than (CSDP) on
the homogeneous cases even when the assumptions in Theorem 3.4 are satisfied,
if the set $\mathcal{E}$ is well selected.

##  4 Further discussions on the enhanced semidefinite relaxation

(ECSDP1) can be further enhanced by introducing a new positive semidefinite
constraint $R\succeq 0$. In this section, we define the following enhanced
semidefinite relaxation to analyze the effects of introducing $R\succeq 0$
into (ECSDP1).

$\displaystyle\min{}$ $\displaystyle Q_{0}\cdot X$ (ECSDP) s.t. $\displaystyle
Q_{i}\cdot X\leq b_{i},~{}i=1,\ldots,m,$ $\displaystyle l_{i}^{2}\leq
R_{ii}=X_{ii}\leq u^{2}_{i},~{}i=1,\ldots,n,$ $\displaystyle
X_{ij}\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij})),~{}\\{i,j\\}\in\mathcal{E},$
$\displaystyle(R_{ii},R_{jj},R_{ij})~{}\textrm{satisfies \eqref{eq1} and
\eqref{eq2}},~{}\\{i,j\\}\in\mathcal{E},$ $\displaystyle X\succeq
0,~{}R\succeq 0.$

Note that since the constraint $R\succeq 0$ implies the constraints
$R_{ij}^{2}\leq R_{ii}R_{jj}$ for all $\\{i,j\\}\in\mathcal{E}$, the latter
constraints can be ignored after adding $R\succeq 0$ into (ECSDP1) to derive
the formulation of (ECSDP). However, in the converse direction, since the
constraints $R_{ij}^{2}\leq R_{ii}R_{jj}$ for all $\\{i,j\\}\in\mathcal{E}$ do
not imply $R\succeq 0$, (ECSDP) can be tighter than (ECSDP1) for some
instances of (CQP). The following example demonstrates this claim.

Consider the following $3$-dimensional instance of (CQP):

$\displaystyle\min{}$ $\displaystyle x^{\dagger}Q_{0}x$ (44) s.t.
$\displaystyle 1\leq|x_{i}|\leq 4,~{}i=1,2,3,$
$\displaystyle\arg(x_{i}^{{\dagger}}x_{j})\in[-\pi/6,\pi/6],~{}\\{i,j\\}\in\mathcal{E},$

where

$\displaystyle Q_{0}=\begin{bmatrix}-2~{}&-4~{}&0\\\ -4~{}&2~{}&-2\\\
0~{}&-2~{}&6\\\ \end{bmatrix}+\texttt{i}\cdot\begin{bmatrix}0~{}&-8~{}&1\\\
8~{}&0~{}&-10\\\ -1~{}&10~{}&0\\\ \end{bmatrix}$ (45)

and $\mathcal{E}=\\{\\{i,j\\}\,|\,1\leq i<j\leq 3\\}$. A direct computation
shows that the optimal values of (ECSDP1) and (ECSDP2) are both equal to
$-248.39$, whereas the optimal value of (ECSDP) is $-248.15$. The absolute
difference between the optimal values of (ECSDP) and (ECSDP1) is $0.24$.
Hence, the proposed relaxation (ECSDP) is strictly tighter than the
semidefinite relaxations (ECSDP1) and (ECSDP2).

When deriving the formulation (ECSDP) from (ECSDP1), the second-order cone
constraints of the form $R_{ii}R_{jj}\geq R^{2}_{ij}$ have been dropped. In
fact, under certain conditions, more constraints can be dropped to simplify
(ECSDP). We consider two such cases based on the next theorem.

###### Theorem 4.1

For a pair of $\\{i,j\\}\in\mathcal{E}$, if

$0\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))$

for all $R_{ij}\geq 0$, then

$\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))\subseteq\textsf{Conv}(\mathcal{G}_{ij}(R^{\prime}_{ij}))$
(46)

holds for any $0\leq R_{ij}<R^{\prime}_{ij}$.

###### Proof

For the case of $R_{ij}=0$, we have
$\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))=\\{0\\}$. Then (46) holds under the
condition $0\in\textsf{Conv}(\mathcal{G}_{ij}(R^{\prime}_{ij}))$. Now we
consider the case of $R_{ij}>0$. For any
$X_{ij}\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))$, there exist a sequence of
points

$X^{t}_{ij}\in\mathcal{G}_{ij}(R_{ij}),~{}\lambda_{t}\geq 0,~{}t=1,\ldots,k,$
(47)

such that

$X_{ij}=\sum_{t=1}^{k}\lambda_{t}X^{t}_{ij}~{}\textrm{and}~{}\sum_{i=1}^{t}\lambda_{t}=1.$
(48)

For any $R^{\prime}_{ij}>R_{ij}$, by the definition of
$\mathcal{G}_{ij}(R^{\prime}_{ij})$, it is easy to check that

$R^{\prime}_{ij}X^{t}_{ij}/R_{ij}\in\mathcal{G}_{ij}(R^{\prime}_{ij}).$ (49)

Then,

$R^{\prime}_{ij}X_{ij}/R_{ij}=\sum_{t=1}^{k}\lambda_{t}R^{\prime}_{ij}X^{t}_{ij}/R_{ij}\in\textsf{Conv}(\mathcal{G}_{ij}(R^{\prime}_{ij})).$
(50)

Equation (50) and the condition
$0\in\textsf{Conv}(\mathcal{G}_{ij}(R^{\prime}_{ij}))$ together imply that
$X_{ij}\in\textsf{Conv}(\mathcal{G}_{ij}(R^{\prime}_{ij}))$, since $X_{ij}$ is
on the line segment which connects $0$ and $R^{\prime}_{ij}X_{ij}/R_{ij}$ when
$R^{\prime}_{ij}>R_{ij}$. This completes the proof. ∎

###### Remark 1

The condition $0\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))$ holds for any
$R_{ij}\geq 0$ if and only if there exists a $\tilde{R}_{ij}>0$ such that
$0\in\textsf{Conv}(\mathcal{G}_{ij}(\tilde{R}_{ij}))$.

Based on Theorem 4.1, we can show that inequalities (4) and (5) are redundant
in (ECSDP) when $0\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))$ for any
$R_{ij}\geq 0$, in the sense that the projection of the feasible domain of
(ECSDP) onto the space of $X$ is not affected by these inequalities. More
specifically, the inequalities in (4) and (5) constrain $R_{ij}$ from below,
and the inequality $R_{ii}R_{jj}\geq R^{2}_{ij}$ constrains $R_{ij}$ from
above, which provides an upper bound $\bar{R}_{ij}:=(R_{ii}R_{jj})^{1/2}$ of
$R_{ij}$. Under the conditions in Theorem 4.1, the equation

$\bigcup_{R_{ij}\in[\underline{R}_{ij},\bar{R}_{ij}]}\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))=\textsf{Conv}(\mathcal{G}_{ij}(\bar{R}_{ij}))$

holds for any $0\leq\underline{R}_{ij}\leq\bar{R}_{ij}$. Thus, dropping the
inequalities (4) and (5), only the lower bound of $R_{ij}$ is affected, but
the upper bound $\bar{R}_{ij}$ does not change, so that the range of $X_{ij}$
is unchanged. Based on the above discussions, we simplify (ECSDP) for the
following two cases.

Case 1: $\mathcal{A}_{ij}=\mathcal{A}^{M}$ for all $\\{i,j\\}\in\mathcal{E}$
where $M\geq 3$. In this case, we can see that
$0\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))$ holds for any $R_{ij}\geq 0$.
Hence, based on Theorem 4.1, we can drop the constraints defined by
inequalities (4) and (5) to simplify (ECSDP).

Case 2: $\mathcal{A}_{ij}=[\underline{\theta}_{ij},\bar{\theta}_{ij}]$ with
$\pi\leq\bar{\theta}_{ij}-\underline{\theta}_{ij}<2\pi$ for all
$\\{i,j\\}\in\mathcal{E}$. In this case, we also have
$0\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))$. Then, based on Theorem 4.1,
constraints (4) and (5) can be dropped. In addition, based on Theorem 4.1
again, the constraints $|X_{ij}|\leq R_{ij}$ for $\\{i,j\\}\in\mathcal{E}$ can
be dropped. In detail, let $(\hat{X},\hat{R})$ be the optimal solution to
(ECSDP) with constraints (4), (5) and constraints $|X_{ij}|\leq R_{ij}$ for
$\\{i,j\\}\in\mathcal{E}$ being dropped. Since the inequalities
$|\hat{X}_{ij}|\leq(\hat{X}_{ii}\hat{X}_{jj})^{1/2}$ holds automatically under
the constraint $\hat{X}\succeq 0$, we can construct another solution
$(\hat{X},R^{\prime})$ by assigning the entries of $R^{\prime}$ to
$R^{\prime}_{ij}=(X_{ii}X_{jj})^{1/2}$. Then, it is easy to check
$(\hat{X},R^{\prime})$ is feasible to (ECSDP) in its original version. Hence,
the constraints $|X_{ij}|\leq R_{ij}$ for $\\{i,j\\}\in\mathcal{E}$ can be
dropped without affecting the optimal value of (ECSDP).

In our numerical experiment, in order to reduce the computational complexity,
we always simplify (ECSDP) according to the types of the phase angle
constraints for a variety of (CQP) arising in different application
backgrounds.

##  5 Numerical results

We carry out numerical experiments to investigate the tightness of the
proposed semidefinite relaxation (ECSDP). Our test instances are randomly
generated to simulate some practical applications in signal processing. The
experiments are carried out on a personal computer with Intel Core(TM) i7-9700
CPU (3.00 GHz) and 16 GB RAM. We use Mosek (Ver 9.2) mosek  to solve all
semidefinite relaxations. All algorithms are implemented in Matlab R2017a. For
all the three problems discussed in the following subsections, the set
$\mathcal{E}$ is always set to $\mathcal{E}=\\{\\{i,j\\}\,|\,1\leq i<j\leq
n\\}$.

###  5.1 Phase quantized waveform design

We consider the phase quantized waveform design problem with constraints on
peak to average ratio (ref. Maio2011 ). The problem can be formulated as
follows:

$\displaystyle\max{}$ $\displaystyle x^{{\dagger}}Qx$ (51) s.t. $\displaystyle
x^{{\dagger}}x=n,$ $\displaystyle{|}x_{i}{|}^{2}\leq\gamma,~{}i=1,\ldots,n,$
$\displaystyle\arg(x_{i})\in\mathcal{A}^{M},~{}i=1,\ldots,n,$

where the meaning of parameters $Q,~{}n,~{}\gamma,~{}M$ and the decision
variables $x_{1},\ldots,x_{n}$ are described in Maio2011 . Based on the
discussions in Section 4, relaxation (ECSDP) for (51) can be simplified as
follows:

$\displaystyle\max{}$ $\displaystyle Q\cdot X$ (52) s.t.
$\displaystyle\texttt{Trace}(X)=n,$ $\displaystyle
X_{ii}=R_{ii}\leq\gamma,~{}i=1,\ldots,n,$ $\displaystyle
X_{ij}\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij})),~{}\\{i,j\\}\in\mathcal{E},$
$\displaystyle X\succeq 0,~{}R\succeq 0,$

where the constraint $X_{ij}\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))$ is
described in (12). Besides, the classical semidefinite relaxation (CSDP) of
(51) can be obtained by dropping the constraint
$X_{ij}\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))$ for
$\\{i,j\\}\in\mathcal{E}$ in (52). In Maio2011 , Maio et al. have applied
(CSDP) to design an approximation algorithm.

In our experiments, we compare (ECSDP) with (CSDP) from two aspects: First, we
investigate whether (ECSDP) can be much tighter than (CSDP). Second, we
investigate whether the approximation algorithm proposed in Maio2011  can be
improved to find better sub-optimal solutions by using (ECSDP) rather than
(CSDP).

The numerical experiments are carried out as follows: we use ten randomly
generated test instances, in each of which the matrix $Q\in\mathbb{C}^{n\times
n}$ is generated using the procedures in Soltanalian :
$Q=\sum_{k=1}^{n}u_{k}u_{k}^{\dagger}$, where $u_{k}$, $k=1,\ldots,n$, is a
random vector in $\mathbb{C}^{n}$ whose real-part and imaginary-part elements
are independently sampled from the standard Gaussian distribution. The
parameter $\gamma$ is set to $1.2$. We consider the cases of $n=20$ and
$M\in\\{3,6\\}$. For each test instance, we solve the relaxations (CSDP) and
(ECSDP) to estimate upper bounds (UB in short) for (51). Based on the optimal
solutions of the two relaxations, we run the approximation algorithm proposed
in Maio2011  to obtain sub-optimal solutions, whose objective values provide
lower bounds (LB in short) for (51). The lower and uppder bounds obtained from
the two relaxations are listed in Table 1, along with the computational time
(in seconds) for solving different semidefinite relaxations. Finally, we
define the “Gap Closed” as111In the literature, the term “gap” means the
difference between the optimal value of an optimization problem and its
lower/upper bound. Here we borrow the term “gap” for convenience, but the
meaning is different.

$\textrm{Gap
Closed}=1-\frac{\textrm{UB}_{\textrm{ECSDP}}-\textrm{LB}_{\textrm{ECSDP}}}{\textrm{UB}_{\textrm{CSDP}}-\textrm{LB}_{\textrm{CSDP}}},$
(53)

where $\textrm{LB}_{(\bullet)}$ and $\textrm{UB}_{(\bullet)}$ denote the lower
and upper bounds obtained from the corresponding relaxation method,
respectively. The results of Gap Closed are listed in the last column of Table
1.

Table 1: Computational results on instances of Problem (51). Instance | CSDP | ECSDP | Gap
---|---|---|---
ID | $(n,M)$ | UB | LB | Time | UB | LB | Time | Closed
1 | (20,3) | 1094.58 | 1044.10 | 0.16 | 1071.85 | 1050.14 | 0.31 | 57%
2 | (20,3) | 1125.75 | 1063.21 | 0.17 | 1078.46 | 1071.90 | 0.32 | 90%
3 | (20,3) | 1137.79 | 1079.27 | 0.16 | 1103.90 | 1081.97 | 0.32 | 63%
4 | (20,3) | 1073.05 | 1015.17 | 0.17 | 1049.16 | 1020.37 | 0.32 | 50%
5 | (20,3) | 1134.78 | 1040.75 | 0.16 | 1084.89 | 1057.29 | 0.31 | 71%
6 | (20,6) | 1130.19 | 1025.88 | 0.16 | 1124.07 | 1031.64 | 0.59 | 11%
7 | (20,6) | 1115.55 | 1033.44 | 0.17 | 1112.86 | 1040.41 | 0.63 | 12%
8 | (20,6) | 1106.84 | 1020.79 | 0.17 | 1103.74 | 1040.53 | 0.65 | 27%
9 | (20,6) | 1126.50 | 1024.32 | 0.17 | 1113.95 | 1028.55 | 0.62 | 16%
10 | (20,6) | 1122.23 | 1045.24 | 0.17 | 1110.84 | 1048.37 | 0.60 | 19%

From the results listed in Table 1, we can see that the upper bounds provided
by (ECSDP) are consistently tighter than the bounds of (CSDP) on all test
instances. For the case of $M=3$, the improvement on closing gaps is
significant. In fact, the set $\mathcal{A}^{M}$ can be regarded as a discrete
approximation of the set $[0,2\pi]$. Hence, for the case that $M$ is small,
the constraint $X_{ij}\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij}))$ can be more
effective for reducing the gap. As $M$ becomes larger, the difference between
the optimal values of (ECSDP) and (CSDP) tends to zero. That is why the
tightness of the upper bounds can be improved more significantly on the case
of $M=3$ than on the case of $M=6$.

On the other hand, for all the ten test instances, the lower bounds obtained
by using (ECSDP) are larger than the lower bounds obtained by using (CSDP).
These results imply that by using (ECSDP) for the approximation algorithm,
better sub-optimal solutions can be found.

The improvement on the upper and lower bounds are not obtained for free. As we
may observe that the computational time for solving (ECSDP) is longer than the
one for (CSDP). This is reasonable since the number of variables and the
number of constraints in (ECSDP) are both larger than those of (CSDP).

In conclusion, using (ECSDP) to replace (CSDP) for problem (51), we may obtain
better upper bounds and better sub-optimal solutions, with the cost of higher
computation complexity. Moreover, we would like to mention that problem (51)
is a homogeneous case of (CQP) that satisfies the assumptions in Theorem 3.4,
hence the semidefinite relaxation proposed in Lu2020  can not be tighter than
(CSDP).

###  5.2 Discrete transmit beamforming

In this subsection, we consider the discrete transmit beamforming problem,
which can be formulated as follows (ref. Demir2015 ):

$\displaystyle\max_{t,x}{}$ $\displaystyle t$ (54) s.t. $\displaystyle
x^{{\dagger}}Q_{i}x\geq t\gamma_{k}\sigma_{k}^{2},~{}i=1,\ldots,k,$
$\displaystyle x^{{\dagger}}x\leq P_{\textrm{tot}},$
$\displaystyle{|}x_{i}{|}\in\\{\Delta,2\Delta,\ldots,2^{m}\Delta\\},~{}i=1,\ldots,n,$
$\displaystyle\arg(x_{i})\in\mathcal{A}^{M},i=1,\ldots,n,$

where $Q_{i}=h_{i}h_{i}^{\dagger}$ with $h_{i}\in\mathbb{C}^{n}$ being the
channel vector for each $i=1,\ldots,k$, $n$ is the number of transmit
antennas, $k$ is the number of receivers, $m$ is the number of bits to
represent the discrete amplitude values, $P_{\textrm{tot}}$ denotes the
maximum total power, $\Delta=\sqrt{P_{\textrm{max}}}/2^{m}$ where
$P_{\textrm{max}}$ is the maximum per-antenna power, and $M=2^{b}$ where $b$
is the number of bits to represent the discrete amplitude values.

If we relax the discrete constraint
${|}x_{i}{|}\in\\{\Delta,2\Delta,\ldots,2^{m}\Delta\\}$ to
$\Delta\leq{|}x_{i}{|}\leq 2^{m}\Delta$, then we have the relaxation (CSDP)
for (54) as follows:

$\displaystyle\max{}$ $\displaystyle t$ (55) s.t. $\displaystyle Q_{i}\cdot
X\geq t\gamma_{k}\sigma_{k}^{2},~{}i=1,\ldots,k,$
$\displaystyle\texttt{Trace}(X)\leq P_{\textrm{tot}},$
$\displaystyle\Delta^{2}\leq X_{ii}\leq P_{\textrm{max}},i=1,\ldots,n,$
$\displaystyle X\succeq 0.$

On the other hand, relaxation (ECSDP) for (54) is formulated as follows:

$\displaystyle\max{}$ $\displaystyle t$ (56) s.t. $\displaystyle Q_{i}\cdot
X\geq t\gamma_{k}\sigma_{k}^{2},~{}i=1,\ldots,k,$
$\displaystyle\texttt{Trace}(X)\leq P_{\textrm{tot}},$
$\displaystyle\Delta^{2}\leq R_{ii}=X_{ii}\leq P_{\textrm{max}},i=1,\ldots,n,$
$\displaystyle
X_{ij}\in\textsf{Conv}(\mathcal{G}_{ij}(R_{ij})),~{}\\{i,j\\}\in\mathcal{E},$
$\displaystyle X\succeq 0,~{}R\succeq 0.$

We compare the performance of the two relaxations on instances that are
randomly generated according to the procedure in Demir2015 : For each
$i=1,\ldots,k$, the vector $h_{i}\in\mathbb{C}^{n}$ follows the standard
$n$-dimensional complex Gaussian distribution, $Q_{i}=h_{i}h_{i}^{\dagger}$,
$\gamma_{k}$ is uniformly selected from $\\{1,2,3,4\\}$, and
$\sigma_{k}^{2}=1.0$. Also based on the parameter settings in Demir2015 , we
set $n=4$, $P_{\textrm{max}}=20$, $P_{\textrm{tot}}=40$, and consider the case
of $k\in\\{4,8,12\\}$, $m\in\\{3,4\\}$, and $b\in\\{3,4\\}$.

Based on the procedures described above, for each setting of parameters
$(n,k,m,b)$, we generate ten test instances. Each instance is relaxed to
(ECSDP) and (CSDP), respectively. Moreover, the optimal value of each instance
is computed by CPLEX, using the integer programming formulation proposed in
Demir2015 . With a known optimal value for each test instance, the “Gap
Closed” is defined as

$\textrm{Gap
Closed}=1-\frac{\textrm{UB}_{\textrm{ECSDP}}-V^{\ast}}{\textrm{UB}_{\textrm{CSDP}}-V^{\ast}},$
(57)

where $V^{\ast}$ denotes the optimal value returned by CPLEX. The numerical
results are listed in Table 2. For each row, the listed results summarize the
average performance on the ten test instances.

Table 2: Computational results on discrete transmit beamforming problems.

$(n,k,m,b)$ | ECSDP | CSDP | Optimal Value | Gap Closed
---|---|---|---|---
Upper Bound | Time | Upper Bound | Time
(4,4,3,3) | 38.7921 | 0.010 | 39.8886 | 0.005 | 36.3148 | 30.16%
(4,8,3,3) | 36.7337 | 0.010 | 37.2159 | 0.005 | 32.1290 | 9.72%
(4,12,3,3) | 25.9584 | 0.011 | 26.2780 | 0.005 | 21.1069 | 10.34%
(4,4,4,4) | 39.3492 | 0.017 | 39.8886 | 0.005 | 38.3498 | 31.58%
(4,8,4,4) | 36.9279 | 0.017 | 37.2159 | 0.005 | 34.1607 | 10.67%
(4,12,4,4) | 26.0792 | 0.017 | 26.2780 | 0.005 | 22.7450 | 10.61%

11footnotetext: Note: The results in each row are averaged over the ten test
instances.

From the results in Table 2, we can see that relaxation (ECSDP) is
consistently tighter than (CSDP) for all settings of parameters. The proposed
valid inequalities exploited from the convex hull of
$\mathcal{G}_{ij}(R_{ij})$ and $\mathcal{H}_{ij}$ are effective for improving
the tightness of the semidefinite relaxation, which reduce 9.7%–30% of the
relaxation gap introduced by (CSDP) on average.

###  5.3 Continuous phase angle constraints

We consider (CQP) with continuous phase angle constraints. As discussed in
Section 4, when $\mathcal{A}_{ij}=[\underline{\theta}_{ij},\bar{\theta}_{ij}]$
with $-\pi/2<\underline{\theta}_{ij}<\bar{\theta}_{ij}<\pi/2$ for all
$\\{i,j\\}\in\mathcal{E}$, (ECSDP1) is equivalent to (ECSDP2). However, it has
been shown that (ECSDP) can be tighter than (ECSDP1). In this subsection, we
compare the tightness of these different relaxations numerically. For this
purpose, we generate test instances of the following form:

$\displaystyle\min{}$ $\displaystyle x^{{\dagger}}Q_{0}x$ (58) $\displaystyle
l_{i}\leq{|}x_{i}{|}\leq u_{i},~{}i=1,\ldots,n,$
$\displaystyle\arg(x_{i}{x_{j}}^{{\dagger}})\in[\underline{\theta}_{ij},\bar{\theta}_{ij}],\\{i,j\\}\in\mathcal{E},$

where $l_{i}=1.0$, $u_{i}=4.0$ for all $i=1,\ldots,n$, and
$Q_{0}\in\mathbb{C}^{n}$ is a randomly generated Hermitian matrix, with each
diagonal entry following the standard Gaussian distribution, and with the
real-part and the imaginary-part of each non-diagonal entry also following the
standard Gaussian distribution.

We first generate ten 20-dimensional test instances with
$\mathcal{A}_{ij}=[-\pi/6,\pi/6]$ for all $\\{i,j\\}\in\mathcal{E}$, and
compare the three relaxations (CSDP), (ECSDP2) and (ECSDP). Since (ECSDP1) is
equivalent to (ECSDP2) but is not as compact as (ECSDP2), it is not selected
for the current comparison. The computational results for the three selected
semidefinite relaxations are listed in Table 3.

Table 3: Computational results on instances with continuous phase angle set. Instance | Lower Bound | Time
---|---|---
ID | CSDP | ECSDP2 | ECSDP | CSDP | ECSDP2 | ECSDP
1 | -2965.66 | -1120.93 | -1116.66 | 0.02 | 0.20 | 0.32
2 | -2895.56 | -593.77 | -592.48 | 0.01 | 0.16 | 0.26
3 | -2567.41 | -1168.01 | -1167.79 | 0.01 | 0.18 | 0.38
4 | -3062.55 | -622.25 | -618.21 | 0.01 | 0.17 | 0.24
5 | -3469.90 | -896.06 | -893.29 | 0.01 | 0.16 | 0.27
6 | -3069.32 | -1026.03 | -1025.35 | 0.01 | 0.19 | 0.27
7 | -2779.32 | -975.31 | -969.00 | 0.01 | 0.17 | 0.25
8 | -2658.00 | -542.72 | -539.58 | 0.01 | 0.15 | 0.24
9 | -3381.43 | -1225.68 | -1221.91 | 0.01 | 0.18 | 0.30
10 | -3087.94 | -1096.40 | -1092.99 | 0.01 | 0.17 | 0.25

From the results in Table 3, we can observe that both (ECSDP) and (ECSDP2) are
much tighter than (CSDP). Meanwhile, the bounds of (ECSDP) are uniformly
tighter than the bounds of (ECSDP2) (although the improvements are marginal).
Based on the above results, we may conclude that in comparison with the
previous semidefinite relaxations in the literatures, (ECSDP) is the tightest
one.

We further consider the case that
$\pi<\bar{\theta}_{ij}-\underline{\theta}_{ij}<2\pi$, for which the
semidefinite relaxation (ECSDP2) proposed in Chen2016  can not be applied. We
investigate whether (ECSDP) can still be tighter than (CSDP) in this case. To
do so, we generate another ten test instances, in which each
$\underline{\theta}_{ij}$ is uniformly sampled from $(-\pi,-\pi/2)$, and
$\bar{\theta}_{ij}=\underline{\theta}_{ij}+\varphi_{ij}$, where $\varphi_{ij}$
is uniformly sampled from $(\pi,2\pi)$. Then, the (ECSDP) and (CSDP) based
lower bounds are computed and listed in Table 4.

Table 4: Computational results on instances with continuous phase angle set. Instance | Lower Bound | Time
---|---|---
ID | CSDP | ECSDP | CSDP | ECSDP
1 | -2984.13 | -2741.61 | 0.02 | 0.07
2 | -3080.58 | -2798.36 | 0.01 | 0.04
3 | -3170.00 | -2972.45 | 0.01 | 0.04
4 | -3630.20 | -3414.64 | 0.01 | 0.04
5 | -3062.33 | -2866.65 | 0.01 | 0.04
6 | -3225.01 | -2945.75 | 0.01 | 0.04
7 | -2760.60 | -2513.31 | 0.01 | 0.04
8 | -3174.43 | -2892.12 | 0.01 | 0.04
9 | -3032.56 | -2909.40 | 0.01 | 0.04
10 | -3083.04 | -2827.94 | 0.01 | 0.04

From the results in Table 4, we can find that even for the case that
$\pi<\bar{\theta}_{ij}-\underline{\theta}_{ij}<2\pi$, (ECSDP) can be tighter
than (CSDP). These results indicate that the new semidefinite relaxation
(ECSDP) can be applied to more general cases of (CQP), whereas the previous
one in Chen2016  is specially designed for the case of
$-\pi/2<\underline{\theta}_{ij}<\bar{\theta}_{ij}<\pi/2$.

##  6 Conclusions

In this paper, we propose some new semidefinite relaxations for a class of
complex quadratic programming problems. The main idea behind the proposed
semidefinite relaxations is that the convex hull of $(X_{ii},X_{jj},X_{ij})$
is exploited to derive valid constraints for the lifted matrix
$X=xx^{\dagger}$, which are very effective for tightening the conventional
semidefinite relaxation. The main technique to derive the valid constraints is
to represent the entry $X_{ij}$ in its polar coordinate form, so that the
convex hull of variables in the polar coordinate representations can be
derived easily. Our numerical results show that the proposed semidefinite
relaxation (ECSDP) achieves better performance than the conventional ones in
terms of tightness. Besides, using the new semidefinite relaxations, some
previous approximation algorithms can be improved for finding better sub-
optimal solutions.

The proposed semidefinite relaxations are theoretically compared with the
previous semidefinite relaxations proposed in Lu2018 ; Lu2020  and our
proposed (ECSDP) can be tighter than the previous ones. In particular, for the
homogeneous cases that satisfy the assumptions in Theorem 3.4, the
semidefinite relaxations proposed in Lu2018 ; Lu2020  is equivalent to (CSDP),
whereas the newly proposed (ECSDP) is tighter than (CSDP). Moreover, the
proposed semidefinite relaxations are also compared with the one proposed in
Chen2016 . As discussed in Section 4, the semidefinite relaxation proposed in
Chen2016  is designed for the case where each $\mathcal{A}_{ij}$ is a sub-
interval of $(-\pi/2,\pi/2)$. In this case, the newly proposed semidefinite
relaxation (ECSDP1) is equivalent to the one proposed in Chen2016 , whereas
(ECSDP) can be strictly tighter than the one in Chen2016 . Moreover, (ECSDP1)
and (ECSDP) can be applied to general cases of (CQP), and keep their
effectiveness even for cases where
$\mathcal{A}_{ij}=[\underline{\theta}_{ij},\bar{\theta}_{ij}]$ with
$\pi<\bar{\theta}_{ij}-\underline{\theta}_{ij}<2\pi$.

Based on the results presented in this paper, there are two potential
directions that deserve further research. First, for the discrete case, such
as the radar waveform design problem discussed in Section 5.1, whether the
theoretical approximation ratio of (ECSDP) based approximation algorithm can
be better than the ratio of (CSDP) based algorithm is an interesting question
to answer. Second, since (ECSDP) can be tighter than the semidefinite
relaxation proposed in Chen2016 , we may try to design a new branch-and-bound
algorithm to solve the optimal power flow problem, using (ECSDP) as a
relaxation method. It is interesting to design a new branch-and-bound
algorithm to compare with the one in Chen2016 .

## References

  * (1) Bandeira, A. S., Boumal, N., Singer, A.: Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Math. Program. 163, 145–167 (2017)
  * (2) Chen, C., Atamtürk, A., Oren, S. S.: A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables. Math. Program. 165, 549–577 (2017)
  * (3) Coffrin, C., Hijazi, H. L., Hentenryck, P. V.: Strengthening the SDP relaxation of AC power flows with convex envelopes, bound tightening, and valid inequalities. IEEE Trans. Power Syst. 32, 3549–3558 (2017)
  * (4) Demir, Ö. T., Tuncer, T. E.: Optimum discrete single group multicast beamforming. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP’14), pp. 7744–7748. IEEE Press, Florence (2014)
  * (5) Demir, Ö. T., Tuncer, T. E.: Optimum discrete transmit beamformer design. Digital Signal Processing 36, 57–68 (2015)
  * (6) Goemans, M., Williamson, D.: Improved approximation algorithms for maximumcut and satisfiability problems using semidefinite programming. J. ACM 42, 1115–1145 (1995)
  * (7) Goemans, M. X., Williamson, D. P.: Approximation algorithms for Max-3-Cut and other problems via complex semidefinite programming. J. Comput. Syst. Sci. 68, 442–470 (2004)
  * (8) Low, S. H.: Convex relaxation of optimal power flow–Part I: Formulations and equivalence. IEEE Trans. Control. Netw. Syst. 1, 15–27 (2014)
  * (9) Low, S. H.: Convex relaxation of optimal power flow–Part II: Exactness. IEEE Trans. Control. Netw. Syst. 1, 177–189 (2014)
  * (10) Lu, C., Deng, Z., Zhang, W.-Q., Fang, S.-C.: Argument division based branch-and-bound algorithm for unit-modulus constrained complex quadratic programming. J. Global Optim. 70, 171–187 (2018)
  * (11) Lu, C., Liu, Y. -F., Zhang, W. -Q., Zhang, S.: Tightness of a new and enhanced semidefinite relaxation for MIMO detection. SIAM J. Optim. 29, 719–742 (2019)
  * (12) Lu, C., Liu, Y. -F., Zhou, J.: An enhanced SDR based global algorithm for nonconvex complex quadratic programs with signal processing applications. IEEE Open Journal of Signal Processing 1, 120–134 (2020)
  * (13) Luo, Z.-Q., Ma, W. -K., So, A. M. -C., Ye, Y., Zhang, S.: Semidefinite relaxation of quadratic optimization problems. IEEE Signal Process. Mag. 27, 20–34 (2010)
  * (14) Ma, W. -K., Ching, P. -C., Ding, Z.: Semidefinite relaxation based multiuser detection for M-ary PSK multiuser systems. IEEE Trans. Signal Process. 52, 2862–2872 (2004)
  * (15) Maio, A. D., Nicola, S. D., Huang, Y., Luo, Z. -Q., Zhang, S.: Design of phase codes for radar performance optimization with a similarity constraint. IEEE Trans. Signal Process. 57, 610–621 (2009)
  * (16) Maio, A. D., Huang, Y., Piezzo, M., Zhang, S., Farina, A.: Design of optimized radar codes with a peak to average power ratio constraint. IEEE Trans. Signal Process. 59, 2683–2697 (2011)
  * (17) Mosek ApS. mosek. http://www.mosek.com (2020)
  * (18) So, A. M. -C., Zhang, J., Ye, Y.: On approximating complex quadratic optimization problems via semidefinite programming relaxations. Math. Program. 110, 93–110 (2007)
  * (19) Soltanalian, M., Stoica, P.: Designing unimodular codes via quadratic optimization. IEEE Trans. Signal Process. 62, 1221–1234 (2014)
  * (20) Waldspurger, I., d’Aspremont, A., Mallat, S.: Phase recovery, MaxCut and complex semidefinite programming. Math. Program. 149, 47–81 (2015)
  * (21) Zhang, S., Huang, Y.: Complex quadratic optimization and semidefinite programming. SIAM J. Optim. 16, 871–890 (2006)
  * (22) Zhao, P. -F., Li, Q. N., Chen, W. K., Liu, Y. -F.: An efficient quadratic programming relaxation based algorithm for large-scale MIMO detection, SIAM J. Optim. 31, 1519–1545 (2021)