Skip to main content
Springer Nature Link
Log in

An objective penalty function method for biconvex programming

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

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

Biconvex programming is nonconvex optimization describing many practical problems. The existing research shows that the difficulty in solving biconvex programming makes it a very valuable subject to find new theories and solution methods. This paper first obtains two important theoretical results about partial optimum of biconvex programming by the objective penalty function. One result holds that the partial Karush–Kuhn–Tucker (KKT) condition is equivalent to the partially exactness for the objective penalty function of biconvex programming. Another result holds that the partial stability condition is equivalent to the partially exactness for the objective penalty function of biconvex programming. These results provide a guarantee for the convergence of algorithms for solving a partial optimum of biconvex programming. Then, based on the objective penalty function, three algorithms are presented for finding an approximate \(\epsilon \)-solution to partial optimum of biconvex programming, and their convergence is also proved. Finally, numerical experiments show that an \(\epsilon \)-feasible solution is obtained by 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
€32.70 /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 (France)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Shen, X., Diamond, S., Udell, M., Gu, Y.: Disciplined multi-convex programming. In: Control and Decision Conference (CCDC), Chongqing, Chinese. https://doi.org/10.1109/CCDC.2017.7978647 (2017)

  2. Grant, M., Boyd, S., Ye, Y.: Disciplined convex programming. In: Liberti, L., Maculan, N. (eds.) Global Optimization: From Theory to Implementation, Nonconvex Optimization and Its Applications, pp. 155–210. Springer, Berlin (2006)

    Chapter  Google Scholar 

  3. Chiu, W.Y.: Method of reduction of variables for bilinear matrix inequality problems in system and control designs. IEEE Trans. Syst. Man Cybern. Syst. 47(7), 1241–1256 (2017)

    Article  Google Scholar 

  4. Ichihara, H., Nobuyama, E.: Difference of multiconvex relaxation of parameterized LMIs: control applications. In: SICE 2003 Annual Conference (2003)

  5. Hours, J., Jones, C.: A parametric multiconvex splitting technique with application to real-time NMPC. In: 53rd IEEE Conference on Decision and Control, pp. 5052–5057 (2014)

  6. Suh, S., Shin, S., Lee, J., Reddy, C.K., Choo, J.: Localized user-driven topic discovery via boosted ensemble of nonnegative matrix factorization. Knowl. Inf. Syst. https://doi.org/10.1007/s10115-017-1147-9 (2018)

  7. Udell, M., Horn, C., Zadeh, R., Boyd, S.: Generalized low rank models. Found. Trends Mach. Learn. 9(1), 1–118 (2016)

    Article  Google Scholar 

  8. Fu, X., Huang, K., Sidiropoulos, N.D.: On identifiability of nonnegative matrix factorization. IEEE Signal Process. Lett. 25(3), 328–332 (2018)

    Article  Google Scholar 

  9. Serbetli, S., Yener, A.: Transceiver optimization for multiuser MIMO systems. IEEE Trans. Signal Process. 52(1), 214–226 (2004)

    Article  MathSciNet  Google Scholar 

  10. Al-Shatri, H., Li, X., Ganesa, R.S.S.: Maximizing the sum rate in cellular networks using multiconvex optimization. IEEE Trans. Wirel. Commun. 15(5), 3199–3211 (2016)

    Article  Google Scholar 

  11. Wen, Z., Yin, W., Zhang, Y.: Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Math. Program. Comput. 4(4), 333–361 (2012)

    Article  MathSciNet  Google Scholar 

  12. Hong, M., Luo, Z.: On the linear convergence of the alternating direction method of multipliers. Math. Program. 162, 165–199 (2017)

    Article  MathSciNet  Google Scholar 

  13. Xu, Y., Yin, W.: A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM J. Imaging Sci. 6(3), 1758–1789 (2013)

    Article  MathSciNet  Google Scholar 

  14. Gorski, J., Pfeuffer, F., Klamroth, K.: Biconvex sets and optimization with biconvex functions: a survey and extensions. Math. Methods Oper. Res. 66, 373–407 (2007)

    Article  MathSciNet  Google Scholar 

  15. Li, G., Wen, C., Zheng, W.X., Zhao, G.: Iterative identification of block-oriented nonlinear systems based on biconvex optimization. Syst. Control Lett. 79, 68–75 (2015)

    Article  MathSciNet  Google Scholar 

  16. Shah, S., Yadav, A.K., Castillo, C.D., Jacobs, D.W., Studer, C., Goldstein, T.: Biconvex Relaxation for semidefinite programming in computer vision. In: European Conference on Computer Vision: Computer Vision, pp. 717–735 (2016)

  17. Faiz, A.A., James, E.F.: jointly constrained biconvex programming. Math. Oper. Res. 8(2), 273–286 (1983)

    Article  MathSciNet  Google Scholar 

  18. Liang, X., Bai, J.: Preconditioned ADMM for a class of bilinear programming problems. Math. Probl. Eng. 2018, 1–9 (2018)

    MathSciNet  MATH  Google Scholar 

  19. Hajinezhad, D., Shi, Q.J.: Alternating direction method of multipliers for a class of nonconvex bilinear optimization: convergence analysis and applications. J. Glob. Optim. 70, 261–88 (2018)

    Article  MathSciNet  Google Scholar 

  20. Charkhgard, H., Savelsbergh, M., Talebian, M.: A linear programming based algorithm to solve a class of optimization problems with a multi-linear objective function and affine constraints. Comput. Oper. Res. 89, 17–30 (2018)

    Article  MathSciNet  Google Scholar 

  21. Pardalos, P.M., Resende, M.G.C.: Handbook of Applied Optimization. Oxford University Press, Oxford (2002)

    Book  Google Scholar 

  22. Zangwill, W.I.: Nonlinear programming via penalty function. Manang. Sci. 13, 334–358 (1967)

    MathSciNet  Google Scholar 

  23. Rosenberg, E.: Globally convergent algorithms for convex programming. Math. Oper. Res. 6, 437–443 (1981)

    Article  MathSciNet  Google Scholar 

  24. Di Pillo, G., Grippo, L.: An exact penalty function method with global convergence properties for nonlinear programming problems. Math. Program. 36, 1–18 (1981)

    Article  MathSciNet  Google Scholar 

  25. Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)

    MATH  Google Scholar 

  26. Burke, J.V.: Calmness and exact penalization. SIAM J. Control. Optim. 29, 493–497 (1991)

    Article  MathSciNet  Google Scholar 

  27. Morrison, D.D.: Optimization by least squares. SIAM J. Numer. Anal. 5, 83–88 (1968)

    Article  MathSciNet  Google Scholar 

  28. Fletcher, R.: Practical Method of Optimization. A Wiley-Interscience Publication, New York (1981)

    MATH  Google Scholar 

  29. Fletcher, R.: Penalty functions. In: Bachem, A., Grotschel, M., Korte, B. (eds) Mathematical Programming: The State of the Art. Springer, Berlin (1983)

  30. Burke, J.V.: An exact penalization viewpoint of constrained optimization. SIAM J. Control Optim. 29, 968–998 (1991)

    Article  MathSciNet  Google Scholar 

  31. Fiacco, A.V., McCormick, G.P.: Nonlinear Programming: Sequential Unconstrained Minimization techniques. Wiley, New York (1968)

    MATH  Google Scholar 

  32. Mauricio, D., Maculan, N.: A Boolean penalty method for zero-one nonlinear programming. J. Glob. Optim. 16, 343–354 (2000)

    Article  MathSciNet  Google Scholar 

  33. Meng, Z.Q., Hu, Q.Y., Dang, C.Y.: A penalty function algorithm with objective parameters for nonlinear mathematical programming. J. Ind. Manag. Optim. 5, 585–601 (2009)

    MathSciNet  MATH  Google Scholar 

  34. Meng, Z., Dang, C., Jiang, M., Xinsheng, X., Shen, R.: Exactness and algorithm of an objective penalty function. J. Glob. Optim. 56(2), 691–711 (2013)

  35. Jiang, M., Meng, Z., Shen, R.: Partially exactness for the penalty function of biconvex programming. Entropy 23, 132 (2021). https://doi.org/10.3390/e23020132

    Article  Google Scholar 

Download references

Acknowledgements

This work is supported by the National Natural Science Foundation of China(No.11871434) and the Natural Science Foundation of Zhejiang Province(No.LY18A010031). The authors would like to express their gratitude to the anonymous referees’ detailed comments and remarks that help improve the presentation of the paper considerably.

Author information

Authors and Affiliations

  1. School of Management, Zhejiang University of Technology, Zhejiang, 310023, Hangzhou, China

    Zhiqing Meng & Min Jiang

  2. School of Economics, Zhejiang University of Technology, Zhejiang, 310023, Hangzhou, China

    Rui Shen

  3. Institute of Digital Business, Nanjing Vocational College of Information Technology, Nanjing, 210023, Jiangsu, China

    Leiyan Xu

  4. Department of System Engineering and Engineering Management, City University of Hong Kong, Kowloon, Hong Kong

    Chuangyin Dang

Authors
  1. Zhiqing Meng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Min Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rui Shen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Leiyan Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Chuangyin Dang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Min Jiang.

Additional information

Publisher's Note

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

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Meng, Z., Jiang, M., Shen, R. et al. An objective penalty function method for biconvex programming. J Glob Optim 81, 599–620 (2021). https://doi.org/10.1007/s10898-021-01064-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-021-01064-5

Keywords

Search

Navigation