All Questions
Tagged with nonlinear-optimization linear-algebra
79 questions
0
votes
0
answers
96
views
When can a point be reconstructed from relative angle measurements?
Given a set of points $p_1,\dots,p_n$ in $\mathbb{R}^d$ and a target point $x\in\mathbb{R}^d$, I measure all the angles between all pairs of points and the target point. In other words, I have the ...
- 427
0
votes
0
answers
72
views
Minimizing the Spectral Norm of the Hadamard Product of a Quadratic Form Using CVX
I am trying to use CVX to minimize the spectral norm of the Hadamard product of two matrices, one of which is in quadratic form. Specifically, I am trying to minimize $\|{\bf A} \odot {\bf XX}^H\|_2$, ...
- 43
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 ...
1
vote
0
answers
91
views
Positive semidefinite maximum principle
Let $K\in\{\mathbb{R},\mathbb{C},\mathbb{H}\}$. Let $\mu$ be a Borel probability measure on $M_n(K)$ supported on a compact set $C$ of positive semidefinite matrices with $\mathbf{0}\not\in C$. ...
3
votes
1
answer
83
views
Detecting linear operator from actions of powers on subspace
Say I have a sequence of linear operators $A_1,...,A_n$ on a (real) vector space $V_1$. I suspect that there's a second vector space $V_2$, and an operator $A$ on $V_1\oplus V_2$, such that $A_i=(\...
- 4,593
1
vote
0
answers
152
views
Constrained trace optimization with relavance to optimal asset selection
Let $D$ and $Q$ be two real $m\times m$ diagonal matrices given
$$
D=\left(\begin{array}{cccc}
d_1 & 0 & \cdots & 0\\
0 & d_2 & \cdots & 0\\
\vdots & \vdots & \ddots &...
- 43
3
votes
0
answers
83
views
How many local maxima can $(x_1,\dots,x_r)\mapsto\|x_1A_1+\dots+x_rA_r\|_\infty/\|(x_1,\dots,x_r)\|_2$ have for Hermitian $A_1,\dots,A_r$?
Let $K\in\{\mathbb{R},\mathbb{C},\mathbb{H}\}$. Suppose that $A_1,\dots,A_r\in M_n(K)$ are all Hermitian.
Define a function $f_{A_1,\dots,A_r}:\mathbb{RP}^{n-1}\rightarrow[0,\infty)$ by setting
$$f_{...
1
vote
0
answers
161
views
On an optimization question
Suppose we have a square matrix $M=(1-z)A+zB$ where $A,B$ have integer entries from $\{0,1\}$ with $\det(A)+\det(B)=1$ and $\det(A),\det(B),per(A),per(B)\in\{0,1\}$ and we want to find $z\in[0,1]$ ...
- 13.9k
0
votes
1
answer
147
views
Seeking closed-form solution for vector equation
I'm working on a problem that involves vectors and scalar values, and I'm looking for a closed-form solution. I hope someone can help me with this or provide insights into how to approach it. Here's ...
- 111
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
183
views
Property of positive semi-definite
Let $A$ is a positive semi-definite matrix like this:
$$ A = \begin{bmatrix}
1 & \alpha_{1,2} & \alpha_{1,3} & \alpha_{1,4}\\
\alpha_{1,2} & 1 & \alpha_{2,3} & \alpha_{2,4}\\
\...
- 25
5
votes
3
answers
496
views
Eigenvectors that are tensor products?
Consider a fixed $N\times N$ positive definite symmetric matrix $A$.
Assume $N=d^r$ for some $d,r\geq 1$.
I wonder if one can find a closed formula for the maximizer/maximum of the function $$f(x):=\...
- 2,135
3
votes
1
answer
331
views
Variant of Wahba's problem
Wahba's problem is the following:
$$\min_R \sum_{k=1}^K \|v_k - Rw_k\|^2$$
where $v_k$ and $w_k$ are arbitrary $3\times 1$ vectors, and $R$ is a rotation matrix (i.e., orthogonal with $\det(R)=1$).
A ...
1
vote
0
answers
202
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
0
votes
0
answers
156
views
Optimal solution of complex optimization problem
Let $Q(x)=a(x)e^{jb(x)}$ be a complex function of $x$. We want to approximate this function with $R(x)=\alpha e^{jx\beta}$ such that
\begin{align}
\text{arg}\min_{\alpha,\beta} \int_{-\frac{A}{2}}^{\...
- 287
2
votes
2
answers
173
views
Analytic solution of low-dimensional Riccati equation
Consider the nonlinear map $F_i:\mathbb R^2 \to \mathbb R$
$F_i(x):=\varepsilon^2\langle x, A_i x\rangle +\varepsilon\langle b_i,x \rangle + x_i,$
where $A_i$ is some matrix and $b_i$ some vector
Can ...
- 192
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
0
votes
0
answers
124
views
The best unitary matrices that approximate a matrix product
Let $\mathbf{A}$ be an arbitrary $N\times N$ complex matrix. Moreover, $\mathcal{U}_1$ and $\mathcal{U}_2$ are distinct subsets of all unitary matrices. Suppose the matrices $\mathbf{U}_1$ and $\...
- 287
0
votes
0
answers
46
views
Lipschitz solutions to linear complementarity problems (LCP)
Let $M\in\mathbb{R}^{n\times n}$.
For $q\in\mathbb{R}^n$, define the set:
$$S_M(q)=\{y\in\mathbb{R}^n|y\ge 0,q+My\ge 0, y^\top (q+My)=0\}.$$
This is the set of solutions to the LCP $(q,M)$.
We say $...
- 183
1
vote
1
answer
173
views
How to solve a system of nonlinear equation, with y known and x or its coefficients unknown? [closed]
While solving a complex problem I have ended up with this simplified problem:
There are eight straight lines in the plane. They are notated as follows:
\begin{gather}
\tag{1}
\label{1}
y=k_1 x+b_1\\
y=...
- 21
0
votes
0
answers
57
views
Numerically finding matrix approximation by lower-dimensional "pseudo-similar" matrix
Consider an $N\times N$ (real or complex) matrix $A$, and some $n<N$. Is there a good numerical algorithm that finds the set consisting of an $n\times n$ matrix $B$, an $n\times N$ matrix $I$, and ...
- 3,001
2
votes
0
answers
66
views
Minimizing a certain norm of the identity operator on $\mathbb R^2$
$\newcommand\R{\mathbb R}\newcommand\Q{\mathcal Q}$For mutually orthogonal vectors unit vectors $a=[a_1,\dots,a_n]^T$ and $b=[b_1,\dots,b_n]^T$ in $\R^n=\R^{n\times1}$ (so that $n\ge2$) and for all $x=...
- 128k
5
votes
1
answer
332
views
On a certain norm of the identity operator on $\mathbb R^2$
$\newcommand\R{\mathbb R}\newcommand\Q{\mathcal Q}$For mutually orthogonal vectors unit vectors $a=[a_1,\dots,a_n]^T$ and $b=[b_1,\dots,b_n]^T$ in $\R^n=\R^{n\times1}$ (so that $n\ge2$) and for all $x=...
- 128k
1
vote
2
answers
202
views
Robust estimation of $Ax=b$
Problem setting :
$ \underset{x}{\text{min}} \|Ax-b\|$, where $A \in \mathcal{R}^{m \times n}, m\gg n $, full rank.
L1 loss is used for robust estimation using IRLS. The corresponding equation to ...
- 21
3
votes
0
answers
122
views
Convex optimization upper bound for a non-linear optimization
Is there any good convex optimization problem based upper-bound for the following non-linear optimization problem?
\begin{align}
\max_{x_1,\ldots,x_N}&\quad \sum_{n=1}^{N} \log(1+\frac{x_n}{1+\...
- 287
0
votes
1
answer
153
views
Difference of two optimization problem's optimal value
Let we have two following optimization problems:
\begin{align}
\text{(P1)}\quad \alpha_1 = \max_{x_1,\ldots,x_M} &\quad \sum_{m=1}^{M}\log(1+f_m(x_1,\ldots,x_M))\\
\textrm{s.t.} &\quad \...
- 287
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
2
answers
338
views
Of all probability matrix $P$ having stationary distribution $\pi$, find the one having smallest diagonal
I am requesting your help today trying to solve a somewhat odd problem. Is there a way to find through some numerical algorithm such as Newton's method the stochastic matrix $\boldsymbol{P}$ having ...
- 23
1
vote
0
answers
163
views
A real system of bilinear equations with $2n$ unknown and equations
I have the following system of $2n$ bilinear equations, for a square invertible matrix $A \in \mathbb{R}_{n \times n}$, and $2n$ unknowns organized in vectors $x,y \in \mathbb{R}^n$:
$$
diag(y) A x = ...
- 560
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
3
votes
1
answer
84
views
Largest subset not spanning the span
Let $S=\{c_1,\dots,c_n\}$ be a set of vectors in $\mathbb{R}^M$. Is the below problem studied in literature?
$$\max\limits_{S'\subset S} \vert S' \vert $$
$$s.t. dim(span(S')) < dim(span(S))$$
...
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
0
votes
0
answers
255
views
Span of a nonlinear function
Fix vectors $x,y\in\mathbb{R}^d$ and a smooth function $\phi:\mathbb{R}\rightarrow \mathbb{R}$. Define $\phi^d: \mathbb{R}^d \rightarrow \mathbb{R}^d$ as applying $\phi$ entrywise (i.e. $\phi^d(x_1, ...
- 159
1
vote
0
answers
311
views
Computing the nearest hermitian positive semi-definite matrix
The real case of finding the nearest semi-definite matrix in terms of the Frobenius norm was solved by Higham in 1988.
But is there any work on computing the nearest
hermitian positive semi-...
- 43
2
votes
1
answer
186
views
Is this graph problem NP-Hard?
I had asked this question in math.se without any success
Let $A$ be the symmetric $n\times n$ adjacency matrix for a graph where $A_{ij}$ is the positive edge value between node $i$ and $j$ (thus ...
- 1,421
0
votes
0
answers
121
views
Closed form solution to an equation
Let $X \in \mathbb{R}^{n \times d}, w \in \mathbb{R}^d, y \in \{\pm 1
\}^{n}, \alpha \in (0, 1)$. Consider the equation
$$ X^{\top}(Xw-y)+\alpha \|w\|_{2}X^{\top}\operatorname{sign}(Xw-y)+\alpha\frac{...
0
votes
1
answer
228
views
Upper and lower bounds for a matrix norm with fixed diagonal
given a vertical vector $x=(x_1,x_2,...x_n)$ of size n and $B$ is a symmetric positive definite matrix ($n \times n$) of choice. All the diagonal elements of B are fixed to one, while extra diagonale ...
- 159
1
vote
0
answers
760
views
Matrix trace minimization of quadratic and linear terms under orthogonal manifold constraints
How would one solve the following orthogonal manifold problem?
$$\begin{array}{ll} \text{maximize} & \mbox{tr}(X^\top A X - X^\top B)\\ \text{subject to} & X^\top X = I\end{array}$$
where $A ...
- 21
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
1
answer
600
views
Closed Form Solution for Optimization Problem over the Space of Rigid Transforms
Is there a closed form solution to this constrained optimization problem:
\begin{equation}
\min_{R \in SO(3),\, \mathbf t \in \mathbb R^3} = \sum_{i = 1}^N \| M_i(R \mathbf p_i + \mathbf t) \|^2,
\...
- 101
3
votes
1
answer
416
views
What's the best orthonormal matrix to align two matrices in the operator norm sense?
Let $A,B \in R^{n\times r}$ with $A^\top B $ invertible. It is known that
\begin{equation}
UV^\top :=\arg\min_{R \in \mathcal{O}^{r\times r}}\|AR-B\|_\mathrm{F},
\end{equation}
where $USV^\top$ is ...
- 515
7
votes
2
answers
1k
views
Maximum average Euclidean distance between $n$ points in $[-1,1]^n$
For my research I have designed a metric that is based on the average Euclidean distance between $n$ points in the $n$-dimensional hypercube $[-1,1]^n$. However, I have a hard time finding the maximal ...
- 71
4
votes
3
answers
2k
views
Maximize the Euclidean norm of a matrix times a vector on unit sub-spheres
For $X = (x_1^T,\ldots,x_N^T)^T \in \mathbb{R}^{Nm \times 1}$, where $x_i \in \mathbb{R}^{m \times 1}$ for $i \in \{1,\ldots,N\}$, $A \in \mathbb{R}^{r \times Nm}$, and $r \geq Nm$, I want to obtain a ...
- 53
4
votes
1
answer
445
views
Proving convergence of modified ALS for non-negative matrix factorization
The general Non-Negative Matrix Factorization (NMF) problem asks that for given a matrix $X \in \mathbb R^{m,n}_{0+}$ (with this notation meaning a matrix containing real numbers greater than or equal ...
7
votes
1
answer
373
views
Is the solution of this optimization problem always positive semidefinite?
We are given a set of unit vectors $U \subset \mathbb{C}^n$ which spans the space $\mathbb{C}^n$. Given another unit vector $x$, consider then the following optimization problem:
$$ \sup_H \left\{ x^*...
- 73
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
7
votes
1
answer
483
views
Generalized Rayleigh-quotient gradient flow on Grassmannian
The following theorem appears without proof in :
Helmke, Uwe, and John B. Moore. Optimization and dynamical systems. Springer Science & Business Media, 2012.
Let $A$ be a symmetric $n\times n$ ...
- 318
0
votes
0
answers
84
views
Number of solutions to non-linear equations
As part of our project, we are required to determine the total number of distinct solutions to the following equations.
There are $n$ variables of one type, say $\{p_i\}_{i=1}^n$, $m$ variables of ...
- 109
27
votes
5
answers
2k
views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121