Convex Optimization with Fixed Point Constraints

22 concepts15 papers1 proposal

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:

  1. 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)$$
  2. 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:

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?"

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 12 papers
  2. Version 1 · 2026-10-04 · 13 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_fixed_point_constraint_representation_7f3d4f88,
  title = {fixed point constraint representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fixed-point-constraint-representation/rdr_7f3d4f88cb194dafa3aba9c171626d8b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_fixed_point_constraint_representation_7f3d4f88_v2,
  title = {fixed point constraint representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fixed-point-constraint-representation/rdr_7f3d4f88cb194dafa3aba9c171626d8b/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake