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

learn more… | top users | synonyms

0
votes
1answer
54 views

Finding the right σ-algebra. Question on uncertainty related to the secretary problem

Assume a number of iid. items is presented and the task was to stop under the objective of picking the best item. In this setting it is relevant what is the distribution of the values of the ...
0
votes
1answer
413 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 ...
7
votes
5answers
1k views

Robust black box function minimization with extremely expensive cost function

There is an enormous amount of information about the common applied math problem of minimizing a function.. software packages, hundreds of books, research, etc. But I still have not found a good ...
2
votes
1answer
32 views

Edge-disjoint paths avoiding some subgraphs

Let $G$ be a directed graph on $n$ vertices. Let $H_1$, ..., $H_k$ be marked subgraphs of $G$. (Specifically, each $H_i$ consists of a subset of the vertices of $G$ and a subset of the edges of the ...
3
votes
1answer
102 views

Choosing $K$ “centers” from the space of permutations

Let $\Pi$ denote the space of all permutations of $\{1,\dots,n\}$, and let $d(\cdot,\cdot)$ be a metric on $\Pi$. Suppose I am given a large integer $K$ and I have to select $K$ permutations ...
7
votes
5answers
1k 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 ...
2
votes
0answers
100 views

Are singular critical points isolated for control systems on compact semisimple Lie groups

Given a control system on $\mathrm{SU}(n)$ (or any other compact, semi-simple Lie group I suspect) of the form: $\frac{d U_t}{dt} = (A + w(t)B)U_t$ where $A,B \in \mathfrak{su}(n)$ generate the ...
2
votes
2answers
107 views

Orthogonal Procrustes problem with Absolute Values

Given a non-negative matrix $T$, how to find a orthogonal matrix $O$ minimising $$ \left\lVert \, |O| - T \right\lVert_F,$$ where $\lVert \cdot \lVert_F$ denotes the Frobenius norm, and $| \cdot |$ ...
6
votes
1answer
1k views

Difference between 'generalized gradient' and 'subgradient' ?

Hi, I am wondering what the difference between 'generalized gradient' and 'subgradient' of a (potentially non-differentiable) convex function 'f' is. The generalized gradient I am interested in is ...
14
votes
4answers
477 views

Maximum of the Vandermonde determinant / minimum of the logarithmic energy

The problem is to find the asymptotics (as $n\to\infty$) of the maximum (say $M_n$) of the Vandermonde determinant $$V_n:=\prod_{0\le i<j\le n-1}(a_j-a_i) $$ over all $a_0,\dots,a_{n-1}$ such ...
2
votes
1answer
33 views

Specific discrete system $x_n = A(n,u)\cdot x_{n-1}$ control papers

Basic discrete control theory mostly studies systems which can be represented as $x_n=A(n)x_{n-1}+B(n)u_n$. I wonder if optimal control of specific discrete systems of the type $x_n = A(n,u)\cdot ...
8
votes
1answer
263 views

An inequality on the simplex involving $x^x$

Is anything known about the behavior of the function $$f(x)=\prod_{i=1}^n x_i^{x_i}$$ on the standard simplex, i.e. the set $\{x\in\mathbb{R}^n:\sum_{i=1}^n x_i=1, x_i\geq0\}$? I ask because I have ...
5
votes
3answers
327 views

Euler-Lagrange equations and Bellman's principle of optimality

One method to optimize the integral $$\int_{\mathcal T} L(t,x,\dot{x}) \; dt $$ of a functional over a curve is the calculus of variations, which leads to ordinary differential equations: the ...
1
vote
0answers
55 views

The state-transition-matrix of a physical system,

Here's a simple but potential research problem that I am learning about. Let's say I am studying a physical system that is governed by N objects. At each time, each object is either "active" and ...
1
vote
0answers
32 views

computational-expensive signal reconstruct - a combination problem [closed]

My problem is: I have a time series signal (vibration signal), use BSS algorithm (Blind Source Separation, we can regard it as a black box), separate the source signal into 100 components. Now I ...
1
vote
1answer
177 views

Max Absolute Difference of Expectations under Change of Measure

Given a sample space $\Omega=\{ 1,\cdots,N \}$, a random variable $x$ defined on $\Omega$ that takes value $x_1,\cdots,x_N$, and a set of strictly positive real numbers $w_1,\cdots,w_N$. Define for ...
0
votes
0answers
60 views

Optimization with vectors

I am trying to solve the following optimization problem as a small part of a research project, and I do not know if there exists closed form solutions. My linear algebra is very rusty and I am looking ...
1
vote
1answer
192 views

Covering max flow arcs by arc disjoint paths

Let $(N,A,s,t,u)$ be a network with node set $N$, arc set $A$, source $s\in N$, sink $t\in N$ and capacity vector $u\in\{1,2,\ldots,T\}^A$, and let $x=(x_a)_{a\in A}$ be a maximum $(s,t)$-flow. Is it ...
0
votes
0answers
47 views

About identifying a few diagrams

Please have a look at these beautiful seminar slides, https://math.berkeley.edu/~bernd/coimbra1.pdf Can someone kindly identify the algebraic description of the spectrahedron that is drawn on slide ...
1
vote
0answers
55 views

Hessian matrix positive definiteness (concavity test) [closed]

I have a rather simple scenario based optimization problem: Maximize $$ Q_1{_s}(A_1{_s}-Q_1{_s}-bQ_2{_s})+ Q_2{_s}(A_2{_s}-Q_2{_s}-bQ_1{_s})-[(Q_1{_s}-K_1)^+ + (Q_2{_s}-K_2)^+]c $$ subject to ...
3
votes
1answer
112 views

Global minimum of nonlinear least square

We have a continuous and differentiable function $f(\cdot)$ that maps from $R^n$ to $R^n$. We are trying to solve a nonlinear least square problem: Minimize $J(x)=\Vert f(x)-z\Vert^2$ subject to box ...
9
votes
4answers
538 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
0answers
49 views

Separable Least squares - is there a notion of conjugate directions?

I have a general question. Suppose I have the following to optimize $$\|Y-A(\mathbf{x})B(\mathbf{y})\|^2$$ where $Y$ is a vector, $A(\mathbf{x})$ is a matrix that depends on a vector $\mathbf{x}$ in a ...
0
votes
1answer
100 views

Is the linear production game a convex game?

In cooperative game theory, the linear production game (LPG) is defined by letting the characteristic function have the form of a linear programming problem. Does anyone know if the LPG is a convex ...
1
vote
1answer
43 views

On optimizing a function whose projection and projected vector go through a linear transformation

Assume the two sets of vectors $\{\mathbf{a}_1,\ldots,\mathbf{a}_N\}$ and $\{\mathbf{b}_1,\ldots,\mathbf{b}_N\}$ of equal length. My goal is to find the optimum matrix $\mathbf{C}$ to the following ...
0
votes
0answers
28 views

Maximisation of a discrete linear function

I am trying to maximise the function $$ Q=\sum_i{\alpha _{i}x_{i}} $$ subject to the constraint $$ W<=\sum_i{\alpha _{i}w_{i}x_{i}} $$ By changing $\alpha _{i}$ subject to $ 0<=\alpha ...
0
votes
0answers
63 views

Curves in $\mathfrak{su}(n)$ with specific property

Consider a curve $\gamma_s= U_s^{\dagger} b U_s$ in $\mathfrak{su}(n)$ where $U_s$ is a smooth curve on $SU(n)$ (starting at $U_0 = \mathbb{I}$) and nonzero $b\in \mathfrak{su}(n)$ and $s \in[0,T]$ ...
2
votes
2answers
185 views

What is the dual of an semidefinitely representable (SDR) cone?

The Question Let $V\simeq \mathbb{R}^r$ be an $r$-dimensional vector space with the usual Euclidean inner product. Let $\mathcal K\subset V$ be a cone defined as $$ \mathcal K=\Big\{x\in V\ ...
10
votes
2answers
284 views

More general than semidefinite program?

I was TAing my convex optimization class and explaining that Linear Programs are a special case of Second Order Cone Programs, which are themselves special cases of Semidefinite Programs. My question ...
0
votes
0answers
26 views

Equivalence between multiclass SVMs, power diagrams, and constrained $k$-means

Apologies in advance for the long post: Suppose we have a collection of points $\mathbf{p}_1,\dots,\mathbf{p}_n$ in $\mathbb{R}^d$, and we consider the following three ways of partitioning these ...
4
votes
1answer
253 views

Kalman filters and stock price prediction

Could someone be so kind as to direct me to a good source that would explain time series (more specifically) stock price prediction using Kalman filters, Extended kalman filters or particle filters. ...
1
vote
0answers
89 views

approximation of rational functions

Suppose $\hat{p}/\hat{q}$ and $p/q$ are two rational functions where $p,q,\hat{p},\hat{q}$ are of degree $n$. Suppose they satisfy that $|p(z)/q(z) - \hat{p}(z)/\hat{q}(z)| < \epsilon$ for any $z$ ...
0
votes
0answers
18 views

Can MDPs over functions be solved?

I understand that dynamic programs are difficult to be solved in general. However I have an MDP, for which intuitively I have a solution, I am curious to know if there is a formal approach to get a ...
11
votes
4answers
4k views

“You can't push a rope” [closed]

"You can't push a rope" is a wisdom saying that some engineering teachers pass along to their students. Since I'm not an engineer, I can only guess at what they mean, but it sounds to me like code ...
0
votes
0answers
22 views

Maximizing modular function subject to supermodular constaint

I'm trying to solve a constrained optimization problem with submodular functions and get some nice properties of the solution. Unfortunately, I think I am in a setting where Topkis' theorem does not ...
0
votes
0answers
20 views

Bounding the error of the optimal solution from an approximated objective

Let $f$ be a smooth convex function defined in a bounded region $X$ and its Hessian is bounded $m I \le |\frac{\partial^2 f(x)}{\partial x^2}| \le M I$ for some $M>m>0$. Let $x^*=argmin_{x\in X} ...
0
votes
0answers
47 views

Applications of systems with multiple time

A dynamical system with multiple time is an action of a group $\mathbb{Z}^d$ or $\mathbb{R}^d$ on a metric space. I am interested in informative examples and applications of such systems. I know ...
4
votes
0answers
200 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 ...
1
vote
0answers
18 views

Deterministic global solution to find the Optimal-knot placements for continuous piecewise linear functions to fit nonlinear data

I have been searching lately for a deterministic global technique to linearize a nonlinear function with continuous piecewise linear regions. I've a univariate nonlinear function y=f(x). where f(x) ...
2
votes
0answers
51 views

Is there a name for this variant of the MST and the TSP?

Suppose I am given a weighted graph $G$ that contains a "start vertex" $v_0$, and my goal is to construct a set of paths that all originate at $v_0$ and touch all of the vertices of $G$, with as ...
3
votes
1answer
373 views

A min-max formula for depth of the origin in a convex set

Depth is defined as the distance to the boundary of a set, i.e., $\operatorname{depth}(x, C) = \operatorname{dist}(x, \mathbb{R}^n \backslash C)$. Let $C$ be a convex set that contains the origin. I ...
1
vote
0answers
31 views

solution of an infinite horizon optimization problem

Give the following formulation: $\min_{\{x_s(t):\forall s,t\}} \sum_{s \in \mathcal{S}} \mathbf{1}\left(\lim_{T\rightarrow \infty} \frac{1}{T} \sum_{t=1}^T \frac{y_s(t)}{x_s(t)}\leq 1\right)$ $s.t. ...
0
votes
1answer
57 views

Solving a nonlinear optimisation problem

I have the following nonlinear optimisation problem arising in my model. $$\min \sum_{k=0}^{N-1} (\tau-t_k)^+\quad \text{ s.t. } {\mathbf{x}^\top\mathbf{w}\le W,\ \mathbf{x}\ge0}, t_k=t_{k-1}+x_k ...
1
vote
2answers
194 views

The term for problems “like” Brachistocrone?

Is there a commonly-accepted umbrella term for infinite-dimensional calculus problems where the goal is to compute an optimal geometric path between a pair of points? Three examples of this would be ...
2
votes
0answers
86 views

Solve non-linear Optimization Problem [closed]

I have to find $x$ that minimizes: $$ \sum_{k}(x^H\textbf A_kx - b_k)^2$$ where $A_k$ are 4 x 4 positive definite matrices ($A_1, A_2,...A_k$), $x$ is 4 x 1 vector and $b_k$ are scalars ...
8
votes
2answers
220 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 ...
1
vote
0answers
160 views

A path optimisation problem

Consider a graph of $n$ nodes randomly located in $[0,1]^2$. Each node moves following a path randomly chosen from the set of all possible paths. Regard nodes as attackers. A policeman seeks an ...
3
votes
1answer
121 views

Singular curves of affine distributions on a Lie group

Are there any results about the rigidity of singular curves of rank 1 affine distributions on a connected compact Lie group? Specifically the case of a right invariant affine distribution: $D_{U} = ...
2
votes
0answers
70 views

Learning rule for recurrent neural network with flexible time steps

Summary: I want to train a recurrent network to output some answers, but the recurrent network is allowed to re-iterate through itself a flexible number of times for each input-output pair. Why this ...
0
votes
2answers
272 views

Mediated envy-free and efficient cake cutting with n=2?

Is there an algorithm in literature to compute an efficient (pareto optimal) and envy-free cake cutting when there are only $n=2$ players and a mediator?