Quadratic Optimization Through the Lens of Adjustable Robust Optimization

References

• Ahmadi AA, Zhang J (2022) On the complexity of finding a local minimizer of a quadratic function over a polytope. Math. Programming 195(1):783–792.Crossref, Google Scholar
• Andrianova A, Korepanova A, Halilova I (2016) One algorithm for branch and bound method for solving concave optimization problem. Proc. IOP Conf. Series: Materials Sci. and Engrg. (IOP Publishing, Bristol, UK), 012005.Crossref, Google Scholar
• Anstreicher KM (2009) Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Global Optim. 43:471–484.Crossref, Google Scholar
• Anstreicher KM, Burer S (2005) DC versus copositive bounds for standard QP. J. Global Optim. 33(2):299–312.Crossref, Google Scholar
• Ardestani-Jaafari A, Delage E (2021) Linearized robust counterparts of two-stage robust optimization problems with applications in operations management. INFORMS J. Comput. 33(3):1138–1161.Link, Google Scholar
• Audet C, Hansen P, Savard G (2005) Essays and Surveys in Global Optimization, vol. 7 (Springer Science & Business Media, New York).Crossref, Google Scholar
• Bao X, Sahinidis NV, Tawarmalani M (2011) Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons. Math. Programming 129:129–157.Crossref, Google Scholar
• Ben-Tal A, Roos E (2022) An algorithm for maximizing a convex function based on its minimum. INFORMS J. Comput. 34(6):3200–3214.Link, Google Scholar
• Ben-Tal A, Goryashko A, Guslitzer E, Nemirovski A (2004) Adjustable robust solutions of uncertain linear programs. Math. Programming 99(2):351–376.Crossref, Google Scholar
• Bentobache M, Telli M, Mokhtari A (2022) New LP-based local and global algorithms for continuous and mixed-integer nonconvex quadratic programming. J. Global Optim. 82(4):659–689.Crossref, Google Scholar
• Bertsimas D, Bidkhori H (2015) On the performance of affine policies for two-stage adaptive optimization: A geometric perspective. Math. Programming 153(2):577–594.Crossref, Google Scholar
• Bertsimas D, Caramanis C (2010) Finite adaptability in multistage linear optimization. IEEE Trans. Automatic Control 55(12):2751–2766.Crossref, Google Scholar
• Bertsimas D, Dunning I (2016) Multistage robust mixed-integer optimization with adaptive partitions. Oper. Res. 64(4):980–998.Link, Google Scholar
• Bertsimas D, Goyal V, Lu BY (2015) A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization. Math. Programming 150(2):281–319.Crossref, Google Scholar
• Bertsimas D, Iancu DA, Parrilo PA (2010) Optimality of affine policies in multistage robust optimization. Math. Oper. Res. 35(2):363–394.Link, Google Scholar
• Bhanja S, Karunaratne D, Panchumarthy R, Rajaram S, Sarkar S (2016) Non-Boolean computing with nanomagnets for computer vision applications. Nature Nanotech. 11(2):177–183.Crossref, Google Scholar
• Bomze IM (2002a) Branch-and-bound approaches to standard quadratic optimization problems. J. Global Optim. 22:17–37.Crossref, Google Scholar
• Bomze IM (2002b) Regularity versus degeneracy in dynamics, games, and optimization: A unified approach to different aspects. SIAM Rev. 44(3):394–414.Crossref, Google Scholar
• Bomze IM (2015) Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained quadratic optimization problems. SIAM J. Optim. 25(3):1249–1275.Crossref, Google Scholar
• Bomze IM, De Klerk E (2002) Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim. 24(2):163–185.Crossref, Google Scholar
• Bomze I, Gabl M (2021) Interplay of non-convex quadratically constrained problems with adjustable robust optimization. Math. Methods Oper. Res. 93(1):115–151.Crossref, Google Scholar
• Bomze IM, Locatelli M, Tardella F (2008) New and old bounds for standard quadratic optimization: Dominance, equivalence and incomparability. Math. Programming 115(1):31–64.Crossref, Google Scholar
• Bomze IM, Schachinger W, Ullrich R (2018) The complexity of simple models—A study of worst and typical hard cases for the standard quadratic optimization problem. Math. Oper. Res. 43(2):651–674.Link, Google Scholar
• Bonami P, Lodi A, Schweiger J, Tramontani A (2019) Solving quadratic programming by cutting planes. SIAM J. Optim. 29(2):1076–1105.Crossref, Google Scholar
• Boyd SP, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Bulo SR, Pelillo M, Bomze IM (2011) Graph-based quadratic optimization: A fast evolutionary approach. Comput. Vision Image Understanding 115(7):984–995.Crossref, Google Scholar
• Bundfuss S, Dur M (2009) An adaptive linear approximation algorithm for copositive programs. SIAM J. Optim. 20(1):30–53.Crossref, Google Scholar
• Burer S (2009) On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Programming 120(2):479–495.Crossref, Google Scholar
• Burer S, Vandenbussche D (2008) A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Programming 113(2):259–282.Crossref, Google Scholar
• Burer S, Vandenbussche D (2009) Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound. Comput. Optim. Appl. 43(2):181–195.Crossref, Google Scholar
• Cen X, Xia Y (2021) A new global optimization scheme for quadratic programs with low-rank nonconvexity. INFORMS J. Comput. 33(4):1368–1383.Abstract, Google Scholar
• Cevikalp H, Polikar R (2008) Local classifier weighting by quadratic programming. IEEE Trans. Neural Networks 19(10):1832–1838.Crossref, Google Scholar
• Chen J, Burer S (2012) Globally solving nonconvex quadratic programming problems via completely positive programming. Math. Programming Comput. 4(1):33–52.Crossref, Google Scholar
• Chinchuluun A, Pardalos PM, Enkhbat R (2005) Global minimization algorithms for concave quadratic programming problems. Optimization 54(6):627–639.Crossref, Google Scholar
• Cuong TH, Lim Y, Yen ND (2024) On a solution method in indefinite quadratic programming under linear constraints. Optimization 73(4):1087–1112.Crossref, Google Scholar
• De Ruiter FJ, Zhen J, Den Hertog D (2023) Dual approach for two-stage robust nonlinear optimization. Oper. Res. 71(5):1794–1799.Link, Google Scholar
• Delage E, Iancu DA (2015) Robust multistage decision making. Aleman DM, Thiele AC, eds. Tutorials in Operations Research (INFORMS, Catonsville, MD), 20–46.Link, Google Scholar
• Dorn WS (1960) Duality in quadratic programming. Quart. Appl. Math. 18(2):155–162.Crossref, Google Scholar
• El Housni O, Goyal V (2021) On the optimality of affine policies for budgeted uncertainty sets. Math. Oper. Res. 46(2):674–711.Link, Google Scholar
• Fampa M, Lee J, Melo W (2017) On global optimization with indefinite quadratics. EURO J. Comput. Optim. 5(3):309–337.Crossref, Google Scholar
• Gibbons LE, Hearn DW, Pardalos PM, Ramana MV (1997) Continuous characterizations of the maximum clique problem. Math. Oper. Res. 22(3):754–768.Link, Google Scholar
• Gökmen YG, Yıldırım EA (2022) On standard quadratic programs with exact and inexact doubly nonnegative relaxations. Math. Programming 193(1):365–403.Crossref, Google Scholar
• Gondzio J, Yıldırım EA (2021) Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations. J. Global Optim. 81(2):293–321.Crossref, Google Scholar
• Gorski J, Pfeuffer F, Klamroth K (2007) Biconvex sets and optimization with biconvex functions: A survey and extensions. Math. Methods Oper. Res. 66(3):373–407.Crossref, Google Scholar
• Gouveia J, Pong TK, Saee M (2020) Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices. J. Global Optim. 76:383–405.Crossref, Google Scholar
• Grippo L, Sciandrone M (2000) On the convergence of the block nonlinear Gauss–Seidel method under convex constraints. Oper. Res. Lett. 26(3):127–136.Crossref, Google Scholar
• Gurobi Optimization (2023) LLC: Gurobi optimizer reference manual, version 10.0.0. Accessed January 14, 2024, http://www.gurobi.com.Google Scholar
• Hadjiyiannis MJ, Goulart PJ, Kuhn D (2011) A scenario approach for estimating the suboptimality of linear decision rules in two-stage robust optimization. Proc. 50th IEEE Conf. Decision Control Eur. Control Conf. (IEEE, Piscataway, NJ), 7386–7391.Google Scholar
• Hansen P, Jaumard B (1992) Reduction of indefinite quadratic programs to bilinear programs. J. Global Optim. 2:41–60.Crossref, Google Scholar
• Horst R, Thoai NV (1999) DC programming: Overview. J. Optim. Theory Appl. 103:1–43.Crossref, Google Scholar
• Hu J, Mitchell JE, Pang J-S (2012) An LPCC approach to nonconvex quadratic programs. Math. Programming 133(1–2):243–277.Crossref, Google Scholar
• Ibaraki T, Katoh N (1988) Resource Allocation Problems: Algorithmic Approaches (MIT Press, Cambridge, MA).Google Scholar
• IBM (2019) IBM ILOG CPLEX optimization studio user’s manual, version 12.9.0 (1987-2019). Accessed January 14, 2024, https://www.ibm.com.Google Scholar
• Khademi A, Marandi A (2025) Quadratic optimization through the lens of adjustable robust optimization. https://github.com/INFORMSJoC/2024.0577, https://doi.org/10.1287/ijoc.2024.0577.cd.Google Scholar
• Khademi A, Marandi A, Soleimani-Damaneh M (2024) A new dual-based cutting plane algorithm for nonlinear adjustable robust optimization. J. Global Optim. 89(3):559–595.Crossref, Google Scholar
• Khadivar F, Chatzilygeroudis K, Billard A (2023) Self-correcting quadratic programming-based robot control. IEEE Trans. Systems Man Cybernetics 53(8):5236–5247.Crossref, Google Scholar
• Kim S, Kojima M, Toh K-C (2020) A geometrical analysis on convex conic reformulations of quadratic and polynomial optimization problems. SIAM J. Optim. 30(2):1251–1273.Crossref, Google Scholar
• Konno H (1976) A cutting plane algorithm for solving bilinear programs. Math. Programming 11(1):14–27.Crossref, Google Scholar
• Kozlov MK, Tarasov SP, Khachiyan LG (1980) The polynomial solvability of convex quadratic programming. USSR Comput. Math. Math. Phys. 20(5):223–228.Crossref, Google Scholar
• Lipp T, Boyd S (2016) Variations and extension of the convex–Concave procedure. Optim. Engrg. 17:263–287.Crossref, Google Scholar
• Liuzzi G, Locatelli M, Piccialli V (2019) A new branch-and-bound algorithm for standard quadratic programming problems. Optim. Methods Software 34(1):79–97.Crossref, Google Scholar
• Löfberg J (2004) YALMIP: A toolbox for modeling and optimization in MATLAB. Proc. CACSD Conf. (IEEE, Piscataway, NJ).Google Scholar
• Luo H, Bai X, Lim G, Peng J (2019) New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation. Math. Programming Comput. 11(1):119–171.Crossref, Google Scholar
• Markowitz HM (1952) Protfilio selection. J. Finance 7(1):77–91.Google Scholar
• Mitchell JE, Pang J-S, Yu B (2014) Convex quadratic relaxations of nonconvex quadratically constrained quadratic programs. Optim. Methods Software 29(1):120–136.Crossref, Google Scholar
• MOSEK ApS (2023) The MOSEK optimization toolbox for MATLAB manual, version 10.1.15. Accessed January 14, 2024, https://www.mosek.com/.Google Scholar
• O’Nan M (1971) Linear Algebra, Eagle Mathematics Series (Harcourt Brace Jovanovich, New York).Google Scholar
• Pardalos PM, Schnitger G (1988) Checking local optimality in constrained quadratic programming is NP-hard. Oper. Res. Lett. 7(1):33–35.Crossref, Google Scholar
• Pardalos PM, Vavasis SA (1991) Quadratic programming with one negative eigenvalue is NP-hard. J. Global Optim. 1(1):15–22.Crossref, Google Scholar
• Phillips AT, Rosen JB (1988) A parallel algorithm for constrained concave quadratic global minimization. Math. Programming 42:421–448.Crossref, Google Scholar
• Postek K, Hertog D D (2016) Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set. INFORMS J. Comput. 28(3):553–574.Link, Google Scholar
• Renegar J (2001) A Mathematical View of Interior-Point Methods in Convex Optimization (SIAM, Philadelphia).Crossref, Google Scholar
• Rostami B, Errico F, Lodi A (2023) A convex reformulation and an outer approximation for a large class of binary quadratic programs. Oper. Res. 71(2):471–486.Link, Google Scholar
• Sahni S (1974) Computationally related problems. SIAM J. Comput. 3(4):262–279.Crossref, Google Scholar
• Scozzari A, Tardella F (2008) A clique algorithm for standard quadratic programming. Discrete Appl. Math. 156(13):2439–2448.Crossref, Google Scholar
• Selvi A, den Hertog D, Wiesemann W (2023) A reformulation-linearization technique for optimization over simplices. Math. Programming 197(1):427–447.Crossref, Google Scholar
• Selvi A, Ben-Tal A, Brekelmans R, den Hertog D (2022) Convex maximization via adjustable robust optimization. INFORMS J. Comput. 34(4):2091–2105.Link, Google Scholar
• Sherali HD, Alameddine A (1992) A new reformulation-linearization technique for bilinear programming problems. J. Global Optim. 2:379–410.Crossref, Google Scholar
• Sherali H, Liberti L (2009) Reformulation-linearization methods for global optimization. Encyclopedia of Optimization (Springer, Boston), 3263–3268.Google Scholar
• Sherali HD, Tuncbilek CH (1995) A reformulation-convexification approach for solving nonconvex quadratic programming problems. J. Global Optim. 7:1–31.Crossref, Google Scholar
• Thomä S, Walther G, Schiffer M (2024) Designing tractable piecewise affine policies for multi-stage adjustable robust optimization. Math. Programming 208(1):661–716.Crossref, Google Scholar
• Wang AL, Kılınç-Karzan F (2022) On the tightness of SDP relaxations of QCQPs. Math. Programming 193(1):33–73.Crossref, Google Scholar
• Wolkowicz H, Saigal R, Vandenberghe L (2012) Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, vol. 27 (Springer Science & Business Media, Kluwer Academic Publishers, Boston).Google Scholar
• Xia W, Vera JC, Zuluaga LF (2020) Globally solving nonconvex quadratic programs via linear integer programming techniques. INFORMS J. Comput. 32(1):40–56.Link, Google Scholar
• Yanıkoğlu İ, Gorissen BL, den Hertog D (2019) A survey of adjustable robust optimization. Eur. J. Oper. Res. 277(3):799–813.Crossref, Google Scholar
• Zamani M (2023) New bounds for nonconvex quadratically constrained quadratic programming. J. Global Optim. 85(3):595–613.Crossref, Google Scholar
• Zhen J, Den Hertog D, Sim M (2018) Adjustable robust optimization via Fourier–Motzkin elimination. Oper. Res. 66(4):1086–1100.Link, Google Scholar
• Zhen J, Marandi A, de Moor D, den Hertog D, Vandenberghe L (2022) Disjoint bilinear optimization: A two-stage robust optimization perspective. INFORMS J. Comput. 34(5):2410–2427.Link, Google Scholar
• Zheng XJ, Sun XL, Li D (2011) Convex relaxations for nonconvex quadratically constrained quadratic programming: Matrix cone decomposition and polyhedral approximation. Math. Programming 129(2):301–329.Crossref, Google Scholar