Questions tagged [quadratic-programming]
The quadratic-programming tag has no summary.
22 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
0
votes
0
answers
25
views
Adam gradients for least squares approaches?
Least squares leads to an n-dimensional "parabola" in the parameters. I assume the same is valid for other constrained least squares like non-negative least-squares.
This may be a wrong ...
1
vote
1
answer
49
views
PAVA for partially-ordered (lattice) x-axis
Given an MxN matrix A, I want to find the nearest matrix B (least squares fit: ie minimize$\displaystyle\sum_{i,j} (B_{ij} - A_{ij})^2$) such that
$$
\forall i_1,j_1,i_2,j_2 : \\
i_1 \leq i_2 \land ...
2
votes
2
answers
274
views
Approximation algorithms for integer convex quadratic programs over a linear subspace
Consider the problem
$$
\min_x \frac{1}{2} x^\top Q x + c^\top x \qquad \text{s.t.}\\
Ax=b\\
x \in \mathbb{Z}^n
$$
where $Q$ is a positive (semi)definite matrix.
Clearly, feasibility can be decided in ...
3
votes
1
answer
134
views
What is the complexity of minimising a convex quadratic function over the integers?
The problem of interest is
$$
\min_{x\in\mathbb{Z}^n} \frac{1}{2}x^\top Q x + c^\top x
$$
where $Q$ is a positive definite matrix. I am reasonably sure this can't be solved in poly-time, since the ...
0
votes
1
answer
272
views
What's the difference between "convex/non-convex optimization" and "quadratic programming"?
I'd like to start by clarifying I'm by no means an expert in any of this, so take everything I say with a grain of salt.
Convex and Non-convex Optimization are subfields of mathematical optimization ...
2
votes
1
answer
202
views
Is the following binary quadratic integer programming NP-Hard?
I'am trying to prove the following binary quadratic integer programming problem NP hard.
$$
\min \frac{\sum\limits_{i=1}^m(u_i-\bar u)^2}{m}\text{ , where }u=Q x,Q\in\mathbb{R}^{m\times n}\\
s.t. \...
1
vote
0
answers
73
views
Finding $\text{argmin}_{x\in \Delta_n} ||A x -y||^2$
Let $\Delta_n :=${$x\in \mathbb{R}^n\colon \sum_{i=1}^n x_i = 1$} denote the probability simplex in $\mathbb{R}^n$ and $A^{n \times n}$ be diagonalizable matrix.
I would like to know what is the ...
0
votes
0
answers
38
views
Polynomial Deterministic Algorithm for MAX-QP problem with multiplicative errror 1ドル/n$
MAX-QP problem (quadratic programming on boolean cube) statement:
Given symmetrical matrix $A$ with 0 on diagonal
$$A = (a_{ij}) : A^T = A, a_{ii} = 0$$
Find maximum $x^TAx$ where $x \in \{0, 1\}^n,ドル ...
0
votes
1
answer
152
views
SVMs - Fat (Margin) Boundary: Why is $\max\frac1{||\theta||}=\min \frac{ ||\theta||^2}{2}$?
I am trying to understand SVMs in depth watching lectures from MIT.
The professor to reduces the classification problem into an optimization problem. To do that, he first defines the decision and ...
3
votes
0
answers
277
views
Verifying a matrix is Copositive
A symmetric matrix $A\in \Bbb{R}^{n\times n}$ is copositive if for every vector $x\in\Bbb{R}^n$ with non-negative entries, we have
$$x^TAx \ge 0.$$
What are known methods to check if a specific matrix ...
4
votes
0
answers
134
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 ...
5
votes
1
answer
1k
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
2
answers
280
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
0
answers
131
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
0
answers
76
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?