PaperlayerView exact revision on arXiv

Source-linked AI summary

Strong Duality Thresholds and Minimum Curvature for the Nearest Rectangular Symplectic Matrix Problem

Yulin Xie, Aiqing Zhu, Yifa Tang

arXiv:2610.31298v1math.OCcs.NAmath.NA

TL;DR

The paper asks when the semidefinite relaxation preserves the minimum for arbitrary targets and when second-order stationarity implies global optimality. The paper analyzes the primal problem, its semidefinite relaxation and duals, and the Riemannian Hessian, then develops a dual-based computational method. For every target, the relaxation is exact if and only if n ≥ 2k − 1; across six tested sizes, Dual is 2.55–12.60 times faster than RSD and 4.61–43.93 times faster than R–TR2.

  • Problem

    The paper asks when the semidefinite relaxation preserves the minimum for arbitrary targets and when second-order stationarity implies global optimality.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes the primal problem, its semidefinite relaxation and duals, and the Riemannian Hessian, then develops a dual-based computational method.

    Source: §1 · p. 2

  • Results

    For every target, the relaxation is exact if and only if n ≥ 2k − 1; across six tested sizes, Dual is 2.55–12.60 times faster than RSD and 4.61–43.93 times faster than R–TR2.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The semidefinite relaxation is exact for every target iff n ≥ 2k − 1, while dimensions k ≤ n ≤ 2k − 2 admit a strict duality gap.

    Source: §1 · p. 2

    At the unweighted critical dimension, arbitrarily small anisotropic perturbations can destroy strong duality for every target.

    Source: §5.5 · p. 15

Abstract

from arXiv · show

We study the nearest rectangular symplectic matrix problem in the squared Frobenius norm for arbitrary targets $T\in\mathbb R^{2n\times2k}$, with $n\ge k$. We prove that its semidefinite relaxation is exact for every target if and only if $n\ge2k-1$. Under this condition, the primal problem, the relaxation, and both Lagrangian dual problems attain the same optimal value. In this range, we derive the exact minimum Rayleigh quotient of the Riemannian Hessian at every feasible point under the Euclidean induced metric, and prove that all second-order stationary points are global minimizers. We also obtain global objective error bounds. We extend the strong-duality and minimum-curvature results to Hermitian positive definite row weights, proving that strong duality holds for every target if and only if the lowest eigenvalue of the weight has complex multiplicity at least $2k-1$. The dual formulation leads to a method whose main iterations use matrices of order $2k$, with $O(k^2)$ iterative storage apart from the full input and output. Across six tested sizes, mean-time speedups are $2.55$--$12.60$ over a Riemannian first-order method and $4.61$--$43.93$ over Jensen--Zimmermann R--TR2; batching gives a further factor of $3.45$--$23.53$ over sequential calls. The theoretical results complete the critical dimensions not covered by Gram convexification and quadratic matrix programming.

1 Introduction

The paper studies when a semidefinite relaxation solves the nearest rectangular symplectic matrix problem for arbitrary targets, and when second-order stationarity ensures global optimality. It establishes a sharp dimension threshold, derives curvature and weighted extensions, and evaluates a dual-based method.

1 Introduction

  • Prior square-problem landscape results assume a symplectic target, while the rectangular problem here allows arbitrary targets, including rank-deficient ones.The paper also addresses critical dimensions n = 2k − 1 not directly handled for k ≥ 3 by the cited quadratic matrix programming condition.Source: §1 · pp. 1–2
  • For every target, the semidefinite relaxation is exact if and only if n ≥ 2k − 1, and below that threshold a strict duality gap persists under sufficiently small target perturbations.In the exactness range, the primal problem, relaxation, and both Lagrangian dual problems attain the same optimal value.Source: §1 · p. 2
  • For n ≥ 2k − 1, the paper gives the exact minimum Riemannian Hessian Rayleigh quotient at every feasible point and shows every second-order stationary point is globally minimizing.It also derives global objective error bounds in all admissible dimensions, controlling the objective gap by the gradient residual and the negative part of the multiplier matrix.Source: §1 · p. 2
  • For Hermitian positive definite row weights, strong duality holds for every target if and only if the lowest eigenvalue has complex multiplicity at least 2k − 1.For the identity weight, this multiplicity is n, recovering the unweighted dimension condition.Source: §1 · p. 2
  • Across six tested sizes, Dual is 2.55–12.60 times faster than RSD and 4.61–43.93 times faster than R–TR2; sequential calls are 3.45–23.53 times slower than batched calls.The comparisons use mean solve times.Source: §1 · p. 2
  • The dual method uses a Newton method with preconditioned conjugate gradients and facilitates batched GPU solves for independent targets.The paper compares complete solve times at a common accuracy.Source: §1 · p. 2

2 The primal problem, semidefinite relaxation, and two duals

The section converts the symplectic constraint into a complex formulation, constructs the primal and relaxation duals, and gives optimality and recovery conditions. The two dual functions coincide, and their optimal values are attained.

2.1 Real and complex representations and constraint regularity

  • The real-to-complex representation preserves the Frobenius inner product and expresses the symplectic constraint as Im(U∗U) = J_m; the feasible set is a smooth embedded manifold and the primal minimum is attained.The constraint differential is surjective at every feasible point.Source: §2.1 · p. 3

2.2 The primal Lagrangian dual

  • The primal Lagrangian dual is finite exactly when K ⪰ 0 and B ker K = {0}; for such multipliers, its global minimizers satisfy UK = B.Outside this effective domain, the dual value is −∞.Source: §2.2 · p. 4

2.3 Semidefinite relaxation

  • The semidefinite relaxation replaces G = U∗U with G − U∗U ⪰ 0 while retaining Im G = J_m.The relaxation attains its minimum.Source: §2.3 · p. 4

2.4 Pointwise equality of the two dual functions

  • For every multiplier, the primal and relaxation dual functions coincide, and an optimal multiplier attaining the common dual value exists.The relaxation is strictly feasible, so Slater’s theorem establishes dual attainment [8, §5.2.3].Source: §2.4 · p. 5

2.5 Optimality conditions and recovery

  • A relaxation-feasible point and dual-feasible multiplier are optimal exactly when UK = B and range(G − U∗U) ⊆ ker K; if U is primal feasible, UK = B suffices for global optimality.For an optimal multiplier, K ≻ 0 gives the unique primal optimizer BK−1; when K is singular and strong duality holds, the optimizer set is described by the kernel of K.Source: §2.5 · p. 5

3 Normal projection multipliers and exact minimum curvature

Under the Euclidean induced metric, the section constructs the normal-projection multiplier and expresses the Riemannian Hessian through it. When n ≥ 2k − 1, a rank-one tangent direction attains the exact minimum curvature.

3.1 Normal projection, gradient, and Hessian

  • The normal projection of the ambient gradient uniquely determines a real skew-symmetric multiplier through a Sylvester equation, and this multiplier depends smoothly on U.With K(U) = I_m + iΩ_B(U), the Hessian is Π_U(2ZK(U)) and its quadratic form is 2 tr(ZK(U)Z∗).Source: §3.1 · p. 6

3.2 Minimum curvature and an attaining direction

  • The minimum-curvature lower bound is 2λ_min(K(U)), with equality precisely when ZK(U) = λZ; a tangent vector of complex rank one attains the minimum and is a smallest-eigenvalue Hessian eigenvector.The exact minimum curvature theorem applies when n ≥ 2k − 1.Source: §3.1 · p. 7, §3.2 · p. 7
  • For K = I_m + iΩ with real skew-symmetric Ω, the attaining direction satisfies ZK = λ_min(K)Z and λ_min(K) = 1 − ∥Ω∥₂.The construction uses a nonzero vector in the kernel of E∗ and a phase choice to satisfy the tangent condition.Source: §3.2 · p. 7

4 The sharp dimension threshold for universal strong duality

The universal exactness threshold is n ≥ 2k − 1: there, the primal, relaxation, and both Lagrangian duals attain the same value; below it, strict gaps occur. At the threshold, second-order stationarity certifies global optimality, and objective error can be bounded using residuals.

4 The sharp dimension threshold for universal strong duality

  • For every target, the semidefinite relaxation is exact if and only if n ≥ 2k − 1; below this threshold, strict duality gaps occur.In the exactness range, the primal problem, relaxation, and both Lagrangian dual problems attain the same optimal value.Source: §4 · p. 8, §4.1 · p. 8

4.1 Proof of the main theorem

  • The strict gap persists under sufficiently small target perturbations, so the dimension condition cannot be weakened.The lower-dimensional counterexamples can have full complex row rank and a real representation of full column rank.Source: §4 · p. 8, §4.1 · p. 10

4.2 Globality of second-order stationary points and objective error bounds

  • If n ≥ 2k − 1, every second-order stationary point is globally minimizing, while every nonglobal first-order stationary point has a strictly negative-curvature direction.The negative-curvature direction comes from the rank-one construction in the exact minimum-curvature result.Source: §4.2 · p. 10
  • In all admissible dimensions, objective error bounds control suboptimality through gradient residuals and negative eigenvalues without requiring an inverse of K.The bounds allow singular multipliers and do not require dual feasibility or primal strong duality.Source: §4.2 · p. 11

5 Strong duality under Hermitian row weighting

For Hermitian positive definite row weights, universal strong duality holds exactly when the smallest eigenvalue has complex multiplicity at least 2k − 1. The paper also establishes weighted minimum curvature and globality of second-order stationary points under this condition.

5.1 The weighted problem and main theorem

  • For fixed Hermitian positive definite H, standard Lagrangian strong duality holds for every B ∈ Cⁿˣᵐ if and only if the smallest-eigenvalue multiplicity d is at least m − 1.In the unweighted case, d = n, so the criterion agrees with Theorem 4.1.Source: §5.1 · p. 12

5.4 Proof of the multiplicity criterion

  • The multiplicity threshold is necessary: below it, the proof constructs targets with a strict primal-dual gap.For multiplicities from k through 2k − 2, the construction reduces the weighted dual value to a lower-dimensional unweighted gap; for d < k, the zero target yields a gap.Source: §5.1 · p. 12, §5.4 · p. 14

5.2 The weighted dual and attainment

  • The weighted primal problem and its standard Lagrangian dual have finite attained optimal values for every target.In diagonal row coordinates, the dual domain requires positive semidefinite row matrices and corresponding kernel conditions.Source: §5.2 · pp. 12–13

5.3 Minimum curvature of the weighted problem

  • When the smallest eigenvalue has complex multiplicity at least 2k − 1, the weighted minimum curvature is attained by a tangent vector of complex rank one.The curvature analysis uses the induced Euclidean metric.Source: §5.1 · p. 12, §5.3 · p. 13

5.5 Second-order stationary points and anisotropic perturbations

  • When the multiplicity is at least 2k − 1, every weighted second-order stationary point is globally minimizing, and every nonglobal first-order stationary point has strictly negative curvature.At the unweighted critical dimension, arbitrarily small anisotropic perturbations can destroy universal strong duality.Source: §5.5 · pp. 14–15

6 Numerical experiments

The experiments compare the dual method with two Riemannian methods and test batching across six problem sizes. Dual solves are faster in the reported comparisons, and batching further reduces total time.

6 Numerical experiments

  • The dual formulation updates a 2k × 2k multiplier and uses O(k^2) iterative storage, rather than iterating on a 2n × 2k primal matrix.The full target is still used to form its Gram matrix and recover the primal solution.Source: §6 · p. 15

6.1 Experimental setup

  • The study uses six combinations of n ∈ {2048, 4096} and k ∈ {16, 32, 48}, with 64 random targets per size and common accuracy requirements.All three methods use the same GPU and double precision; solve times include initialization, data transfers, and output recovery.Source: §6.1 · p. 16

6.2 Experimental results

  • Dual is 2.55–12.60 times faster than RSD and 4.61–43.93 times faster than R–TR2 across the six tested sizes.All 3456 single-target solves terminated normally and passed the accuracy checks.Source: Figure 1 · p. 17, §6.2 · p. 18
  • Batching reduces total solve time by a factor of 3.45–23.53 compared with sequential Dual solves.The relative separation narrows as k increases; the authors offer fuller GPU utilization by larger problems as one possible explanation.Source: Figure 1 · p. 17, §6.2 · p. 18

Conclusions

The paper establishes a sharp dimension threshold for universal strong duality and connects it to global optimality and curvature. It extends the criterion to weighted problems and reports computational advantages for the dual formulation.

Conclusions

  • For arbitrary targets, the exact threshold for strong duality is n ≥ 2k − 1; in the unweighted case, this dimension threshold follows from the stated criterion.Source: Conclusions · p. 18
  • Within the threshold range, the exact minimum-curvature formula shows every second-order stationary point is a global minimizer, and global objective error bounds quantify approximate-solution suboptimality..Source: Conclusions · p. 18
  • For Hermitian positive definite row weights, universal strong duality holds exactly when the lowest eigenvalue has complex multiplicity at least 2k − 1.The identity weight recovers the unweighted dimension threshold.Source: Conclusions · p. 18
  • Across six tested sizes, the dual method has shorter mean solve times than both Riemannian methods, and batching further reduces total time relative to sequential solves.The experiments complement the global optimality analysis with computational comparisons.Source: Conclusions · pp. 18–19

Related papers

Loading 2610.31298v1…