15
votes
Accepted
Minimizing $x_1^2+x_2^2+x_3^2+x_1x_2+x_2x_3+x_3x_1$
The question is about the signature of a quadratic form
$$
\sum_{i=1}^n x_i^2 + \frac12\sum_{1 \le \mathrm{dist}(i,j) \le p} x_ix_j
$$
(or about the spectrum of the corresponding linear operator). The ...
- 6,337
8
votes
Accepted
Symmetric linear least-squares solution
I assume that $A$ is onto, so that $H:=A^TA$ is positive definite. Minimizing $\|AX-Y\|_F^2$ in Frobenius norm (the least square) among symmetric matrices $X$ yields the optimality condition that
$$\...
- 52.3k
7
votes
Accepted
Does the Perron vector maximize $x^TAx$ in the simplex?
No. The Perron vector is in general very far from optimizing the quantity you're looking at.
Here is an example:
Let $A$ be the $n\times n$ tridiagonal matrix with $\frac 13$ on the diagonal and the ...
- 23.2k
4
votes
Accepted
Convex Decomposition of matrix
I guess, uniqueness depends on the rank of $X$.
I would also suggest to look at the reformulate with vectorization as
$$\newcommand{\vec}{\operatorname{vec}}
\|X-XC\|_F^2 = \|\vec(X) - (I\otimes X)\...
- 12.7k
4
votes
Least square solution to $AXB+CXD=E$
This is the Sylvester equation. A simple explicit solution is possible under certain conditions (no common eigenvalues of the matrices $C^{-1}A$ and $-DB^{-1}$), as explained in the Wikipedia page. ...
- 188k
4
votes
Accepted
Does the value function of a quadratic program stay convex when adding constraints?
Not necessarily as written in the generality you want. Suppose that we are in $\mathbb R^1$, there is no linear constraint, and $Q(y)$ is some positive function of $y$. Then $v(y)\equiv 0$, which is ...
- 61.9k
3
votes
Accepted
Sensitivity of the solution of QP with respect to parameters
$\newcommand\R{\mathbb R}\newcommand\tz{\tilde z}\newcommand{\de}{\delta}$Yes, the minimizer $x_{A,b}$ of $\frac12 x^TAx + b^Tx$ subject to $Cx\le d$ is
continuous with respect to $A$ and $b$ -- ...
- 128k
2
votes
Clarification on FPTAS optimization in a paper
Unfortunately, no. The form we use is very restrictive. The key is that the function $f(x)$ can be decomposed in a sign compatible way as
$f(x) = g(x) h(x)$, where $g(x)$ is convex (or concave) and ...
1
vote
Accepted
Convexity of a positive definite objective with min(x,y)-nonlinearity
$f(x)$ is not convex. Here is a counterexample to its convexity in MATLAB notation.
C = [2 1;1 2]
x1 = [1 2]'
x2 = [2 1]'
x3 = 0.5*(x1 + x2)
Then
...
- 1,517
1
vote
A quadratic program with non-negativity constraints
Is the problem well-defined in case $B$ has a negative eigenvalue?
Consider an unit eigenvector $v$ corresponding to a negative eigenvalue $\lambda$ of $B$. Since any vector $v$ can be written as ...
- 1,216
1
vote
Correlation between the first and a random position of an ergodic bit sequence
Edit: Please note that this answer does not solve the problem. It only shows that the attempt to reduce the problem to a geometric problem fails.
I think a have a counterexample to the geometric ...
- 947
1
vote
Accepted
Efficient algorithm for solving a convex quadratic program
Using an SVD $A=USV^T$, and setting $y=U^Tx$, $c=U^Tb$, you can reduce the problem to a diagonal one $$\min_{y\in\mathbb{R}^n} c^Ty + \frac12 y^T S^2 y = \min_{y\in\mathbb{R}^n} \sum_{i=1}^n c_i y_i + ...
- 20.2k
1
vote
Maximizing quadratic form subject to inequality constraints
This can be formulated and solved as a Quadratic Programming (QP) problem, by minimizing -trace($X^TSX)$ subject to the element-wise bounds $0 \le X \le 1$. If the objective is not convex, then a ...
- 1,517
1
vote
Accepted
Norm of solution of quadratic program
We can show more, namely that if $K$ is a closed convex set (such as $\ker A$) containing the origin and
\begin{align*}
x_c^* &= \operatorname*{argmin}_x \,\frac{1}{2}x^\mathsf{T} P x - q^\mathsf{...
- 153
1
vote
Is this result on an unconstrained inverse quadratic programming problem new or known already?
The problem you solve does not have anything to do with minimizing a quadratic function with linear constraints. You can see this as $Ax\leq b$ plays no role in your analysis. Your problem is a ...
- 1,638
Only top scored, non community-wiki answers of a minimum length are eligible