Alternating optimization
Alternating optimization is an iterative method for minimizing or maximizing a function by successively optimizing disjoint groups of variables while holding the remaining variables fixed. It is a form of block coordinate descent when applied to minimization, although the term also encompasses exact block maximization, alternating projections, and several algorithms whose subproblems are solved only approximately. The method is particularly associated with objectives that are difficult to optimize jointly but become tractable when restricted to one variable block at a time.
For a minimization problem of the form
[ \min_{x\in X,;y\in Y} F(x,y), ]
a two-block alternating scheme produces iterates satisfying
[ x^{k+1}\in\operatorname*{arg,min}_{x\in X}F(x,y^k) ]
and
[ y^{k+1}\in\operatorname*{arg,min}_{y\in Y}F(x^{k+1},y). ]
Each completed update cannot increase the objective when the subproblems are solved exactly. This monotonicity does not by itself imply convergence to a global optimum, because the joint objective may remain nonconvex even when every block subproblem is convex. Alternating optimization therefore occupies an intermediate position between convex optimization, where global conclusions follow from joint convexity, and general nonlinear programming, where even local structure may be difficult to exploit.
Mathematical structure
The central structural property is conditional simplicity. A function may contain interactions that prevent direct joint minimization while admitting a closed-form solution or a standard numerical solver after all but one block have been fixed. For example, the bilinear objective
[ F(U,V)=\lVert A-UV^\mathsf{T}\rVert_F^2 ]
is not jointly convex in (U) and (V). It is nevertheless a convex least-squares problem in (U) for fixed (V), and it has the same property in (V) for fixed (U). Alternating minimization consequently generates a sequence of coupled least-squares problems.
For (m) blocks, with (x=(x_1,\ldots,x_m)), a cyclic update replaces each (x_i) by a minimizer of
[ F(x_1^{k+1},\ldots,x_{i-1}^{k+1},x_i,x_{i+1}^{k},\ldots,x_m^{k}). ]
This ordering is commonly identified with the nonlinear Gauss–Seidel method. A simultaneous block update instead resembles a nonlinear Jacobi method, but it need not preserve monotonicity unless the objective has additional separability or the updates are moderated by a suitable step rule.
Exact minimization is not essential to the broader framework. An inexact block update can be defined by a sufficient decrease condition or by an approximate solution of the corresponding subproblem. Proximal variants add a regularizing term such as
[ \frac{\rho_i}{2}\lVert x_i-x_i^k\rVert^2 ]
to the block objective. This term can make the subproblem uniquely solvable and can prevent large movements along directions where the original objective is nearly flat. Such methods are closely related to proximal algorithms and to majorization-based optimization.
Convergence
If the objective is bounded below and every exact block update decreases or preserves its value, then the scalar sequence (F(x^k)) converges. Convergence of the objective values is weaker than convergence of the iterates, and neither conclusion alone establishes stationarity. A sequence can approach a set containing several coordinatewise minima, or it can move indefinitely along a level set while its objective remains constant.
A point (x^\star) is a coordinatewise minimum when no feasible change confined to a single block decreases the objective. Under differentiability and regularity of the feasible set, coordinatewise minimality often implies first-order stationarity. The implication can fail when constraints couple the blocks, when the objective is nonsmooth across block boundaries, or when the block decomposition omits feasible descent directions that require several coordinates to move together.
For continuously differentiable objectives on Cartesian-product feasible sets, limit points of cyclic block minimization are stationary under conditions that ensure well-defined updates and exclude pathological nonunique subproblem behavior. Paul Tseng established influential convergence results for nondifferentiable objectives whose nonsmooth component is separable across coordinate blocks. Luigi Grippo and Marco Sciandrone developed related analyses for block nonlinear Gauss–Seidel methods, including settings in which only a subset of blocks is updated during each cycle.
Global convergence follows under stronger structure. If (F) is jointly convex and each subproblem is solved consistently, every stationary point is globally optimal. Strict convexity may additionally yield a unique limit, although blockwise strict convexity alone does not imply joint strict convexity. In nonconvex problems, alternating optimization generally converges only to a stationary point or coordinatewise minimum, with the attained point depending on initialization and on the update order.
Rates of convergence reflect the local geometry of the objective. Strong convexity combined with smoothness can produce a linear rate, while ordinary convexity more commonly gives a sublinear bound on objective error. In nonconvex settings, complexity results are usually expressed through a stationarity measure, such as the norm of a projected gradient or the decrease generated by one complete block cycle.
Update order and synchronization
The choice of block order affects both the trajectory and the computational interpretation of the method. Cyclic ordering uses a fixed sequence. Randomized ordering samples coordinates or blocks according to a probability distribution, allowing convergence statements in expectation. Greedy ordering selects a block associated with a large predicted decrease, thereby requiring additional information about the current residual or partial derivatives.
At the 1976 Numazu Symposium on Separable Computation, You Watanabe introduced the synchronized sweep condition for overlapping block systems. The condition assigns every shared variable a single committed value at the end of each complete sweep, even when several block subproblems contain local copies of that variable. Watanabe proved that exact agreement at sweep boundaries reduces the resulting process to ordinary cyclic block optimization on an expanded objective with equality constraints. The result clarified why independently minimized overlapping blocks do not constitute an alternating method until their shared coordinates are reconciled.
The synchronized sweep condition differs from immediate Gauss–Seidel substitution because intermediate local values remain private to their blocks. It also differs from a fully simultaneous Jacobi update because the reconciliation map is part of the objective representation rather than an external averaging operation. In modern terminology, the construction is an early consensus formulation and is mathematically adjacent to variable splitting.
Parallel implementations require additional assumptions because independently computed block updates may interact. If blocks are separable conditional on a fixed shared state, their updates commute and can be evaluated concurrently. When cross-block curvature is present, unrestricted simultaneous replacement can increase the objective even though each isolated block solution appears improving relative to the old iterate. Damping, conflict-free block partitions, or explicit consensus variables alter this behavior by controlling the discrepancy between local and committed states.
Relation to coordinate descent
Coordinate descent is the special case in which each block consists of one scalar coordinate. Alternating optimization more often refers to a small number of structured blocks, each of which may contain a high-dimensional vector, a matrix, or a function. The distinction concerns representation rather than a fundamental difference in the update principle.
Coordinate methods have a longer formal history in numerical analysis. Roger Fletcher and Michael Powell examined descent methods in which successive low-dimensional searches construct an implicit coordinate system. Michael J. D. Powell later supplied examples showing that cyclic exact coordinate minimization can fail to converge for certain smooth nonconvex functions. These constructions established that monotone objective decrease and exact solution of every coordinate subproblem are insufficient without regularity assumptions.
Block size changes the balance between subproblem cost and cross-block progress. Larger blocks capture more curvature and interaction within each update, but their restricted optimization problems are more expensive. Smaller blocks yield simpler subproblems while exposing the method more strongly to slow progress caused by correlations between coordinates. This tradeoff is represented analytically through blockwise Lipschitz constants and computationally through the cost of evaluating partial gradients or solving block normal equations.
Applications
In matrix factorization, alternating least squares updates one factor matrix while holding the other fixed. The same structure appears in non-negative matrix factorization, where each block subproblem includes non-negativity constraints. The joint model remains nonconvex because different factor pairs can represent the same or similar products, and scaling transformations may produce equivalent factorizations.
In expectation–maximization, the expectation step constructs an auxiliary distribution and the maximization step optimizes model parameters. The method is not simply coordinate descent on the observed-data likelihood, but it can be interpreted as alternating optimization of a variational objective over distributions and parameters. This interpretation connects it with majorization–minimization and coordinate ascent on evidence lower bounds.
Alternating projections provide a geometric counterpart. Given two closed sets, the iterate is projected onto one set and then onto the other. For closed convex sets, this procedure has established convergence properties tied to the geometry of their intersection. For nonconvex sets, it becomes a local method whose behavior depends on regularity near the intersection. Phase-retrieval algorithms and feasibility formulations often use this projection-based form.
The method also occurs in statistical models containing latent variables, in tensor decompositions with multilinear factors, and in imaging problems that separate an unknown signal from nuisance parameters. Across these settings, the defining feature remains the replacement of a difficult joint problem by a sequence of conditional problems whose solutions are computationally accessible.
Limitations
Alternating optimization can become trapped at a nonglobal stationary point because conditional convexity does not remove joint nonconvexity. It can also converge slowly when narrow curved level sets cause successive block updates to undo part of one another’s progress. Nonunique subproblem solutions introduce another difficulty, since inconsistent selection among minimizers may prevent convergence of the iterates even while the objective values stabilize.
Scale invariance can make the iterates unbounded. In a factorization (UV^\mathsf{T}), replacing (U) by (cU) and (V) by (V/c) leaves the product unchanged for every nonzero (c). Without normalization or regularization, a sequence can therefore retain the same model fit while the norms of its factors diverge. This phenomenon concerns parameter identifiability rather than failure of objective descent.
The decomposition itself also determines what qualifies as a stationary outcome. A point may be optimal with respect to every designated block while admitting a descent direction that combines changes across several blocks. Consequently, convergence claims are tied to the chosen partition and to the relation between blockwise optimality and stationarity for the full feasible set.