Skip to main content
SpringerLink
Log in

Biconvex sets and optimization with biconvex functions: a survey and extensions

  • Original Article
  • Published:
Mathematical Methods of Operations Research Aims and scope Submit manuscript

Abstract

The problem of optimizing a biconvex function over a given (bi)convex or compact set frequently occurs in theory as well as in industrial applications, for example, in the field of multifacility location or medical image registration. Thereby, a function \(f:X\times Y\to{\mathbb{R}}\) is called biconvex, if f(x,y) is convex in y for fixed x∈X, and f(x,y) is convex in x for fixed y∈Y. This paper presents a survey of existing results concerning the theory of biconvex sets and biconvex functions and gives some extensions. In particular, we focus on biconvex minimization problems and survey methods and algorithms for the constrained as well as for the unconstrained case. Furthermore, we state new theoretical results for the maximum of a biconvex function over biconvex sets.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Al-Khayyal F (1990) Jointly constrained bilinear programs and related problems: an overview. Comput Math Appl 19(11):53–62

    Article  MATH  MathSciNet  Google Scholar 

  • Al-Khayyal F, Falk J (1983) Jointly constrained biconvex programming. Math Oper Res 8(2):273–286

    MATH  MathSciNet  Google Scholar 

  • Audet C, Hansen P, Jaumard B, Savard G (2000) A branch and cut algorithm for non-convex quadratically constrained quadratic programming. Math Program Ser A 87(1):131–152

    MATH  MathSciNet  Google Scholar 

  • Aumann R, Hart S (1986) Bi-convexity and bi-martingales. Isr J Math 54(2):159–180

    MATH  MathSciNet  Google Scholar 

  • Barmish B (1994) New Tools for Robustness of Linear Systems. Maxwell, Macmillan International, New York

    MATH  Google Scholar 

  • Barmish B, Floudas C, Hollot C, Tempo R (1995) A global programming solution to some open robustness problems including matrix polytope stability. In: Proceedings of the American Control Conference, Seattle, Washington, pp 3871–3877

  • Bazaraa M, Sherali H, Shetty C (1993) Nonlinear programming—theory and algorithms, 2nd edn. Wiley, New York

    MATH  Google Scholar 

  • Benders J (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4:238–252

    Article  MATH  MathSciNet  Google Scholar 

  • Besl P, McKay N (1992) A method for registration of 3-D shapes. IEEE Trans Pattern Anal Mach Intell 14:239–256

    Article  Google Scholar 

  • Borwein J (1986) Partially monotone operators and the generic differentiability of convex-concave and biconvex mappings. Isr J Math 54(1):42–50

    MATH  Google Scholar 

  • Burkholder D (1981) A geometrical characterization of Banach spaces in which martingale difference sequences are unconditional. Ann Probab 9(6):997–1011

    MATH  MathSciNet  Google Scholar 

  • Burkholder D (1986) Lecture Notes in Mathematics. Probability and Analysis (Varenna, 1985), vol 1206. Chapter Martingales and Fourier analysis in Banach spaces, pp 61–108. Springer, Heidelberg

  • Cooper L (1963) Location-allocation problems. Oper Res 11:331–343

    MATH  Google Scholar 

  • Cooper L (1964) Heuristic methods for location-allocation problems. SIAM Rev 6:37–53

    Article  MathSciNet  Google Scholar 

  • de Leeuw J (1994) Block relaxation algorithms in statistics. In: Bock H, Lenski W, Richter M (eds) Information systems and data analysis. Springer, Heidelberg, pp 308–325

    Google Scholar 

  • Falk J, Soland R (1969) An algorithm for separable nonconvex programming problems. Manage Sci 15(9):550–569

    MathSciNet  MATH  Google Scholar 

  • Floudas C (1995) Nonlinear and mixed integer optimization: fundamentals and applications. Oxford Press, New York

    MATH  Google Scholar 

  • Floudas C (2000) Deterministic global optimization, 1st edn. Kluwer, Dordrecht

    Google Scholar 

  • Floudas C, Visweswaran V (1990) A global optimization algorithm (GOP) for certain classes of nonconvex NLPs: I. Theory. Comput Chem Eng 14(12):1397–1417

    Article  Google Scholar 

  • Floudas C, Visweswaran V (1993) A primal-relaxed dual global optimization approach. J Optim Theory Appl 78(2):187–225

    Article  MATH  MathSciNet  Google Scholar 

  • Gao Y, Xu C (2002) An outer approximation method for solving the biconcave programs with separable linear constraints. Math Appl 15(3):42–46

    MATH  MathSciNet  Google Scholar 

  • Gelbaum B, Olmsted J (2003) Counterexamples in analysis. Dover, Mineola, New York

    MATH  Google Scholar 

  • Geng Z, Huang L (2000a) Robust stability of systems with both parametric and dynamic uncertainties. Syst Control Lett 39:87–96

    Article  MATH  MathSciNet  Google Scholar 

  • Geng Z, Huang L (2000b) Robust stability of the systems with mixed uncertainties under the IQC descriptions. Int J Control 73(9):776–786

    Article  MATH  MathSciNet  Google Scholar 

  • Geoffrion A (1972) Generalized Benders decomposition. J Optim Theory Appl 10(4):237–260

    Article  MATH  MathSciNet  Google Scholar 

  • Goh K, Turan L, Safonov M, Papavassilopoulos G, Ly J (1994) Biaffine matrix inequality properties and computational methods. In: Proceedings of the American Control Conference, Baltimore, Maryland, pp 850–855

  • Goh K, Safonov M, Papavassilopoulos G (1995) Global optimization for the biaffine matrix inequality problem. J Global Optim 7:365–380

    Article  MATH  MathSciNet  Google Scholar 

  • Hodgson M, Rosing K, Shmulevitz (1993) A review of location-allocation applications literature. Stud Locat Anal 5:3–29

    Google Scholar 

  • Horst R, Thoai N (1996) Decomposition approach for the global minimization of biconcave functions over polytopes. J Optim Theory Appl 88(3):561–583

    Article  MATH  MathSciNet  Google Scholar 

  • Horst R, Tuy H (1990) Global optimization, deterministic approaches. Springer, Berlin

    MATH  Google Scholar 

  • Huang S, Batta R, Klamroth K, Nagi R (2005) K-Connection location problem in a plane. Ann Oper Res 136:193–209

    Article  MATH  MathSciNet  Google Scholar 

  • Jouak M, Thibault L (1985) Directional derivatives and almost everywhere differentiability of biconvex and concave-convex operators. Math Scand 57:215–224

    MATH  MathSciNet  Google Scholar 

  • Lee J (1993) On Burkholder’s biconvex-function characterisation of Hilbert spaces. In: Proceedings of the American Mathematical Society, vol 118, pp 555–559

  • Luenberger D (1989) Linear and nonlinear programming, 2nd edn. Addison-Wesley, Reading

    Google Scholar 

  • Meyer R (1976) Sufficient conditions for the convergence of monotonic mathematical programming algorithms. J Comput Syst Sci 12:108–121

    MATH  Google Scholar 

  • Ostrowski A (1966) Solution of equations and systems of equations, 2nd edn. Academic, New York

    MATH  Google Scholar 

  • Plastria F (1995) Continuous location problems. In: Drezner Z (ed) Facility location, pp 225–262. Springer Series in Operations Research

  • Rockafellar R (1997) Convex analysis, 1st edn. Princeton University Press, Princton

    MATH  Google Scholar 

  • Sherali H, Alameddine A, Glickman T (1994) Biconvex models and algorithms for risk management problems. Am J Math Manage Sci 14(3–4):197–228

    MATH  MathSciNet  Google Scholar 

  • Sherali H, Alameddine A, Glickman T (1995) Biconvex models and algorithms for risk management problems. Oper Res Manage Sci 35(4):405–408

    Google Scholar 

  • Thibault L (1984) Continuity of measurable convex and biconvex operators. In: Proceedings of the American Mathematical Society, vol 90, pp 281–284

  • Tuyen H, Muu L (2001) Biconvex programming approach to optimization over the weakly efficient set of a multiple objective affine fractional problem. Oper Res Lett 28:81–92

    Article  MATH  MathSciNet  Google Scholar 

  • Visweswaran V, Floudas C (1990) A global optimization algorithm (GOP) for certain classes of nonconvex NLPs: II. Application of theory and test problems. Comput Chem Eng 14(12):1419–1434

    Article  Google Scholar 

  • Visweswaran V, Floudas C (1993) New properties and computational improvement of the GOP algorithm for problems with quadratic objective function and constraints. J Global Optim 3(3):439–462

    Article  MATH  MathSciNet  Google Scholar 

  • Wendell R, Hurter A Jr (1976) Minimization of non-separable objective function subject to disjoint constraints. Oper Res 24(4):643–657

    MATH  MathSciNet  Google Scholar 

  • Zangwill W (1969) Convergence conditions for nonlinear programming algorithms. Manage Sci 16(1):1–13

    Article  MathSciNet  MATH  Google Scholar 

  • Zitová B, Flusser J (2003) Image registration methods: a survey. Image Vis Comput 21:977–1000

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute for Applied Mathematics, Friedrich-Alexander-University Erlangen-Nuremberg, Erlangen, Germany

    Jochen Gorski, Frank Pfeuffer & Kathrin Klamroth

Authors
  1. Jochen Gorski
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Frank Pfeuffer
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kathrin Klamroth
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jochen Gorski.

Additional information

J. Gorski and K. Klamroth were partially supported by a grant of the German Research Foundation (DFG).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gorski, J., Pfeuffer, F. & Klamroth, K. Biconvex sets and optimization with biconvex functions: a survey and extensions. Math Meth Oper Res 66, 373–407 (2007). https://doi.org/10.1007/s00186-007-0161-1

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00186-007-0161-1

Keywords

Search

Navigation