All Questions
Tagged with linear-algebra convex-optimization
121 questions
2
votes
1
answer
585
views
A problem about convex optimization and trace of symmetric matrix
Please prove or disprove that, for symmetric matrix $A=A^T$, we have
$$\max_{x \in \{\pm 1\}^n} x^T A x \geq \mbox{Tr}(A)$$
- 21
2
votes
1
answer
135
views
Is first term of my cost function convex?
I have an optimization problem in the form of
[\begin{array}{l}
\mathop {{\rm{Minimize}}}\limits_{\bf{X}} \,\,\,2\left| \delta \right|\sqrt {{\rm{Tr}}\left( {{\bf{A}}{{\bf{X}}^2}} \right)} {\rm{ - ...
- 33
2
votes
1
answer
1k
views
Subgradient of Minimum Eigenvalue
Consider three $N \times N$ Hermitian matrices $A_0$, $A_1$, $A_2$. Consider the function
\begin{align}
f(t_1,t_2)=\lambda_{\text{min}}(A_0+t_1A_1+t_2A_2)
\end{align}
where $\lambda_{\text{min}}$ ...
- 1,421
2
votes
1
answer
170
views
Equivalence of minimizing trace and determinant over matrix quadratic form in multivariate regression
Consider the multivariate regression model
$$Y = XB + E$$
where $Y$ is $n \times p$ and corresponds to the dependent variables, $X$ is $n \times k$ and corresponds to the independent variables, $B$ is ...
2
votes
2
answers
276
views
Is this parametrized semidefinite program convex?
I am considering an optimization problem of the form:
\begin{equation}
\begin{split}
f(s) &= \min_{X} \mathrm{tr}(C(s)X) \\
&\;\;\;\;\;\;\;\;\;\;\; X \ge 0, \\
&\;\;\;\;\;\;\;\;\;\;\; \...
- 101
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$$
- 422
2
votes
0
answers
119
views
Seeking insights on bounded set positive solutions for a set of linear systems in $\mathbb{R}^n$
Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (...
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
$$
...
- 21
2
votes
1
answer
506
views
Effect of duplicated row on singular values and vectors
Let $\mathbf{A}$ be a $n\times n$ matrix with Singular Value Decomposition (SVD) $\mathbf{A}=\mathbf{U}\mathbf{S}\mathbf{V}$ and $\mathbf{a}_1$ be the first row of $\mathbf{A}$. What can we say about ...
- 287
2
votes
0
answers
618
views
block diagonal approximation of (SPD) matrix
I am interested in approximating a symmetric matrix in a block diagonal form, i.e. compute just some entries of the matrix located in blocks around the diagonal. Are there any theoretical guarantees ...
- 335
2
votes
0
answers
46
views
Notion of distance between linear programs
Consider the linear programming problem
\begin{align}
\max_{x}&~c^Tx \\~s.t.~~a^Tx &\leq B~,~0\leq x_i \le1
\end{align}
where $c$ and $a$ are $n \times 1$ given non-negative vectors. $B$ is a ...
- 1,421
2
votes
0
answers
298
views
Is the following map a diffeomorphism?
Context:
I'm working on a convergence theorem for an accelerated version of an iterative optimisation algorithm. At regularly-spaced intervals during the algorithm, a number of previous (...
- 21
2
votes
0
answers
210
views
projection of a matrix to the the space such that the diagonal elements are the greatest
Suppose there is a symmetric matrix $A$ in $\mathcal{S}^n$. I would like to compute the nearest symmetric matrix $X \in \mathcal{S}^n$ such that $X_{ij} \le X_{ii}$, $i ,j \in \{1,...,n \}$. In other ...
- 263
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,207
2
votes
0
answers
299
views
Practical application of envelope theorem for linear programs
Assume that we have solved a (standard) linear program
$$
\text{minimize}_{x\in {\mathbb R^n}}\,\, c_0^Tx, \,\,\,\,\, \text{s.t. } A_0x \leq b_0,
$$
and would like to know how sensitive is the optimal ...
- 7,182
2
votes
0
answers
199
views
Constrained absolute orientation of 3D point sets
Let us assume we have two 3D point sets, $P=\{p_i\}$ and $Q=\{q_i\}$, and that we need to recover the transformation that takes $P$ as close to $Q$ as possible. In particular, I am interested in roto-...
- 121
2
votes
0
answers
210
views
Finding optimal linear transformation for intersection of convex polytopes
I previously posted this on MathSE and am now trying here.
I have the following situation, as shown in the following diagram:
$W=\{w_i\}_{i=1..|W|}$ is a set of vertices (show in diagram in blue) ...
- 695
1
vote
1
answer
877
views
Minimization problem involving the inverse of an affine matrix function
I want to minimize $v^T (A+I+UQU^*)^{-1} v$, subject to $Q$ and $A$ being positive semi-definite and ${\rm trace}(Q)<1$. Here, $v$ is a given vector with unit norm, that is, $\|v\|_2=1$.
- 377
1
vote
2
answers
229
views
Feasibility of a given set of homogenuous nonconvex quadratic inequality constraints
Let $C_1$,$C_2$,...$C_N$ be $M \times M$ indefinite hermitian matrices. What can we say about the following quadratic constriants
\begin{align}
w^{H}C_1w>0 \\\
w^{H}C_2w>0 \\\
...~~~~~~~~~~ \\\
....
- 1,421
1
vote
1
answer
156
views
Matrix reconstruction puzzle
Say a reconstruction of matrix $A$ is $A'$ and it's defined as
$$
A' = PDP^TA
$$
where $P$ is an orthogonal matrix, $D$ is a diagonal binary (1 or 0) matrix. In a trivial case, when all diagonal ...
- 433
1
vote
1
answer
113
views
Expected rank - computable approximations
I'm interested in finding the expected rank of some random matrix $A$ (I don't want to specify its distribution right now, since my question makes sense in general).
Computing $\mathbb{E} \ \mathrm{...
- 3,323
1
vote
1
answer
234
views
Log Fractional optimization problem
Let $\mathbf{x}$ be a vector of $N$ variables. Then, how can I solve the following optimization problem?
\begin{align}
\max_\mathbf{x}&\quad \sum_{n} \log(1+\frac{x_n}{\alpha+\sum_{m}\beta_m^{(n)}...
- 287
1
vote
1
answer
336
views
A close-form solution for a simple quadratic optimization problem
Is there any closed form solution for the following optimization problem:
\begin{align}
&\min_{\mathbf{X},\alpha} \mathrm{Tr}[(\mathbf{A}-\mathbf{B}\mathbf{X})(\mathbf{A}-\mathbf{B}\mathbf{X})^{\...
- 287
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
1
vote
1
answer
169
views
On optimizing a function whose projection and projected vector go through a linear transformation
Assume the two sets of vectors $\{\mathbf{a}_1,\ldots,\mathbf{a}_N\}$ and $\{\mathbf{b}_1,\ldots,\mathbf{b}_N\}$ of equal length. My goal is to find the optimum matrix $\mathbf{C}$ to the following ...
- 345
1
vote
2
answers
151
views
Sensitivity analysis in minimum norm problems under a linear constraint
Suppose $\Delta$ is some nice topological space, say compact, and Hausdorff.
Let $A:\Delta \rightarrow \mathbb{R}^{m\times n}$ be a continuous $m\times n$ matrix valued map. Let $b\in \mathbb{R}^{m}$ ...
- 11
1
vote
1
answer
514
views
Semidefinite relaxation for a quadratic feasibility problem using CVX
The following decides the feasibility of a semidefinite program (SDP)
\begin{align}
\max_{\mathbf{Z}}~0 \\\
\mathrm{trace}(\mathbf{Z})\leq \rho \\\
\mathrm{trace}(\mathbf{S}_1\mathbf{Z}) \geq \alpha \...
- 1,421
1
vote
1
answer
141
views
Numerical optimisation for multivariate Gaussians
Hi,
I want to calculate
$
f_{\mathbf x}(x_1,\ldots,x_k)\, =
\frac{1}{(2\pi)^{k/2}|\boldsymbol\Sigma|^{1/2}}
\exp\left(-\frac{1}{2}({\mathbf x}-{\boldsymbol\mu})^T{\boldsymbol\Sigma}^{-1}({\mathbf x}...
- 619
1
vote
0
answers
37
views
When does an optimal input sequence for a discrete-time system exist?
Suppose an LTI discrete-time system is given by the equations
$$
x_{k+1} = Ax_k + Bu_k,\\
y_{k} = Cx_k + Du_k
$$
with $x_k\in\mathbb{R}^{m}$, $y_k\in\mathbb{R}^{n}$ and $u_k\in\mathbb{R}^{p}$ and $\...
1
vote
0
answers
73
views
What is the closed form of a polyhedral cone's dual cone?
A polyhedral cone can be defined as
$$
\mathcal{K} = \{x~|~Ax\preceq 0\},
$$
where $A \in \mathbb{R}^{m \times n}$, $x\in \mathbb{R}^n$ and $\preceq$ denotes component-wise less than and equal to.
The ...
- 71
1
vote
0
answers
204
views
Matrix relative condition number
I've been working on some distributed optimization problems and faced a bit of a challenge with the following question.
Given $A_1, A_2, .., A_m \in M_n({\mathbb{R})} $ symmetric positive definite ...
- 11
1
vote
0
answers
98
views
Solution of a simple optimization problem
Let $\mathbf{U}_1$ and $\mathbf{U}_2$ be two arbitrary unitary matrices and $\mathbf{D}$ be a diagonal matrix. What is the solution of the following optimization problem?
\begin{align}
\min_{\mathbf{...
- 287
1
vote
0
answers
52
views
When the summands of a positive definite matrix are positive definite
Let $A,B$ be two real symmetric matrices. Let $C = A+B$ be a positive-definite matrix. Write $C>0$ for $C$ being positive-definite. Suppose that $A>0 \implies C>0$ and $B > 0 \implies C>...
- 71
1
vote
0
answers
176
views
Maximum mutual information of random unitary transformation
Let $\mathbf{U}$ and $\mathbf{V}$ be random unitary matrices independent of random input vector $\mathbf{x}$. Moreover, $\mathbf{z}$ be random iid complex Gaussian vector with zero mean and identity ...
- 287
1
vote
0
answers
139
views
Subgradient chain rule
Suppose $$F:\mathbb{R}^n \to \mathbb{R},\; F(x)=\mathrm{max}_\mathrm{eig}(C-\mbox{diag}(x)).$$
I am trying to find a subgradient of $F$ at $x_0$. A subgradient of $\mathrm{max}_\mathrm{eig}$ is given ...
- 11
1
vote
0
answers
150
views
Minimax optimization of diagonal entries of function of matrix
Let $\mathbf{A}$ and $\mathbf{U}$ be arbitrary complex $M\times N$ and $N\times M$ matrices, respectively. Let denote superscript $(\cdot)^{\dagger}$ and $(\cdot)^{\mathrm{H}}$ as pseudo-inverse and ...
- 287
1
vote
0
answers
208
views
Maximum theorem with linear constraints. On parametric continuity of in optimization
Given
\begin{align}
s(\theta)= &\text{arg min}( g( \boldsymbol{x}) ) \\
\text{subject to }& \boldsymbol{A}(\theta) \boldsymbol{x} = \boldsymbol{b}(\theta) \\
&c_1 \le x_i \le c_2 , ...
- 88
1
vote
0
answers
163
views
Properties of vector combinations in the non-negative orthant
Given a vector $x \in \mathbb{R}^{n}_{0+}$ such that $x = \sum^{k}_{i=1} \alpha_{i}v_{i}$, the vectors $(v_{1},...,v_{k}) \in \mathbb{R}^{n}_{0+}$ are an independent set, $k < n$, and $\alpha_{i} &...
1
vote
0
answers
138
views
Matrix completion in $2\times2$ case by nuclear norm minimization to guarantee rank $1$?
Does fixing diagonal entries and minimizing nuclear norm under weighted sum of entries conditions produce a rank $1$ matrix? I think the answer for this is no.
At least could it be true in $2\times2$ ...
- 13.9k
1
vote
0
answers
483
views
minimize norm of matrix product
I have the matrix Product $PAP^H$ and I need to minimize $\|(PAP^H)^{-1}\|^2$ (over $P$ and Frobenius norm).
$A$ is a positive definite Hermitian matrix and $P$ has the structure
$$P=\left[\begin{...
- 129
1
vote
0
answers
481
views
psd condition for matrix completion
The nuclear norm minimization for the matrix completion problem is given by
\begin{align}
\textrm{minimize } \quad &\|X\|_{*}\\
\textrm{subject to } \quad & X_{ij}=M_{ij} \quad \forall (i,j)...
- 221
1
vote
0
answers
1k
views
Analytic formula for minimizing the maximum inner product of a set of vectors
Given $x_j\in\mathbb{R}^n$, $j=1,\ldots,p$, find
$$
\widehat{w} \in \arg\min_{\Vert w\Vert=1}\max_{1\le j\le p} |\langle w,x_j\rangle|.
$$
I am also interested in the special case where we further ...
- 710
1
vote
0
answers
227
views
Find optimal value for a regularization parameter in generalized eigenvalue problem
Consider the generalized eigenvalue problem :
$ \Sigma_{XY} \Sigma_{YX} {W} = \lambda \Sigma_{XX} {W} $
where $\Sigma_{XX} $ and $\Sigma_{XY}$ are sample covariance matrices are of the matrices $X$...
- 45
1
vote
0
answers
100
views
Changing a nonlinear equality constraint into some conic inequality plus rank constraint
If we have a constraint optimization problem in which one of our constraint is $\prod\limits_{k = 1}^N {\left( {x - {a_k}} \right) = 0} $ . How could this nonlinear equality condition be changed into ...
- 33
1
vote
0
answers
1k
views
Diagonal entries of a Cholesky factorization
Let $I$ denote an identity matrix, $E$ denote the all-one matrix of dimension $k\times k$ and $c$ some positive real number. Define $X=B(I-cE)B^T$ where $B$ is given by
$B:=\begin{pmatrix}
1 &\...
- 29
0
votes
2
answers
97
views
Optimization algorithms for Kronecker approximation of high-dimensional covariance matrices
I'm working with a high-dimensional covariance matrix and exploring Kronecker product approximations to make it computationally manageable.
Here's the setup:
I have a graph $G$ represented by a $D\...
- 1
0
votes
1
answer
917
views
What is the most accurate and efficient method of finding an inverse of a hessian matrix?
For any hessian matrix, of say 300 by 300, and may or may not necessarily be positive semi-definite, thus algorithms such as Cholesky decomposition may not be used.
I've found that some algorithms ...
- 17
0
votes
1
answer
157
views
Generalization of Dickson's Lemma
Given $\{v^i\}_{i \in \mathbb{N}} \subseteq \mathbb{N}^n$, and $\cup_{k=1, \ldots, m} C_j = \mathbb{N}^n$ for some $m$, where each $C_k$ is a cone generated by rational vectors. My question is: does ...
- 37
0
votes
1
answer
246
views
Matrix equation
Let $A$ be $k\times n$ matrix i.e., $A=(a_{1},\ldots, a_{n})$ where $a_{j} \in \mathbb{R}^{k}$, $rank(A)=k$ and $1\leq k \leq n$. Let $q=(q_{1},\ldots, q_{n})\in\mathbb{R}^{n}$ be such that $0<q_{j}...
- 3,946
0
votes
1
answer
147
views
Is there a redundant constraint in linear programming? [closed]
From wikipedia:
But... Why do we need the $x\ge 0$ part? We can instead do $-x\le 0$, and thus saving a line in the definition (which is not a big deal but nevertheless nice).
(In order to do that, ...
- 3