The tag has no usage guidance.

12 questions
Filter by
Sorted by
Tagged with
72 views

### Approximation algorithms for indefinite quadratic form maximization with linear constraints

Consider the following program: \begin{align} \max_x ~& x^TQx \\ \mbox{s.t.} ~& Ax \geq b \end{align} where $Q$ is a symmetric (possibly indefinite) matrix and the inequality is element-wise ...
45 views

### Is unconstrained quadratic programming NP-hard?

I could not find the answer on the Internet. The case of quadratic programming with constraints is already solved on this forum, see Transforming SAT to Quadratic Programming in polynomial time. But ...
48 views

### Can an optimization algorithm be “universal”?

I am wondering if a Bayesian Optimization framework (e.g. Google's Vizier) can be used in lieu of a traditional solver like Gurobi or CPLEX. In trying to answer this question, I realized that I don'...
19 views

### Does Quadratically-Constrainted Quadratic Programming get easier if all constraints are equalities?

A Quadratically-Constrainted Quadratic Program consists of optimizing a quadratic objective function while imposing quadratic constraints, which can be inequalities or equalities. Obviously, ...
74 views

### How to prove QUADPROG is NP-hard using 3COLOR? [duplicate]

I am given a task to prove using 3COLOR that Quadratic Programming is NP-hard. Does anyone have a clue on how this is meant to be done?
19 views

### NP Reduction from 3Color to QuadProg [duplicate]

i just signed up here because im struggling very hard with a problem i gotta solve. What I wanna do is reducing an Instance of 3color to an instance of Quadprog to prove that quadprog is np-hard, and ...
I am trying to solve the following problem, which is a simplification of our original question: $\max\limits_{x,y}\min \{x_iy_i-b_i \mbox{ for } i=1,\ldots, n: x,y\in \Delta_n\}$ where $\Delta_n$ is ...