[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

An efficient alternating minimization method for fourth degree polynomial optimization

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

In this paper, we consider a class of fourth degree polynomial problems, which are NP-hard. First, we are concerned with the bi-quadratic optimization problem (Bi-QOP) over compact sets, which is proven to be equivalent to a multi-linear optimization problem (MOP) when the objective function of Bi-QOP is concave. Then, we introduce an augmented Bi-QOP (which can also be regarded as a regularized Bi-QOP) for the purpose to guarantee the concavity of the underlying objective function. Theoretically, both the augmented Bi-QOP and the original problem share the same optimal solutions when the compact sets are specified as unit spheres. By exploiting the multi-block structure of the resulting MOP, we accordingly propose a proximal alternating minimization algorithm to get an approximate optimal value of the problem under consideration. Convergence of the proposed algorithm is established under mild conditions. Finally, some preliminary computational results on synthetic datasets are reported to show the efficiency of the proposed algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Barmpoutis, A., Jian, B., Vemuri, B., Shepherd, T.: Symmetric positive 4th order tensors and their estimation from diffusion weighted MRI. In: Karssemijer, N., Lelieveldt, B. (eds.) Lecture Notes in Computer Science, pp. 308–319. Springer, New York (2007)

    Google Scholar 

  2. Chen, B., He, S., Li, Z., Zhang, S.: Maximum block improvement and polynomial optimization. SIAM J. Optim. 22, 87–107 (2012)

    Article  MathSciNet  Google Scholar 

  3. Chen, H., Chen, Y., Li, G., Qi, L.: A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test. Numer. Linear Algebra Appl. 25(1), e2125 (2018)

    Article  MathSciNet  Google Scholar 

  4. Chen, H., Huang, Z., Qi, L.: Copositivity detection of tensors: theory and algorithm. J. Optim. Theory Appl. 174, 746–761 (2017)

    Article  MathSciNet  Google Scholar 

  5. Chen, H., Huang, Z., Qi, L.: Copositive tensor detection and its applications in physics and hypergraphs. Comput. Optim. Appl. 69, 133–158 (2018)

    Article  MathSciNet  Google Scholar 

  6. Han, D., Dai, H., Qi, L.: Conditions for strong ellipticity of anisotropic elastic materials. J. Elast. 97, 1–13 (2009)

    Article  MathSciNet  Google Scholar 

  7. He, S., Li, Z., Zhang, S.: Approximation algorithms for homogeneous polynomial optimization with quadratic constraints. Math. Program. Ser. B 125, 353–383 (2010)

    Article  MathSciNet  Google Scholar 

  8. Hof, P., Scherer, C., Heuberger, P.: Model-Based Control: Bridging Rigorous Theory and Advanced Technology: Part I. Springer, New York (2009)

    Google Scholar 

  9. Hu, S.L., Huang, Z.: Alternating direction method for bi-quadratic programming. J. Global Optim. 51, 429–446 (2011)

    Article  MathSciNet  Google Scholar 

  10. Jiang, B., Ma, S., Zhang, S.: Alternating direction method of multipliers for real and complex polynomial optimization models. Optimization 63, 883–898 (2014)

    Article  MathSciNet  Google Scholar 

  11. Kolda, T., Mayo, J.: Shifted power method for computing tensor eigenvalues. SIAM J. Matrix Anal. Appl. 32, 1095–1124 (2011)

    Article  MathSciNet  Google Scholar 

  12. Lasserre, J.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796–817 (2001)

    Article  MathSciNet  Google Scholar 

  13. Ling, C., He, H.J., Qi, L.Q.: Improved approximation results on standard quartic polynomial optimization. Optim. Lett. 11, 1767–1782 (2017)

    Article  MathSciNet  Google Scholar 

  14. Ling, C., Nie, J., Qi, L., Ye, Y.: Biquadratic optimization over unit spheres and semidefinite programming relaxations. SIAM J. Optim. 20, 1286–1310 (2009)

    Article  MathSciNet  Google Scholar 

  15. Luo, Z., Zhang, S.: A semidefinite relaxation scheme for multivariate quartic polynomial optimization with wuadratic constraints. SIAM J. Optim. 20, 1716–1736 (2010)

    Article  MathSciNet  Google Scholar 

  16. Nie, J.: An exact Jacobian SDP relaxation for polynomial optimization. SIAM J. Optim. 137, 225–255 (2013)

    MathSciNet  MATH  Google Scholar 

  17. Nie, J.: Polynomial optimization with real varieties. SIAM J. Optim. 23, 1634–1646 (2013)

    Article  MathSciNet  Google Scholar 

  18. Nie, J.: The hierarchy of local minimums in polynomial optimization. Math. Program. 151, 555–583 (2015)

    Article  MathSciNet  Google Scholar 

  19. Nie, J.: Generating polynomials and symmetric tensor decomposition. Found. Comput. Math. 17, 423–465 (2017)

    Article  MathSciNet  Google Scholar 

  20. Nie, J., Wang, L.: Semidefinite relaxations for best rank-1 tensor approximations. SIAM J. Matrix Anal. Appl. 35, 1155–1179 (2014)

    Article  MathSciNet  Google Scholar 

  21. Parrilo, P.: Structured semidefinite programs and semialgebraic geometrymethods in robustness and optimization. Ph.D. thesis, California Institute of Technology, Pasadena, California

  22. Qi, L.: Eigenvalues of a real supersymmetric tensor. J. Symbolic Comput. 40(6), 1302–1324 (2005)

    Article  MathSciNet  Google Scholar 

  23. Qi, L., Wang, F., Wang, Y.: Z-eigenvalue methods for a global polynomial optimization problem. Math. Program. 118(2), 301–316 (2009)

    Article  MathSciNet  Google Scholar 

  24. Razaviyayn, M., Hong, M., Luo, Z.: A unified convergence analysis of block successive minimization methods for nonsmooth optimization. SIAM J. Optim. 23(2), 1126–1153 (2013)

    Article  MathSciNet  Google Scholar 

  25. So, A.M.C.: Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems. Math. Program. 129, 357–382 (2011)

    Article  MathSciNet  Google Scholar 

  26. Soare, S., Yoon, J., Cazacu, O.: On the use of homogeneous polynomials to develop anisotropic yield functions with applications to sheet forming. Int. J. Plast. 24, 915–944 (2008)

    Article  Google Scholar 

  27. Tseng, P.: Convergenc of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109, 475–494 (2001)

    Article  MathSciNet  Google Scholar 

  28. Wang, Y., Aron, M.: A reformulation of the strong ellipticity conditions for unconstrained hyperelastic media. J. Elasticity 44, 89–96 (1996)

    Article  MathSciNet  Google Scholar 

  29. Wang, Y., Caccetta, L., Zhou, G.: Convergence analysis of a block improvement method for polynomial optimization over unit spheres. Numer. Linear Algebra Appl. 22, 1059–1076 (2015)

    Article  MathSciNet  Google Scholar 

  30. Yang, Y., Yang, Q.: On solving biquadratic optimization via semidefinite relaxation. Comput. Optim. Appl. 53, 845–867 (2012)

    Article  MathSciNet  Google Scholar 

  31. Zhang, X., Ling, C., Qi, L.: Semidefinite relaxation bounds for bi-quadratic optimization problems with quadratic constraints. J. Global Optim. 49, 293–311 (2011)

    Article  MathSciNet  Google Scholar 

  32. Zhou, G., Caccette, L., Teo, K., Wu, S.: Nonnegative polynomial optimization over unit spheres and convex programming relaxations. SIAM J. Optim. 22, 987–1008 (2012)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors would like to thank the two anonymous referees for their valuable comments, which greatly helped us improve the quality of this paper. H. Chen was supported in part by National Natural Science Foundation of China (NSFC) (No. 12071249). H. He was supported in part by NSFC (Nos. 11771113 and 11971138) and Natural Science Foundation of Zhejiang Province (No. LY20A010018). Y. Wang was supported in part by NSFC (No. 12071250).

Author information

Authors and Affiliations

  1. School of Management Science, Qufu Normal University, Rizhao, Shandong, 276800, China

    Haibin Chen & Yiju Wang

  2. School of Mathematics and Statistics, Ningbo University, Ningbo, 315211, China

    Hongjin He

  3. Department of Mathematics and Statistics, Curtin University, Perth, WA, Australia

    Guanglu Zhou

Authors
  1. Haibin Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hongjin He
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yiju Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Guanglu Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hongjin He.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

Appendix

In this appendix, we present detailed proofs for Theorems 4 and 5.

A Proof of Theorem 4

Proof

Due to the compactness of both \({\mathbb {D}}_1\) and \({\mathbb {D}}_2\), it is not difficult to see that the sequence \(\{(\mathbf{x}^{(k)},\mathbf{y}^{(k)},\mathbf{z}^{(k)},\mathbf{w}^{(k)})\}\) generated by Algorithm 1 is bounded, which further implies that such a sequence has at least one limit point \(\mathbf{t}^*=(\mathbf{x}^*,\mathbf{y}^*,\mathbf{z}^*,\mathbf{w}^*)\). Without loss of generality, suppose that \(\{\mathbf{t}^{(p_k)}\}\) is a subsequence of \(\{\mathbf{t}^{(k)}\}\) with limit point \(\mathbf{t}^*\), i.e.,

$$\begin{aligned} \lim _{k\rightarrow \infty }{} \mathbf{t}^{(p_k)}=\mathbf{t}^*. \end{aligned}$$

It follows from Item (ii) of Theorem 3 that

$$\begin{aligned} \Vert \mathbf{t}^{(p_k+1)}-\mathbf{t}^*\Vert \le \Vert \mathbf{t}^{(p_k+1)}-\mathbf{t}^{(p_k)}\Vert +\Vert \mathbf{t}^{(p_k)}-\mathbf{t}^*\Vert \rightarrow 0,~~ k\rightarrow \infty . \end{aligned}$$

To verify that \(\mathbf{t}^*\) is a stationary point of (9), we just need to prove the following variational inequality holds:

$$\begin{aligned} \langle \nabla f_{\alpha }(\mathbf{t}^*), \mathbf{t}-\mathbf{t}^*\rangle \ge 0,\quad \forall \mathbf{t}\in {\mathbb {D}}_1\times {\mathbb {D}}_1\times {\mathbb {D}}_2\times {\mathbb {D}}_2. \end{aligned}$$
(14)

Since \(\{\mathbf{t}^{(p_k)}\}\) is a subsequence of \(\{\mathbf{t}^{(k)}\}\), it is clear from the \(\mathbf{x}\)-subproblem of Algorithm 1 that

$$\begin{aligned} f_{\alpha }(\mathbf{x},\mathbf{y}^{(p_k)},\mathbf{z}^{(p_k)},\mathbf{w}^{(p_k)})\ge f_{\alpha }(\mathbf{x}^{(p_k+1)},\mathbf{y}^{(p_k)},\mathbf{z}^{(p_k)},\mathbf{w}^{(p_k)}),~\forall ~\mathbf{x}\in {\mathbb {D}}_1. \end{aligned}$$

Consequently, letting \(k\rightarrow \infty \) in the above inequality leads to

$$\begin{aligned} \langle \nabla _\mathbf{x}f_{\alpha }(\mathbf{t}^*),\mathbf{x}-\mathbf{x}^*\rangle&=f_{\alpha }(\mathbf{x}-\mathbf{x}^*,\mathbf{y}^*,\mathbf{z}^*,\mathbf{w}^*) \nonumber \\&=f_{\alpha }(\mathbf{x},\mathbf{y}^*,\mathbf{z}^*,\mathbf{w}^*)-f_{\alpha }(\mathbf{x}^*,\mathbf{y}^*,\mathbf{z}^*,\mathbf{w}^*) \nonumber \\&\ge 0. \end{aligned}$$
(15)

Similarly, it follows from the \(\mathbf{y}\)-, \(\mathbf{z}\)-, and \(\mathbf{w}\)-subproblems of Algorithm 1 that

$$\begin{aligned} \left\{ \begin{aligned}&\langle \nabla _\mathbf{y}f_{\alpha }(\mathbf{t}^*),\mathbf{y}-\mathbf{y}^*\rangle \ge 0, \quad \forall \mathbf{y}\in {\mathbb {D}}_1,\\&\langle \nabla _\mathbf{z}f_{\alpha }(\mathbf{t}^*),\mathbf{z}-\mathbf{z}^*\rangle \ge 0,\quad \forall \mathbf{z}\in {\mathbb {D}}_2,\\&\langle \nabla _\mathbf{w}f_{\alpha }(\mathbf{t}^*),\mathbf{w}-\mathbf{w}^*\rangle \ge 0, \quad \forall \mathbf{w}\in {\mathbb {D}}_2. \end{aligned} \right. \end{aligned}$$
(16)

By invoking the fact that

$$\begin{aligned} \nabla f_{\alpha }(\mathbf{t}^*)=\left( \nabla _\mathbf{x}f_{\alpha }(\mathbf{t}^*),\nabla _\mathbf{y}f_{\alpha }(\mathbf{t}^*),\nabla _\mathbf{z}f_{\alpha }(\mathbf{t}^*),\nabla _\mathbf{w}f_{\alpha }(\mathbf{t}^*)\right) , \end{aligned}$$

it then follows from (15) and (16) that variational inequality (14) holds, which means that \(\mathbf{t}^*\) is a stationary point of the augmented MOP (9). \(\square \)

B Proof of Theorem 5

Proof

We first prove Item (i). By the concavity of \({{\varvec{f}}}^2_{\alpha }(\mathbf{x},\mathbf{z})\), it holds for \(k\in {\mathbb {N}}\) that

$$\begin{aligned} {{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k+1)},\mathbf{z}^{(k)})-{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)}) \le \left\langle \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)}), \mathbf{x}^{(k+1)}-\mathbf{x}^{(k)}\right\rangle . \end{aligned}$$
(17)

Clearly, if \(\nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)})=0\), then, it follows from Algorithm 2 that \(\mathbf{x}^{(k+1)}=\mathbf{x}^{(k)}\) and (17) holds; Otherwise, i.e.,

$$\begin{aligned} \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)})\ne 0. \end{aligned}$$

It follows that

$$\begin{aligned}&\left\langle \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)}), \mathbf{x}^{(k+1)}-\mathbf{x}^{(k)}\right\rangle \\&=\left\langle \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)}), -\frac{\nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)})}{\Vert \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)})\Vert }-\mathbf{x}^{(k)}\right\rangle \\&= -\Vert \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)})\Vert -\left\langle \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)}), \mathbf{x}^{(k)}\right\rangle , \end{aligned}$$

which, together with Cauchy-Schwarz inequality, implies that

$$\begin{aligned} \left\langle \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)}), \mathbf{x}^{(k+1)}-\mathbf{x}^{(k)}\right\rangle \le 0. \end{aligned}$$

Consequently, it follows from (17) that

$$\begin{aligned} {{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k+1)},\mathbf{z}^{(k)})\le {{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)}). \end{aligned}$$
(18)

Similarly, we have

$$\begin{aligned} {{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k+1)},\mathbf{z}^{(k+1)})\le {{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k+1)},\mathbf{z}^{(k)}). \end{aligned}$$
(19)

Combining (19) with (18) immediately leads to

$$\begin{aligned} {{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k+1)},\mathbf{z}^{(k+1)})\le {{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)}). \end{aligned}$$

On the other hand, if there exists a k such that

$$\begin{aligned} {{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k+1)},\mathbf{z}^{(k+1)})= {{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)}), \end{aligned}$$

then, it follows from (18) and (19) that

$$\begin{aligned} {{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k+1)},\mathbf{z}^{(k+1)})={{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k+1)},\mathbf{z}^{(k)})={{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)}). \end{aligned}$$

From (17) and the fact that \(\Vert \mathbf{x}^{(k+1)}\Vert =\Vert \mathbf{x}^{(k)}\Vert =1\), we know that

$$\begin{aligned} {{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k+1)},\mathbf{z}^{(k)})<{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)})~\Leftrightarrow ~\mathbf{x}^{(k+1)}\ne \mathbf{x}^{(k)}. \end{aligned}$$

Similarly, we can obtain that

$$\begin{aligned} {{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k+1)},\mathbf{z}^{(k+1)})<{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k+1)},\mathbf{z}^{(k)})~\Leftrightarrow ~\mathbf{z}^{(k+1)}\ne \mathbf{z}^{(k)}, \end{aligned}$$

which means that \(\{{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)})\}\) is strictly decreasing.

Now, we prove Item (ii). If Algorithm 2 terminates in finite number of steps, without loss of generality, suppose it stops at the k-th iteration. From the discussion of Item (i), it holds that

$$\begin{aligned} {{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k+1)},\mathbf{z}^{(k+1)})={{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)}) \end{aligned}$$

and

$$\begin{aligned} \mathbf{x}^{(k+1)}=\mathbf{x}^{(k)},~\mathbf{z}^{(k+1)}=\mathbf{z}^{(k)}. \end{aligned}$$

Then, it follows from the iterative schemes of Algorithm 2 that

$$\begin{aligned} \left\{ \begin{aligned}&\nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)})=\mathbf{0}, \\&\nabla _{\mathbf{z}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)})=\mathbf{0}. \end{aligned} \right. \end{aligned}$$

Thus, for any \(\mathbf{x}\in {\mathbb {R}}^n, \mathbf{z}\in {\mathbb {R}}^m\) with \(\Vert \mathbf{x}\Vert =1\) and \(\Vert \mathbf{z}\Vert =1\), it holds that

$$\begin{aligned} \left\langle \mathbf{x}-\mathbf{x}^{(k)}, \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)})\right\rangle +\left\langle \mathbf{z}-\mathbf{z}^{(k)}, \nabla _{\mathbf{z}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)})\right\rangle =0, \end{aligned}$$

which implies that \((\mathbf{x}^{(k)}, \mathbf{z}^{(k)})\) is a stationary point of Bi-QOP (2).

Hereafter, we prove Item (iii). Due to the monotonicity of \(\{{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)})\}\) and compactness of \({\mathbb {D}}_1\) and \({\mathbb {D}}_2\), we know that \(\{{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)})\}\) is a convergent sequence. It then follows from (17) that

$$\begin{aligned} \lim _{k\rightarrow \infty }\left\langle \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k)},\mathbf{z}^{(k)}), \mathbf{x}^{(k+1)}-\mathbf{x}^{(k)}\right\rangle =0. \end{aligned}$$
(20)

On the other hand, the boundedness of the sequence \(\{(\mathbf{x}^{(k)}, \mathbf{z}^{(k)})\}\) implies that it has at least one accumulation point. Without loss of generality, assume \(({\hat{\mathbf{x}}}, {\hat{\mathbf{z}}})\) is an accumulation point of the subsequence \(\{(\mathbf{x}^{(k_j)}, \mathbf{z}^{(k_j)})\}\). Then we have

$$\begin{aligned} \Vert {\hat{\mathbf{x}}}\Vert =\Vert {\hat{\mathbf{z}}}\Vert =1. \end{aligned}$$

Now, if \(\lim _{j\rightarrow \infty }\nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k_j)},\mathbf{z}^{(k_j)})=\mathbf{0}\), it then follows from (20) and the continuity of \({{\varvec{f}}}^2_{\alpha }(\mathbf{x},\mathbf{z})\) that

$$\begin{aligned} \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }({\hat{\mathbf{x}}},{\hat{\mathbf{z}}})=\mathbf{0}, \end{aligned}$$

which means that

$$\begin{aligned} \mathcal {A}{\hat{\mathbf{x}}}{\hat{\mathbf{z}}}{\hat{\mathbf{z}}}=\alpha {\hat{\mathbf{x}}}. \end{aligned}$$
(21)

If \(\lim _{j\rightarrow \infty }\nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k_j)},\mathbf{z}^{(k_j)})\ne \mathbf{0}\), then by Step 3 of Algorithm 2, it follows from (17) and (20) that

$$\begin{aligned}&\lim _{k\rightarrow \infty }\left\langle \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k_j)},\mathbf{z}^{(k_j)}), \mathbf{x}^{(k_j+1)}-\mathbf{x}^{(k_j)}\right\rangle \\&=\lim _{k\rightarrow \infty }\left\langle \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k_j)},\mathbf{z}^{(k_j)}), -\frac{\nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k_j)},\mathbf{z}^{(k_j)})}{\Vert \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k_j)},\mathbf{z}^{(k_j)})\Vert } -\mathbf{x}^{(k_j)}\right\rangle \\&=\lim _{k\rightarrow \infty }\left( -\Vert \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k_j)},\mathbf{z}^{(k_j)})\Vert -\left\langle \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }(\mathbf{x}^{(k_j)},\mathbf{z}^{(k_j)}),{\hat{\mathbf{x}}}\right\rangle \right) \\&=-\Vert \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }({\hat{\mathbf{x}}},{\hat{\mathbf{z}}})\Vert -\left\langle \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }({\hat{\mathbf{x}}},{\hat{\mathbf{z}}}),{\hat{\mathbf{x}}}\right\rangle \\&=0, \end{aligned}$$

which, together with \(\Vert {\hat{\mathbf{x}}}\Vert =1\), implies that

$$\begin{aligned} \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }({\hat{\mathbf{x}}},{\hat{\mathbf{z}}})=-\Vert \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }({\hat{\mathbf{x}}},{\hat{\mathbf{z}}})\Vert {\hat{\mathbf{x}}}. \end{aligned}$$

Consequently, we have

$$\begin{aligned} \mathcal {A}{\hat{\mathbf{x}}}{\hat{\mathbf{z}}}{\hat{\mathbf{z}}}=\frac{1}{2}\left( -\Vert \nabla _{\mathbf{x}}{{\varvec{f}}}^2_{\alpha }({\hat{\mathbf{x}}},{\hat{\mathbf{z}}})\Vert +2\alpha \right) {\hat{\mathbf{x}}}. \end{aligned}$$
(22)

Combining (21) with (22) yields the \({\hat{\mathbf{x}}}\)-part KKT system of (2). Similarly, we can obtain the \({\hat{\mathbf{z}}}\)-part KKT system of the problem. Hence, \(({\hat{\mathbf{x}}}, {\hat{\mathbf{z}}})\) is a KKT point of Bi-QOP (2).

Finally, we prove Item (iv). If \({{\varvec{f}}}^2_{\alpha }(\mathbf{x},\mathbf{z})\) is strictly concave for any fixed \(\mathbf{x}\in {\mathbb {D}}_1\) and \(\mathbf{z}\in {\mathbb {D}}_2\), it then follows from (20) that

$$\begin{aligned} \lim _{k\rightarrow \infty } \left( \Vert \mathbf{x}^{(k+1)}\Vert ^2-\langle \mathbf{x}^{(k+1)},\mathbf{x}^{(k)}\rangle \right) =0, \end{aligned}$$

which implies that

$$\begin{aligned} \lim _{k\rightarrow \infty }\langle \mathbf{x}^{(k+1)},\mathbf{x}^{(k)}\rangle =\lim _{k\rightarrow \infty } \Vert \mathbf{x}^{(k+1)}\Vert ^2=1. \end{aligned}$$

So, we conclude that

$$\begin{aligned} \lim _{k\rightarrow \infty }\Vert \mathbf{x}^{(k+1)}-\mathbf{x}^{(k)}\Vert =0. \end{aligned}$$
(23)

On the other hand, by a similar proof, one can prove that \(\lim _{k\rightarrow \infty }\Vert \mathbf{z}^{(k+1)}-\mathbf{z}^{(k)}\Vert =0\), which, together with (23), implies that

$$\begin{aligned} \lim _{k\rightarrow \infty }\Vert (\mathbf{x}^{(k+1)},\mathbf{z}^{(k+1)})-(\mathbf{x}^{(k)},\mathbf{z}^{(k)})\Vert =0. \end{aligned}$$

The proof is completed. \(\square \)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chen, H., He, H., Wang, Y. et al. An efficient alternating minimization method for fourth degree polynomial optimization. J Glob Optim 82, 83–103 (2022). https://doi.org/10.1007/s10898-021-01060-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-021-01060-9

Keywords

Mathematics Subject Classification

Search

Navigation