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

learn more… | top users | synonyms

0
votes
0answers
13 views

Zeros of non-lipschitz functions (when noisy estimates are available only)

Given noisy (martingale difference) of a Lipschitz continuous function $f$ it is known how to compute zeros of it. It is the stochastic approximation approach (by Borkar, Kushner and Yin etc.). Is ...
1
vote
0answers
41 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) = ...
2
votes
0answers
21 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?
0
votes
0answers
40 views

Representation of piecewise functions using variational inequalities

I need some help about how to represent piecewise smooth functions defined over N subintervals by using variational inequalities. From a paper I'm analyzing I get: "If we can find a function ...
1
vote
1answer
87 views

Are there some algorithms to solve the diagonal matrix $X$ to the following matrix equation?

Suppose $X$ is an unknown $m \times m$ diagonal matrix. Given a scalar $0<c<1$, and a matrix $A$ of $m \times m$ size whose entries $0<A_{i,j}<1$. Are there some algorithms to find the ...
1
vote
1answer
136 views

Solving a matrix equation $X=c \cdot AXA' +I$ with a diagonal corrections

I am now struggling to solve the matrix $X \in R^{n \times n}$ in the following equation: $X=c \cdot AXA' - diag(c \cdot AXA')+ I$, where (1) $A \in R^{n \times n}$ is a given matrix whose element ...
1
vote
1answer
72 views

A certain instance of the Set Covering problem

Is there any useful structure associated with the following instance of the Set Covering problem? Let $G$ be a weighted graph and let $\mathcal{P}$ denote the set of all shortest paths between all ...
0
votes
0answers
33 views

A Optimization problem using co-ordinates of joint numerical range.

Let $\mathbf{A}_1,\dots,\mathbf{A}_L$ be $N\times N$ hermitian matrices. Define the mapping from the $N-$dimensional unit sphere to $\mathbb{R}^L$ as \begin{align} ...
6
votes
2answers
146 views

Relativistic Control Theory

I am looking for literature that combines General relativity and control theory. So far I found a video lecture on "Integrability meets Control Theory: Harmonic maps in GR", other than that not so ...
0
votes
0answers
25 views

Stability condition for linear time varying Kalman filter

For the traditional time invariant system: $x(k+1)=Ax(k)+w(k)$ $y(k)=Cx(k)+v(k)$ the stability of $\Delta(t)\triangleq x(t)-\hat{x}(t)$ is the observability of (A, C) pair. What if now C is a ...
0
votes
2answers
57 views

Approximate solution to large mixed integer programming problem

What are the available approaches to find an approximate solution to a large mixed integer programming problem? I ran my problem in the Gurobi MIP solver. It can find a feasible solution in ...
1
vote
0answers
19 views

Minimal rectangular confidence regions

For a given multivariate pdf $f$ (mainly the gaussian one) I'm looking to compute a minimal rectangular confidence region for a given level $\alpha$. For example, I would like to solve problems of the ...
3
votes
0answers
96 views

Rank 1 Approximation of Elementwise Inverse Matrix

I'm wondering whether there is a good way to solve the following optimisation problem. Given a strictly positive quadratic matrix $A$, find two diagonal matrices $D_1$ and $D_2$ so that $$ \| D_1 A ...
1
vote
1answer
162 views

System of quadratic complex equations

I want to solve this system of N non-linear equations without using a numerical method: $x_{k}^{2}= \alpha_{k }+ \sum\limits_{m=1}^{N} (\beta_{km} x_{m} + \psi_{km} x_{m}^{*})$ With $\left| ...
2
votes
1answer
139 views

Optimization problem whose cardinality never exceeds 7 for some reason

I am working on a problem in which I have a collection of $n$ points, $x_1,\dots,x_n$, in the plane, as well as a positive definite matrix $\Sigma$ and another point $\mu$ in the plane. I am trying ...
14
votes
3answers
581 views

“Entropy” proof of Brunn-Minkowski Inequality?

I read in an information theory textbook the Brunn-Minkowski inequality follows from the Entropy Power inequality. The first one says that if $A,B$ are convex polygons in $\mathbb{R}^d$, then $$ ...
1
vote
1answer
35 views

How to find all possible solution in the problem of simplex mesthod in maple? [closed]

I have an object to maximize and some constraints in Maple, but Maple just give me only one solution. How can I get more than one solution, i.e. I would like to know all possible solution for the ...
0
votes
0answers
18 views

Examples of POMDPs where the actions impact the transitions of the underlying markov Chain

I am not sure if the following is a legitimate question for this board. I am looking for examples of Partially observed Markov decision processes (preferably infinite horizon, Discrete time, Discrete ...
8
votes
0answers
192 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 ...
1
vote
0answers
43 views

Special case of Forced Harmonic Oscillator

$$ \frac{d^2l}{dt^2} + c \frac{dl}{dt} +k= F_0\sqrt{1-l^2}$$ Either a closed form or something like given initial conditions, the max value of $l$. For small $l$, this boils down to simple step ...
3
votes
1answer
104 views

A problem related to routing in a graph

I have come across a new problem - I want to know whether this problem is similar to some existing problem or not. The new problem is this. There is a tourist who has a having the following ...
2
votes
0answers
82 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 ...
0
votes
0answers
61 views

Weak convergence of 4-th degrees

Good day! We have an equation $y'+Ay=Bu$ where $y=\{\theta,\varphi\}$, $A, B$ are nonlinear operators. $u \in L^\infty(\Gamma)$, $\theta, \varphi \in W = \{y \in L^2(0,T;V) : y'\in L^2(0,T;V')\}$, ...
3
votes
1answer
66 views

Counting extrema on a simplex

Let $p(x_{1},x_{2},\ldots,x_{n})=\sum_{i,j=1}^{n}{a_{ij}x_{i}x_{j}}$ be a homogenous multivariate polynomial of degree $2$. I would like to know how many extrema $p$ has on the standard simplex ...
0
votes
0answers
40 views

Sequence of solutions of approximated problem converging to stationary solution of the original problem

Let $I(x)$ be the indicator function defined as $$I(x) \triangleq \begin{cases} 1, & x \geq 0 \\ 0, & x < 0 \end{cases}$$ and let $L(x,\alpha) \in [0,1]$ be a smoothing function that ...
0
votes
0answers
18 views

Kalman Filter for coupled difference equations with stochastic volatilty

I am trying to estimate the following discrete-time system using the Kalman Filter: y_t = a*y_t-1 + b*x_t-1 + c+ sigma_1(t)*Z_1,t x_t = d*x_t-1 + e*y_t-1 + f+ sigma_2*exp(g*i_t-1)*Z_2,t v_t = ...
1
vote
0answers
174 views

An optimization problem on the sphere

Let $S$ be a sphere centered at origin in $\Bbb R^{2n}$ of radius $\sqrt{2n}$. Let $D$ be a diagonal matrix. Let $U$ be an orthogonal matrix. Let $r\in\Bbb Z_+$ be a fixed integer. Let vector ...
2
votes
2answers
95 views

Find the optimal set of subsets

Consider a set of $N$ individuals and let their distance be given by $R$, a $N\times N$ matrix. In that, $R(1,2)$ is the distance between individual 1 and 2. Now lets say that I want to separate the ...
5
votes
1answer
121 views

Are there any known results on numerical ranges of rank-one positive semi-definite matrices?

In my problem, I came across numerical ranges of rank-one positive semidefinite matrices. Through Toeplitz-Hausdorff theorem and some other extensions, I know if there are at most three matrices, then ...
2
votes
1answer
135 views

derivative of sum of singular values

can someone point me to the direction how to calculate the derivatives of a sum of singular values of a matrix? I am trying to minimize $$\min_A \parallel A \parallel_*+ \cdots $$ where $\parallel A ...
1
vote
1answer
174 views

Maximizing linear objective function with absolute values

This has be asked on other forums, though couldn't find authoritative answer. I have a linear program over the reals and don't want to introduce integer or binary variables. The objective function ...
2
votes
2answers
127 views

Finding the maximum of a multivariate polynomial of degree one

I need to find the global maximum of the function \begin{align} f\left(x\right) & = p_1 \max\left(\sum a_{1i} x_{1i}, \sum b_{1i} x_{1i}\right) - \sum c_{1i} x_{1i} \\ &+\ldots \\ &+ p_n ...
1
vote
0answers
163 views

Incoherence of the row/column span

Due to V.Chandrasekaran., et al‎ (p.11) : In general for any $k$-dimensional subspace of $A_{n×n}$ we have that: $$\sqrt{(k/n)} \leq incoherence(A)\leq 1$$ where the lower bound is achieved (for ...
1
vote
0answers
96 views

Complexity of Nested Linear Optimization

My question is motivated by the fact, that among other ways, it is possible to restrict a variable to two discrete values, e.g. the prototypical $0$ and $1$, via an optimization constraint: ...
4
votes
2answers
132 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
47 views

generalization from linear programming solution [closed]

I have a series of similar linear programs that depend on an input vector $a\in A$ and whose solution is an output vector $b\in B$. I can solve them individually, but this is wasteful. I suspect that ...
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} ...
0
votes
2answers
92 views

Union of linear inequalities cover whole space?

We have $n$ variables $a_0,a_1,\ldots,a_n$ such that $a_i\geq a_{i+1}$. There are $k$ sets of linear inequality constraints on the $a_i$. I need to check that any choice of $a_i$ satisfies at least ...
1
vote
0answers
133 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 ...
2
votes
0answers
131 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 ...
0
votes
1answer
121 views

Supremum in a Markov chain model

A Markov chain $X$ with finite state space $\{1,2,\cdots,N\}$ is defined on a probability space $(\Omega, P, \mathcal{F})$ equiped with filtration $\{\mathcal{F}_t\}$. And we assume that we can reach ...
1
vote
0answers
98 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
2answers
198 views

Moreau-Yosida regularization in Banach spaces

For a seminar I am working on a Moreau-Yosida regularization in Banach spaces. The regularization is defined by $$f_\lambda(x) := \inf \left \{ \frac{\|x-y\|^2}{2\lambda} +f(y) : y \in X \right \}, ...
1
vote
0answers
41 views

Discrete Optimal Control and Monotone Policies

Let $x = (x_1,x_2) \in \mathbb{N}^2$ be the state, $u$ be the control, and the dynamics be given by $x^{(k+1)} = f(x^{(k)}, u^{(k)}, w^{(k)})$ where $w^{(k)}$ is an IID noise source. For some stage ...
1
vote
1answer
95 views

Kalman filter with long term bias

I was reading about the Kalman filter and I do not understand how it should be used when our measurements have a long term offset like GPS location updates do. As I understand, the Kalman filter ...
3
votes
0answers
29 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
2answers
212 views

Why eigenvectors optimize this orthogonally constrained nonlinear minimization problem?

Given a $p \times p$ positive definite matrix $\Sigma$, why eigenvectors of $\Sigma$, stacked as columns of a matrix $R \equiv [r_1 \, r_2 \, \ldots \, r_p]$, optimize the following orthogonally ...
5
votes
3answers
356 views

Optimization problem on trace of rotated positive definite matrices

Given two $n \times n$ symmetric positive definite matrices $A$ and $B$, I am interested in solving the following optimization problem over $n \times n$ unitary matrices $R$: $$ \mathrm{arg}\max_R ...
1
vote
0answers
92 views

Forcing a set of complex points to be closed under conjugation

I am a PhD student and I have to address the optimization of a real scalar function of complex variables $f(z_1,z_2,\ldots,z_n)$. The function is real valued in my case because each complex $z_i$ ...
3
votes
2answers
162 views

Generalized Moore Graphs

A generalized Moore graph - as defined by Cerf, Cowan, Mullin and Stanton - is one for which the girth G and diameter D satisfy G ≥ 2D - 1. These graphs retain many of the optimal properties of Moore ...