In constrained optimization, the standard prescription for keeping iterates feasible is the metric projection. To minimize a function $f(x)$ over a convex set $C$, an algorithm takes a step in a descent direction and then projects the result back onto $C$ by finding the closest point:
$$P_C(x) = \arg\min_{y \in C} \|x - y\|$$
This approach works elegantly when $C$ is a simple geometric shape, such as a hypersphere or a box. However, real-world engineering problems frequently introduce constraints that are mathematically intricate or implicitly defined. For instance, $C$ might be the intersection of dozens of separate convex sets, or a sublevel set of a non-smooth function.
As Pustelnik et al. observe in the context of signal modeling (A proximal approach for constrained cosparse modelling), computing an exact closed-form projection onto these complex geometric sets is often computationally intractable. Forcing an algorithm to compute exact projections at every iteration leads to nested, expensive inner loops that cripple performance.
A powerful alternative framework bypasses exact metric projections entirely. Instead of treating the feasible region as a geometric target to project onto, it represents the constraint set as the fixed point set of an operator.
The Core Idea: Shifting to Operator Invariance
Instead of defining a constraint set explicitly via inequalities ($C = \{x : g(x) \le 0\}$), we look for a mapping $T$ such that its fixed points—the points left invariant by the mapping—exactly coincide with our feasible region:
$$\text{Fix}(T) := \{x : T(x) = x\} = C$$
If we can construct such an operator $T$, the task of satisfying constraints transforms from a hard geometric minimization problem into an iterative operator application.
To make this substitution mathematically sound and ensure that optimization algorithms don't diverge, $T$ cannot arbitrary distort space. It must satisfy a stability condition from operator theory. The most fundamental requirement is that $T$ is nonexpansive, meaning it never amplifies the distance between any two points:
$$\|T(x) - T(y)\| \le \|x - y\|$$
In many practical scenarios, this condition can be relaxed to quasi-nonexpansivity. A mapping is quasi-nonexpansive if it doesn't move points further away from the target feasible set:
$$\|T(x) - z\| \le \|x - z\| \quad \text{for all } z \in \text{Fix}(T)$$
As Iiduka demonstrates in PARALLEL OPTIMIZATION ALGORITHM FOR SMOOTH CONVEX OPTIMIZATION OVER FIXED POINT SETS OF QUASI-NONEXPANSIVE MAPPINGS, quasi-nonexpansive mappings are highly versatile. They can easily model subgradient projections for non-smooth functions, allowing algorithms to handle implicit feasible regions like sublevel sets without requiring expensive proximity operators.
| Approach | Mathematical Operation | Computational Cost for Complex Sets |
|---|---|---|
| Metric Projection | $P_C(x) = \arg\min_{y \in C} \|x - y\|$ | High (Requires solving an optimization problem per step) |
| Fixed Point Mapping | $T(x)$ where $\text{Fix}(T) = C$ | Low (Requires a single function evaluation or subgradient step) |
Why It Works: Interleaving Optimization and Feasibility
How do we simultaneously minimize an objective function $f(x)$ and drive our iterates toward the fixed point set of $T$?
Rather than enforcing feasibility at every single step, fixed-point constraint algorithms interleave optimization steps (such as gradient descent, subgradient steps, or proximal updates) with fixed-point relaxation steps. Two classical iterative schemes form the backbone of this integration:
- Krasnosel’skiĭ–Mann (KM) Iteration: This scheme takes a convex combination of the current point and its image under $T$: $$x_{k+1} = (1 - \alpha_k) x_k + \alpha_k T(x_k)$$
- Halpern Iteration: This scheme anchors the update to a fixed reference point $u$, preventing the sequence from drifting: $$x_{k+1} = \alpha_k u + (1 - \alpha_k) T(x_k)$$
By embedding optimization steps directly into these fixed-point iterations, the algorithm balances two competing forces: the optimization step pulls the iterate toward the minimum of the function, while the operator $T$ coaxes the iterate back toward the invariant feasible region.
In Acceleration method for convex optimization over the fixed point set of a nonexpansive mapping, Iiduka proves that substituting exact metric projections with quasi-nonexpansive subgradient projections satisfies a "quasi-firm" nonexpansivity condition. This mathematical property ensures that the joint iteration converges globally to an optimal, feasible solution without ever requiring an exact projection.
Similarly, Iiduka shows in Proximal Point Algorithms for Nonsmooth Convex Optimization with Fixed Point Constraints and Incremental subgradient method for nonsmooth convex optimization with fixed point constraints that combining proximal operators with Halpern or KM updates yields faster convergence and stronger theoretical guarantees for non-smooth objectives than traditional subgradient projection methods.
Simplifying Intersections of Constraints
One of the most compelling reasons to use the fixed-point representation is its ability to handle multiple constraints seamlessly. Suppose our feasible region is the intersection of many convex sets:
$$C = \bigcap_{i=1}^m C_i$$
Projecting a point onto an intersection of sets sequentially (i.e., alternating projections) can be slow and geometrically erratic. However, fixed-point theory provides an elegant shortcut: we can construct a single composite mapping to represent the entire intersection.
As Iiduka et al. demonstrate in Fixed Point Quasiconvex Subgradient Method, one can average the individual mappings or projections of each constraint $C_i$ to form a single, unified nonexpansive mapping $T$. The fixed point set of this averaged operator is precisely the intersection of the individual sets. This structural simplification drastically reduces computational overhead, as the algorithm only needs to evaluate a single blended operator per iteration rather than navigating a complex hierarchy of individual geometric constraints.
Traditional Alternating Projections:
Iterate -> Project onto C1 -> Project onto C2 -> Project onto C3 (High Overhead)
Fixed-Point Convex Combination:
Iterate -> Evaluate T = w1*T1 + w2*T2 + w3*T3 -> Single Unified Step (Low Overhead)
Scaling and Extensions
The flexibility of the fixed-point constraint representation has allowed it to scale across several domains of modern optimization:
- Distributed and Parallel Computing: In large-scale networks, private objective functions may be distributed across multiple nodes. Iiduka (Parallel computing subgradient method for nonsmooth convex optimization over the intersection of fixed point sets of nonexpansive mappings) and Sakurai et al. (Iterative methods for parallel convex optimization with fixed point constraints) developed parallelized architectures where agents maintain local feasibility and optimize cooperatively using only local subgradient information and fixed-point mappings.
- Stochastic Optimization: For machine learning and large data regimes, Iiduka extended this paradigm to stochastic settings. In Two stochastic optimization algorithms for convex optimization with fixed point constraints and Stochastic approximation method using diagonal positive-definite matrices for convex optimization with fixed point constraints, the author blends Halpern fixed-point steps with stochastic gradients and adaptive learning rates (reminiscent of Adam and AMSGrad), enabling efficient online learning under complex operational constraints.
- Non-Euclidean and Non-Convex Domains: The framework has broken past flat, convex spaces. Iiduka et al. in Riemannian stochastic fixed point optimization algorithm successfully port quasi-nonexpansive constraint mappings to curved Riemannian manifolds. Meanwhile, application-specific settings like sparse portfolio optimization leverage these principles; Lai et al. in Linear Trading Position with Sparse Spectrum utilize a KM-structured fixed-point algorithm with a proximal-gradient step to handle non-differentiable geometric constraints that standard solvers cannot process efficiently.
By translating rigid geometric constraints into fluid, distance-preserving operator mappings, fixed-point representation changes the fundamental question of constrained optimization. It shifts the paradigm from "how do we force the point back into the set?" to "how do we smoothly guide the point toward invariance?"
Key Foundational Work
PARALLEL OPTIMIZATION ALGORITHM FOR SMOOTH CONVEX OPTIMIZATION OVER FIXED POINT SETS OF QUASI-NONEXPANSIVE MAPPINGS (2015) — contributed 3 concept elements to this direction.
Parallel computing subgradient method for nonsmooth convex optimization over the intersection of fixed point sets of nonexpansive mappings (2015) — contributed 2 concept elements to this direction.
Acceleration method for convex optimization over the fixed point set of a nonexpansive mapping (2015) — contributed 2 concept elements to this direction.