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

learn more… | top users | synonyms

3
votes
2answers
165 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 ...
4
votes
2answers
363 views

Simplified knapsack problem

There is a problem that I can not solve. Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...
3
votes
1answer
178 views

Fast algorithm for maximizing smallest eigenvalue of linear combination of hermitian matrices

I have an engineering back ground. Due to work, I came across this problem \begin{align} &\max_{\lambda,y_i\in \mathbb{R}}~\lambda \\\ ...
0
votes
1answer
64 views

About the suboptimality of linear estimators

Let $X$ be a random variable and $N$ a Gaussian noise independent from $X$. We observe $Y=X+N$ and want to estimate $X$ based on $Y$ to minimize the mean square error $mmse(X|Y):=E(\hat X(Y)-X)^2$. ...
0
votes
0answers
100 views

Modifying a QP to incorporate more constraints

Consider the following problem: $$\min \sum_{i=1}^n (Y_i - Z^{(i)})^2 \\ \text{subjected to}~ \epsilon_k^{\top}(X_j-X_k) \leq Z^{(j)}-Z^{(k)} ~ \forall k,j = 1 \ldots n. $$ where $\epsilon_1, ...
1
vote
0answers
70 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 ...
0
votes
0answers
137 views

If $\phi_n$ is a sequence of mollifier converging to the identity, does $\inf f\ast \phi_n \to \inf f$?

Let $\phi_n$ be a sequence of mollifier converging to the identity $$ \phi_n(x) \to \delta_{0}(x), \text{pointwise}, $$ with $\delta_{0}(\cdot)$ the delta function at zero, and $\phi_n \in ...
0
votes
0answers
42 views

fundamental optimal-trajectory result known?

It's well-known and obvious that if you have a spaceship and your sole constraint is an upper bound on magnitude of acceleration/deceleration, the fastest way to get to a distant star (a fixed ...
2
votes
1answer
200 views

More than controlability: Speed of controllability!

Consider the continuous linear time-invariant system $$ \begin{array}{l} \dot{\mathbf{x}}(t) = A \mathbf{x}(t) + B \mathbf{u}(t)\\ \mathbf{y}(t) = C \mathbf{x}(t) + D \mathbf{u}(t) ...
0
votes
1answer
342 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. ...
3
votes
0answers
198 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 ...
2
votes
1answer
154 views

Upper bounds on the worst-case traveling salesman tours in the unit square

The paper [1] proves that, if we place $N$ points in the unit square, then the length $\ell$ of the euclidean TSP tour of those points must satisfy $$\ell \leq \sqrt{2N} + 7/4~~.$$ I'm wondering, can ...
2
votes
1answer
139 views

optimization over positive semidefinite matrices

I wonder what is the most explicit characterization that can be given for the solution to the ($N$-dimensional) problem of maximizing the criterion $$ -\textrm{trace}[AS^{-1}] - b^\top Sb $$ over ...
-2
votes
1answer
106 views

A kind of economic objective function in assignment

I recently thought about a concept that seems like it should come up in economics, but I don't know if there's a name for it and where people would have encountered it elsewhere: Suppose we have a ...
2
votes
1answer
53 views

Stability of a stable systems with a converging input

Does the following hold? Let $x=0$ be an equilibrium point for the system $\dot x(t)=f(x(t))$ and suppose the existence and uniqueness conditions of solutions on $[t_0, +\infty)$ are satisfied. If ...
1
vote
1answer
60 views

On impulsive optimal control with functions of not bounded variation

I have the following optimal control problem $$ J=\int_0^TF(t,y_1(t),y_2(t))dt \to \min, $$ subject to \begin{align} &\dot y_1(t) = f(t,y_1(t),y_2(t)) + g(t)\nu(t),\\ &\dot y_2(t) = ...
3
votes
1answer
185 views

Intuition on a certain class of quadratic optimization problems

Let $\mathcal{X} = \{\mathbf{X}\in\mathbb{C}^{d\times d}:\|\mathbf{X}\|\leq 1\}$, where $\|\cdot\|$ is the Frobenius norm. Let $\mathbf{y}\in\mathbb{C}^{d\times 1}$. We are familiar with the following ...
1
vote
1answer
198 views

Semi Definite Relaxation for a Quadratic Feasibility Problem using CVX

Consider the following Semi-Definite Feasibility problem \begin{align} \max_{\mathbf{Z}}~0 \\\ \mathrm{trace}(\mathbf{Z})\leq \rho \\\ \mathrm{trace}(\mathbf{S}_1\mathbf{Z}) \geq \alpha \\\ ...
3
votes
1answer
151 views

Explicit formula for an LMI solution

Suppose we have a linear matrix inequality (aka LMI aka spectahedron aka linear matrix pencil): $$A_{0}+x_{1}A_{1}+x_{2}A_{2}+\ldots+x_{m}A_{m} \succeq 0.$$ (The notation $X \succeq Y$ means that ...
3
votes
3answers
335 views

A NICE necessary and sufficient condition on positive semi-definiteness of a matrix with a special structure!

Let $$ A = \begin{pmatrix} \sum_{j\ne 1}a_{1j} & -a_{12} & \cdots & -a_{1n}\\ -a_{21} & \sum_{j\ne 2}a_{2j} & \cdots & -a_{2n}\\ \vdots & \vdots & \ddots & ...
4
votes
2answers
115 views

A certain type of constrained Rayleigh-Ritz ratio

Let $\mathbf{A_1}$ and $\mathbf{A_2}$ be two hermitian matrices. Consider the problem \begin{align} \max_{\mathbf{u}^H\mathbf{u}=1}~\mathbf{u}^H\mathbf{A}_1\mathbf{u} \\\ ...
0
votes
1answer
248 views

Anyone has Kushner's book “Introduction to stochastic control” 1971? I need a theorem from it

In a paper I'm reading, it refers to Theorem 8, Page 217 of the book "Introduction to Stochastic Control" H. J. Kushner, New York: Holt, Reinhart, and Winston 1971. Unfortunately I don't have it and ...
1
vote
0answers
84 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 ...
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 ...
2
votes
0answers
152 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 ...
-1
votes
1answer
129 views

Regularized Gradient with respect to a matrix (with a specific structure)

Suppose we have a typical logdet function $\mathcal{L}$ $$ \mathcal{L} = \log\vert \mathbf{I} + \mathbf{A}\mathbf{S} \vert - \mathbf{q}^T(\mathbf{A}^{-1} + \mathbf{S})^{-1} \mathbf{q}, $$ where ...
3
votes
1answer
193 views

Delta-convex functions and inner products

A delta-convex (d.c.) function is one which can be written as the difference of two convex functions. The space of d.c. functions includes all C2 functions, and is interesting because it allows many ...
2
votes
0answers
166 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$, ...
0
votes
1answer
206 views

solve non-convex quadratic constrained quadratic programming

$\min_{\beta}\beta^{T} A \beta$ $s.t. \ \beta^{T} C \beta=1\ and\ \beta\geqslant 0$ Here $A,C\in \mathbb{R}^{M\times M}$, $\beta \in \mathbb{R}^{M}$ I saw in one paper saying that it could be ...
2
votes
1answer
188 views

How to maximize the determinant of a matrix of the form VDV^H

Hi, I have a matrix of the form $A=VDV^H$, where $V$ is a $M \times 2M$ complex matrix, $D$ is a $2M \times 2M$ diagonal real matrix, thus the dimension of $A$ is $M \times M$. My problem is how ...
1
vote
2answers
209 views

On a version of gradient descent

I am trying to read this paper and have gotten stuck. The author considers the problem of minimizing a convex function whose gradient has Lipschitz constant $M$ and considers the scheme $$ x(t+1) = ...
-1
votes
1answer
137 views

To what equal constant in the Gibbs lemma

The Gibbs lemma is broadly used in games theory and in mathematical economics (optimal distributions of resourses, Cournot competition e.t.c.). Here it is: Lemma (Gibbs). $f_1,f_2,\ldots,f_n$ be ...
1
vote
0answers
270 views

A detail in the proof of the Motzkin-Straus theorem

The Motzkin-Straus theorem says that the global optimum of the quadratic program $$\max f(x)=\frac{1}{2} x^{t}Ax,\qquad \mbox{ subject to }\sum x_{i}=1 \mbox{ and } x_{i}\geq 0,$$ where $A$ is the ...
0
votes
0answers
169 views

A tricky optimization problem over matrices

Hi I have the following problem whose solution has lured me for some months now.... All matrices are complex $N\times N$. Let $A$ be a positive definite matrix with all eigenvalues strictly smaller ...
1
vote
0answers
88 views

null controllability of linear wave equation

Consider the linear wave equation : $$z_{tt}=\Delta z + k(x) z + h(t) , \; in \; \Omega\times (0,T)$$ Are there sufficient conditions on the functions $k(x)$ and $h(t)$ for which $(z,z_t)$ vanish ...
2
votes
0answers
203 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
84 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
137 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 ...
1
vote
0answers
54 views

strong stability for the wave equation

Consider the $n-$dimensional wave equation $$z_{tt}=\Delta z + k(x) z - \epsilon {1}_\omega z_t, \; in \; \Omega\times (0,T)$$ where $\omega\subset \Omega.$ Can I have $z(t) \to 0,$ as $t\to+\infty$ ...
1
vote
0answers
92 views

Compactness of the set of solutions to an ODE

I am interested in optimal control problems with state constraints in the form of ordinary differential equations given by $\dot{x} = f(x,p), \quad t \in [0,T], \quad x(0) = x_{0}, \quad p \in K$, ...
0
votes
1answer
60 views

Representation of all pass transfer functions/inner functions as Blaschke product.

What is the proof for: 'An all pass transfer function/inner function can be represented by a Blaschke Product' ?
1
vote
1answer
111 views

Control a linear system to the kernal space of the output matrix.

Consider the following controllable and observable linear system $$\dot x=Ax+Bu, y=Cx,$$ where $x\in \mathbb{R}^n, u\in \mathbb{R}^m, y\in \mathbb{R}^p$. The observability of $(A,C)$ ...
2
votes
0answers
63 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 ...
1
vote
2answers
147 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 ...
3
votes
0answers
98 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. ...
2
votes
1answer
82 views

Maximal probability of “infinitely often” over MDP

Let us consider a Markov Decision Process (MDP) with a Borel state space $X$. Often, the optimization problems over MDP involve optimization of some objectives dependent on the reward function $$ ...
4
votes
0answers
68 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 ...
0
votes
1answer
84 views

Avoiding epsilon in mixed integer linear and quadratically constrained programs

I would like to represent the following constraint as MILP constraint where $x \in [a, b]$ with fixed $a, b \in \mathbb{R}$ and $y \in \lbrace 0, 1 \rbrace$. $(x = 0 \wedge y = 1) \vee (x \neq 0 ...
3
votes
1answer
450 views

Symplectic block-diagonalization of a real symmetric Hamiltonian matrix

Given a $2n\times 2n$ real, symmetric, Hamiltonian matrix $W$ (anticommutes with the symplectic metric), is there an orthogonal, symplectic matrix $R$ such that $R^\top WR$ is block-diagonal? Being ...
1
vote
1answer
352 views

for what arguments the function reaches maximum?

Hi, What is the maximum of the following function?: $f(x_i,w_i)=\frac { \sum w_i}{ \sum \frac {w_i}{x_i} } - \frac{ 1 - \prod \left ( 1 - w_{i}\right )}{ 1 - \prod \left ( 1 - \frac{w_{i}}{ ...