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

learn more… | top users | synonyms

3
votes
2answers
574 views

Problem equivalent to “largest square in a cube”

The "largest square in a cube" problem, which asks for the largest square inside a cube, has a solution as can be seen on this page, which also says that the general problem in higher dimensions is ...
0
votes
0answers
27 views

How is constrained optimization done? [on hold]

I am trying to implement an optimizer described in http://arxiv.org/pdf/1406.2572v1.pdf I have an objective function, gradient and hessian. The algorithm for unconstrained optimization is described ...
5
votes
2answers
335 views

Heaviest Convex Polygon

Suppose we have an arbitrary function $f : \mathbb{R}^2 \to \mathbb{R}$. For any subset $s \subseteq \mathbb{R}^2$, we can define $g_f(s)$ as the integral* of $f$ over the region $s$. Suppose ...
2
votes
1answer
52 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$. ...
7
votes
2answers
393 views

How to solve such an optimization problem

I encounter the following optimization problem, but I can't solve it. Given $N$ variables satisfying $0 \leq x_1 \leq x_2 \leq x_3 \leq ... \leq x_N \leq 1$ and an integer $K$ no large than $N$, find ...
1
vote
1answer
170 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 ...
-2
votes
0answers
85 views

exponential columns and rows in Linear programming [closed]

In one of my previous post, I mention a Linear programming system with exponentially many constraints and variables Linear programming with exponentially many constraints and variables . It is ...
0
votes
1answer
83 views

A problem on about a matrix norm on $\mathfrak{su}(4)$

Given a fixed $B \in \mathfrak{su}(4)$ is it possible to solve for $F$: $\sigma^{\text{max}}\left(\frac{A}{F(A)} + B \right) = 1$, $\forall A \in \mathfrak{su}(4)$. A theorem in ...
3
votes
0answers
58 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 ...
2
votes
2answers
304 views

High dimensional Steiner tree

Given n affinely independent points in n-1 dimensional Euclidean space, how is the minimum Steiner tree constructed? Or assuming that the topology of the Steiner tree is given, is there an easy way ...
7
votes
3answers
312 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 ...
0
votes
1answer
64 views

Linear programming with exponentially many constraints and variables [closed]

From class, I learnt that problems like traveller salesman have a Linear programming representation with exponentially many constraints. Using method of separation, this problem is solved rather ...
1
vote
0answers
99 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
2answers
102 views

Combinatorial optimization problem involving infinite spin system

In material science research, I am developing an algorithm to solve an infinite combinatorial optimization problem which I believe is the most natural problem when the system size goes to infinity. ...
28
votes
1answer
1k views

Optimization problem arising from the study of zeta zeros

Motivation: The following problem arose in [1] while studying the vertical distribution of the zeros of the Riemann zeta-function. At the time, my collaborators and I were unable to solve it and I ...
0
votes
1answer
158 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 ...
0
votes
1answer
402 views

eigen-decomposition solution? is it unique?

Assume an N*N covariance matrix (Q) which is a positive definite matrix. The decoder X is assumed to be N*s, where s<=N. X is calculated to be s eigenvectors corresponding to s minimum eigenvalues. ...
0
votes
0answers
23 views

Optimization problem involving an entrywise function

Let $X$ a $n\times p$ real-valued matrix and $Y$ a $p\times q$ real-valued matrix. Let $\phi:\mathbb{R} \to \mathbb{R}$ a function. What is the appropriate way to deal with the following optimization ...
2
votes
4answers
259 views

Algorithm to find the “optimal” path in a given graph

Assume that $G=(V,E)$ is an undirected connected graph and that $H: V \to \mathbb R$ is a function that assign at each vertex $v \in V$ its height $H(v)$. Think of the pair $(G,H)$ as an energy ...
3
votes
2answers
3k views

Linear program to maximize the minimum absolute value of linear functions ?

I'd like to compute $\max_{x,t} t$ such that $\forall i$, $t < a_i + |x - b_i|$. where $a_i,\ldots, a_n$ and $b_1,\ldots,b_n$ are fixed and $x \in [0,1]$. Can this be solved with a linear ...
0
votes
1answer
43 views

Generalized assignment problem with no integrality gap

Suppose I am solving the generalized assignment problem, so that I am given matrices $U$ and $W$ and a vector $c$ (all three of which have, say, positive entries), and I want to solve ...
-1
votes
0answers
27 views

Finding the source for minimizer of a functional for all $C^2$-curve $x(t_0)=x_0$ and $x(t_1)=x_1$

I am trying to find where this problem comes from and its corresponding proof for my students, but I cannot find the source anywhere. If anyone can find the source of this, or has any ideas where I ...
2
votes
0answers
22 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
64 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 ...
6
votes
1answer
239 views

Generalization of the equilateral triangle?

I consider points in the two-dimensional plane. An equilateral triangle is a set of three points in the plane which are equidistant. Suppose now I have $n$ points $x_1,...,x_n$. What is the ...
4
votes
1answer
49 views

What are the upper bound and stability conditions for the following simple linear system?

Consider the following linear system $$\dot{x}=\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}\left( t \right)\cdot {{A}_{i}}\cdot x \quad (1) $$ where, $x\in {{\mathbb{R}}^{n}}$ represents the state vector, ...
2
votes
2answers
381 views

Why does not the Hamiltonian depend on the derivative of the state?

I am reading "Optimal Control Theory" from Kirk. When solving the optimal control problem, there is defined The Hamiltonian $H(x(t),u(t),p(t), t)$ as $g(x(t), u(t), t) + p [a(x(t), u(t), t]$ where ...
0
votes
1answer
68 views

equation for geodesics of a right invairant Finsler metric on $SU(n)$ which are parallel to a linear affine distribution

I am looking for an equation analogous to the Euler-Poincare equations for a right invariant Finlser metric except I want the geodesics which are parallel to a linear affine distribution on $SU(n)$. ...
0
votes
0answers
17 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
54 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) = ...
4
votes
0answers
69 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 ...
2
votes
0answers
27 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
46 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
96 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
79 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 ...
4
votes
4answers
307 views

Linear complementarity problem - Tridiagonal and Convex Case

I need an algorithm for the following LCP: $\mathbf{Mz}+\mathbf{q} \ge \mathbf{0}$ $\mathbf{z} \ge \mathbf{0}$ $\mathbf{z}^{\mathrm{T}}(\mathbf{Mz}+\mathbf{q}) = 0$ Here, $\mathbf{M}$, is a ...
0
votes
0answers
36 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} ...
2
votes
1answer
145 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 ...
6
votes
2answers
151 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
32 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 ...
6
votes
4answers
571 views

solving Lyapunov-like equation

The following matrix equation might be a Lyapunov-like equation, but it seems hard for me to develop a simpler way to solve it. From the computation effort, I need some help for solving the special ...
0
votes
2answers
65 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 ...
1
vote
1answer
166 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| ...
4
votes
0answers
103 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 ...
14
votes
3answers
642 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
38 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
19 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 ...
5
votes
1answer
263 views

Geometric applications of Ekeland's variational principle

I'm looking for geometric applications of Ekeland's variational principle in order to see it at work in a context I'm familiar with. Let me recall the principle itself: Definition. Let $(X,d)$ be a ...
2
votes
1answer
180 views

Optimal Control

Consider the optimal control problem with an optimal trajectory $x^*(t)$ and an initial point $(x_1^0,x_2^0)$ \begin{equation} \begin{split} \dot{x}=A x + Bu \\\ J=\int^\infty_0(x_2^2+\epsilon u^2)dt ...