Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [quadratic]

The tag has no usage guidance.

0
votes
0answers
233 views

Complexity of Quadratic Programming

I'm trying to learn the complexity of a quadratic program in the form of: minimize: $f(x,y)=x^2-y^2-4xy$ given only $x*y$ s.t. $x=a+b$ $y=a-b$ $x+y>3\,\sqrt{xy}$ $x,y,a,b >0$ What I ...
1
vote
0answers
56 views

Polynomial cases of 0 1 quadratic programm with linear constraints

A pseudo boolean function f:{0,1}^n-> R is defined as f(x)= x^tQx +cx where Q is a symmetric matrix with null elements in the diagonal. Finding the minimum of this function is solvable in polynomial ...
9
votes
0answers
251 views

Checking whether two quadratic equations have a common zero

Given two quadratic equations (with integer coefficients): $x^T A_1 x+ b^T_1 x + c_1=0$ and $x^T A_2 x+ b^T_2 x + c_2=0$ The problem is to decide whether they have a common zero. Here $x$ is a ...
6
votes
1answer
141 views

Bounds on the size of the solution of a quadratic program

I am interested in a quadratic program of the form $$ \min x^T Q x $$ $$s.t.$$ $$ Ax \leq b $$ where $x$ is a vector with $n$ entries, the size of the maximal entry in $Q, A$, and $b$ is $\varphi$, $...
3
votes
1answer
226 views

NP-hardness of a bilinear program?

Given $a_i, b_i, c_i, d_{ij}\in [0,1]$ for $i,j\in [n]$ and $i\neq j$ such that $\sum_{i\in [n]} a_i=1$ and $d_{ij}=d_{ji}$. I have the following bilinear program: max $\sum_{i=1}^n (x_i-a_i)y_i$ ...
0
votes
1answer
113 views

What are some efficient algorithms for determining if a system of quadratic multivariate polynomials have a solution?

I know that in the general case it isn't efficient. However, I'm wondering if there are any good techniques in the quadratic case over the reals, specifically if there is a polynomial time solution.
2
votes
0answers
149 views

What are some efficient algorithms for finding the solutions to a quadratic multivariate polynomial?

Based on this question, there's an efficient algorithm to determine whether a quadratic multivariate polynomial has a root. What are some algorithms to enumerate these solutions? I'm interested in ...
8
votes
4answers
600 views

What are some efficient algorithms for determining if a quadratic multivariate polynomial has a solution?

I know that in general, multivariate polynomial satisfiability is equivalent to 3-SAT; however, I'm wondering if there are any good techniques in the quadratic case, specifically if there is a ...
3
votes
3answers
1k views

Maximize quadratic function subject to linear constraints

Can one maximize $\sum_i c_i x_i^2$ where the $c_i$ are constants (possibly negative), subject to linear constraints over the $x_i$? This paper seems to come close to answering "no." They show it is ...