# Questions tagged [quadratic-programming]

A quadratic program (QP) is an optimization problem in which the objective function is quadratic and the feasible region is a convex polytope.

54 questions
Filter by
Sorted by
Tagged with
128 views

### Positive definite quadratic form algorithm

Let $f(x,y)= ax^2+bxy+cy^2$, or similarly denote it by $(a,b,c)$. This question is about the case $(1,0,p)$ where $p$ is prime. Suppose I have one solution $\bar{x}_1=(x_0,y_0)$ for $f(x,y)=m$ for ...
1 vote
165 views

### Does the value function of a quadratic program stay convex when adding constraints?

I am interested in the value function of a quadratic program of the form $$v(y)=\min_x \frac{1}{2} x^\top Q(y) x,$$ subject to a linear equality constraint $$E(y)x=d(y),$$ and a linear inequality ...
• 379
110 views

### Can we get the exact solution of large-scale quadratic programming problems (quadratic objective, linear inequality constraints) using KKT condition?

Crossposted at Computational Science SE Consider a quadratic programming problem with the following format: $$\text{min} Q(x) = c^Tx+\frac{1}{2}x^TDx \\$$ $$\text{s.t.} Ax\leq b, \\ x\geq 0$$ ...
114 views

### Sensitivity of the solution of QP with respect to parameters

Given a quadratic program, $$\begin{array}{ll} \text{minimize} & \displaystyle \frac12 x^TAx + b^Tx \\ \text{subject to} & Cx \le d \end{array}$$ Suppose $A \succ 0$, so the program strongly ...
• 33
1 vote
73 views

### On optimizing a multivariate quadratic function subject to certain conditions

The problem is to maximize $f(x_1,x_2,\cdots,x_n)=\sum\limits_{i=1}^{n}\Big(x_i-k_i\Big)^2$ for $n\ge 3$ subject to the conditions (1) $\sum\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}k_i\le n(n-1)$ ...
107 views

641 views

### Can this quadratic program be solved analyticaly?

I have a convex quadratic program wich is structured as follows : \begin{align*} \operatorname{argmin}_{p} &\hspace{0.5em} p' A p - 2 p' b \\ \mathrm{s.t.} &\hspace{0.5em} Ep=f \\ ...
• 653
141 views

### Necessary optimality condition for quadratic programming: a solution of a constrained QAP is a solution of a LP

I have a concern about a result given by Murty in [1] and also written by Floudas and Visweswaran in [2] They consider a QP: \begin{array}{ll}{\min _{x} Q(x)} & {=c^{T} x+\frac{1}{2} x^{T} D ...
1 vote
313 views

• 21
247 views

367 views

483 views

### Minimizing $x_1^2+x_2^2+x_3^2+x_1x_2+x_2x_3+x_3x_1$

Look at the expression $$f(x_1,x_2,x_3) = x_1^2+x_2^2+x_3^2+x_1x_2+x_2x_3+x_3x_1.$$ The numbers $x_1,x_2,x_3$ are non-negative, and I assume that $x_1+x_2+x_3=3$. This is a sum of squares and "...
• 2,189
152 views

### Optimization of quadratic form with band matrices

Let $A_1$ be the $N \times N$-matrix for which $a_{i,j} = 1$ for $i=j$ and 0 otherwise. Let $A_2$ be the matrix for which $a_{i,j}=1$ for $|i-j| \leq 1$ and 0 otherwise. Similarly define $A_3$ (which ...
• 2,189
171 views

• 11
1 vote
51 views

### Which algorithm is most efficient for a specific QP problem

I have a QP problem of the following kind: $\min_{\alpha\in\mathbb{R}^n}\frac{1}{2}\alpha^T M \alpha - p^T\alpha$ s.t. $l\leq \alpha \leq u$ The matrix $M$ is symmetric and positive definite and of ...
1 vote
143 views

103 views

Minimize $0<\omega_{dd}<2$ subject to $$\sum_{j=1}^{d}(\omega_{dj} - \omega_{ij})^{2} \geq 4, i=0,1,...,d-1,$$ where $-2<\omega_{ij}<2$ is known for $0 \leq i \leq d-1$ and $1 \leq j \leq ... • 1,353 1 vote 0 answers 129 views ### Optimization question: maximize quadratic objective with semidefinite constraints I recently encountered the following optimization problem:$\max \|AX\|_F^2$subject to:$X\succeq0$and$Xb_i\leq c_i$for a collection of$T$conditions:$i=1,\ldots,T$. Matrices$A$and$X$are ... • 123 1 vote 0 answers 87 views ### Frobenius nearest non-negative Gram matrix of balanced row-sums Let$W \in \mathbb{R}^{n \times n}$be any non-negative real symmetric matrix. For$k \leq n$, let$\mathcal{F} := \{X \in \mathbb{R}^{n \times k} \ | \ X \geq 0, X \mathbf{1} = \alpha \mathbf{1}, \...
I want to solve a generalized form of a quadratic programming problem $$\min_x \left(\sqrt{x^TPx}+\sqrt{x^TQx}\right)^2+c^Tx$$, $$\textrm{ s.t. } Ax\le b.$$ Here, $P$ and $Q$ are both positive ...