×

zbMATH — the first resource for mathematics

Nonconvex min-max fractional quadratic problems under quadratic constraints: copositive relaxations. (English) Zbl 1434.90216
Summary: In this paper we address a min-max problem of fractional quadratic (not necessarily convex) over linear functions on a feasible set described by linear and (not necessarily convex) quadratic functions. We propose a conic reformulation on the cone of completely positive matrices. By relaxation, a doubly nonnegative conic formulation is used to provide lower bounds with evidence of very small gaps. It is known that in many solvers using Branch and Bound the optimal solution is obtained in early stages and a heavy computational price is paid in the next iterations to obtain the optimality certificate. To reduce this effort tight lower bounds are crucial. We will show empirical evidence that lower bounds provided by the copositive relaxation are able to substantially speed up a well known solver in obtaining the optimality certificate.
MSC:
90C47 Minimax problems in mathematical programming
90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization
90C32 Fractional programming
Software:
BARON; SDPT3; YALMIP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Amaral, PA; Bomze, IM, Copositivity-based approximations for mixed-integer fractional quadratic optimization, Pac. J. Optim., 11, 225-238, (2015) · Zbl 1321.90135
[2] Amaral, PA; Bomze, IM; Júdice, JJ, Copositivity and constrained fractional quadratic problems, Math. Program., 146, 325-350, (2014) · Zbl 1312.90049
[3] Benadada, Y.; Ferland, JA, Partial linearization for generalized fractional programming, Z. Oper. Res., 32, 101-106, (1988) · Zbl 0643.90086
[4] Bomze, IM; Klerk, E., Solving standard quadratic optimization problems via linear, semidefinite and copositive programming, J. Glob. Optim., 24, 163-185, (2002) · Zbl 1047.90038
[5] Bomze, IM; Dür, M.; Klerk, E.; Roos, C.; Quist, AJ; Terlaky, T., On copositive programming and standard quadratic optimization problems, J. Glob. Optim., 18, 301-320, (2000) · Zbl 0967.00090
[6] Bundfuss, S.: Copositive matrices, copositive programming, and applications. Dissertation, Technische Universität Darmstadt, Darmstadt, Germany (2009) · Zbl 1170.65047
[7] Burer, S., On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 120, 479-495, (2009) · Zbl 1180.90234
[8] Cohen, G., An algorithm for convex constrained minimax optimization based on duality, Appl. Math. Optim., 7, 347-372, (1981) · Zbl 0477.49021
[9] Crouzeix, J-P; Ferland, JA, Algorithms for generalized fractional programming, Math. Program., 52, 191-207, (1991) · Zbl 0748.90067
[10] Dickinson, PJC; Gijben, L., On the computational complexity of membership problems for the completely positive cone and its dual, Comput. Optim. Appl., 57, 403-415, (2014) · Zbl 1330.90103
[11] Lo, AW; MacKinlay, AC, Maximizing predictability in the stock and bond markets, Macroecon. Dyn., 1, 102-134, (1997) · Zbl 0915.90025
[12] Löfberg, J.: YALMIP: a toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei, Taiwan (2004)
[13] Medanić, JV; Andjelić, M., On a class of differential games without saddle-point solutions, J. Optim. Theory Appl., 8, 413430, (1971) · Zbl 0209.46104
[14] Murty, KG; Kabadi, SN, Some NP-complete problems in quadratic and nonlinear programming, Math. Program., 39, 117-129, (1987) · Zbl 0637.90078
[15] Parpas, P., Rustem, B.: Algorithms for Minimax and Expected Value Optimization, pp. 121-151. Wiley, New York (2009) · Zbl 1168.90016
[16] Parrilo, P.A.: Structured semidefinite programs and semi-algebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology, Pasadena, CA, May (2000)
[17] Peña, J.; Vera, J.; Zuluaga, LF, Computing the stability number of a graph via linear and semidefinite programming, SIAM J. Optim., 18, 87-105, (2007) · Zbl 1176.90611
[18] Preisig, JC, Copositivity and the minimization of quadratic functions with nonnegativity and quadratic equality constraints, SIAM J. Control Optim., 34, 1135-1150, (1996) · Zbl 0853.90105
[19] Rao, MR, Cluster analysis and mathematical programming, J. Am. Stat. Assoc., 66, 622-626, (1971) · Zbl 0238.90042
[20] Rustem, B., Howe, M.: Algorithms for Worst-case Design and Applications to Risk Management. Princeton University Press, Princeton (2002) · Zbl 1140.90013
[21] Sahinidis, N.V.: BARON 17.8.9: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual (2017)
[22] Schaible, S., Fractional programming. I, duality, Manag. Sci., 22, 858-867, (1976) · Zbl 0338.90050
[23] Sponsel, J.; Bundfuss, S.; Dür, M., An improved algorithm to test copositivity, J. Glob. Optim., 52, 537-551, (2012) · Zbl 1250.65061
[24] Stancu-Minasian, IM, On the transportation problem with multiple objective functions, Bull. Math. Soc. Sci. Math. Roum., 3, 315-328, (1978) · Zbl 0391.90060
[25] Stancu-Minasian, I.M.: Fractional Programming: Theory, Methods and Applications. Kluwer Academic Publishers, Dordrecht (1997) · Zbl 0899.90155
[26] Toh, KC; Todd, MJ; Tütüncü, RH, SDPT3: a Matlab software package for semidefinite programming, version 1.3, Optim. Methods Softw., 11, 545-581, (1999) · Zbl 0997.90060
[27] Ziemba, WT; Parkan, C.; Brooks-Hill, R., Calculation of investment portfolios with risk free borrowing and lending, Manag. Sci., 21, 209-222, (1974) · Zbl 0294.90004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.