# Tagged Questions

**7**

votes

**3**answers

313 views

### The distribution of the shortest path through $n$ points

In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small?
More ...

**2**

votes

**1**answer

52 views

### A difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$.
(Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. ...

**4**

votes

**2**answers

139 views

### Minimax theorem on a non convex domain

A minimax theorem is a theorem which states that under certain conditions on $\mathcal{X}$, $\mathcal{Y}$ and $f$:
$$ \inf_{x \in \mathcal{X}}{\sup_{y \in \mathcal{Y}}{f(x,y)}} = \sup_{y \in ...

**0**

votes

**1**answer

108 views

### Eigenvalues of a given parametrized matrix.

Let $\mathbf{A}$ and $\mathbf{B}$ be two complex rank-one $N\times N$ positive semi-definite matrices. Let the matrix $\mathbf{C}$ be defined as
\begin{align}
...

**1**

vote

**0**answers

136 views

### How to solve such an optimization problem efficiently？

Given a symmetric positive semi-definite matrix $\mathbf Y$ and a convex set $\mathcal M$ which is a subset of all symmetric positive semi-definite matrices (consider a simple case of $\mathcal M$： a ...

**1**

vote

**0**answers

99 views

### Maximizing an integral over a convex region

Let $C$ denote a compact, convex region in the plane containing the origin with unit area, and let $f$ be a probability distribution on $C$. Let $f^\ast$ denote the distribution that maximizes the ...

**3**

votes

**1**answer

185 views

### Fast algorithm for maximizing smallest eigenvalue of linear combination of hermitian matrices

I have an engineering back ground. Due to work, I came across this problem
\begin{align}
&\max_{\lambda,y_i\in \mathbb{R}}~\lambda \\\
...

**0**

votes

**0**answers

101 views

### Modifying a QP to incorporate more constraints

Consider the following problem:
$$\min \sum_{i=1}^n (Y_i - Z^{(i)})^2 \\
\text{subjected to}~ \epsilon_k^{\top}(X_j-X_k) \leq Z^{(j)}-Z^{(k)} ~ \forall k,j = 1 \ldots n. $$
where $\epsilon_1, ...

**2**

votes

**1**answer

145 views

### optimization over positive semidefinite matrices

I wonder what is the most explicit characterization that can be given for the solution to the ($N$-dimensional) problem of maximizing the criterion
$$
-\textrm{trace}[AS^{-1}] - b^\top Sb
$$
over ...

**1**

vote

**1**answer

212 views

### Semi Definite Relaxation for a Quadratic Feasibility Problem using CVX

Consider the following Semi-Definite Feasibility problem
\begin{align}
\max_{\mathbf{Z}}~0 \\\
\mathrm{trace}(\mathbf{Z})\leq \rho \\\
\mathrm{trace}(\mathbf{S}_1\mathbf{Z}) \geq \alpha \\\
...

**4**

votes

**2**answers

119 views

### A certain type of constrained Rayleigh-Ritz ratio

Let $\mathbf{A_1}$ and $\mathbf{A_2}$ be two hermitian matrices. Consider the problem
\begin{align}
\max_{\mathbf{u}^H\mathbf{u}=1}~\mathbf{u}^H\mathbf{A}_1\mathbf{u} \\\
...

**-1**

votes

**1**answer

131 views

### Regularized Gradient with respect to a matrix (with a specific structure)

Suppose we have a typical logdet function $\mathcal{L}$
$$
\mathcal{L} = \log\vert \mathbf{I} + \mathbf{A}\mathbf{S} \vert - \mathbf{q}^T(\mathbf{A}^{-1} + \mathbf{S})^{-1} \mathbf{q},
$$
where ...

**0**

votes

**1**answer

218 views

### solve non-convex quadratic constrained quadratic programming

$\min_{\beta}\beta^{T} A \beta$
$s.t. \ \beta^{T} C \beta=1\ and\ \beta\geqslant 0$
Here $A,C\in \mathbb{R}^{M\times M}$, $\beta \in \mathbb{R}^{M}$
I saw in one paper saying that it could be ...

**1**

vote

**2**answers

209 views

### On a version of gradient descent

I am trying to read this paper and have gotten stuck. The author considers the problem of minimizing a convex function whose gradient has Lipschitz constant $M$ and considers the scheme
$$ x(t+1) = ...

**2**

votes

**0**answers

139 views

### Quadratic optimization with parameter in constraint

Disclaimer: I posted the same question on math.stackexchange. However, the FAQ suggests to post research-level questions in this forum.
Question: Given a function $q: \mathbb R^{N\times N}\mapsto ...

**1**

vote

**2**answers

148 views

### What is the dual of an semidefinitely representable (SDR) cone?

The Question
Let $V\simeq \mathbb{R}^r$ be an $r$-dimensional vector space with the usual Euclidean inner product.
Let $\mathcal K\subset V$ be a cone defined as
$$
\mathcal K=\Big\{x\in ...

**1**

vote

**1**answer

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

**5**

votes

**0**answers

140 views

### Numerical linear algebra: how to compute $B^TC^{−1}B$ efficiently

Hi,
my question is similar to this one. I have to compute $B^TC^{−1}B$, where $C$ is a strictly positive definite $n\times n$ matrix and $B$ is $n\times m$.
The matrix $C$ is huge ($n$ up to a ...

**0**

votes

**1**answer

225 views

### Is unconstrained integer convex optimization problem NP-hard?

Does anyone know a reference to the answer if unconstrained integer convex optimization problem (i.e. $\min_{x\in \mathbb{Z}^N} F(x)$, $F$ is convex and $N$ is NOT fixed) is NP-hard?
Thank you in ...