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

49 questions
Filter by
Sorted by
Tagged with
24 views

### Quadratic optimization under Frobenius norm constraint

Let $A,B \in \mathbb{R}^{p \times p}$ be positive semi-definite. I have troubles on the following optimization problem: \begin{equation} \max_{\|X\|^{2}_F=1} \text{tr}(X^{T}AXB) \end{equation} It ...
20 views

### Binary optimisation to maximise covariance or L2-error, is it even possible? Could it be solved by relaxation?

I have a matrix A and a vector y, given A invertible the solution to find x is simple, however if we restrict x to be a binary vector i.e. $$x_{i} \in \{0,1\} \quad \forall i$$ then we are not ...
40 views

189 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 \\ ...
105 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  and also written by Floudas and Visweswaran in  They consider a QP: \begin{array}{ll}{\min _{x} Q(x)} & {=c^{T} x+\frac{1}{2} x^{T} D ...
44 views

159 views

### Least squares problem with constrained solution [closed]

If $a_{m\times 1}$ and $Q_{m\times n}$ ($m<n$) are known, and we know every element of $b$ is between $[-1\ \ 1]$, how to determine $b$ to minimize $\|a+Qb\|_2$?
692 views

### Quadratic Programming With Piecewise Linear Term

The problem I have can be defined as: $$\min \frac{1}{2}\mathbf{x}^T\mathbf{Q}\mathbf{x} + \mathbf{c}^T\mathbf{x}$$ s.t. linear equality constraints: $$\mathbf{Ax=b}$$ and linear inequality ...
153 views

148 views

118 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 ...
74 views

451 views

### Solution of a linearly constrained quadratic programming problem [closed]

What is the solution of the following optimization problem: \begin{align} &\min{\mathbf{p}^\mathrm{T} \mathbf{B} \mathbf{p}}\\ &\text{subject to}: \mathbf{0}\leq{\mathbf{p}}\leq \mathbf{1}. \...
114 views

260 views

### Efficiently factorize a KKT system with block diagonal upper corner

I have a system resulting from a quadratic energy minimization with linear equality constraints enforced with Lagrange multipliers which has the form: \begin{equation} A = \left[\begin{array}{c|c} \...
194 views

### combinatorial and linear duality

Let $S$ be a finite set, and let $W$ be a nonempty set of subsets of $S$; we will identify every subset of $S$ with its characteristic function, a 0-1 vector in $\mathbb R^S$. The combinatorial dual \$\...