**23**

votes

**2**answers

874 views

### An Interesting Optimization Problem

You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference ...

**15**

votes

**8**answers

911 views

### When do people actually use the maximum entropy distribution?

One of the standard problems in convex optimization is the calculation of the maximum entropy distribution that satisfies some set of criteria. For example, if $\mathbf{x} \in \mathbb R^n$ is an ...

**8**

votes

**3**answers

283 views

### Lower bound for spectral radius on $\operatorname{GL}(n,\mathbb{Z})$

Consider the group of matrices $G =\operatorname{GL}(n,\mathbb{Z})$ with integer entries and determinant $\pm 1$. For each matrix $D \in G$, the product of the eigenvalues of $D$ is equal to $\det D ...

**8**

votes

**3**answers

700 views

### Is group theory useful in any way to optimization?

For what I have seen, optimization uses a lot of linear algebra and convex analysis, but I have not seen any group theory being used, so I was curious about it.
Is group theory useful in any way to ...

**7**

votes

**3**answers

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

**7**

votes

**2**answers

200 views

### Removing constraints in convex optimization

Say I have a convex optimization problem of the form $$\min_x f(x) ~~ s.t.\\ g_1(x)\leq0,\\\vdots \\g_n(x)\leq 0$$ with all functions convex. Suppose that $x^*$ is a unique optimizer to my problem and ...

**6**

votes

**2**answers

171 views

### On the convexity of element-wise norm 1 of the inverse

Question first asked on math.stackexchange here: http://math.stackexchange.com/questions/317209/on-the-convexity-of-element-wise-norm-1-of-the-inverse
On the convexity of element-wise norm 1 of the ...

**6**

votes

**0**answers

90 views

### A specific case of the $p$-center problem

Given a fixed positive integer $m$, let $\cal{S}$ be the subset from $\mathbb{R}^m$ defined as $\cal{S} = \{u \in \mathbb{R}^m \mid \forall i \in \{1, \dots, m\}, u(i) > 0$ and $\sum_{i=1}^m{u(i) = ...

**6**

votes

**0**answers

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

**5**

votes

**1**answer

261 views

### What it is the volume of the unit ball section of the cone of positive definite matrices?

Let $PD_{n}$ be the cone of positive definite $n \times n$ real matrices and let $B$ be the unit sphere in $n \times n$ dimensions. What is the volume of $PD_{n} \cap B$?
EDIT: Let's assume that $B$ ...

**5**

votes

**1**answer

118 views

### Reference request: Continuity of unique maximizer of linear functional on convex set

Does anyone know reference for a theorem of the following sort:
Proposition: Let $K \subset\mathbb {R}^n$ be a compact convex set, and assume that
$$f(w):=\operatorname{argmax}_{x\in K}w(x) $$ is ...

**5**

votes

**1**answer

168 views

### Algorithm to minimally connect line segments in Euclidean plane

Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?"
More formally and generally, what I'm looking for ...

**5**

votes

**0**answers

51 views

### Finding the optimal mixture of two convex functions

I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where ...

**5**

votes

**0**answers

144 views

### Characterizing matrices with rank constraint

Given matrix $M\in\Bbb Z_{\geq0,\leq b}^{n\times n}$, is there a nice method to characterize $$\mathscr{D}[M,b]=\{Q\in\Bbb R_{\geq0,\leq b}^{n\times n}:\mathsf{rank}(M-Q)= \mathsf{rank}(Q),\quad ...

**4**

votes

**2**answers

270 views

### Convex Sets and Nearest Neighbors

For a set $S \subseteq \mathbb{R}^n$ and a point $x \in \mathbb{R}^n$, let $c_S(x)$ be the point $s \in S$ that minimizes $\|x-s\|$ if such a point exists and is uniquely determined. It is known that ...

**4**

votes

**2**answers

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

**4**

votes

**2**answers

151 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} \\\
...

**4**

votes

**1**answer

183 views

### optimization problem, any solution?

The objective is as follows:
$\min_{\mathbf{F}} a Tr(\mathbf{F} \mathbf{F}^H) - Re\{\mathbf{b}\mathbf{F}^H \mathbf{C} \mathbf{F} \mathbf{d}\}$
$s.t.\ \ \ Tr(\Sigma \mathbf{F} \mathbf{F}^H)<p$
...

**4**

votes

**2**answers

374 views

### Gradient descent-like optimization on a convex landscape with noisy sampling

This is a rewrite of the original positing (below), and is crossposted to ...

**4**

votes

**0**answers

110 views

### Two quadratic programming problems always same answer? [closed]

Was exploring quadratic programming optimization and for two types of problems the answers seemed to always equal.
Problem 1:
Minimize $\tfrac{1}{2} \mathbf{x}^T Q\mathbf{x}$
Subject to $ A ...

**4**

votes

**0**answers

164 views

### When is the sum of a weak-$*$ closed convex cone and a subspace also weak-$*$ closed?

Let $X$ be a Banach space. Suppose $C \subset X^*$ is a convex cone and $V \subset X^*$ is a subspace, and suppose both $C$ and $V$ are closed in the weak-$*$ topology. Are there any general ...

**3**

votes

**1**answer

192 views

### Is the Binomial Expectation of a Multivariate Convex Function Convex in the Vector p?

Let $\mathbf{p}=(p_1,\dots,p_m)$ be a vector in $[0,1]^m$ and let $\mathbf{X}=(X_1,\dots,X_m)$ be a vector of independently-distributed binomial random variables such that $X_i\sim ...

**3**

votes

**1**answer

82 views

### Maximizing Frobenius Norm of Commutator (an opposite Procrustes problem)

I was wondering if anybody has any suggestions on the following problem:
Let $S$ be an $n\times n$ positive definite symmetric matrix. I wish to find an $n\times n$ orthogonal matrix $R$ which ...

**3**

votes

**2**answers

75 views

### Is the prox-residual monotone?

$\newcommand{\scp}[2]{\langle #1,#2\rangle}\newcommand{\id}{\mathrm{Id}}$
Let $f$ and $g$ be two proper, convex and lower semi-continuous functions (on a Hilbert space $X$ or $X=\mathbb{R}^n$) and let ...

**3**

votes

**1**answer

63 views

### generalized mean inequality extension

from generalized inequality, we now that for $p>q$, we have $M_p(\mathbf{x})\ge M_q(\mathbf{x})$. now I am curious to know if we can find a constant $\alpha(p,q)$ which is only function of $p,q$ ...

**3**

votes

**1**answer

235 views

### SDP formulation of noisy low rank matrix completion

Exact low rank matrix completion using nuclear norm minimization can be formulated as a semidefinite program (SDP). Following the notation in the paper, a convex problem for noisy matrix completion ...

**3**

votes

**1**answer

168 views

### Linear dependency of real numbers with integer coefficients adding up to zero [closed]

Let $x = (x_1, \dots, x_n)$ be a vector of real number. I was asking myself if there was an efficient way of telling whether there exists a non-zero vector of integers $z \in \mathbb Z$ such that both
...

**3**

votes

**1**answer

61 views

### Analysis of first-order methods for constrained convex optimization with approximate oracles

In many first-order optimization methods an oracle is needed whose action enforces the constraint/regularizations. For example, in projected gradient descent, conditional gradient method, and proximal ...

**3**

votes

**1**answer

82 views

### Can one always find sparse solutions to an $\ell^1$-minimization problem?

Consider $A\in\mathbb{R}^{m \times N}$ and $b \in \mathbb{R}^m$, with $m<N$. Is it true that the optimization problem
$$\min \|x\|_1 \quad s.t. \;\; A x = b,$$
admits an $m$-sparse solution in ...

**3**

votes

**1**answer

108 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$. ...

**3**

votes

**1**answer

148 views

### Equivalent method for maximum likelihood estimation of covariance parameters

My goal is to estimate the parameters of a covariance matrix $\Omega$, by maximizing the following log-likelihood function:
$$\log L(\vec\tau, \rho, \sigma \mid W, X) = -m\ln(\left | \Omega \right |) ...

**3**

votes

**1**answer

247 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 \\\
...

**3**

votes

**0**answers

97 views

### This function looks quasiconvex, can't understand why

Suppose that $\mathbf{C}$ is a given matrix with non-negative entries in $\mathbb{R}^{m\times n}$ and $d$ is a given scalar, and let $g(\mathbf{y})$ be defined by ...

**3**

votes

**0**answers

311 views

### Coordinate mirror descent

Let $f$ be a jointly convex function of 2 variables say $x,y$. I am interested in solving the optimization problem $$\min_{x,y\in\Delta} f(x,y)$$ where $\Delta$ is a $d$ dimensional simplex. An ...

**2**

votes

**5**answers

245 views

### Distance between two sets

Let $A, B$ be two convex and closed subsets of $\mathbb{R}^n$. We would like to the minimum distance between these two sets. i.e., we want to find a solution for the following problem.
$$ \min ...

**2**

votes

**1**answer

174 views

### Multiplicative gradient descent?

The normal gradient descent is additive: $w_{t+1}=w_t-\lambda_t\nabla f(w_t)$, but is there a multiplicative gradient descent that looks something like $w_{t+1}=w_t[-\lambda_t\nabla f(w_t)]$?
I know ...

**2**

votes

**2**answers

103 views

### Projection onto rotated box

Does anyone know if there is an efficient way to find the projection of an arbitrary point $z$ onto a rotated box, i.e. onto the set $\Omega=\{x \mid a \leq Ux \leq b\}$ where $U$ is a unitary matrix?
...

**2**

votes

**2**answers

110 views

### sensitivity analysis in conic optimization

I have a conic optimization of the form:
$\min_x \langle c, x \rangle$, s.t. $Ax = b$, $x \in K$.
Where $x \in \mathbb{R}^{n}$, $A$ is an $m \times n$ matrix, $b \in \mathbb{R}^m$, $K$ is a self ...

**2**

votes

**1**answer

220 views

### quadratic programming on hypercube

I want to maximize a quadratic form $\mathbf x^T\mathbf Q\mathbf x$ and also want to find out which vector $\mathbf x$ maximizes the quadratic form when
$\mathbf Q$ is an $n\times n$ positive ...

**2**

votes

**1**answer

169 views

### maximizing convex quadratic form over the intersection of unit sphere and positive orthant

For a positive semi-definite matrix $C$, I want to find the solution to the following problem:
$\arg\max_{h\geq 0} h^T C h\quad$ s.t. $\quad h^T h\leq 1$
Any pointers are welcome.

**2**

votes

**1**answer

332 views

### lipschitz constant of a multivariate function

I have a function $f:\mathbb{R}^{50} \rightarrow \mathbb{R}$ and I need to compute the Lipschitz constant of $f$ to solve an optimization problem using a specific algorithm. Does any one have ...

**2**

votes

**2**answers

276 views

### A certain type of Quadratic Constrained Quadratic Programming Problem (QCQP)

Let $P_1$, $P_2$ be two hermitian matrices. Can anyone comment about the following (QCQP)
\begin{equation}
\min_{z}~z^{H}z \\\
~~subject~to ~z^{H}P_1z+1\leq 0,~z^{H}P_2z+1\leq 0
\end{equation}
I am ...

**2**

votes

**1**answer

82 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{ - ...

**2**

votes

**1**answer

130 views

### Projection onto $\ell^{2,1}$ ball

Does anyone have an idea how to project onto the $\ell^{2,1}$ ball efficiently, i.e. how to solve
$$ u = \arg \min_u \|u-f \|^2 \text{such that } \left(\sum_i \big(\sum_j |u_{i,j}|\big)^2 ...

**2**

votes

**2**answers

151 views

### How to minimize the Bregman divergence on a convex hull spanned from a set of vectors?

everyone.
It has been well known that the following minimization problem of a Bregman divergence with linear inequality
can be solved by successively projecting the current point to each constraint ...

**2**

votes

**1**answer

249 views

### Block Covariance Matrix - Positive Definite? (Quadratic Optimization) [closed]

I have a covariance matrix C. I have then formulated an quadratic optimization problem that involves the following matrix in the quadratic form:
[ C C ]
[ C C ]
However, the quadratic solver ...

**2**

votes

**1**answer

137 views

### Circumscribed ellipsoid of minimum Hilbert-Schmidt norm

Let $K\subseteq \mathbb{R}^n$ be a full-dumensional convex body. The Löwner ellipsoid of $K$ is the unique ellipsoid of smallest volume containing $K$. My question is about a related object: the ...

**2**

votes

**1**answer

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

**2**

votes

**2**answers

358 views

### convergence of the infima of convex functions

Can one give a reference to a result like this:
If a sequence of convex functions $f_{n}$ on $\mathbb{R}$ converges pointwise to a non-monotonic function $f$, then ...

**2**

votes

**1**answer

93 views

### Fastest 'Oracle' Algorithm for satisfying a single linear constraint on a convex set?

In this paper by Arora, Hazan, and Kale (http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf) a method is given for using the Multiplicative Weights Update algorithm to quickly solve Linear Programs ...