HSC welcomes all external visitors to this site, especially students and members of the academic community. Please use the comments box at the bottom of each page to record any comments or suggestions for improvement.
Introduction
Second order cone programming is a convex_optimization technique which has many applications in wireless technologies. It has been suggested as part of algorithms to solve the PAPR problem, as well as optimal weight computation for transmit/receive beamforming.
A convex programming problem requires us to find the optimal vector x so as to maximize a convex function f(x), subject to a set of inequality constraints f_i(x) \le k, and equality constraints h_i(x) = 0 where all the functions f_i(x) are convex and the functions h_i(x) are affine i.e. they can be put in the form Ax + b. The constraints thus restrict the solution x to a convex set C. While in most cases, an analytical solution does not exist, due to several good properties of convexity i.e. all local minima are global, the function is differentiable in the set, intersections of convex sets are also convex, etc. there exist many techniques to compute the optimal value of x. These range from game theoretic approaches, to interior point methods, to the famous and very widely used Lagrangian and Kuhn Tucker algorithms. Convex programming is widely used in practically every field of engineering and science. In the communications area, a common usage is for Power_Control in cellular networks.
Second order cone programming
A cone is a set in n+1 dimensions of the form \Vert x \Vert \le t, where x is a vector in n dimensions. Geometrically, it looks like this: 
.
Understandably it is sometimes called an ice-cream cone as well.
Note: In the rest of the text, x^T stands for the
transpose operation on a matrix or vector x.
Definition
If A^i is a matrix of dimensions n_i X N and b_i , c_i are vectors of dimension n_i, then we can map a vector x of dimension n to a vector of dimension n_i using the mapping X = A_i x + b_i . In this case, we can construct a cone of dimension n_i + 1 as follows: \Vert X \Vert \le t , where X = A_i x + b_i and t = {c_i}^T x + d. where d is a real number
A second order cone program is defined as follows:
minimize f^T x subject to a second order cone inequality
constraint \Vert A_i x + b_i \Vert \le {c_i}^T x + d. The simplest form of SOCP is the norm
minimization problem:
minimize t such that \Vert x \Vert_\infty \le t
where x is vector in N dimensions and t is a scalar.
Note: The infinite norm of a vector x = \{ x_0, x_1 \ldots , x_{M-1} \} is given as
\max {\{ x_0, x_1, \ldots , x_{M-1} \}}
As we discussed earlier, the constraint set is defined as a second order cone, hence the name. As we shall see below, many problems can be converted to the SOCP form.
The beamforming problem consists of optimally combining the received signals at a multi-antenna receiver so as to maximize the signal coming from a specific direction (called the look direction \theta ) and reducing the signal in other directions (called the null directions \phi_i, i = 0, 1, \ldots, M ). Consider that the receiving antenna has N elements, each of which are placed a distance d apart on a straight line. The signal at the kth antenna from a signal s(t) arriving at the angle \theta is given as:
r_k(\theta) = s(t) e^{2\pi (k-1) \frac{d}{\lambda} cos (\theta)}
We can simplify by writing \delta = 2\pi d/\lambda
in which case the equation becomes
r_k(\theta) = s(t) e^{ (k-1) \delta cos (\theta)}
If we multiply the k^{th} received signal by the weight w_{k-1} and add, the combined received signal becomes
\begin{eqnarray}
r(\theta) = \sum_k w_k r_k(\theta) = s(t) \sum_k w_k e^{ (k-1) \delta cos (\theta)} \\
= s(t)\vec{W}\vec{F(\theta)} \\
\vec{W} = \{ w_0, w_1, \ldots, w_{N-1}\} \\
\vec{F(\theta)} = \{ 1, e^{j\delta cos(\theta)},e^{2j\delta cos(\theta)}, \ldots \}
\end{eqnarray}
We can thus rewrite the problem as:
\begin{eqnarray}
\textrm{Maximize } r(\theta) = \vec{W}^T.\vec{F(\theta)} \\
\textrm{subject to} \vec{W}^T.\vec{F(\phi_i)} = 0
\end{eqnarray}
The matrix solution and its pitfalls
If the number of look directions (K) and null directions (M) match the number of elements (N = M + K), we can solve this as a matrix inversion problem
\vec{W} = \left[1,1,\ldots,0,0,\ldots \right] \left[\vec{{F_\theta}_0},\ldots,\vec{{F_\theta}_{M-1}},\vec{{F_\phi}_0},\ldots,\vec{{F_\phi}_{N-1}} \right]
.
Unfortunately, in this context, the solution often leads to impossibly large magnitudes for the coefficients of the weight vector W. This makes the solution unworkable.
Formulation as a second order cone program
We can formulate the problem as a second order cone program, and ensure that the weight vector coefficients are limited as follows:
\begin{eqnarray}
\textrm{Maximize } {f_\theta} W
\textrm{Subject to } \Vert {f_\phi}_i W \Vert \le \left[ \eta \eta \ldots \eta \right]\\
\textrm{and } \Vert W \Vert \le \left[ W_{max} W_{max} \ldots \right]
\end{eqnarray}
We have shown the two constraints (rejection and coefficient limit) separately, in reality they can be combined into a single constraint. This problem can be readily solved using one of many interior point methods and the value of W_max_ can be tweaked to achieve any desired rejection ratio (the ratio between the power of the received signal in the look direction and that in the null directions).
PAPR is a problem that affects OFDM based wireless transmission techniques; when multiple sinusoids of slightly offset frequencies are transmitted simultaneously, instantaneous constructive synchronization can cause large peaks in the output power; this can lead to non-linearity or saturation of the power amplifier, causing inter-modulation harmonics and other noise patterns. The Tone reservation technique Tellado? reserves a small set of tones in which a special signal is injected so as to destructively interfere with the other tones and keep the peak low.
Consider an OFDM signal X = \{ X_0, X_1, \ldots X_{M-1} \} . After the IDFT operation, we can write the output vector
as
\begin{eqnarray}
\left[ \begin{array}{c} x_0 \\ x_1 \\ \ldots \\ x_{M-1} \end{array} \right] = Q\left[ \begin{array}{c} X_0 \\ X_1 \\ \ldots \\ X_{M-1} \end{array} \right] \\
Q = \left[ \begin{array}{c c c c} 1 & 1 & \ldots & 1 \\ 1 & e^{j2 \frac{\pi}{M}} & \ldots & e^{j2 \frac{\pi(M-1)}{M}} \\ 1 & \ldots & \ldots & \ldots \\ 1 & e^{j2 \frac{\pi(M-1)}{M}} & \ldots & e^{j2 \frac{\pi(M-1)}{M}(M-1)} \end{array} \right]
\end{eqnarray}
For the tone injection technique, a certain number (M-P) out of the M tones in the original signal X is reserved for insertion of the PAPR reduction sequence; the receiver discards these tones when it gets them. The vector X then looks like \{ X_0, X_1, \ldots X_{P-1}, 0,0,0,0, \ldots \} . We then prepare a second set of tones, whose only purpose is to reduce the peak transmission; we can define this vector as C = \{ 0,0,0, C_0, C_1, \ldots, C_{M-P-1} \} . We then have to ensure that the output of the combined transmissioni.e. \Vert Q(X+C)\Vert is minimized.
To express this as an SOCP problem, we first write C in generalized form Cd = \{ Cd_0, Cd_1, \ldots, C_0, C_1, \ldots, C_{M-P-1} \} . We can then write C as Cd * I_P, where I_P = diag\{0,0,\ldots \textrm{ p times}, 1,1,1 \textrm {m-p times} \} . The PAPR reduction problem then becomes the problem of minimizing the norm of the vector \Vert Q(X+I_P C)\Vert . As we have shown in the introductory section, this is the standard form of the SOCP.
Solutions
SOCP problems are solved by one of many Interior_Point_Methods.
References
[Boyd and Vandenberghe] Convex Optimization, Cambridge University Press
[LVBL98]Lobo, Vandenberghe, Boyd, Lebret, "Applications of Second Order Cone Programing", March 1998
[LB97]Lebret, Boyd, "Antenna Array Pattern Synthesis via Convex Optimization", IEEE Transactions on Signal Processing, March 1997
[Alizadeh and Goldfarb] Second Order Cone Programing
[AgMeng] Aggarwal, Meng, "Minimizing the Peak to Average Power Ratio of OFDM signals via Convex Optimization", Globecom 2003
[Tellado] Jose Tellado, "Peak to Average Power Reduction for Multicarrier Modulation", Ph.d. thesis, submitted to Stanford University
Comments
