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

5
votes
1answer
395 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 ...
3
votes
1answer
57 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 ...
4
votes
0answers
37 views

Quadratic optimisation with quadratic equality constraints

I would like to solve the following optimisation problem: $\min_{x} (x'Ax)$ subject to $x'Bx = x'Cx = 1$. Where A is symmetric and B and C are diagonal. Does anyone have a suggestion for an ...
4
votes
0answers
95 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
15 views

Quadratic programming

For a research project I am interested in minimizing $x^TQx$ under the constraints $Qx \le b$, where $Q$ is a positive definite matrix and $b$ is a vector of negative elements. I have solved this ...
2
votes
0answers
150 views

Lagrange multiplier expression

I would like to solve the following optimization problem using the gradient ascend method: \begin{array}{ll} \text{maximize}_{\theta} & \theta^TQ_1\theta + b_1\\ \text{subject to} & ...
2
votes
0answers
35 views

Nearest non-negative solution for $Av=b$

Let $A$ be a $n\times m$ matrix. Let us define the system $$Av=b$$ $$v\geq 0$$ I want to find a solution $v$ of this system that is the closest (euclidean norm) to $v_0$, a given $n$-dimensional ...
2
votes
0answers
35 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
27 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
72 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
58 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 ...
2
votes
0answers
132 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
43 views

Quadratic optimization problem (inner products) with stochastic constraints

Let the set of feasible solution be the set of all row-stochastic $n \times k$ matrices $P = [p_{ij}]$, that is $\mathcal{P} := \{P \in \mathbb{R}^{n \times k} \ | \ P \mathbf{1} = \mathbf{1}, P \geq ...
1
vote
0answers
59 views

Why use two slack variables in the support vector regression formulation?

I am learning support vector regression but cannot fully understand the rational of the slack variable tricks in its formulation. The original optimization problem for SVR is as follows: ...
1
vote
0answers
40 views

Two quadratic programming problems always same answer?

Was exploring quadratic programming optimization and for two types of problems the answers seemed to always equal. Is there an intuitive proof? Problem 1: Minimize $\tfrac{1}{2} \mathbf{x}^T ...
1
vote
0answers
24 views

How to interpolate a function with a reproducing kernel

I am trying to interpolate a function that is noisy, but I know with a high amount of certainty about a third of the points in the series. I am trying to estimate the smooth mean of the signal via a ...
1
vote
0answers
49 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
13 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
31 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
57 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} ...
1
vote
0answers
27 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
78 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 ...
1
vote
0answers
36 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 ...
1
vote
0answers
22 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
61 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
139 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
156 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
125 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
10 views

Complexity of solving quadratic programming (QP) using ADMM

I am trying to analysis the time complexity of quadratic programming problem, using alternating direction method of multipliers. Anyone could give me a help?
0
votes
0answers
17 views

Approximate inverse (or fast optimization) of non-linear least squares problem

Problem Statement Let ${\bf x}\in\mathbb{R}^N$ and ${\bf W}\in\mathbb{R}^{K\times N}$, ${\bf V}\in\mathbb{R}^{N\times K}$. We define $${\bf y} = f({\bf x}) = [{\bf V}[{\bf Wx}]_+]_+$$ where $[.]_+ = ...
0
votes
0answers
19 views

How to obtain the optimal lagrange multiplier vectors if the globally optimal solution for a nonconvex QCQP is found.?

I am using a blackbox solver to solve the following nonconvex QCQP to global optimality. $$ \min_x x^TQ_0x + c^T x \\ s.t. \quad x^TQ_1x+c_1^Tx=b_1 \\ Ax=b \\ l\leq x\leq u $$ where $Q_0$ is ...
0
votes
0answers
22 views

When is a quadratically constrained quadratic program (indefinite objective matrix) unbounded?

I have a nonconvex QCQP of the form $$x^TQ_0x + c^T x$$ such that $x^TQ_1x+c_1^Tx=b_1$, $Ax=b$, and $l\leq x\leq m$ where $Q_0$ is indefinite diagonal matrix and $Q_1$ is positive semidefinite ...
0
votes
0answers
6 views

How to deal with a barrier function when constrained variables reach their bounds?

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
151 views

Linear - Quadratic optimization for system of objectives

I have two distinct data sets, $\{x^{\mu},J^{\mu}\}$, $\mu=1,\ldots,n$ and $\{x^{\nu},V^{\nu}\}$, $\nu=1,\ldots,m$ that also include uncertainties $\delta J^{\mu}$ and $\delta V^{\nu}$. In these I fit ...
0
votes
0answers
16 views

Quadratic program with complementarity/modular constraints is NP?

Is the following program NP/NP-hard? Any neat way to prove it, or a helpful reference? $\min x^TMx$, subject to $\|x\|_1=1,e^Tx=0$ Here $M$ is a real, symmetric and semidefinite positive matrix, ...
0
votes
0answers
20 views

How to convert the following optimization problem to quadratic program?

Given positive constants $C$ and $\epsilon$ and points $\{ (x^i,b_i)\} _{i=1}^I \subset \mathbb{R}^{n+1}$, how can we rewrite the following optimization problem as minimizing a convex quadratic ...
0
votes
0answers
43 views

Using Gurobi QP to solve SVM problem

I am trying to use Gurobi to solve the QP problem in primal form of soft margin SVM. The quadprog function seems to return the correct answer while Gurobi cannot solve the problem. Gurobi keeps ...
0
votes
0answers
8 views

How to test if a set of underdetermined equations have solution in a particular region?

For a underdetermined system $A\cdot x = b$ where $A$ is a $m \times n$ matrix with $m<n$, how to test if it has a solution within a specific region $\{ x | lb<x_i<ub \}$? Basically I have ...
0
votes
0answers
26 views

Reformulate as quadratic programming

I am trying to approximate L0 constrained quad-prog problem as L1 but not making any progress. The objective is to minimize $x A x'$, s.t. $\sum x <=n$ , where $0<=x<=1$ and A is positive ...
0
votes
0answers
22 views

Portfolio Optimization Problem: Variance Co-variance matrix

I have a set of daily returns and using these daily returns I calculated the average annual return for each asset and also by using the daily returns I calculated the var-cov matrix. To get optimize ...
0
votes
0answers
37 views

Finding a solution on Matlab for a quadratic programming-type problem with more restrictions

I have some existence results using one modified version of the Farkas Lemma for which I need to solve the following problem. This problem has its application on economics but I will refer here merely ...
0
votes
0answers
19 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
30 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
34 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
19 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
68 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
22 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
26 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
95 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
80 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