Ferkans — Interactive Telecom Tutor

Definition:
Standard-Form Optimization Problem

A general optimization problem in standard form is

$\begin{aligned} \text{minimise} \quad & f_0(\mathbf{x}) \\ \text{subject to} \quad & f_i(\mathbf{x}) \leq 0, \quad i = 1, \ldots, m \\ & h_j(\mathbf{x}) = 0, \quad j = 1, \ldots, p \end{aligned}$

where $\mathbf{x} \in \mathbb{R}^n$ is the optimisation variable, $f_0$ is the objective, $f_i$ are inequality constraints, and $h_j$ are equality constraints.

The optimal value is $p^\star = \inf\{f_0(\mathbf{x}) : \mathbf{x} \text{ feasible}\}$ .

If the problem is a maximisation, we convert it by minimising $-f_0$ .

Definition:
Convex Optimization Problem

An optimization problem is convex if:

The objective $f_0$ is convex.
Each inequality constraint function $f_i$ is convex.
Each equality constraint is affine: $h_j(\mathbf{x}) = \mathbf{a}_j^T \mathbf{x} - b_j$ .

Equivalently, the feasible set is convex and the objective is convex over it.

The fundamental property: every local minimum of a convex problem is a global minimum.

Theorem: Local Optima Are Global Optima

For a convex optimization problem, any locally optimal point is also globally optimal.

If there were a better point elsewhere, the line segment connecting it to the local minimum would contain a feasible point with even lower objective, contradicting local optimality.

Proof

Proof by contradiction

Suppose $\mathbf{x}^\star$ is locally optimal but not globally optimal: there exists feasible $\mathbf{y}$ with $f_0(\mathbf{y}) < f_0(\mathbf{x}^\star)$ . By convexity of the feasible set, $\mathbf{z}_\theta = (1-\theta)\mathbf{x}^\star + \theta \mathbf{y}$ is feasible for $\theta \in (0,1)$ . By convexity of $f_0$ : $f_0(\mathbf{z}_\theta) \leq (1-\theta)f_0(\mathbf{x}^\star) + \theta f_0(\mathbf{y}) < f_0(\mathbf{x}^\star)$ . For $\theta$ small enough, $\mathbf{z}_\theta$ is arbitrarily close to $\mathbf{x}^\star$ yet has strictly lower cost — contradicting local optimality. $\blacksquare$

Definition:
Linear Program (LP)

A linear program has a linear objective and linear constraints:

$\begin{aligned} \text{minimise} \quad & \mathbf{c}^T \mathbf{x} \\ \text{subject to} \quad & \mathbf{A}\mathbf{x} \preceq \mathbf{b}, \quad \mathbf{C}\mathbf{x} = \mathbf{d} \end{aligned}$

LPs are convex and solvable in polynomial time (e.g., interior-point methods). The feasible set is a polyhedron, and the optimum is attained at a vertex (extreme point) when bounded.

Definition:
Quadratic Program (QP)

A quadratic program has a quadratic objective and linear constraints:

$\begin{aligned} \text{minimise} \quad & \tfrac{1}{2}\mathbf{x}^T \mathbf{Q}\mathbf{x} + \mathbf{c}^T \mathbf{x} \\ \text{subject to} \quad & \mathbf{A}\mathbf{x} \preceq \mathbf{b} \end{aligned}$

The QP is convex if and only if $\mathbf{Q} \succeq 0$ .

Definition:
Second-Order Cone Program (SOCP)

A second-order cone program has the form:

$\begin{aligned} \text{minimise} \quad & \mathbf{f}^T \mathbf{x} \\ \text{subject to} \quad & \|\mathbf{A}_i \mathbf{x} + \mathbf{b}_i\|_2 \leq \mathbf{c}_i^T \mathbf{x} + d_i, \quad i = 1, \ldots, m \end{aligned}$

SOCPs generalise LPs and QPs and are solvable in polynomial time.

Robust beamforming problems in MIMO systems are naturally SOCPs: the constraint $\|\mathbf{w}\| \leq P_{\max}^{1/2}$ is a second-order cone constraint.

Definition:
Semidefinite Program (SDP)

A semidefinite program optimises a linear objective over the intersection of the PSD cone with affine constraints:

$\begin{aligned} \text{minimise} \quad & \text{tr}(\mathbf{C}\mathbf{X}) \\ \text{subject to} \quad & \text{tr}(\mathbf{A}_i \mathbf{X}) = b_i, \quad i = 1, \ldots, m \\ & \mathbf{X} \succeq 0 \end{aligned}$

SDPs generalise LPs, QPs, and SOCPs. They are solvable in polynomial time via interior-point methods.

SDPs appear throughout wireless communications: relaxations of beamformer design, MIMO transceiver optimisation, and sensor localisation.

Hierarchy of Convex Programs

Problem	Objective	Constraints	Example in Wireless
LP	Linear	Linear	Power control (high-SNR regime)
QP	Quadratic ( $\mathbf{Q} \succeq 0$ )	Linear	MMSE receiver design
SOCP	Linear	Second-order cone	Robust beamforming
SDP	Linear in $\mathbf{X}$	$\mathbf{X} \succeq 0$ + affine	MIMO transmit covariance optimisation

Definition:
Lagrangian and Lagrangian Dual Function

For the standard-form problem, the Lagrangian is

$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}) = f_0(\mathbf{x}) + \sum_{i=1}^m \lambda_i f_i(\mathbf{x}) + \sum_{j=1}^p \nu_j h_j(\mathbf{x})$

where $\boldsymbol{\lambda} \succeq 0$ are the dual variables (or Lagrange multipliers) for the inequality constraints and $\boldsymbol{\nu}$ are the multipliers for equalities.

The Lagrangian dual function is

$g(\boldsymbol{\lambda}, \boldsymbol{\nu}) = \inf_{\mathbf{x}} \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}).$

The dual function is always concave (as the pointwise infimum of affine functions of $(\boldsymbol{\lambda}, \boldsymbol{\nu})$ ), regardless of convexity of the original problem.

Theorem: Weak and Strong Duality

Weak duality: For any $\boldsymbol{\lambda} \succeq 0$ and any $\boldsymbol{\nu}$ , $g(\boldsymbol{\lambda}, \boldsymbol{\nu}) \leq p^\star$ .

The dual problem is $d^\star = \sup_{\boldsymbol{\lambda} \succeq 0, \boldsymbol{\nu}} g(\boldsymbol{\lambda}, \boldsymbol{\nu})$ , so $d^\star \leq p^\star$ always.

Strong duality ( $d^\star = p^\star$ ) holds for convex problems that satisfy a constraint qualification, the most common being Slater's condition: there exists a strictly feasible point $\tilde{\mathbf{x}}$ with $f_i(\tilde{\mathbf{x}}) < 0$ for all $i = 1, \ldots, m$ .

Weak duality says the dual always provides a lower bound on the primal optimal value. Slater's condition ensures the bound is tight. In wireless problems, strong duality almost always holds because the constraints typically have non-empty interior.

Proof

Weak duality

Let $\mathbf{x}$ be any feasible point. Then $f_i(\mathbf{x}) \leq 0$ and $h_j(\mathbf{x}) = 0$ . With $\boldsymbol{\lambda} \succeq 0$ : $\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}) = f_0(\mathbf{x}) + \sum_i \lambda_i f_i(\mathbf{x}) + \sum_j \nu_j h_j(\mathbf{x}) \leq f_0(\mathbf{x})$ . Taking the infimum over $\mathbf{x}$ : $g(\boldsymbol{\lambda}, \boldsymbol{\nu}) \leq f_0(\mathbf{x})$ . Since this holds for every feasible $\mathbf{x}$ : $g(\boldsymbol{\lambda}, \boldsymbol{\nu}) \leq p^\star$ .

Maximising the bound

Taking the supremum over $(\boldsymbol{\lambda}, \boldsymbol{\nu})$ with $\boldsymbol{\lambda} \succeq 0$ gives $d^\star \leq p^\star$ .

Slater's condition guarantees that the duality gap $p^\star - d^\star = 0$ for convex problems. The proof uses a separating hyperplane argument applied to the set $\{(f_1(\mathbf{x}), \ldots, f_m(\mathbf{x}), f_0(\mathbf{x})) : \mathbf{x} \in \text{dom}\}$ and the point $(0, \ldots, 0, p^\star)$ . $\blacksquare$

Lagrangian Dual Function for a Simple QP

Visualise the Lagrangian dual function $g(\lambda)$ for the quadratic program $\min\; x^2 \;\text{s.t.}\; x \geq a$ . The dual provides a lower bound on the optimal value, and the duality gap closes when strong duality holds.

Parameters

Constraint bound

a

1

Show duality gap

Example: Dual of a Linear Program

Find the dual of the LP: $\min\;\mathbf{c}^T \mathbf{x}$ subject to $\mathbf{A}\mathbf{x} \preceq \mathbf{b}$ .

Solution

Form the Lagrangian

$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = \mathbf{c}^T \mathbf{x} + \boldsymbol{\lambda}^T (\mathbf{A}\mathbf{x} - \mathbf{b}) = (\mathbf{c} + \mathbf{A}^T \boldsymbol{\lambda})^T \mathbf{x} - \boldsymbol{\lambda}^T \mathbf{b}$ .

Minimise over $\mathbf{x}$

The Lagrangian is linear in $\mathbf{x}$ , so it is unbounded below unless the coefficient is zero:

$g(\boldsymbol{\lambda}) = \begin{cases} -\boldsymbol{\lambda}^T \mathbf{b} & \text{if } \mathbf{A}^T \boldsymbol{\lambda} + \mathbf{c} = \mathbf{0} \\ -\infty & \text{otherwise} \end{cases}$

State the dual

The dual problem is: $\max\;-\boldsymbol{\lambda}^T \mathbf{b}$ subject to $\mathbf{A}^T \boldsymbol{\lambda} + \mathbf{c} = \mathbf{0}$ , $\boldsymbol{\lambda} \succeq 0$ .

Equivalently: $\max\;\mathbf{b}^T \boldsymbol{\mu}$ subject to $\mathbf{A}^T \boldsymbol{\mu} \preceq \mathbf{c}$ (with sign change $\boldsymbol{\mu} = -\boldsymbol{\lambda}$ ). The dual of an LP is another LP. $\blacksquare$

Why This Matters: SDPs in MIMO Beamforming

The optimal downlink beamforming problem (minimise total transmit power subject to per-user SINR constraints) can be formulated as an SOCP or, via rank-one relaxation $\mathbf{W}_k = \mathbf{w}_k \mathbf{w}_k^H$ , as an SDP. The SDP relaxation is tight (the optimal $\mathbf{W}_k$ is always rank one), so the relaxation solves the original problem exactly. This remarkable result, due to Bengtsson and Ottersten (2001), is a cornerstone of modern beamforming theory.

See full treatment in MMSE-SIC Optimality

Hierarchy of Convex Programs — The nesting of convex program classes: LP $\subset$ QP $\subset$ SOCP $\subset$ SDP $\subset$ general convex. Each class includes all classes above it and adds expressiveness.

⚠️Engineering Note

Numerical Precision of Interior-Point Solvers

Modern interior-point solvers (MOSEK, SeDuMi, SDPT3) solve SDPs and SOCPs to roughly 6–8 digits of accuracy in $O(n^{3.5})$ time. In practice, be aware of the following:

Conditioning: Poorly scaled problems (coefficients spanning many orders of magnitude) cause numerical issues. Always normalise constraints so that coefficients are $O(1)$ .
Solver tolerances: Default feasibility/optimality tolerances are typically $10^{-8}$ . For beamforming problems with per-antenna power constraints, tighter tolerances ( $10^{-10}$ ) may be needed to ensure the rank-one property of SDP solutions.
Problem size limits: SDPs with matrix variable size $n > 500$ become impractical for general-purpose solvers. First-order methods (ADMM, proximal) scale better but give lower accuracy.
Standard tools: CVXPY (Python) and CVX (MATLAB) provide disciplined convex programming interfaces that automatically verify convexity and select appropriate solvers.

Practical Constraints

•
SDP matrix variable size limited to ~500 for general-purpose interior-point solvers
•
Problem conditioning: normalise coefficients to $O(1)$
•
Default solver tolerance $\sim 10^{-8}$ ; tighten for rank-constrained problems

📋 Ref: MOSEK, SeDuMi, SDPT3 solver documentation

Common Mistake: Not All QPs Are Convex

Mistake:

Assuming that any quadratic program is convex and efficiently solvable.

Correction:

A QP is convex only if $\mathbf{Q} \succeq 0$ . If $\mathbf{Q}$ has negative eigenvalues, the problem is non-convex and generally NP-hard. Always check the Hessian/Q matrix before claiming convexity.

Lagrangian

The function $\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}) = f_0(\mathbf{x}) + \sum_i \lambda_i f_i(\mathbf{x}) + \sum_j \nu_j h_j(\mathbf{x})$ that incorporates constraints into the objective via dual variables.

Related: Dual Function, KKT Conditions

Duality Gap

The difference $p^\star - d^\star$ between the primal and dual optimal values. Under Slater's condition, the gap is zero (strong duality).

Slater's Condition

A constraint qualification for convex problems: there exists a point $\tilde{\mathbf{x}}$ that is strictly feasible, meaning $f_i(\tilde{\mathbf{x}}) < 0$ for all inequality constraints. Guarantees strong duality ( $p^\star = d^\star$ ).

Convex Optimization Problems

Definition: Standard-Form Optimization Problem

Definition: Convex Optimization Problem

Theorem: Local Optima Are Global Optima

Proof by contradiction

Definition: Linear Program (LP)

Definition: Quadratic Program (QP)

Definition: Second-Order Cone Program (SOCP)

Definition: Semidefinite Program (SDP)

Hierarchy of Convex Programs

Definition: Lagrangian and Lagrangian Dual Function

Theorem: Weak and Strong Duality

Weak duality

Maximising the bound

Lagrangian Dual Function for a Simple QP

Parameters

Example: Dual of a Linear Program

Form the Lagrangian

Minimise over $\mathbf{x}$

State the dual

Why This Matters: SDPs in MIMO Beamforming

Hierarchy of Convex Programs

Numerical Precision of Interior-Point Solvers

Common Mistake: Not All QPs Are Convex

Lagrangian

Duality Gap

Slater's Condition

Definition:
Standard-Form Optimization Problem

Definition:
Convex Optimization Problem

Definition:
Linear Program (LP)

Definition:
Quadratic Program (QP)

Definition:
Second-Order Cone Program (SOCP)

Definition:
Semidefinite Program (SDP)

Definition:
Lagrangian and Lagrangian Dual Function