Sums-of-squares Polyconvexity

Find this post at FAU DCN-AvH Math & Research posts.

1 Introduction

Polyconvex functions are functions of a matrix variable characterized by a convex dependence on the minors of the matrix. This generalization of convexity is fundamental in the Calculus of Variations, where it provides a sufficient condition for the well-posedness of many optimization problems arising in material modelling and nonlinear elasticity [3, 6]. Unfortunately, checking polyconvexity is very difficult in general, even for well-behaved classes of functions such as polynomials.

To overcome this difficulty, we take advantage of the tractable Semidefinite Program (SDP) formulation of sum-of-squares (SOS) problems to introduce two computationally tractable strengthenings of polyconvexity for polynomials.

Notation. Given a matrix in $X \in \mathbb{R}^{m \times n}$ , $\operatorname{adj}_s X$ stands for the matrix of all $s \times s$ minors of the matrix $X$ for $2 \leq s \leq \min \{m, n\}$ and

$N = \sum\limits_{s=1}^{\min\{m,n\}} \binom{m}{s} \binom{n}{s}.$

We define $T : \mathbb{R}^{m \times n} \to \mathbb{R}^{N}$ as

$T(X) = (X,\operatorname{adj}_2X,\ldots,\operatorname{adj}_{\min\{m,n\}}X).$

SOS-polyconvexity

We begin by recalling the definition of a polyconvex function.

Definition 1 (Polyconvexity)
A function $f:\R^{m\times n}\to\R \cup \{+\infty\}$ is polyconvex if there exists a convex function

We also recall the following equivalent characterization of polyconvexity, which resembles the usual first-order characterization of convexity.

Proposition 1. ([3, Theorem 5.6])
A function $f:\R^{m\times n} \to \R$ is polyconvex if and only if there exists a function $q:\R^{m\times n}\to \R^N$ such that

$f(X)-f(Y)- \langle{q(Y)},{p(X)-p(Y)}\rangle \geq 0 \quad \forall X,Y \in \R^{m\times n}.$

We now define SOS strengthenings using these equivalent definitions of polyconvexity.

The first strengthening, called Lifted SOS polyconvexity, requires a polynomial function of a matrix variable to be an SOS convex polynomial of the matrix minors.

Definition 2 (Lifted SOS polyconvexity)
A polynomial $f(X) : \mathbb{R}^{m \times n} \to \mathbb{R}$ is said to be Lifted SOS polyconvex (Lifted SOS PC) if there exists an SOS convex polynomial $g:\mathbb{R}^{N} \to \mathbb{R}$ such that $f(X)=g(T(X))$ .

The second strengthening, called SOS polyconvexity, replaces non-negativity with SOS constraints in Proposition 1.

Definition 3 (SOS polyconvexity)
A polynomial $f(X) : \mathbb{R}^{m \times n} \to \mathbb{R}$ is said to be SOS polyconvex (SOS PC) if for all matrices $X,Y \in \mathbb{R}^{m\times n}$ , there exists a vector-valued polynomial $q: \mathbb{R}^{m \times n} \to \mathbb{R}^{N}$ such that

$f(X)-f(Y) - \langle{q(Y)},{T(X)-T(Y)}\rangle \text{ is SOS in X and Y.}$

As all SOS convex polynomials are convex, it is clear that all lifted SOS PC polynomials are also polyconvex. Similarly, all SOS PC polynomials are also polyconvex polynomials since all SOS polynomials are non-negative.

We now investigate the relation between these two strengthenings. Contrary to the equivalent definitions of SOS convexity in [1], the two approaches to defining SOS polyconvexity are not equivalent.

Theorem 1. Lifted SOS polyconvex polynomials are always SOS polyconvex.
The converse implication fails for polynomials in $2 \times 2$ matrices of degree at least four [5, Theorem 2.2]. Specifically, borrowing a classical example of Alibert, Dacorogna, and Marcellini [2, 3, 4], we show that the polynomial $\left| X \right|^2(\left| X \right|^2 - 2\det X)$ is SOS polyconvex but not lifted SOS polyconvex.

Theorem 2.
The function $f:\R^{2\times 2} \to \R$ defined by $f(X)=\left| X \right|^2 ( \left| X \right|^2 - 2\det X )$ is SOS PC but not lifted SOS PC.

Sketch of proof. To show that $f(X)$ is SOS PC, we fix the order of the minors vector to be $p(X)=(X_{11}, X_{21}, X_{12}, X_{22}, \det X)$ and use semidefinite programming to search for a cubic polynomial vector $q:\R^{2\times 2} \to \R^5$ such that the polynomial

$f(X)-f(Y)-\langle{q(Y)},{p(X)-p(Y)}\rangle \text{ is SOS.}$

After rounding for numerical errors, we use the resulting SDP solution to provide an explicit analytical certificate [5, Sect. 2.3.1].

3 Conclusion

We have introduced two notions of SOS polyconvexity that generalize the notions of SOS convexity. Unlike SOS convexity, we have seen that equivalent notions of polyconvexity do not lead to equivalent notions of their SOS strengthenings. The gap between the definitions of SOS polyconvexity and polyconvexity needs to be investigated further. For example, we expect there to be polynomials that are polyconvex in the ‘first order’ sense that are not SOS polyconvex, but we do not presently have explicit examples.

Joint work with:
• Giovanni Fantuzzi. Department of Mathematics, Friedrich–Alexander Universität Erlangen–Nürnberg
• Didier Henrion. LAAS–CNRS, Université de Toulouse
• Martin Kružík. Institute of Information Theory and Automation, Czech Academy of Sciences,
• Stephan Weis. Czech Technical University in Prague

This work was funded by the ANR-DFG project MONET: Moment-SOS Optimization for Network Dynamics (grant no. 568735456).

Pre-print on arXiv:
G. Fantuzzi, D. Henrion, M. Kru{ž}ík, A. Murali, and S. Weis (2026) Polyconvexity with Moments and Sums of Squares, arXiv: 2604.11124 [math.OC], https://arxiv.org/abs/2604.11124

References

[1] A. A. Ahmadi and P. A. Parrilo (2013) A complete characterization of the gap between convexity and sosconvexity”, SIAM J. Optim., Vol. 23, No. 2, pp. 811–833, https://doi.org/10.1137/110856010
[2] J.-J. Alibert and B. Dacorogna (1992) An example of a quasiconvex function that is not polyconvex in two dimensions”, Arch. Rational Mech. Anal, Vol. 117, No. 2, pp. 155–166, https://doi.org/10.1007/BF00387763
[3] B. Dacorogna (1989) Direct methods in the calculus of variations, Applied Mathematical Sciences. Springer-Verlag, Berlin, Vol. 78, pp. x+308, https://doi.org/10.1007/978-3-642-51440-1
[4] B. Dacorogna and H. Koshigoe (1993) On the different notions of convexity for rotationally invariant functions”, Ann. Fac. Sci. Toulouse Math. Vol. 6, No. 2.2, pp. 163–184. url: http://www.numdam.org/item?id=AFST_1993_6_2_2_163_0
[5] G. Fantuzzi, D. Henrion, M. Kružík, A. Murali, and S. Weis (2026) Polyconvexity with Moments and Sums of Squares, arXiv: 2604.11124 [math.OC], https://arxiv.org/abs/2604.11124
[6] F. Rindler (2018) Calculus of variations, Universitext. Springer, Cham, pp. xii+444. doi: 10.1007/978-3319-77637-8, https://doi.org/10.1007/978-3-319-77637-8