Operations research, linear programming, control theory, systems theory, optimal control, game theory

learn more… | top users | synonyms

27
votes
0answers
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$, ...
8
votes
0answers
240 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
0answers
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
0answers
46 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
0answers
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
0answers
412 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
0answers
136 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
0answers
75 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
0answers
130 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
0answers
89 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
0answers
163 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
0answers
177 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
0answers
302 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
0answers
287 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
0answers
476 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
0answers
94 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
0answers
81 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
0answers
33 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 ...
3
votes
0answers
217 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
0answers
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
0answers
103 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
0answers
254 views

An S-lemma for polynomials of degree 4 in three variables

Might the following be true: Let $p,q\in\mathbb{R}[x,y,z]$ be homogeneous polynomials, with $\deg(p)\leq 4$ and $\deg(q)= 2$. Suppose $q(x,y,z)>0$ for some $x,y,z\in\mathbb{R}$. Then the ...
3
votes
0answers
150 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
0answers
320 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
0answers
319 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
0answers
237 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
0answers
115 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
0answers
87 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
0answers
28 views

kalman filter with delayed (outdated) information

We have a linear system with observation as follows: $x(t+1)=Ax(t)+Bu(t)+w(t)$ $y(t)=Cx(t)+z(t)$ for given information $y(0\sim t)$, we can construct the dynamics of $\hat{x}(t)$ using the Kalman ...
2
votes
0answers
120 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
0answers
33 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
0answers
95 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
0answers
138 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
0answers
250 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
0answers
174 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
0answers
273 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
0answers
88 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
0answers
149 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
0answers
72 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
0answers
151 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
0answers
200 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
0answers
342 views

Partial feedback linearization (Control theory)

Greetings, I'm trying to understand a theorem about partial feedback linearization from a paper "On the largest feedback linearizable subsystem" by R.Marino (you can find it here: ...
2
votes
0answers
81 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
0answers
497 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
0answers
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
0answers
158 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
0answers
30 views

Optimization of a multilinear function over a product of hypersimplices

Let $P = \Delta_1 \times \cdots \times \Delta_N$ be the Cartesian product of $N$ hypersimplices. Let $f : P \to \mathbb{R}$ be a multilinear function of $N$ variables, ie $x_i \mapsto f(x_1, \ldots, ...
1
vote
0answers
34 views

Theorems on stochastic Lyapunov function

Let $X_n$ be a sequence of random variables such that $$P(X_{n+1} \in A|X_m,x_m,m\leq n)= \int_A p(dw|X_n,x_n)$$ It is called a controlled Markov process. Now, suppose there exist $\epsilon_0$, ...
1
vote
0answers
115 views

lower bound for difference between max cut and min cut

Let $G=(V,E)$ be a graph on $n$ vertices with edge weights $w=(w_e)_{e\in E}$. Let $M^+$ and $M^-$ be the maximum and the minimum cut values, i.e. ...
1
vote
0answers
102 views

An optimization problem for a Markov Chain

Consider a Markov Chain $\{X_n\}$ whose transition probability depends on some parameter $\theta$ ($p_{ij}(\theta)$). Now I want to optimize the following quantity $$\lambda(\theta) = ...