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

4
votes
0answers
79 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
192 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
29 views

Boolean Quadratic Programming

I am new to optimization and I am trying to understand concepts of semi-definite relaxation (SDR) through examples. It seems my understanding of this topic is not fully clear as I will show in details ...
2
votes
0answers
26 views

How to efficiently solve a quadratic program repeatedly?

I have a quadratic problem, \begin{align} \min_{x\in [0,1]^n} x^T p+ \frac{1}{2\lambda} x^T Q x \end{align} ($Q$ is semidefinite) which I want to solve repeatedly, with the slight change of p and Q, ...
2
votes
0answers
28 views

Theoretically understanding the algorithmic solution to this Quadratically Constrained Quadratic Optimization Problem

I have a simple QCQP problem to solve: $\min_{t} x(t)^{T}Ax(t)$ subject to constraints $x(t)^{T}Ax(t) > 1 $ where A is a positive definite matrix and $x(t) \in \mathbb{R}^2$ is some time ...
2
votes
0answers
25 views

Transformation into quadratic program

I am struggling with the following optimization problem: \begin{equation*} \begin{aligned} & \underset{x_{1}, \ ..., \ x_{5} \in \mathrm{R}}{\text{minimize}} & & \begin{pmatrix} x_{1} + ...
2
votes
0answers
46 views

Reformulate absolute value as quadratic problem

I'm looking for standard approach to reformulate this objective function. The aim is to find values of $x_i$ that are close to either $y_i$ or $-y_i$ ($y_i$s are known) in a least-squares sense: $...
2
votes
0answers
97 views

Relaxation of non-convex QCQP with one quadratic and one linear constraint

According to Boyd we know that a non-convex QCQP problem with one quadratic constraint has strong duality with the relaxed SDP or Lagrange counterpart. (check "Convex Optimization" by Boyd, Appendix B)...
2
votes
0answers
24 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
165 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} & \theta^...
2
votes
0answers
48 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
41 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
77 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} \...
2
votes
0answers
44 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
149 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)= \alpha^tK\...
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
178 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
38 views

Quadratic problem with two vectors linked by one quadratic constraint

I would like to find $$\min_{w,b} w_iA_{ij}w_{j} + b_iB_{ij}b_j + 2\alpha_iw_i + 2\beta_ib_i $$ Constrained to: $$ w_i > 0 $$ $$ \sum w_i = 1 $$ $$ b_i=w_i^2 $$ Where $A$ and $B$ are positive ...
1
vote
0answers
36 views

How to prove that this is a Quadratic Optimization Problem?

Show that the following problem is a Quadratic Optimization Problem. $$ \begin{array}{ll} \max & \sum\limits_{i=1}^n \left( \mu_i(z_i + x_i) - a_i \lvert x_i \rvert - b_i x_i^2 \right) \\ \text{s....
1
vote
0answers
77 views

Linear reformulation or approximation of a quadratic inequality set

Based on the useful comments I reformulated my problem - hopefully it's more clear now. Let $A,B \in \mathbb{R}^{d \times d}$ be symmetric positive-semidefinite matrices, $x \in \mathbb{R}^d$ and $||...
1
vote
0answers
36 views

Projection onto the positive subset of a hyperplane

I am wondering if there is a closed form solution for the projection of a point $x_0$ onto the subset of a hyperplane $Ax=b$ in the positive orthnat, that is $x\geq0$?
1
vote
0answers
70 views

Quadratic Programming “big M” method

How does the optimization problem $$\min_{x,\eta} \frac{1}{2} x^TGx+x^Tc+M\eta$$ $$ s.t. Ax+\eta-b \geq0$$ $$\eta\geq0$$ look in standard form? What would the KKT look like? The problem is, that I'...
1
vote
0answers
51 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?
1
vote
0answers
77 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
117 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: $\mathrm{...
1
vote
0answers
55 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 Q\...
1
vote
0answers
60 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
113 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
16 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
42 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
59 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
192 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
47 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
76 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
166 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}\} \\\ subject~to~&\mathbb{x}^Hx\...
1
vote
0answers
221 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
139 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
36 views

How to solve this quadratic matrix equation?

I have to solve the following equation where D is the unknown matrix: $$D^{T}D(DVD^{T}+I)^{-1}=A$$ I is the identity matrix, V and A are know constant matrices. Does anyone have any idea how to solve ...
0
votes
0answers
12 views

How to solve a LMI with inverse matrix and quadratic form

I have to solve the following LMI, where $\Sigma$ is a symmetric positive definite matrix. K,D and $\Sigma$ are unknown: $$\left[\begin{array}{cc} K\Sigma^{-1}K^{T}+DVD^{T}+I & KA^{T}\\ AK^{T} &...
0
votes
0answers
30 views

Minimizing trace with equality constraints

I would like to solve the following trace-minimization under equality constraints optimization problem: $$W^* =\arg\min \operatorname{Tr}[WCW^T] \text{ s.t. } A=B^TW^TWB$$ where $W,C\in\mathbb{R}^{...
0
votes
0answers
10 views

Lagrangian Relaxation of quadratically constrained quadratic program

I have the following problem: $$ \min_{w,\theta\ge0}\frac{1}{2}\|w-w_t\|^2+(\theta-\theta_t)^2 \text{ s.t. } w^\top(\hat n\hat z-nz)+\theta w^\top(z-\hat z)+1 \le 0,\theta-1\le 0 $$ Notice that $w$ is ...
0
votes
0answers
20 views

How to calculate a projection matrix for nonnegative constrained least squares?

Suppose we have a data vector $\boldsymbol{z}$ in R^{p} and a training data matrix $\boldsymbol{X}$ in $R^{p \times N}$, where N (N>p) is the number of samples in the training data matrix. If we'd ...
0
votes
0answers
16 views

Converting a sum over squared norms to Quadratic Programming problem

I'm trying to minimize the following function which is a function of a set of vectors $\vec{x}_i \in \mathbb{R}^2$, and is parametrized by the fixed parameters $\alpha, \beta,\gamma_i,\vec{u}_i$ where ...
0
votes
0answers
33 views

Residual norm of active set method in non negative least squares

I am having trouble with understanding one of the statements in active set methods done for non negative least squares given in Book written by Lawson. The quadratic problem can be written as \begin{...
0
votes
0answers
21 views

Quadratization of $5 x_1 x_2 − 7 x_1 x_2 x_3 x_4 + 2 x_1 x_2 x_3 x_5$ using Rosenberg's algorithm

In section 4.4 of Pseudo-Boolean Optimization by Boros et al., the authors have reproduced Rosenberg's quadratization algorithm as follows. Then they have given an example of implementing the ...
0
votes
0answers
10 views

Bipartite Matching with quadratic objective

I'm looking for the best way to formulate and solve the following bipartite matching problem: I have n nodes on the left hand side of the diagram, partitioned into ...
0
votes
0answers
13 views

Matrix inversion vs. iterative scheme in quadratic programming problem for high dimensions

According to this entry about quadratic programming problems with equality constraints the system will not be positive definite any longer for higher dimensions. For lower dimensions this system could ...
0
votes
0answers
21 views

Finding a suitable solver

I have a problem finding a solver that can solve a mathematical programming model with a quasi quadratic object function. I have tried some commercially available quadratic and non-linear solvers, but ...
0
votes
0answers
19 views

Binding inequality constraints in linear programming with quadratic constraints

I am trying to maximize the following objective function: $a_{1}b_{1}x_{1}+a_{2}b_{2}x_{2}+a_{3}b_{3}x_{3}+a_{4}b_{4}x_{4}$ The quadratic constraint is given by $b_{1}^2 x_{1}^2 + b_{2}^2 x_{2}^2 + ...