Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [quadratic-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
1answer
30 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 ...
1
vote
1answer
47 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'...
1
vote
0answers
16 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, ...
0
votes
0answers
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?
0
votes
0answers
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 ...
0
votes
1answer
45 views

Max-min of a nonconvex quadratic problem

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 ...
4
votes
2answers
555 views

Approximate subset sum with two-dimensional vectors

Consider the following optimization problem: Given $n\leq 10^3$ vectors $v_i\in\mathbb{R}^2$, all of which are small, i.e., $\|v_i\| \leq 1$, find a subset $S$ of them that minimizes $ \| w + \...
2
votes
0answers
36 views

Can any Mixed Integer Quadratic Program be approximately solved with Semi Definite Programming relaxation?

I understand that we can approximate solutions to Integer Quadratic Programming optimization problems containing just a positive semi definite matrix, as outlined here (i.e. the Q matrix): https://...
0
votes
0answers
45 views

Qudratic Equations - Promise Problem

Is the follwing promise problem NP-hard? Input: A system of quadratic equations. Promise: The system has either one or zero solutions. Question: Does the system have a solution?
0
votes
0answers
168 views

Complexity of active set method for Quadratic Programming

The Quadratic Programming problem is as follows: $$\min_x \{\frac12x^THx+x^Tg\}$$ $$Ax\le b$$ where $H$ is symmetric and positive semi-definite. What is the complexity of the active set method for ...
2
votes
1answer
169 views

Modeling $(x > 0 \wedge y > 0) \Leftrightarrow z > 0$ in a linear program: impossible?

In this question, we see how to model boolean logic in $0 - 1$ ILPs. Moving to a relaxation, modelling $(x > 0 \vee y > 0) \Leftrightarrow z > 0$ with $x,y,z \in [0,1]$ with linear ...