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

learn more… | top users | synonyms

4
votes
2answers
143 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
278 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 ...
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 ...
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
230 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
137 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
221 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
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$, ...
0
votes
1answer
247 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
335 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
211 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
145 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
348 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
207 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
90 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
265 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
146 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
57 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
96 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
68 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
121 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
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 ...
1
vote
2answers
157 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
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. ...
2
votes
1answer
87 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
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 ...
0
votes
1answer
90 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
555 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 ...
6
votes
1answer
243 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 ...
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}}{ ...
3
votes
1answer
189 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 ...
4
votes
2answers
231 views

Riemannian metric on a space of “not-quite-smooth” (hyper)surfaces?

Apologies if the title's a bit vague; I'll try to explain everything below, and please let me know if I should clarify anything. I've been looking for a while at variational problems on polytopes. ...
2
votes
1answer
144 views

Upper bound concerning Snell envelope

Consider, on a filtred probability space $ \left (\Omega, \mathcal F, \mathbb F , \mathbb P \right )$ where $ \mathbb F = \left(\mathcal F_ t \right )_ {t\geq 0}$ is filtration satisfying the usuual ...
7
votes
1answer
305 views

Probability density that minimizes the sample range

Let $\mathcal{F}$ denote the set of all "concave probability distributions" on the unit interval, that is, all functions $f:[0,1]\to \mathbb{R}$ such that $f$ is concave, $f(x)\geq 0$ for all $x\in ...
3
votes
1answer
585 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 ...
2
votes
1answer
67 views

(A)periodicity and (In)dependence on the boundary condition for optimization problem related to ODE

The question is pair to MO117505 and translates some problem on error-correction codes to similar problem about differential operators. (See also If “force” is periodic does it imply “velocity” is ...
3
votes
2answers
360 views

Minimum eigenvalue of a Affine Combination of two Hermitian matrices

Consider two $N \times N$ hermitian indefinite matrices $A_1$ and $A_2$. Consider their affine combination \begin{align} M(t)=(1-t)A_1+tA_2 \end{align} I am interested in the minimum eigenvalue of ...
0
votes
0answers
99 views

maximum of the sum of polynomials

Hi I have $n$ polynomials, each one is positive over a certain range and the maximum value each can attain is 1. Also each polynomial has atmost one peak(maximum). Is there some way that I can show ...
3
votes
1answer
243 views

If “force” is periodic does it imply “velocity” is periodic ? (or decoding tail-bited conv. codes)

I'll try to translate certain problem about convolutional codes to more common language of ODE, hope my translation is correct, but welcome to criticize. Consider two given functions periodic ...
1
vote
1answer
75 views

Numerical optimisation for multivariate Gaussians

Hi, I want to calculate $ f_{\mathbf x}(x_1,\ldots,x_k)\, = \frac{1}{(2\pi)^{k/2}|\boldsymbol\Sigma|^{1/2}} \exp\left(-\frac{1}{2}({\mathbf x}-{\boldsymbol\mu})^T{\boldsymbol\Sigma}^{-1}({\mathbf ...
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 ...
2
votes
1answer
123 views

Rayleight Ritz Ratio and smallest eigenvalue for a set of given matrices

I am familiar with Rayleigh Ritz Ratio for hermitian matrices. Let $A_1$ be a given $N \times N$ hermitian matrix. Then the smallest eigenvalue of $A_1$ is given by \begin{align} ...
2
votes
1answer
226 views

An optimization problem, non complete bipartite graph and hungarian algorithm

I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like the rows in reference dataset with the ...
5
votes
1answer
308 views

Solve equation with matrix variable

I want to solve a matrix $\Omega$ from a equation $\sum_k (\Omega + \Theta_k)^{-1} = Q$. The $Q$ and $\Theta, \forall k=1...K$ are known, and are positive definite matrices. $\Omega$ also has to be ...
0
votes
1answer
252 views

Is unconstrained integer convex optimization problem NP-hard?

Does anyone know a reference to the answer if unconstrained integer convex optimization problem (i.e. $\min_{x\in \mathbb{Z}^N} F(x)$, $F$ is convex and $N$ is NOT fixed) is NP-hard? Thank you in ...
2
votes
1answer
919 views

Choice of Lipschitz constant for proximal gradient optimization

I'm trying to use proximal gradient methods (Forward-Backwards Splitting and FISTA) to minimize a function $f(B) = \frac{1}{2}|| XB - Y||_F^2 + \frac{\gamma}{2}||B C^T||_F^2$, where $X \in ...
3
votes
0answers
237 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 ...
5
votes
2answers
267 views

Simultaneous maximization of two Generalized Rayleigh Ritz Ratios

Consider hermitian positive semi-definite matrices $A_1$ and $A_2$. Consider also positive definite matrices $B_1$ and $B_2$. I want to maximize the minimum of the two Generalized Rayleigh Ritz ratios ...
0
votes
0answers
147 views

Stochastic optimal control with no diffusion

Classical stochastic optimal control problem is to minimize functional $$ J(u) = \mathbf E \int_0^T f(t,x_t,u_t)dt, \tag{1} $$ subject to SDE $$ dx_t = b(t,x_t,u_t)dt + \sigma(t,x_t,u_t)dW_t, \quad ...