Questions tagged [quadratic-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
15 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
44 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
515 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
43 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
159 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 ...