An efficient global optimization algorithm for a class of linear multiplicative problems based on convex relaxation

This paper presents an efficient global optimization algorithm to solve a class of linear multiplicative problems (LMP). The algorithm first converts LMP into an equivalent problem (EP) via some variables transformation, and a convex relaxation problem is constructed to derive a lower bound to the optimal value of EP. Consequently, the process of solving LMP is transformed into tackling a series of convex programs. Additionally, a pruning rule is developed to offer a chance to remove the portion of the investigated space which does not contain the optimal solution of EP, and we propose a strategy which provides more choices of the feasible solution to update the upper bound for the optimal value of LMP. We also analyze the convergence of the algorithm and give its complexity result. Finally, our approach has been confirmed to be effective based on numerical results.

No data was used for the research described in the article.

We thank each reviewer for their valuable comments and suggestions, which help us to improve the quality of the paper. This research was supported by the National Natural Science Foundation of China (grant number: 12071133;11871196).

Authors and Affiliations

1. College of Mathematics and Information Science, Henan Normal University, Xinxiang, 453007, China

   Bingdi Huang & Peiping Shen

2. School of Mathematics and Statistics, North China University of Water Resources and Electric Power, Zhengzhou, 450046, China

   Peiping Shen

Corresponding author

Correspondence to Peiping Shen.

Conflict of interest

The authors have no conflict of interest to declare that are relevant to the content of this article.

Publisher's Note

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

This work is supported by National Natural Science Foundation of China (Grant numbers: 12071133, 11871196).

Appendix A. The derivation of the relaxations in Cambini et al. (2023)

We first report the two linear relaxations offered by Cambini et al. (2023) for Problem 2. To this end, the following 4p linear programs need to be solved:

Then the two linear relaxations of Problem 2 can be expressed as follows:

Next, we will introduce the six convex relaxation programs in Cambini et al. (2023), towards this end, we first rewrite \(\varphi (x)\) as the following three D.C. functions (D.C. function: the difference between two convex functions):

(i) \(\varphi (x)=\sum \nolimits _{i=1}^{p}({c}_{0i}{d}_{0i}+( {c}_{0i}d_{i}+{d}_{0i}c_{i})^{\top }x)+\frac{1}{2}\sum \nolimits _{i=1}^{p} (c_{i}^{\top }x+d_{i}^{\top }x) ^{2}-\frac{1}{2}\sum \nolimits _{i=1}^{p} ((c_{i}^{\top }x)^2+ (d_{i}^{\top }x)^2)\);

(ii) \(\varphi (x)=\sum \nolimits _{i=1}^{p}({c}_{0i}{d}_{0i}+( {c}_{0i}d_{i}+{d}_{0i}c_{i})^{\top }x)+\frac{1}{4}\sum \nolimits _{i=1}^{p} (c_{i}^{\top }x+d_{i}^{\top }x) ^{2}-\frac{1}{4}\sum \nolimits _{i=1}^{p} (c_{i}^{\top }x-d_{i}^{\top }x)^2\);

(iii) \(\varphi (x)=\sum \nolimits _{i=1}^{p}({c}_{0i}{d}_{0i}+( {c}_{0i}d_{i}+{d}_{0i}c_{i})^{\top }x)+\frac{1}{2}\sum \nolimits _{i=1}^{p} ((c_{i}^{\top }x)^2+ (d_{i}^{\top }x)^2)-\frac{1}{2}\sum \nolimits _{i=1}^{p} (c_{i}^{\top }x-d_{i}^{\top }x)^2\).

Based on (i)–(iii), Problem 2 can be relaxed to the following three convex programs:

where \({\underline{\sigma }}_{i}=\min _{{x}\in D}(c_{i}^{\top }x-d_{i}^{\top }x),\) \({\overline{\sigma }}_{i}=\max _{{x}\in D}(c_{i}^{\top }x-d_{i}^{\top }x), i=1,\ldots , p.\)

The last three convex relaxation programs are based on the D.C. forms of the objective function \(\varphi (x)\) in Problem 2 and the eigenvalue decomposition of the matrix in the quadratic representation of \(\varphi (x)\). The details are explained as follows.

Note that the D.C. forms offered by (i)–(ii) can be rewritten as:

(i) \(\varphi (x)=\sum \nolimits _{i=1}^{p}({c}_{0i}{d}_{0i}+( {c}_{0i}d_{i}+{d}_{0i}c_{i})^{\top }x)+\frac{1}{2}\sum \nolimits _{i=1}^{p} (c_{i}^{\top }x+d_{i}^{\top }x) ^{2}-x^{\top }Q_{1}x\),

(ii) \(\varphi (x)=\sum \nolimits _{i=1}^{p}({c}_{0i}{d}_{0i}+( {c}_{0i}d_{i}+{d}_{0i}c_{i})^{\top }x)+\frac{1}{4}\sum \nolimits _{i=1}^{p} (c_{i}^{\top }x+d_{i}^{\top }x) ^{2}-x^{\top }Q_{2}x\),

where \(Q_{1}=\frac{1}{2}\sum \nolimits _{i=1}^{p}(c_{i}c_{i}^{\top }+d_{i}d_{i}^{\top }),\ Q_{2}=\frac{1}{4}\sum \nolimits _{i=1}^{p}(c_{i}-d_{i})(c_{i}-d_{i})^{\top }\) are symmetric positive semidefinite matrices. Therefore, there exists an orthonormal matrix \({\tilde{U}}\in {\mathbb {R}}^{n\times n}\) with its columns \({\tilde{u}}_{1},\ldots ,{\tilde{u}}_{n}\in {\mathbb {R}}^{n}\), and a diagonal matrix \({\tilde{D}}\in {\mathbb {R}}^{n\times n}\) with its diagonal elements \({\tilde{\lambda }}_{1},\ldots ,{\tilde{\lambda }}_{n}\in {\mathbb {R}}\) such that \(Q_{1}={\tilde{U}}{\tilde{D}}{\tilde{U}}^{\top }\). Let \(\Theta ^{+}=\{i=1,\ldots ,n: {\tilde{\lambda }}_{i}> 0\}\) and \({\tilde{\vartheta }}_{i}=\sqrt{{\tilde{\lambda }}_{i}}\cdot {\tilde{u}}_{i}\) for all \(i\in \Theta ^{+},\) then the convex relaxation of Problem 2 can be obtained as follows:

where \({\tilde{\vartheta }}^{L}_{i}=\min _{{x}\in D}({\tilde{\vartheta }}_{i}^{T}{x}),\) \({\tilde{\vartheta }}^{U}_{i}=\max _{{x}\in D}({\tilde{\vartheta }}_{i}^{T}{x}), \ i\in \Theta ^{+}.\)

Similarly, there exists an orthonormal matrix \({\hat{U}}\in {\mathbb {R}}^{n\times n}\) with its columns \({\hat{u}}_{1},\ldots ,{\hat{u}}_{n}\in {\mathbb {R}}^{n}\), and a diagonal matrix \({\hat{D}}\in {\mathbb {R}}^{n\times n}\) with its diagonal elements \({\hat{\lambda }}_{1},\ldots ,{\hat{\lambda }}_{n}\in {\mathbb {R}}\) such that \(Q_{2}={\hat{U}}{\hat{D}}{\hat{U}}^{\top }\). Let \(\Gamma ^{+}=\{i=1,\ldots ,n: {\hat{\lambda }}_{i}> 0\}\) and \({\hat{\vartheta }}_{i}=\sqrt{{\hat{\lambda }}_{i}}\cdot {\hat{u}}_{i}\) for all \(i\in \Gamma ^{+},\) then we can construct the convex relaxation of Problem 2 as follows:

where \({\hat{\vartheta }}^{L}_{i}=\min _{{x}\in D}({\hat{\vartheta }}_{i}^{T}{x}),\) \({\hat{\vartheta }}^{U}_{i}=\max _{{x}\in D}({\hat{\vartheta }}_{i}^{T}{x}), \ i\in \Gamma ^{+}.\)

To report the last convex relaxation of Problem 2, we rewrite \(\varphi (x)\) as a quadratic function below:

where \({\hat{a}}=\sum _{i=1}^{p}(c_{0i}d_{i}+d_{0i}c_{i}),\ {\hat{a}}_{0}=\sum _{i=1}^{p}c_{0i}d_{0i},\ {\hat{Q}}=\frac{1}{2}\sum _{i=1}^{p}(c_{i}d_{i}^{\top }+d_{i}c_{i}^{\top })\) is a symmetric matrix, thus there exists an orthonormal matrix \({\bar{P}}\in {\mathbb {R}}^{n\times n}\) with its columns \({\bar{p}}_{1},\ldots ,{\bar{p}}_{n}\in {\mathbb {R}}^{n}\), and a diagonal matrix \({\bar{D}}\in {\mathbb {R}}^{n\times n}\) with its diagonal elements \({\bar{\lambda }}_{1},\ldots ,{\bar{\lambda }}_{n}\in {\mathbb {R}}\) such that \({\hat{Q}}={\bar{P}}{\bar{D}}{\bar{P}}^{\top }\). Let \(\Lambda ^{+}=\{i=1,\ldots ,n: {\bar{\lambda }}_{i}> 0\},\ \Lambda ^{-}=\{i=1,\ldots ,n: {\bar{\lambda }}_{i}< 0\}\) and \({\bar{\vartheta }}_{i}=\sqrt{{\bar{\lambda }}_{i}}\cdot {\bar{p}}_{i},\ i\in \Lambda ^{+}\cup \Lambda ^{-}\), then \(x^{\top }{\hat{Q}}x=\sum _{i\in \Lambda ^{+}}({\bar{\vartheta }}_{i}^{\top }x)^{2}-\sum _{i\in \Lambda ^{-}}({\bar{\vartheta }}_{i}^{\top }x)^{2}\), and the convex relaxation of Problem 2 can be obtained as follows:

where \({\bar{\vartheta }}^{L}_{i}=\min _{{x}\in D}({\bar{\vartheta }}_{i}^{T}{x}),\) \({\bar{\vartheta }}^{U}_{i}=\max _{{x}\in D}({\bar{\vartheta }}_{i}^{T}{x}), \ i\in \Lambda ^{-}.\)

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions