All Questions
Tagged with convex-optimization quadratic-programming
18 questions
2
votes
1
answer
307
views
Positivity of quadratic form minus linear form on the simplex
Let $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, \...
CommunityBot
- 1
1
vote
1
answer
209
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 ...
- 61.9k
3
votes
1
answer
189
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 ...
- 434
2
votes
0
answers
178
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
$$
...
2
votes
0
answers
159
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 ...
- 21
2
votes
1
answer
59
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 \...
- 123
0
votes
1
answer
274
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 ...
- 4,713
1
vote
0
answers
99
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 $...
- 1,826
2
votes
1
answer
255
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
291
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^* ...
- 153
4
votes
1
answer
456
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) \...
- 188k
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?
- 13.9k
2
votes
0
answers
156
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
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 ...
- 101
1
vote
0
answers
52
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 ...
- 11
2
votes
0
answers
149
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 ...
- 21
4
votes
0
answers
165
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{...
- 171
1
vote
1
answer
928
views
Block Covariance Matrix - Positive Definite? (Quadratic Optimization) [closed]
I have a covariance matrix C. I have then formulated an quadratic optimization problem that involves the following matrix in the quadratic form:
[ C C ]
[ C C ]
However, the quadratic solver ...
- 10.7k