4
votes
2answers
134 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
1answer
104 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
0answers
134 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
0answers
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
1answer
179 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
0answers
100 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
1answer
140 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
1answer
203 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
2answers
117 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
1answer
130 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
1answer
210 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
2answers
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
0answers
138 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
2answers
147 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
1answer
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
0answers
139 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
1answer
218 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 ...