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

2
votes
2answers
41 views

Maximizing a convex quadratic function in CVX and Matlab

I understand that a convex function can not be maximized as there is no such value. However, consider the following function: $$\begin{array}{ll} \text{maximize} & 3x^2 + 5y^2\\ \text{subject to} ...
3
votes
1answer
48 views

How to solve the following quadratic matrix equation?

Solve the following matrix equation in $D$ $$ A=D^{T}(DVD^{T}+\alpha\lambda_{\max}(D^{T}D)I)^{-1}D$$ where $I$ is the identity matrix, $A$ and $V$ are known matrices, $\alpha$ is a known ...
2
votes
0answers
41 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 ...
4
votes
1answer
111 views

Find closest point, subject to linear inequality constraints

Given a point $p\in \mathcal{R}^2$, I want to compute the closest point $x \in \mathcal{R}^2$, subject to linear inequality constraints $Ax \leq b$. That is, $$\begin{array}{ll} \text{minimize} & ...
1
vote
1answer
39 views

Prioritized solution of a linear system subject to inequality constraints

Consider the following linear system \begin{equation} y = A_1 x_1 + A_2 x_2 \end{equation} subject to the linear constrains \begin{equation} C_1 x_1 + C_2 x_2 \leq d \end{equation} I am looking ...
1
vote
1answer
150 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 \mathbb{R}_+^n,Q\in\...
6
votes
1answer
644 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 ...
5
votes
0answers
90 views

Quadratic optimisation with quadratic equality constraints

I would like to solve the following optimisation problem: $$\text{minimize} \quad x'Ax \qquad \qquad \text{subject to} \quad x'Bx = x'Cx = 1$$ Where $A$ is symmetric and $B$ and $C$ are diagonal. ...
2
votes
1answer
128 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
0answers
49 views

Quadratic optimization problem with quadratic equality constraint

I am trying to solve the following optimization problem: $$ \min_{x \in \mathbf{R}^2} \, x^T A x + b^Tx \quad \text{subject to $x^T J x = 1$} $$ where $A$ is a positive semi-definite $2 \times 2$ ...
1
vote
0answers
19 views

Different ways of solving $\underset{\mathbf{s}}{\text{min}}\;\|F\mathbf{s}-\mathbf{x}\|_{l_2}^2 + \|W\mathbf{s}\|_{l_2}^2$ least square problem?

The problem that I am going to describe arises from compressed sensing technique and after using weighted least squares it can be transformed into the following least squares problem: $$\underset{\...
1
vote
1answer
189 views

Step-by-step example of solving a quadratic program with linear inequality constraints

I'm doing an exercise work about Support Vector Machines which involves solving a quadratic program of the form $$\begin{aligned} & \underset{\boldsymbol\alpha \in \mathbb{R}^N}{\text{minimize:}} ...
0
votes
1answer
44 views

Optimize wrt a partial matrix?

I have a common optimization problem $$\arg\min_A \text{tr}( A^TWA),$$ where $W$ is a positive semi-definite matrix, and $A$ is the matrix to be optimized. If $A$ is completely unknown, with some ...
1
vote
1answer
26 views

Reducing KKT system

I was using CVXOPT library to solve one of my quadratic programming problem. I found that, CVXOPT library solves KKT system efficiently by reducing a 3x3 matrox into 2x2 blocks which has the following ...
0
votes
0answers
8 views

Why is the duality gap zero for non convex quadratic programming with a single constraint?

From what I read here Convex Optimization, Appendix B and Perfect Duality §2.3, strong duality holds for quadratic programs of the form: $$ \min_x x^\top Ax+x^\top a+\alpha \ni x^\top Bx+x^\top b+\...
6
votes
3answers
85 views

Is a sinc-distance matrix positive semidefinite?

I've been trying to crack this problem for days but I can't find a way around it. Given a set of unique N points $X = {x_1,..x,N}, x_i \in R^3$, the associated sinc-distance matrix $S \in R^{n\times n}...
1
vote
1answer
62 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
16 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
36 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
67 views

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

I am using a black-box solver to solve the following non-convex 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
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 ...
2
votes
0answers
108 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)...
1
vote
2answers
50 views

Optimizing a problem using Lagrange multipliers

$\newcommand{\norm}[1]{\|#1\|}$ I have the following problem: $$ \min_{w,\theta}\frac{1}{2}\norm{w-w_t}^2+\frac{1}{2}(\theta-\theta_t)^2 \text{ s.t. } w^\top(z(n-\theta)-\hat z(\hat n - \theta)) \ge 1 ...
1
vote
0answers
43 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
2answers
481 views

Using Lagrange multipliers to find the shortest distance between two straight lines

A problem asks me to use the method of Lagrange multipliers to find the shortest distance between the straight lines $x=y = z$ and $x = -y, z=2$ (It also warns me that using this method is a bit ...
2
votes
1answer
38 views

Minimizing the Frobenius norm with linear inequality constraints

How to solve the following system for $\mathbf{C}$ and $\mathbf{a}$: $\min\|\mathbf{X-XC} \,\mbox{diag} (\mathbf{a})\|_F^2$ subject to $\mathbf{c}_{ik}\geq 0$, $1^T \mathbf{c}_k = 1$ and $1-\delta\...
1
vote
2answers
55 views

Given a set of vectors and a target vector, find the set of scaling factors that minimizes distance of sum of those vectors from target

I have a set of $n$ starting vectors $\vec i_n$ and a target vector $\vec t$. I have a set of scaling factors $a_n$ for which I can compute the sum $\vec s$: $$ \vec s = \sum_{i=1}^n {a_i \vec i_i} $$...
2
votes
2answers
67 views

How do I solve the following equality-constrained quadratic program?

I am trying to minimize: $$(x_1-k_1)^2 + (x_2-k_2)^2 + (x_3-k_3)^2 +\ldots+ (x_n-k_n)^2$$ subject to following equality: $$B = 1 + x_1 + x_2 + x_3 + x_4+\ldots+x_n.$$ Is there a closed form ...
0
votes
0answers
22 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
2answers
19 views

QP with simplex constraints. [closed]

I want to solve something: $\Vert \mathbf{x-Da}\Vert_2^2$ s.t. $\sum \mathbf{a}_i=1$ and $\mathbf{a}_i\geq 0$. How to convert such problems into equivelent Quadratic program so that I can use Matlab'...
0
votes
0answers
17 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
1answer
17 views

Geometric interpretation of support vector values in primal space

The Linear Support Vector Machine classification ($y_{k} = -1\ \mathrm{or}\ +1$) with misclassification tolerance loss function in primal weight space looks like this: $$\min\limits_{w,b,\xi} J_{P}(w,...
0
votes
1answer
12 views

SVM / QP result for impossible to satisfy conditions

The theory behind Linear Support Vector Machines with tolerance of misclassifications states that we are trying to minimise in the primal weight space the following function: $$\min\limits_{w,b,\xi} ...
2
votes
1answer
33 views

Solving a quadratic convex optimization problem

There's this convex optimization problem which I got stuck after writing the Lagrange equation. I simply couldn't find a way to eliminate the Lagrange multiplier. $$\begin{array}{ll} \text{minimize} &...
1
vote
1answer
15 views

Tree-width of a quadratic pseudo-Boolean function

A pseudo-Boolean function $f : \mathbb{B}^n \mapsto \mathbb{R}$ is of the following form. $$ f \left(x_1, \ldots, x_n\right) = \sum_{S\subseteq V} c_S \prod_{j \in S} x_j $$ Here $c_S \in \mathbb{R}$,...
0
votes
0answers
34 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
22 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
1answer
46 views

Convex optimization: Piece-wise, quadratic objective

This question is about convex optimization with a convex objective function, which is defined piecewise. We have two functions, a concave function A(x) and a strictly convex, increasing function B(x), ...
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 ...
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, ...
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
20 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 + ...
0
votes
1answer
68 views

A light solution of a quadratic programming problem

I have a simple and light quadratic programming problem that I need to solve, as following: \begin{align} & \underset{x}{\arg\min} & & \dfrac{1}{2}x^T x-z^T x\\ & \text{subject ...
2
votes
0answers
29 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 ...
1
vote
2answers
4k views

Using Matlab quadprog to solve markowitz model

I have the markowitz model shown below and I need to use the quadprog function to solve it (i.e get the values for w_i values). However I am a bit new to mat lab and not sure which definition of ...
0
votes
1answer
20 views

Why in quadratic programming is particularly simple when there are only equality constraints; specifically, the problem is linear

I found in wikipedia that... Quadratic programming is particularly simple when there are only equality constraints; specifically, the problem is linear font: Quadratic Programming What I can'...
0
votes
1answer
22 views

General form to standard form regarding ellipse?

I've tried 2 hours to do this so I hope someone can help me: $$11400000=-0.64x^2+2560x-y^2+6000y$$ It says that it have to equal an ellipse with center at the point $(2000,3000)$ and a horizontal ...
1
vote
1answer
30 views

Quadratic programing problem and MATLAB

I have a little problem with quadratic programing problem: ${\bf v}^T \Sigma {\bf v} \rightarrow min $, and constrains are $ {\bf v}^T \mu = \mu_*, {\bf v}^T {\bf 1 }= 1, 0 \leq {\bf v}. $ Where ...
0
votes
0answers
26 views

Nonlinear Optimization

I have a nonlinear optimization problem, but constraints are ODE. Cost function is $J= x1+x1*x2+x1^2$ while constraints are, $\underline{x_i} < x < \bar{x_i}$ (for i=1,2,3) ; $\frac{dx3}{dt}=...