# 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

0
votes

0
answers

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

1
answer

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 ...

2
votes

0
answers

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
$$
...

3
votes

1
answer

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 ...

1
vote

0
answers

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)$ ...

0
votes

0
answers

107
views

### A property of quadratic optimization solution map

Define for a given $\mathbf{b}$ the quadratic optimization solution map by
$$
\mathcal{S} \ \colon \ U \mapsto \mathbf{x} \ \colon \ \mathbf{x}^\top \, U^{-1} \, \mathbf{x} = \min_{\mathbf{y} \geq \...

1
vote

0
answers

113
views

### Can I solve this quadratic program "fast"?

We are given a matrix $D \in \mathbb{Z}^{C \times C}$ of non-negative entries, an integer $k \geq 1$ and we need to maximize the quadratic form $x^T D x$ under some simple constraints. For all ...

1
vote

0
answers

117
views

### Drawing a 3D object in a 3D environment, and converting to math [closed]

So I have been granted a free time and I want to work on a project but first I had to research.
As we know, lines have infinite points, and with lines, we can create infinite shapes. I want to let ...

2
votes

0
answers

116
views

### Complexity of Quadratic Programming where the symmetric matrix Q is positive semidefinite only in the feasible directions

playing around with stuff for my dissertation, I derived a quadratic problem in the general form
\begin{equation}
\begin{aligned}
\min_{x} \quad & x^TQx + c^Tx \\
\textrm{s.t.} \quad & Ax \leq ...

2
votes

1
answer

56
views

### Convexity of a positive definite objective with min(x,y)-nonlinearity

I have derived an optimization objective of the form
$$
f(x) = \sum_{i,j} C_{ij}\min(x_i, x_j), s.t. g(x) \geq 0
$$
where $C \in \mathcal{R}^{N \times N}$ is a positive definite matrix, and $x \in \...

1
vote

0
answers

56
views

### (Iterative?) Solutions to a certain quadratic program with non-convex constraints

Let $y\in\mathbb{R}^m$, $\tau\in\mathbb{R}$ and $X\in\mathbb{R}^{m\times n}$, with $\tau>0$
I would like to efficiently solve the following problem:
Problem 1
Choose $\alpha,z\in\mathbb{R}^m,\beta\...

2
votes

1
answer

244
views

### Positivity of quadratic form minus linear form on the simplex

Let us $a_{ij}$ be the elements of a $n$-dimensional covariance matrix. Can we prove the following?
$$ 1-\sum_{k=1}^n a_{ik} \lambda_k + \sum_{j=1}^n \sum_{k=1}^n \lambda_j a_{jk} \lambda_k > 0, \...

2
votes

0
answers

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 \\
...

3
votes

0
answers

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

1
answer

313
views

### A quadratic program with non-negativity constraints

Is there any closed form solution for the optimal value of the folowing optimization problem?
$$\begin{array}{ll} \text{minimize} & (\mathbf{x} - \mathbf{y})^{\mathrm{T}}\mathbf{B}(\mathbf{x} - \...

2
votes

1
answer

458
views

### Does the Perron vector maximize $x^TAx$ in the simplex?

Let $\mathbf{A}$ be any $n\times n$ symmetric positive matrix ($A_{ij}>0$). It is easy to show that the solution to the following optimization problem
\begin{align}
\max_{\mathbf{x}}~~\mathbf{x^...

5
votes

2
answers

840
views

### Symmetric linear least-squares solution

Given tall matrices $A$ and $Y$ and the following overdetermined linear system in square matrix $X$
$$AX=Y$$
is there an explicit formula for the least-squares solution if $X$ is constrained to be ...

0
votes

1
answer

242
views

### KKT conditions for min-cost flow QP [closed]

I'm working on a convex quadratic separable min-cost flow problem with the following structure:
$P = \{\min \frac{1}{2}x^tQx + qx : Ex = b, 0 \leq x \leq u\}$
But I'm stuck on deriving the KKT ...

1
vote

0
answers

119
views

### Mixed integer formulation of union of polytopes?

Given $t$ different unbounded polyhedra $P_1:A^{(1)}x^{(1)}\leq b^{(1)},\dots,P_t:A^{(t)}x^{(t)}\leq b^{(t)}$ we are looking for the representation of $\bigcup_{i=1}^tP_i$ (not their convex hull) with ...

1
vote

0
answers

98
views

### Finding a point on a convex set

Given a compact bounded convex set $\mathcal C\subseteq\mathbb R^n$ given by $t$ hyperplane inequalities I want to find a point $u\in\mathcal C$ such that for all $v\in\mathcal C$
a convex relation $...

0
votes

0
answers

122
views

### Does positivstellensatz and SOS proof system help here?

I have a system of $m$ homogeneous degree $2$ polynomial equations in $\mathbb Z[x_1,\dots,x_n]$ where $m=poly(n)$. Take
$$f_1(x_1,\dots,x_n)=0$$
$$\dots$$
$$f_m(x_1,\dots,x_n)=0$$
to be the system.
...

1
vote

0
answers

48
views

### How Sequential Quadratic Programming versus Quadratic programming and Iterative QP are related? [closed]

What is the difference between Sequential Quadratic Programming (SQP) versus Quadratic Programming (QP)? Is it the same as Iterative Quadratic Programming (IQP)? For example, BFGS, DFP are types of QP/...

2
votes

1
answer

332
views

### A "nice" (but non-definite) quadratic programme

For integers $n\geq k>0$, let $f$ be the following quadratic form:
$$f(x_1,\ldots,x_n)=\sum_{i=1}^n\sum_{j=0}^{k-1}x_ix_{i+j\bmod n}.$$
Is it true that the minimum of $f$ over the unit simplex is ...

2
votes

2
answers

110
views

### Correlation between the first and a random position of an ergodic bit sequence

Edit: Since the geometric approach did not work, I try now another approach: phrasing the problem as a quadratic programme.
Probabilistic version.
Let $x=(x_1,x_2, \ldots) $ be an ergodic random ...

2
votes

1
answer

67
views

### Clarification on FPTAS optimization in a paper

In the abstract of this paper by Hildebrand, Weismantel & Zemmer it is stated that they provide an FPTAS for $$\min x'Qx$$ over a fixed dimension polyhedron when $Q$ has at most one negative or ...

2
votes

1
answer

204
views

### Efficient algorithm for solving a convex quadratic program [duplicate]

Let $A \in \mathbb{R}^{n \times m}$ and $b \in \mathbb{R}^n$. Suppose $m \ll n$. How to solve this quadratic program efficiently?
$$\min_{x \in \mathbb{R}^n} \frac{1}{2} x^\top AA^\top x + b^\top x$$

1
vote

1
answer

459
views

### Maximizing quadratic form subject to inequality constraints [closed]

Given a $n \times n$ symmetric matrix $\rm S$, solve the optimization problem in $n \times k$ (where $n \geq k$) matrix $\rm X$
$$\begin{array}{ll} \text{maximize} & \mbox{tr} \left( \mathrm X^\...

3
votes

0
answers

247
views

### Solve Huber's M-Estimation using quadratic programming

The Huber's M-estimate is to solve the problem
$$\underset{\mathbf x}{\rm{minimize}} \rho(\mathbf b-\mathbf A\mathbf x) + \alpha|\mathbf x|$$
where
$$ \rho(t) = \left\{\begin{array}{c}\frac{t^2}{2\...

1
vote

1
answer

278
views

### Norm of solution of quadratic program

In a quadratic program (QP), do linear equality constraints always reduce the norm of the minimizer? Specifically, let $P \succ 0$, $A \in \mathsf{M}_{m\times n}$ and $q\in\mathbb{R}^n$. Define
$$x^* ...

4
votes

1
answer

367
views

### Least square solution to $AXB+CXD=E$

I am trying to find the least-squares solution $X$ of the following matrix equation
$$AXB+CXD=E$$
Of course, I know that this equation can be written in the form
$$(B^T \otimes A+D^T \otimes C) \...

3
votes

0
answers

99
views

### Are there scenarios under which feasibility bilinear programming is easy?

Given $c\in\Bbb R^{n_1},d\in\Bbb R^{n_2}$, $E\in\Bbb R^{n_1\times n_2}$, $A\in\Bbb R^{m_1\times n_1}$, $B\in\Bbb R^{m_2\times n_2}$ $a\in\Bbb R^{m_1}$, $b\in\Bbb R^{m_2}$ and $t\in\Bbb R$ we know ...

1
vote

0
answers

88
views

### On convex quadratic programming clarification

We know convex quadratic programming is in $P$.
Is it also in $P$ if the function of interest is only convex in the domain of interest?

3
votes

1
answer

542
views

### Is this result on an unconstrained inverse quadratic programming problem new or known already?

Is this problem and solution actually new, or has someone done this earlier?
The details can be found in the preprint: arxiv:1701.01477.
Let us consider a direct quadratic programming problem:
$$
\...

5
votes

2
answers

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
votes

0
answers

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 ...

3
votes

1
answer

171
views

### Convex Decomposition of matrix

For a matrix $\mathbf{X} \in \mathbb{R}^{n\times l}$, we have the following problem of representing vectors in $\mathbf{X}$ as a convex combination of other vectors excluding the vector itself:
$\min\...

1
vote

1
answer

197
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$?

2
votes

3
answers

1k
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 ...

1
vote

1
answer

166
views

### Quadratically constrained quadratic programming/optimization involving piece-wise function

I have a quadratically constrained quadratic programming/optimization problem involving kind-of piece-wise quadratic functions $f_n (x_m)=a_{n,m} (x_m-\theta_n)^2$, if $|x_m-\theta_n|<c$; $c^2a_{n....

1
vote

0
answers

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

0
answers

143
views

### Hessian matrix positive definiteness (concavity test) [closed]

I have a rather simple scenario based optimization problem:
Maximize
$$
Q_1{_s}(A_1{_s}-Q_1{_s}-bQ_2{_s})+ Q_2{_s}(A_2{_s}-Q_2{_s}-bQ_1{_s})-[(Q_1{_s}-K_1)^+ + (Q_2{_s}-K_2)^+]c
$$
subject to $Q_1{...

2
votes

1
answer

153
views

### A graph assignment problem

Consider bipartite graph with vertex set $V_1\cup V_2$ where $|V_1|=\frac{n(n-1)}2$ and $|V_2|=n$. The vertices in $V_1$ all have degree $2$ and connected to two vertices in $V_2$. The vertices in $...

2
votes

0
answers

103
views

### A (non-convex) minimization quadratic programming problem with d constraints

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
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 ...

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}, \...

2
votes

0
answers

147
views

### How to solve the following generalized quadratic programming problem [closed]

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 ...

4
votes

0
answers

164
views

### Two quadratic programming problems always same answer? [closed]

Was exploring quadratic programming optimization and for two types of problems the answers seemed to always equal.
Problem 1:
Minimize $\tfrac{1}{2} \mathbf{x}^T Q\mathbf{x}$
Subject to $ A \mathbf{...

4
votes

0
answers

511
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}.
\...

0
votes

2
answers

118
views

### Inner Product of Given 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 A,\,\sup\...

3
votes

1
answer

728
views

### General method for under and over determined systems?

Suppose I have a system:
$$
Ax = b
$$
where $A$ is a $m$ by $n$ matrix which is less than full rank (neither full column nor row rank). In my particular case $m<n$.
I'd like a combination of a ...