**28**

votes

**0**answers

2k views

### A Combinatorial Abstraction for The “Polynomial Hirsch Conjecture”

Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ .
Suppose that
(*)
For every $i \lt j \lt k$
and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, ...

**10**

votes

**0**answers

141 views

### Dividing a convex region to minimize average distances

Let $C$ be a convex region in the plane with area 1 that contains distinct points $p_1,\dots,p_n$. Say I'd like to divide $C$ into $n$ pieces $C_1,\dots,C_n$, each of area $1/n$, and I'd like to ...

**8**

votes

**0**answers

263 views

### Hasse-Weil Bound and Chebyshev Inequality

I was reading about the Hasse-Weil bound for the number of points in on a curve over the finite field $\mathbb{F}_q$.
$$ \big| |C(\mathbb{F}_q)| - (q+1) \big| \leq 2g \sqrt{q} $$
However, this ...

**6**

votes

**0**answers

147 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

**0**answers

59 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

126 views

### Minmax problem for polygons

Let $\text{Pol}_n$ be the set of all convex polygons on a plane with $n$ vertices. For $P\in \text{Pol}_n$ denote by $\text{Tr}(P)$ the set of all triangles which vertices are some vertices of $P$. I ...

**5**

votes

**0**answers

428 views

### Maximizing the matrix norm

Hi all,
I wish to find a 3x3 rotation (orthogonal) matrix $\mathbf{R}$ such that it maximizes the following matrix norm:
$||\mathbf{A} \mathbf{D}_r \mathbf{D}_b ||_2$
where $\mathbf{A}$ is a known ...

**4**

votes

**0**answers

138 views

### Is there a name for this quantity between two distributions?

Let $f$ be a probability density on a compact domain $D$, and say that $x_1,\dots,x_n$ are samples from $f$. If we wanted to compute the Wasserstein distance between $f$ and the empirical ...

**4**

votes

**0**answers

137 views

### Are there some numerical test to check if a map is a contraction?

Let's say I have a multivariate function
$$
f:D \to D, D \subset \mathbb R ^n, D \text{ compact},
$$
for which there is no closed form.
That is the only way to evaluate the function is to do it ...

**4**

votes

**0**answers

81 views

### Sufficiency of stationary policy for negative stochastic dynamic programming

Consider a Markov Decision Process with Borel state space $X$ and Borel action space $U$, like the one defined in the book "Stochastic Optimal Control: Discrete-time case" by Bertsekas and Shreve. All ...

**4**

votes

**0**answers

132 views

### Convexified threshold of a function

Upd. The question in a nutshell: find convex set on plane which is «closest» to a given non-convex set.
It is given integrable function $0\leq f(x,y)\leq 1$ with bounded support: $f(x,y)=0$ when ...

**4**

votes

**0**answers

90 views

### Applications of k-medians with moment constraints

Suppose I have a collection of points $p_1,\dots,p_N$ in the plane. In the Euclidean $k$-medians (or $k$-means) problems, our objective is to distribute a set of $k$ points $x_1,\dots,x_k$ in the ...

**4**

votes

**0**answers

165 views

### Is it possible to solve the argument maximization problem $\arg\max_x \langle x,l \rangle −f_1(x)−f_2(x)$ via convex duality?

I am attempting to solve the argument maximization problem
$$\arg\sup_x \{ \langle x,l \rangle − f_1(x)−f_2(x) \} \ \ \ \ \ \ \ \ \ \ (1)$$
where the functions $f_1$ and $f_2$ are concave but ...

**4**

votes

**0**answers

178 views

### restricting “dances of minimal cost” (optimization on braids/permutations?)

Consider applying the permutation (1,3,0,5,2,7,4,6) to the integers (0,1,2,3,4,5,6,7) three times.
I call this a "dance of minimal cost" because all unordered pairs in {0..7} meet each other, and the
...

**4**

votes

**0**answers

306 views

### Can the Littlewood-Richardson cone be used for combinatorial optimization?

The Littlewood-Richardson cone $LR_{n, k}$ consists of all $k-$tuples $(a_1, a_2, \dots, a_k)$ of real $n-$vectors with monotonically decreasing entries such that there exist $k$ $n \times ...

**4**

votes

**0**answers

294 views

### The Gömböc and monostatic objects

This made the popular news a few years ago. Summary: it's the first homogeneous, convex solid to be found with only one stable and one unstable mechanical equilibrium when resting on a flat surface. I ...

**4**

votes

**0**answers

492 views

### Dynamic programming principle (DPP)

In stochastic control problem, one shall use the measurable selection theorem to prove DPP. It was discussed in discrete time case in [Bertsekas and Shreve 1978]. Is there unified framework in ...

**3**

votes

**0**answers

113 views

### existence of optimal control

I'm looking for an existential result in optimal control for the following class of problems:
Given $T > 0$, $\bar x, \hat x\in\mathbb R^d$, an instantaneous cost function $c:\mathbb R^d\times ...

**3**

votes

**0**answers

101 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

90 views

### Containing a “fuzzy” ellipsoid within an ordinary ellipsoid

Consider the ellipsoid described by the inequality $(x - x_c)^T P^{-1} (x - x_c) \leq 1$, where the vector $x_c \in \mathbb{R}^n$ denotes the center of the ellipsoid and the symmetric positive ...

**3**

votes

**0**answers

237 views

### An optimization problem over real symmetric matrices

Given an $n\times s$ matrix $P$ of positive real numbers and $T\geq n$, find (either by a formula or an algorithm) the real symmetric $n\times n$ Z-matrix $A$ which maximizes $\min\limits_{1\leq ...

**3**

votes

**0**answers

101 views

### Copositivity in matrix pencils

Given two square symmetric matrices $A,B$ of the same order, the matrix pencil $P(A,B)$ is the set of linear combinations of $A$ and $B$. Finsler's theorem gives an elegant criterion for $P(A,B)$ to ...

**3**

votes

**0**answers

106 views

### Multiple Number Partitioning / “Multiprocessor Scheduling”

Consider the well-known Number Partitioning / "Multiprocessor Scheduling Problem": You want to partition a set $S$ of objects (jobs) $i$ with weights $w_i$ (process time) into subsets $S_k$ (e.g. ...

**3**

votes

**0**answers

151 views

### stochastic control / geometric mean

Consider the following problem:
Given $\Omega$ and $U$ two symmetric definite positive matrices, choose a matrix $K$ to minimize the expectation $x' \Omega x + x'K'UKx$ when $x$ follows the invariant ...

**3**

votes

**0**answers

321 views

### maximum variance unfolding

Consider positive weights $\pi_1, \ldots, \pi_n$ (one can suppose that they add up to $1$) and $n-1$ lengths $d_1, \ldots, d_{n-1}$.
Is there an analytical solution to the following problem:
find the ...

**3**

votes

**0**answers

324 views

### Convergence to a (unique?) fixed point?

Consider a given $N\times P$ matrix $X$ (full rank with columns ${\bf x}_p$, $p=1,\ldots,P$), a given vector ${\bf y}\in R^N$ and a thresholding function $\eta_\lambda(|x|)=(|x|-\lambda)_+$ with ...

**3**

votes

**0**answers

239 views

### Nonlinear conjugate gradient update strategy by Dai and Yuan

In Nocedal and Wright book "Numerical Optimization", they describe on
page 123 (formula 5.49) an update strategy for the beta parameter in
the nonlinear conjugate gradient optimization, which was ...

**2**

votes

**0**answers

118 views

### Polynomial-time algorithm solving approximately a generalization of the travelling salesman problem

Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the ...

**2**

votes

**0**answers

44 views

### LQR solution when there are linear terms in the cost function?

I am trying to solve the following Bellman Equation:
$V(s) =\max_u \left[a'u - (u-s)'Q(u-s) + V(u)\right]$
In the equation above, $s,u,a\in \mathbb R^n$, $Q\in \mathbb R^{n\times n}$ is positive ...

**2**

votes

**0**answers

122 views

### Fixed area, largest mass — is there a name?

Let $x\in \mathbb{R}^n$ and let $s_k(x)$ denote the sum of the $k$ largest entries of $x$. The function $s_k(x)$ is well-known to be convex and is often used in optimization, such as
...

**2**

votes

**0**answers

92 views

### Copositivity under tensor products

Is there any symmetric real matrix $A$ such that $A^{\otimes n}$ is copositive for all positive integers $n$, but such that A is neither positive semidefinite nor has just non-negative entries?
...

**2**

votes

**0**answers

147 views

### First Variation of Dyson Series/Magnus Expansion

Given the matrix differential equation $\frac{dU_t}{dt}=A_t U_t$ there are at least two ways to write a formal solution. Both the Dyson series: $U_t = \mathcal{T} e^{\int_{0}^{t} A_t dt}$ and the ...

**2**

votes

**0**answers

35 views

### Linear control systems

Are there some algorithms to compute the error bound of the difference between the original system and the balance system using the Balance truncation method?

**2**

votes

**0**answers

102 views

### Quickly checking an inequality on a convex region

I previously posted this question to math.sx at: http://math.stackexchange.com/questions/748015/quickly-checking-if-an-inequality-holds-on-a-convex-region but I'm thinking that MO may be more ...

**2**

votes

**0**answers

139 views

### An optimization in Markov Chain

We are given two correlated random variables $V$ and $X$ supported over a finite alphabets $\mathcal{V}$ and $\mathcal{X}$. Suppose the marginal $P_V$ and conditional distribution $P_{X|V}$ are ...

**2**

votes

**0**answers

35 views

### Continuity of minimizer of a function with respect to another variable

Suppose the real function $f(w,X)=wg(X)+h(X)$ ($g$ and $h$ are other functions) is differentiable with respect to scalar $w$ and vector $X \in \mathbf{R}^m$ everywhere and $f$ is bounded below. What ...

**2**

votes

**0**answers

78 views

### Maximum Principle with Banach Control Space

This is a problem that seems very natural to me, but I couldn't find any formal statement in the literature for some time now. I am basically considering an autonomous optimal control problem in ...

**2**

votes

**0**answers

303 views

### minimize a cost function with matrix traces

Hi, I have a cost function of the form
$$F(X) = \operatorname{tr}(X'AX)+\operatorname{tr}(X'B),\quad\textrm{ s.t. }X'X=I.$$
$X$ is a $m\times n$ matrix, ($m>n$), with orthonormal columns. $A$ is ...

**2**

votes

**0**answers

180 views

### Tools for “infinite-dimensional linear programming”

I was wondering, whether you could point me to some tools with which I could tackle the following "infinite-dimensional linear programming" problem:
Notation:
$a=1,2,\ldots, A$, ...

**2**

votes

**0**answers

314 views

### Incremental minimum spanning tree

Given a connected graph $G=(V,E)$ with a weight function $w:E\to\mathbb{R}$ and a subset $E_0\subseteq E$ such that the subgraph $(V,E_0)$ is connected, I am looking for a sequence $E_0\subseteq ...

**2**

votes

**0**answers

90 views

### A Conjecture related to minimization of product of determinants over permutations

Hi
I have the following problem (and a conjecture which holds in Matlab).
Given an $N\times N$ matrix $H$, represent it by its $2N\times 2N$ real-valued representation (which I will also denote by ...

**2**

votes

**0**answers

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

**2**

votes

**0**answers

75 views

### Approximating solutions to minima of the discrete Lagrangian

I have been stuck on this problem for a week and I'm not sure whether or not it is hard or I'm just missing something obvious.
General gist of the problem
I have a variational problem on a ...

**2**

votes

**0**answers

156 views

### Honeycomb-type properties of the Delaunay triangulation and Voronoi diagram

Suppose I'd like to distribute a set of points $P=\lbrace p_1 ,\dots, p_n \rbrace$ in the unit square $S=[0,1]\times[0,1]$ to minimize a weighted sum of two things:
1) The average distance between a ...

**2**

votes

**0**answers

205 views

### Copositive matrix?

I want to check under what conditions a matrix of the form $\alpha J -Q$ is copositive, where $J$ is the all-ones matrix and $Q$ is doubly nonegative (i.e. entrywise nonnegative and positive ...

**2**

votes

**0**answers

82 views

### Minimum time planar paths under a bound on magnitude of acceleration

On a plane, given initial position (x1,y1), initial velocity (u1,v1), final position (x2,y2), and final velocity (u2,v2), compute the solution to x''= cos(z), y''=sin(z) that has these endpoint ...

**2**

votes

**0**answers

501 views

### The marriage problem on NBC's “The Voice”

I'm a long time lurker here just never got around to registering so excuse the lack of reputation points.
So most people here are aware of the marriage problem: You're given a known number of ...

**2**

votes

**0**answers

183 views

### Projecting the unit cube onto subspaces of dimension at least $2$

This is an updated revision of a recent question where I asked:
Given a set $S$ of non-zero vectors in $\mathbb{R}^n,$ and a subspace $L,$ consider $f(S,L)=\max_{s \in S}\frac{\|Ps\|_2}{\|s\|_2}$ ...

**2**

votes

**0**answers

159 views

### modification of singlestart in global optimization

When minimizing a nonconvex function $f : \Omega \rightarrow \mathbb{R}$ that may have multiple minima, there are some very simple strategies to improve the odds of finding the global minimum point. ...

**1**

vote

**0**answers

52 views

### Optimization with random matrix

Consider $J$ a random matrix of size $n\times n$ with i.i.d. Gaussian entries $J_{ij} \sim \mathcal{N}(0,\sigma^2/n)$. Let $f(x)=tanh(x)$, and for $x\in\mathbb{R}^n$, $f(x)$ denotes the vector where ...