Improved local convergence analysis of the Gauss–Newton method under a majorant condition

We present a local convergence analysis of Gauss-Newton method for solving nonlinear least square problems. Using more precise majorant conditions than in earlier studies such as Chen (Comput Optim Appl 40:97–118, 2008), Chen and Li (Appl Math Comput 170:686–705, 2005), Chen and Li (Appl Math Comput 324:1381–1394, 2006), Ferreira (J Comput Appl Math 235:1515–1522, 2011), Ferreira and Gonçalves (Comput Optim Appl 48:1–21, 2011), Ferreira and Gonçalves (J Complex 27(1):111–125, 2011), Li et al. (J Complex 26:268–295, 2010), Li et al. (Comput Optim Appl 47:1057–1067, 2004), Proinov (J Complex 25:38–62, 2009), Ewing, Gross, Martin (eds.) (The merging of disciplines: new directions in pure, applied and computational mathematics 185–196, 1986), Traup (Iterative methods for the solution of equations, 1964), Wang (J Numer Anal 20:123–134, 2000), we provide a larger radius of convergence; tighter error estimates on the distances involved and a clearer relationship between the majorant function and the associated least squares problem. Moreover, these advantages are obtained under the same computational cost.     

Local convergence and the dynamics of a two-point four parameter Jarratt-like method under weak conditions

We present a local convergence analysis of a two-point four parameter Jarratt-like method of high convergence order in order to approximate a locally unique solution of a nonlinear equation. In contrast to earlier studies such us (Amat et al. Aequat. Math. 69(3), 212–223 2015; Amat et al. J. Math. Anal. Appl. 366(3), 24–32 2010; Behl, R. 2013; Bruns and Bailey Chem. Eng. Sci. 32, 257–264 1977; Candela and Marquina. Computing 44, 169–184 1990; Candela and Marquina. Computing 45(4), 355–367 1990; Chun. Appl. Math. Comput. 190(2), 1432–1437 2007; Cordero and Torregrosa. Appl. Math. Comput. 190, 686–698 2007; Deghan. Comput. Appl Math. 29(1), 19–30 2010; Deghan. Comput. Math. Math. Phys. 51(4), 513–519 2011; Deghan and Masoud. Eng. Comput. 29(4), 356–365 15; Cordero and Torregrosa. Appl. Math. Comput. 190, 686–698 2012; Deghan and Masoud. Eng. Comput. 29(4), 356–365 2012; Ezquerro and Hernández. Appl. Math. Optim. 41(2), 227–236 2000; Ezquerro and Hernández. BIT Numer. Math. 49, 325–342 2009; Ezquerro and Hernández. J. Math. Anal. Appl. 303, 591–601 2005; Gutiérrez and Hernández. Comput. Math. Appl. 36(7), 1–8 1998; Ganesh and Joshi. IMA J. Numer. Anal. 11, 21–31 1991; González-Crespo et al. Expert Syst. Appl. 40(18), 7381–7390 2013; Hernández. Comput. Math. Appl. 41(3-4), 433–455 2001; Hernández and Salanova. Southwest J. Pure Appl. Math. 1, 29–40 1999; Jarratt. Math. Comput. 20(95), 434–437 1966; Kou and Li. Appl. Math. Comput. 189, 1816–1821 2007; Kou and Wang. Numer. Algor. 60, 369–390 2012; Lorenzo et al. Int. J. Interact. Multimed. Artif. Intell. 1(3), 60–66 2010; Magreñán. Appl. Math. Comput. 233, 29–38 2014; Magreñán. Appl. Math. Comput. 248, 215–224 2014; Parhi and Gupta. J. Comput. Appl. Math. 206(2), 873–887 2007; Rall 1979; Ren et al. Numer. Algor. 52(4), 585–603 2009; Rheinboldt Pol. Acad. Sci. Banach Ctr. Publ. 3, 129–142 1978; Sicilia et al. J. Comput. Appl. Math. 291, 468–477 2016; Traub 1964; Wang et al. Numer. Algor. 57, 441–456 2011) using hypotheses up to the fifth derivative, our sufficient convergence conditions involve only hypotheses on the first Fréchet-derivative of the operator involved. The dynamics of the family for choices of the parameters such that it is optimal is also shown. Numerical examples are also provided in this study     

On the solution of systems of equations with constant rank derivatives

The famous for its simplicity and clarity Newton–Kantorovich hypothesis of Newton’s method has been used for a long time as the sufficient convergence condition for solving nonlinear equations. Recently, in the elegant study by Hu et al. (J Comput Appl Math 219:110–122, 2008), a Kantorovich-type convergence analysis for the Gauss–Newton method (GNM) was given improving earlier results by Häubler (Numer Math 48:119–125, 1986), and extending some results by Argyros (Adv Nonlinear Var Inequal 8:93–99, 2005, 2007) to hold for systems of equations with constant rank derivatives. In this study, we use our new idea of recurrent functions to extend the applicability of (GNM) by replacing existing conditions by weaker ones. Finally, we provide numerical examples to solve equations in cases not covered before (Häubler, Numer Math 48:119–125, 1986; Hu et al., J Comput Appl Math 219:110–122, 2008; Kontorovich and Akilov 2004).     

Performance of convex underestimators in a branch-and-bound framework

The efficient determination of tight lower bounds in a branch-and-bound algorithm is crucial for the global optimization of models spanning numerous applications and fields. The global optimization method \(\alpha \)-branch-and-bound (\(\alpha \)BB, Adjiman et al. in Comput Chem Eng 22(9):1159–1179, 1998b, Comput Chem Eng 22(9):1137–1158, 1998a; Adjiman and Floudas in J Global Optim 9(1):23–40, 1996; Androulakis et al. J Global Optim 7(4):337–363, 1995; Floudas in Deterministic Global Optimization: Theory, Methods and Applications, vol. 37. Springer, Berlin, 2000; Maranas and Floudas in J Chem Phys 97(10):7667–7678, 1992, J Chem Phys 100(2):1247–1261, 1994a, J Global Optim 4(2):135–170, 1994), guarantees a global optimum with \(\epsilon \)-convergence for any \(\mathcal {C}^2\)-continuous function within a finite number of iterations via fathoming nodes of a branch-and-bound tree. We explored the performance of the \(\alpha \)BB method and a number of competing methods designed to provide tight, convex underestimators, including the piecewise (Meyer and Floudas in J Global Optim 32(2):221–258, 2005), generalized (Akrotirianakis and Floudas in J Global Optim 30(4):367–390, 2004a, J Global Optim 29(3):249–264, 2004b), and nondiagonal (Skjäl et al. in J Optim Theory Appl 154(2):462–490, 2012) \(\alpha \)BB methods, the Brauer and Rohn+E (Skjäl et al. in J Global Optim 58(3):411–427, 2014) \(\alpha \)BB methods, and the moment method (Lasserre and Thanh in J Global Optim 56(1):1–25, 2013). Using a test suite of 40 multivariate, box-constrained, nonconvex functions, the methods were compared based on the tightness of generated underestimators and the efficiency of convergence of a branch-and-bound global optimization algorithm.     

Spectral Properties of Unbounded Jacobi Matrices with Almost Monotonic Weights

We present a unified framework to identify spectra of Jacobi matrices. We give applications of the long-standing problem of Chihara (Mt J Math 21(1):121–137, 1991, J Comput Appl Math 153(1–2):535–536, 2003) concerning one-quarter class of orthogonal polynomials, to the conjecture posed by Roehner and Valent (SIAM J Appl Math 42(5):1020–1046, 1982) concerning continuous spectra of generators of birth and death processes, and to spectral properties of operators studied by Janas and Moszyńki (Integral Equ Oper Theory 43(4):397–416, 2002) and Pedersen (Proc Am Math Soc 130(8):2369–2376, 2002).     

Absolute Cesàro Series Spaces and Matrix Operators

In this paper we derive a series space \(\vert C_{\lambda,\mu} \vert _{k}\) using the well known absolute Cesàro summability \(\vert C_{\lambda,\mu} \vert _{k}\) of Das (Proc. Camb. Philol. Soc. 67:321–326, 1970), compute its \(\beta\)-dual, give some algebraic and topological properties, and characterize some matrix operators defined on that space. So we generalize some results of Bosanquet (J. Lond. Math. Soc. 20:39–48, 1945), Flett (Proc. Lond. Math. Soc. 7:113–141, 1957), Mehdi (Proc. Lond. Math. Soc. (3)10:180–199, 1960), Mazhar (Tohoku Math. J. 23:433–451, 1971), Orhan and Sar?göl (Rocky Mt. J. Math. 23(3):1091–1097, 1993) and Sar?göl (Commun. Math. Appl. 7(1):11–22, 2016; Math. Comput. Model. 55:1763–1769, 2012).     

Numerical Studies on Asymptotics of European Option Under Multiscale Stochastic Volatility

Multiscale stochastic volatilities models relax the constant volatility assumption from Black-Scholes option pricing model. Such models can capture the smile and skew of volatilities and therefore describe more accurately the movements of the trading prices. Christoffersen et al. Manag Sci 55(2):1914–1932 (2009) presented a model where the underlying price is governed by two volatility components, one changing fast and another changing slowly. Chiarella and Ziveyi Appl Math Comput 224:283–310 (2013) transformed Christoffersen’s model and computed an approximate formula for pricing American options. They used Duhamel’s principle to derive an integral form solution of the boundary value problem associated to the option price. Using method of characteristics, Fourier and Laplace transforms, they obtained with good accuracy the American option prices. In a previous research of the authors (Canhanga et al. 2014), a particular case of Chiarella and Ziveyi Appl Math Comput 224:283–310 (2013) model is used for pricing of European options. The novelty of this earlier work is to present an asymptotic expansion for the option price. The present paper provides experimental and numerical studies on investigating the accuracy of the approximation formulae given by this asymptotic expansion. We present also a procedure for calibrating the parameters produced by our first-order asymptotic approximation formulae. Our approximated option prices will be compared to the approximation obtained by Chiarella and Ziveyi Appl Math Comput 224:283–310 (2013).     

Numerical solutions to dynamic portfolio problems with upper bounds

In this paper, we apply value function iteration to solve a multi-period portfolio choice problem. Our problem uses power utility preferences and a vector autoregressive process for the return of a single risky asset. In contrast to the observation in van Binsbergen and Brandt (Comput Econ 29:355–368, 2007) that value function iteration produces inaccurate results, we achieve highly accurate solutions through refining the conventional value function iteration by two innovative ingredients: (1) approximating certainty equivalents of value functions by regression, and (2) taking certainty equivalent transformation on expected value functions in optimization. We illustrate that the new approach offers more accurate results than those exclusively designed for improvement through a Taylor series expansion in Garlappi and Skoulakis (Comput Econ 33:193–207, 2009). In particular, both van Binsbergen and Brandt (Comput Econ 29:355–368, 2007) and Garlappi and Skoulakis (Comput Econ 33:193–207, 2009) comparing their lower bounds with other lower bounds, we more objectively assess our lower bounds by comparing with upper bounds. Negligible gaps between our lower and upper bounds across various parameter sets indicate our proposed lower bound strategy is close to optimal.     

Condition Length and Complexity for the Solution of Polynomial Systems

Smale’s 17th problem asks for an algorithm which finds an approximate zero of polynomial systems in average polynomial time (see Smale in Mathematical problems for the next century, American Mathematical Society, Providence, 2000). The main progress on Smale’s problem is Beltrán and Pardo (Found Comput Math 11(1):95–129, 2011) and Bürgisser and Cucker (Ann Math 174(3):1785–1836, 2011). In this paper, we will improve on both approaches and prove an interesting intermediate result on the average value of the condition number. Our main results are Theorem 1 on the complexity of a randomized algorithm which improves the result of Beltrán and Pardo (2011), Theorem 2 on the average of the condition number of polynomial systems which improves the estimate found in Bürgisser and Cucker (2011), and Theorem 3 on the complexity of finding a single zero of polynomial systems. This last theorem is similar to the main result of Bürgisser and Cucker (2011) but relies only on homotopy methods, thus removing the need for the elimination theory methods used in Bürgisser and Cucker (2011). We build on methods developed in Armentano et al. (2014).     

Preconditioning of spectral methods via Birkhoff interpolation

High-order differentiation matrices as calculated in spectral collocation methods usually include a large round-off error and have a large condition number (Baltensperger and Berrut Computers and Mathematics with Applications 37(1), 41–48 1999; Baltensperger and Trummer SIAM J. Sci. Comput. 24(5), 1465–1487 2003; Costa and Don Appl. Numer. Math. 33(1), 151–159 2000). Wang et al. (Wang et al. SIAM J. Sci. Comput. 36(3), A907–A929 2014) present a method to precondition these matrices using Birkhoff interpolation. We generalize this method for all orders and boundary conditions and allowing arbitrary rows of the system matrix to be replaced by the boundary conditions. The preconditioner is an exact inverse of the highest-order differentiation matrix in the equation; thus, its product with that matrix can be replaced by the identity matrix. We show the benefits of the method for high-order differential equations. These include improved condition number and, more importantly, higher accuracy of solutions compared to other methods.     

Filtration de monodromie et cycles évanescents formels

Berkovich (Invent. Math. 125(2):367–390, 1996), Fujiwara (Duke Math. J. 80(1):15–57, 1995) and Huber (J. Algebraic Geom. 7(2):359–403, 1998) have proved that the fiber of the vanishing cycles at a point of the special fiber depends only on the formal completion at this point. We refine this result and prove the invariance under formal completion of the perverse monodromy filtration on the fiber of vanishing cycles. This result is used in an essential way by Boyer (Invent. Math. doi: 10.1007/s00222-009-0183-9, 2009).     

On the maximum TSP with <Emphasis Type="Italic">γ</Emphasis>-parameterized triangle inequality

The maximum TSP with γ-parameterized triangle inequality is defined as follows. Given a complete graph G = (V, E, w) in which the edge weights satisfy w(uv) ≤ γ · (w(ux) + w(xv)) for all distinct nodes \({u,x,v \in V}\), find a tour with maximum weight that visits each node exactly once. Recently, Zhang et al. (Theor Comput Sci 411(26–28):2537–2541, 2010) proposed a \({\frac{\gamma+1}{3\gamma}}\)-approximation algorithm for \({\gamma\in\left[\frac{1}{2},1\right)}\). In this paper, we show that the approximation ratio of Kostochka and Serdyukov’s algorithm (Upravlyaemye Sistemy 26:55–59, 1985) is \({\frac{4\gamma+1}{6\gamma}}\), and the expected approximation ratio of Hassin and Rubinstein’s randomized algorithm (Inf Process Lett 81(5):247–251, 2002) is \({\frac{3\gamma+\frac{1}{2}}{4\gamma}-O\left(\frac{1}{\sqrt{n}}\right)}\), for \({\gamma\in\left[\frac{1}{2},+\infty\right)}\). These improve the result in Zhang et al. (Theor Comput Sci 411(26–28):2537–2541, 2010) and generalize the results in Hassin and Rubinstein and Kostochka and Serdyukov (Inf Process Lett 81(5):247–251, 2002; Upravlyaemye Sistemy 26:55–59, 1985).     

Biorthogonal wavelets with 4-fold axial symmetry for quadrilateral surface multiresolution processing

Surface multiresolution processing is an important subject in CAGD. It also poses many challenging problems including the design of multiresolution algorithms. Unlike images which are in general sampled on a regular square or hexagonal lattice, the meshes in surfaces processing could have an arbitrary topology, namely, they consist of not only regular vertices but also extraordinary vertices, which requires the multiresolution algorithms have high symmetry. With the idea of lifting scheme, Bertram (Computing 72(1–2):29–39, 2004) introduces a novel triangle surface multiresolution algorithm which works for both regular and extraordinary vertices. This method is also successfully used to develop multiresolution algorithms for quad surface and \(\sqrt 3\) triangle surface processing in Wang et al. (Vis Comput 22(9–11):874–884, 2006; IEEE Trans Vis Comput Graph 13(5):914–925, 2007) respectively. When considering the biorthogonality, these papers do not use the conventional \(L^2({{\rm I}\kern-.2em{\rm R}}^2)\) inner product, and they do not consider the corresponding lowpass filter, highpass filters, scaling function and wavelets. Hence, some basic properties such as smoothness and approximation power of the scaling functions and wavelets for regular vertices are unclear. On the other hand, the symmetry of subdivision masks (namely, the lowpass filters of filter banks) for surface subdivision is well studied, while the symmetry of the highpass filters for surface processing is rarely considered in the literature. In this paper we introduce the notion of 4-fold symmetry for biorthogonal filter banks. We demonstrate that 4-fold symmetric filter banks result in multiresolution algorithms with the required symmetry for quad surface processing. In addition, we provide 4-fold symmetric biorthogonal FIR filter banks and construct the associated wavelets, with both the dyadic and \(\sqrt 2\) refinements. Furthermore, we show that some filter banks constructed in this paper result in very simple multiresolution decomposition and reconstruction algorithms as those in Bertram (Computing 72(1–2):29–39, 2004) and Wang et al. (Vis Comput 22(9–11):874–884, 2006; IEEE Trans Vis Comput Graph 13(5):914–925, 2007). Our method can provide the filter banks corresponding to the multiresolution algorithms in Wang et al. (Vis Comput 22(9–11):874–884, 2006) for dyadic multiresolution quad surface processing. Therefore, the properties of the scaling functions and wavelets corresponding to those algorithms can be obtained by analyzing the corresponding filter banks.     

A Complex Analogue of Toda’s Theorem

Toda (SIAM J. Comput. 20(5):865–877, 1991) proved in 1989 that the (discrete) polynomial time hierarchy, PH, is contained in the class P ^#P , namely the class of languages that can be decided by a Turing machine in polynomial time given access to an oracle with the power to compute a function in the counting complexity class #P. This result, which illustrates the power of counting, is considered to be a seminal result in computational complexity theory. An analogous result (with a compactness hypothesis) in the complexity theory over the reals (in the sense of Blum–Shub–Smale real machines (Blum et al. in Bull. Am. Math. Soc. 21(1):1–46, 1989) was proved in Basu and Zell (Found. Comput. Math. 10(4):429–454, 2010). Unlike Toda’s proof in the discrete case, which relied on sophisticated combinatorial arguments, the proof in Basu and Zell (Found. Comput. Math. 10(4):429–454, 2010) is topological in nature; the properties of the topological join are used in a fundamental way. However, the constructions used in Basu and Zell (Found. Comput. Math. 10(4):429–454, 2010) were semi-algebraic—they used real inequalities in an essential way and as such do not extend to the complex case. In this paper, we extend the techniques developed in Basu and Zell (Found. Comput. Math. 10(4):429–454, 2010) to the complex projective case. A key role is played by the complex join of quasi-projective complex varieties. As a consequence, we obtain a complex analogue of Toda’s theorem. The results of this paper, combined with those in Basu and Zell (Found. Comput. Math. 10(4):429–454, 2010), illustrate the central role of the Poincaré polynomial in algorithmic algebraic geometry, as well as in computational complexity theory over the complex and real numbers: the ability to compute it efficiently enables one to decide in polynomial time all languages in the (compact) polynomial hierarchy over the appropriate field.     

A Double-Parameter Scaling Broyden–Fletcher–Goldfarb–Shanno Method Based on Minimizing the Measure Function of Byrd and Nocedal for Unconstrained Optimization

In this paper, the first two terms on the right-hand side of the Broyden–Fletcher–Goldfarb–Shanno update are scaled with a positive parameter, while the third one is also scaled with another positive parameter. These scaling parameters are determined by minimizing the measure function introduced by Byrd and Nocedal (SIAM J Numer Anal 26:727–739, 1989). The obtained algorithm is close to the algorithm based on clustering the eigenvalues of the Broyden–Fletcher–Goldfarb–Shanno approximation of the Hessian and on shifting its large eigenvalues to the left, but it is not superior to it. Under classical assumptions, the convergence is proved by using the trace and the determinant of the iteration matrix. By using a set of 80 unconstrained optimization test problems, it is proved that the algorithm minimizing the measure function of Byrd and Nocedal is more efficient and more robust than some other scaling Broyden–Fletcher–Goldfarb–Shanno algorithms, including the variants of Biggs (J Inst Math Appl 12:337–338, 1973), Yuan (IMA J Numer Anal 11:325–332, 1991), Oren and Luenberger (Manag Sci 20:845–862, 1974) and of Nocedal and Yuan (Math Program 61:19–37, 1993). However, it is less efficient than the algorithms based on clustering the eigenvalues of the iteration matrix and on shifting its large eigenvalues to the left, as shown by Andrei (J Comput Appl Math 332:26–44, 2018, Numer Algorithms 77:413–432, 2018).     

Multivariate Higher-Degree Stochastic Increasing Convexity

Building on the seminal work by Shaked and Shanthikumar (Adv Appl Probab 20:427–446, 1988a; Stoch Process Appl 27:1–20, 1988b), Denuit et al. (Eng Inf Sci 13:275–291, 1999; Methodol Comput Appl Probab 2:231–254, 2000; 2001) studied the stochastic s-increasing convexity properties of standard parametric families of distributions. However, the analysis is restricted there to a single parameter. As many standard families of distributions involve several parameters, multivariate higher-order stochastic convexity properties also deserve consideration for applications. This is precisely the topic of the present paper, devoted to stochastic \((s_1,s_2,\ldots ,s_d)\)-increasing convexity of distribution families indexed by a vector \((\theta _1,\theta _2,\ldots ,\theta _d)\) of parameters. This approach accounts for possible correlation in multivariate mixture models.     

Extensions of the Noncommutative Integration

In this paper we will continue the analysis undertaken in Bagarello et al. (Rend Circ Mat Palermo (2) 55:21–28, 2006), Bongiorno et al. (Rocky Mt J Math 40(6):1745–1777, 2010), Triolo (Rend Circ Mat Palermo (2) 60(3):409–416, 2011) on the general problem of extending the noncommutative integration in a *-algebra of measurable operators. As in Aiena et al. (Filomat 28(2):263–273, 2014), Bagarello (Stud Math 172(3):289–305, 2006) and Bagarello et al. (Rend Circ Mat Palermo (2) 55:21–28, 2006), the main problem is to represent different types of partial *-algebras into a *-algebra of measurable operators in Segal’s sense, provided that these partial *-algebras posses a sufficient family of positive linear functionals (states) (Fragoulopoulou et al., J Math Anal Appl 388(2):1180–1193, 2012; Trapani and Triolo, Stud Math 184(2):133–148, 2008; Trapani and Triolo, Rend Circolo Mat Palermo 59:295–302, 2010; La Russa and Triolo, J Oper Theory, 69:2, 2013; Triolo, J Pure Appl Math, 43(6):601–617, 2012). In this paper, a new condition is given in an attempt to provide a extension of the non commutative integration.     

Linear codes from simplicial complexes

In this article we introduce a method of constructing binary linear codes and computing their weights by means of Boolean functions arising from mathematical objects called simplicial complexes. Inspired by Adamaszek (Am Math Mon 122:367–370, 2015) we introduce n-variable generating functions associated with simplicial complexes and derive explicit formulae. Applying the construction (Carlet in Finite Field Appl 13:121–135, 2007; Wadayama in Des Codes Cryptogr 23:23–33, 2001) of binary linear codes to Boolean functions arising from simplicial complexes, we obtain a class of optimal linear codes and a class of minimal linear codes.     

Further properties of the forward–backward envelope with applications to difference-of-convex programming

In this paper, we further study the forward–backward envelope first introduced in Patrinos and Bemporad (Proceedings of the IEEE Conference on Decision and Control, pp 2358–2363, 2013) and Stella et al. (Comput Optim Appl, doi: 10.1007/s10589-017-9912-y, 2017) for problems whose objective is the sum of a proper closed convex function and a twice continuously differentiable possibly nonconvex function with Lipschitz continuous gradient. We derive sufficient conditions on the original problem for the corresponding forward–backward envelope to be a level-bounded and Kurdyka–?ojasiewicz function with an exponent of \(\frac{1}{2}\); these results are important for the efficient minimization of the forward–backward envelope by classical optimization algorithms. In addition, we demonstrate how to minimize some difference-of-convex regularized least squares problems by minimizing a suitably constructed forward–backward envelope. Our preliminary numerical results on randomly generated instances of large-scale \(\ell _{1-2}\) regularized least squares problems (Yin et al. in SIAM J Sci Comput 37:A536–A563, 2015) illustrate that an implementation of this approach with a limited-memory BFGS scheme usually outperforms standard first-order methods such as the nonmonotone proximal gradient method in Wright et al. (IEEE Trans Signal Process 57:2479–2493, 2009).     

Mixed-integer quadratic programming is in NP

Mixed-integer quadratic programming is the problem of optimizing a quadratic function over points in a polyhedral set where some of the components are restricted to be integral. In this paper, we prove that the decision version of mixed-integer quadratic programming is in NP, thereby showing that it is NP-complete. This is established by showing that if the decision version of mixed-integer quadratic programming is feasible, then there exists a solution of polynomial size. This result generalizes and unifies classical results that quadratic programming is in NP (Vavasis in Inf Process Lett 36(2):73–77 [17]) and integer linear programming is in NP (Borosh and Treybig in Proc Am Math Soc 55:299–304 [1], von zur Gathen and Sieveking in Proc Am Math Soc 72:155–158 [18], Kannan and Monma in Lecture Notes in Economics and Mathematical Systems, vol. 157, pp. 161–172. Springer [9], Papadimitriou in J Assoc Comput Mach 28:765–768 [15]).