0
votes
1answer
34 views

Linear programming with non-convex quadratic constraint

Could anyone let me know if the following linear programming problem can be solved in polynomial time or should be NP-hard? $\min c^Tx$ s.t. $x^TQx\geq C^2, x\in [0,1]^n,c\in ...
0
votes
0answers
31 views

Linear programming with quadratic constraints

I want to solve a problem of this form: $max_{y,k} \,\,\, w^\top y + C 1^\top k$ s.t. $k y^\top B^\top = I $ $A^\top y \geq b$ is there an algorithm that can solve such a problem? Is there an ...
1
vote
0answers
76 views

Linear Programming with One Quadratic Equality Constraint

I have a problem which can be formulated as a Linear Programming with One Quadratic Equality Constraint: where variable x is n-dimensional vector and H is a Semi-Positive Definite n-by-n matrix. I ...
0
votes
0answers
18 views

How to check if steepest gradient method will converge?

So I have this function $ f(x,y) = x^4 - 2x^2 +x + 4y^2 $ and I want to know if the steepest gradient method will converge if I pick an arbitrary point and apply said method. My initial thought ...
0
votes
0answers
26 views

Total unimodularity in quadratic programming.

I have a quadratic integer problem of the following form: \begin{align} minimize & \quad \tfrac{1}{2} x^T Q x + c^T x \\ subject \ to & \quad M x = 1 \\ & \quad x_i \in \{0, 1\} ...
0
votes
0answers
36 views

Finding an optimal set of weights for combining correlated classifiers

In order to combine classifiers that are correlated with one another, I would need to solve the following optimization problem: Find a vector $\mathbf{w}$ that minimizes $\mathbf{w}^T M \mathbf{w}$ ...
0
votes
0answers
21 views

Question concerning quadratic programming

Consider a quadratic program where you are given a polyhedron Ax <= b And you are given an arbitrary point F such that you want to maximize the distance from this point and you are guaranteed the ...
2
votes
1answer
154 views

Convex optimization and linear programming please help! :)

How would I write the following as a standard form LP? Minimizing $\sum_{i=1}^n x_i + c\max(a_i-x_i)$ for $a_i \ge 0$ and what is the optimal value for when $c=n$ How to express minimize $\frac{1}{2} ...
0
votes
1answer
63 views

Solving equation of the form $Axb^Tx = y$

I have a square, invertible $n\times n$ matrix $A$, and column vectors $b$ and $y$. I'd like to find a column vector $x$ such that $Axb^Tx=y$. I suspect there's some way to get it into a QP form, but ...
1
vote
1answer
649 views

Example of a quadratic programming problem with no optimal solution on vertices?

Is there a way to write a quadratic programming problem with two variables bounded, nonempty feasible region linear constraints and yet have none of the vertices of the region optimize the ...