This is for questions on Quadratic Programming (QP). A QP problem is the problem of minimising or maximising a quadratic objective function subject to affine constraints.

learn more… | top users | synonyms

3
votes
2answers
1k views

what is the computational complexity of solving a quadratic program with linear inequality constraints

I'm aware of several solution methods and have several solvers at my disposal, but I can't for the life of me find analysis on the complexity. In particular, I'm interested in the complexity of ...
3
votes
1answer
42 views

Finiteness of the Supremum of Inner Product of Two Finite Sum Positive Sequence

Let $$A = \Big\{(a_1,a_2,\dots)\ \Big|\ a_i\ge 0, \sum_{i=1}^\infty a_i=1\Big\},$$ $$v(x)=\sup\left(\bigg\{\sum_{i=1}^\infty a_ib_i\ \bigg|\ (a_i)_{i=1}^\infty,\, (b_i)_{i=1}^\infty \in ...
3
votes
1answer
233 views

Optimization problem with ratio objective

I need to solve the following optimization problem $$ \text{maximize} \quad \frac{(a^T x)^2}{x^TBx+c^T|x|} \quad \text{subject to} \quad \|x\|_1=1 \quad (\text{or alternatively} \quad c^T|x|=1), $$ ...
2
votes
1answer
178 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} ...
2
votes
1answer
100 views

Software to optimize a quadratic program with quadratic constraints

I'm working in eight dimensions and want to minimize $x^TAx$ under the constraints $x^TBx \geq c$. Unfortunately, A is not positive semidefinite. Worse, I am almost positive that my domain is not ...
1
vote
1answer
52 views

Solving multiple $L_1$ penalties with quadratic programming

Starting from a simple $L_1$ penalization: \begin{equation} min_x \frac{1}{2}||y-x||^2_2 + \lambda||Dx||_1 \end{equation} We can solve this with quadratic programming via the dual problem: ...
1
vote
1answer
265 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
1answer
28 views

Quadratic equation formula for a,b,c from 3 points

I can solve for a, b, c given three points for a parabola for example (1,1)(2,4)(3,9) but i need to create a program which returns a,b,c in the form: ...
0
votes
1answer
71 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
1answer
52 views

Is a given point P outside a given bounding box, in Ax < b form

Given a point $x$ and a bounding box $B$ - let's say we have the unit normals $N_i$ of the sides (pointing inwards) and one point on each side $P_i$ - we can check if $x$ is inside $B$ as follows: ...
4
votes
0answers
38 views

How to find accuracy of Matlab's quadprog solver?

I have solved with quadprog from Matlab a strong convex quadratic problem given as $$ f(x) = x^TQx + c^Tx$$ with constrains $$ Cx \leq b.$$ Now the output of quadprog is: Minimum found that ...
2
votes
0answers
33 views

Effective convexity criterion for the finite point set in $\mathbb{R}^3$

I need to find effective convexity criterion for the finite point set. Below there is description of what is meant by "effective" criterion. Definition. Let $M = \{A_{1}, \ldots, A_{n}\}$ be the ...
2
votes
0answers
21 views

Reproducing Kernel Function Interpolation

My problem is as follows: I am attempting to use a reproducing kernel and quadratic programming to optimize/interpolate a smooth function from constraints. I am using all local extrema to calculate ...
2
votes
0answers
37 views

Constrained Quadratic Optimization(Reproducing Kernel)

I am attempting to use a constrained quadratic optimization to find the coefficients of a reproducing kernel. The problem is as follows: $y(t)=\sum_{i=0}^J\alpha_iK(t, t_i)$ $Q(\alpha)= ...
2
votes
0answers
57 views

Quadratic Integer Programming

Would anyone mind helping me solve this problem $$ \min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda $$ where $x$ is a vector whose entries are positive ...
1
vote
0answers
11 views

Modeling a lower-bound constraint on a euclidean distance in quadratic programming

I have been trying to model a certain problem into a mainly linear program, but with some quadratic constraints since I don't think that is something that can be avoided. I hope to solve it either ...
1
vote
0answers
12 views

Optimizing a set of rules to better predict the outcome of events

I'm trying to better predict the top three finishers of the next 1000 800m mens freestyle swimming race. I've got a set of rules to rate the swimmers: 1) Add 5 points if the swimmer won his last ...
1
vote
0answers
22 views

Reduce degree of a high degree unconstrained binary term to quadratic unconstrained binary term

I'm working on a optimization project, in this project I have to convert higher order unconstrained binary polynomial to quadratic unconstrained binary polynomial. Can anyone give me a hint of how to ...
1
vote
0answers
18 views

Existence criterion for solution in quadratic programming

I have the problem $$ \begin{align*}\min \quad&f(x)= c^Tx + x^TQx \\ &x\in D \end{align*}$$ with $D=\{ x \in \mathbb{R}^n \mid Ax \leq b\}$, $A,Q\in \mathbb{R}^{n\times n}$ and $b,c \in ...
1
vote
0answers
18 views

Uniqueness of the solution to a quadratic opt problem

Consider a positive definite matrix $\boldsymbol H$, the known vectors ${\boldsymbol b}$ and ${\boldsymbol a}_i$. Now the minimization problem is casted with respect to the vector ${\boldsymbol x} $ ...
1
vote
0answers
53 views

Linear Complementarity Problem - multiple solutions, which one will it find?

If I have a inequality constrained system: w = Mz + q <= 0, z<=0, z^T w = 0 that for some given properties M and ...
1
vote
0answers
92 views

Nearest point to a convex polytope

I am looking for fast, memory-efficient computational algorithms to solve the following problem: Minimize: $||x - x*||_2^2$, subject to constraints $A x = a, B x <= b, l <= x <= u$, where ...
1
vote
0answers
109 views

Minimize a complex quadratic subject to two convex quadratic constraints

I have the following the optimization problem \begin{align} \min_{\mathbb{x}\in \mathbb{C}^{N \times 1}}~&||\mathbb{x}^H\mathbb{u}||_2^2-2*Real\{ \mathbb{x^Hu}\} \\\ ...
1
vote
0answers
126 views

Quadratic programming with simplex constraints

I have this quadratic function $x'Ax$ which is not convex. I want to maximize this function subject to the constraints that the solution x lies in a simplex such that $\sum_{i=1}^{n}x_i=1$. That means ...
1
vote
0answers
119 views

Algorithm and solver for large, dense, positive-semidefinite integer QP

I am interested in the solutions of a very large quadratic programming (QP) problem \begin{align} \min_{x \in \mathbb{R}^n} & x^T Q x\\ \mathrm{subject\ to} & A x = b\\ & x \in \{0,1\}^n ...
0
votes
0answers
32 views

Least squares with three quadratic constraints (Ellipse fitting based on algebraic distance)

I would like to fit an ellipse to a given set of scattered data in $\mathcal{R}^2$. The fitting problem is in form least squares, minimizing the sum of squared algebraic distances \begin{equation} ...
0
votes
0answers
16 views

Is there a software package to solve large (128 x 128) non-positive-definite quadratic programming problems?

I am trying to solve a quadratic program of the form maximize $\sum_{i=1}^n\sum_{j=1}^nA_{i,j}w_iw_j$ subject to $\forall i:w_i\ge 0$ and $\sum_{i=1}^nw_i=1$ for a 128$\times$128 matrix $A$. ...
0
votes
0answers
19 views

Quadratic programming over a simplex

I have to solve the following problem: $$\left\{\begin{array}{l}\hat\theta = \arg \min_{\theta} \theta^TQ\theta + \theta^Tl\\ \text{s.t.}\\ \sum_{i=1}^n \theta_i = M\\ \theta_i \in [0, M] ~ \forall i ...
0
votes
0answers
56 views

Quadratic programming using Python

guys I'm trying to solve quadratic programming problem with constraints. I know how to solve simple quadratic problems using scipy.optimize like following: Define objective function as F = ...
0
votes
0answers
40 views

Determining initial values for optimization problem

I am trying to solve an optimization problem with a quadratic objective function and non-linear constraints, using SQP (Sequential Quadratic Programming). I am attempting at doing the implementation ...
0
votes
0answers
22 views

First and second derivatives of barrier term in a quadratic programming problem

I am implementing an algorithm of Dang and Xu's, ``Non-convex Quadratic Programming Problem with Box Constraints'' and I'm hoping that somebody could verify what I'm doing. Their algorithm minimizes ...
0
votes
0answers
20 views

Restating optimization problem for quadratic programming

I'm working on implementing an author disambiguation algorithm as described in Torvik et al's paper. I've got most steps done, but am completely stumped on implementing a quadratic optimization step. ...
0
votes
0answers
17 views

Backwards quadratic programming to infer Q matrix

Consider the standard QP problem: $\arg\min \frac{1}{2}x^TQx +c^Tx$ Say I know the optimal $x$ for a large number of solutions to this problem with various (known) $c$, and identical (unknown) $Q$. ...
0
votes
0answers
23 views

Hinge point in quadratic program (bilateral constraint)

My question itself is possibly quite simple and I guess that if someone can answer me they probably does not need a wall of text that is my background to the problem, but I figured I should provide as ...
0
votes
0answers
6 views

Perturbation of Polyhedral Projection

I am interested in understanding the behavior of the Euclidean projection $\pi_K(x)$ as the polyhedral set $K$ varies. I know there are different approaches to this, but for what I am doing it would ...
0
votes
0answers
60 views

enforcing big M constraints in quadprog

I have a QP with LC type problem. I have several sets of variables x1, x2 ... ,y where x is continuous and y is binary. However I don't enforce this, it is simply bound 0 <= y <= 1 Now I use big ...
0
votes
0answers
45 views

Writing down the KKT optimality conditions

Consider the problem Minimize $(1/2)\times{x}^{T}\times Q\times x+{P}^{T}\times x$ Subject to $(1/2)\times {x}^{T}\times P\times x+{d}^{T}\times x≤r$ Where Q and P are n×n matrices, P is ...
0
votes
0answers
30 views

How to find maximum of $w_1^Ta + w_2^Tb + w_3^Tc$

I have a question that is not homework, but I have gotten nowhere on yet. Define: $w_1^T := [x_1,\ldots,x_n]$, $w_2^T := [x_1^2,\ldots,x_n^2]$ and $w_3^T := [x_1^3,\ldots,x_n^3]$. How do I maximise ...
0
votes
0answers
21 views

Optimization with intervals

I am trying to solve a specific problem, and I was able to summarize it in the following optimization problem. I have a portfolio comprised of two assets. Asset 1 has return $r_1$, standard deviation ...
0
votes
0answers
84 views

a question about relationship between KKT matrix equation and optimal solution of quadratic problem.

I have a question regarding how the KKT matrix plays in solving for optimization problem: Is it correct that the optimal solution for quadratic optimization problem with positive definite hessian ...
0
votes
0answers
92 views

Are box constraints problematic when using KKT conditions to solve quadratic programming problems?

I've dealt with quadratic programming before, but I've never seen something of this sort: $$\min \frac12 \|v\|^2 + \sum_ip_i$$ $$\text{s.t. }f(v,p)\ge0 $$ $$0\le p_i\le a$$ for some constant a ...
0
votes
0answers
32 views

Implementing SVM: Help converting equation into form of another

I'm currently programming a simple linear SVM (Support Vector Machine). For the optimization involved, I need to find a way to convert the equation $\sum\limits_{i=1}^L a_i ...
0
votes
0answers
24 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
126 views

Optimization problem given a known solution space

Here is my problem. I have to find four points in 3D (x1,y1,z1; x2,y2,z2; x3,y3,z3; x4,y4,z4) that satisfy some given quadratic constraints. In addition, I have a solution space in the form of a set ...
0
votes
0answers
86 views

Is this a quadratic programming problem?

I have $N$ unknown 2D points ${\bf x} = (x,y)$ and I want to minimize: $f({\bf x}) = \sum_{i=0}^{N-1}{(||x_{i+1} - x_i||_2 - c_i)^2}$ where c are $N-1$ known scalars. What is the simplest form that ...
0
votes
0answers
75 views

Solving non concave quadratic function in matlab with constraints

How can I solve non concave quadratic problem in matlab with constraints. I tried using quadprog but it doesn't work