Extreme Point Pursuit - Part I: A Framework for Constant Modulus Optimization

Junbin Liu, Ya Liu, Wing-Kin Ma, Mingjie Shao, Anthony Man-Cho SoIEEE TSP 2024

Abstract

This study develops a framework for a class of constant modulus (CM) optimization problems, covering binary constraints, discrete phase constraints, semi-orthogonal matrix constraints, non-negative semi-orthogonal matrix constraints, and several types of binary assignment constraints. Capitalizing on the basic principles of concave minimization and error bounds, we study a convex-constrained penalized formulation for general CM problems. The advantage of such formulation is that it allows us to leverage non-convex optimization techniques, such as the simple projected gradient method, to build algorithms. As the first part of this study, we explore the theory of this framework, examining conditions for exact penalization and computational aspects of the projected gradient method for various CM constraints. Our study suggests that the proposed framework has a broad scope of applicability.

Introduction

In fields ranging from signal processing and communications to data science, researchers frequently encounter Constant Modulus (CM) constraints. These requirements dictate that every element of a solution vector or matrix must possess a fixed magnitude or "size." Common examples include binary selection (e.g., in MIMO detection), phase constraints where signals must lie on a unit circle (e.g., radar waveforms), and orthogonality constraints where matrix columns must be orthonormal (e.g., in PCA or graph matching).

The fundamental challenge of CM optimization is that these constraints define "hollow" or discrete sets that are inherently non-convex. Traditionally, solving such problems required highly specialized, case-specific heuristics. This paper introduces Extreme Point Pursuit (EXPP), a unified mathematical framework designed to transform these difficult non-convex problems into manageable penalized convex problems, allowing for a standardized approach to a diverse array of CM challenges.

The EXPP Framework

The core innovation of EXPP is the replacement of the hard non-convex constraint set $\mathcal{V}$ with its convex hull, $\text{conv}(\mathcal{V})$—the smallest convex set containing it. To ensure the solution remains faithful to the original non-convex requirements, the authors introduce a negative quadratic penalty term to the objective function.

The problem is reformulated as: $$\min_{x \in \text{conv}(\mathcal{V})} f(x) - \lambda \|x\|_2^2$$

By shifting the optimization to the convex hull and applying a penalty, the framework "pushes" the optimizer away from the interior of the convex set and toward its "extreme points." In the case of CM sets, these extreme points correspond exactly to the original non-convex constraints.

Theoretical Pillars

The validity of the EXPP framework rests on two primary theoretical foundations:

1. Concave Minimization

For smooth objective functions $f$, a sufficiently large penalty parameter $\lambda$ renders the entire objective function strictly concave. A fundamental principle of geometry dictates that the minimum of a concave function over a convex set must occur at an extreme point. For the sets studied here, these extreme points are precisely the CM points of interest. This ensures that the global minimum of the penalized convex problem is identical to the global minimum of the original non-convex problem.

2. Error Bound Theory

In scenarios where the objective function is non-smooth, the concave minimization argument is insufficient. To address this, the authors utilize error bound theory to demonstrate that the distance between a point and the CM set can be bounded by the penalty term. This proves that for a finite, computable $\lambda$, the penalized formulation remains an exact penalization, meaning the solution to the reformulated problem is the exact solution to the original problem.

Computational Strategy

To solve the reformulated problem, the authors advocate for the Projected Gradient Method (PGM). The framework provides a "cookbook" of projection operators, showing that projecting onto the convex hulls of complex sets—such as the spectral norm ball for matrices or the unit simplex for vectors—is often computationally efficient.

To mitigate the risk of the algorithm becoming trapped in local minima, the authors suggest a homotopy strategy. This involves gradually increasing the penalty parameter $\lambda$ during the optimization process, allowing the algorithm to explore the space before converging on an extreme point.

Key Results and Scope

The theoretical analysis in Part I establishes several critical milestones:

  • Theorem 1 (Smooth Case): Confirms that if the objective has a Lipschitz continuous gradient, EXPP serves as an exact formulation for any CM set.
  • Theorem 4 (Non-smooth Case): Establishes specific error bounds for binary vectors, MPSK signals, unit spheres, and semi-orthogonal matrices, proving exact penalization even without objective smoothness.
  • Unified Applicability: The framework successfully covers binary constraints, discrete phase constraints, and semi-orthogonal matrix constraints under a single theoretical umbrella.

Limitations and Future Work

While EXPP provides a powerful unified theory, certain challenges remain:

  • Local Minima: Although the global solutions of the original and penalized formulations match, the penalized objective is non-convex. Gradient-based methods like PGM can still get trapped in local optima. While homotopy is a useful heuristic, universal theoretical guarantees for global convergence remain an open area of research.
  • Non-negative Orthogonality: The framework identifies non-negative semi-orthogonal matrices (often used in Non-negative Matrix Factorization) as a difficult case. Because the projection onto the convex hull of this specific set is currently an open problem, it marks a boundary for the current reach of the EXPP theory.
  • Empirical Validation: As Part I is strictly theoretical, the practical performance and speed of EXPP relative to specialized solvers will be evaluated in the forthcoming Part II of this study.

Conclusion

Extreme Point Pursuit offers a robust theoretical bridge between non-convex CM constraints and convex optimization techniques. By leveraging the geometric properties of extreme points and the analytical power of error bounds, the framework provides a standardized path for solving a wide variety of previously fragmented optimization problems.

Summary updated

Abstract

This study develops a framework for a class of constant modulus (CM) optimization problems, which covers binary constraints, discrete phase constraints, semi-orthogonal matrix constraints, non-negative semi-orthogonal matrix constraints, and several types of binary assignment constraints. Capitalizing on the basic principles of concave minimization and error bounds, we study a convex-constrained penalized formulation for general CM problems. The advantage of such formulation is that it allows us to leverage non-convex optimization techniques, such as the simple projected gradient method, to build algorithms. As the first part of this study, we explore the theory of this framework. We study conditions under which the formulation provides exact penalization results. We also examine computational aspects relating to the use of the projected gradient method for each type of CM constraint. Our study suggests that the proposed framework has a broad scope of applicability.
BibTeX
@article{liu2024extreme,
  author = {Junbin Liu and Ya Liu and Wing-Kin Ma and Mingjie Shao and Anthony Man-Cho So},
  title = {{Extreme Point Pursuit - Part I: A Framework for Constant Modulus Optimization}},
  journal = {IEEE Trans. Signal Process.},
  year = {2024},
}
Figure