Tagged Questions

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

learn more… | top users | synonyms

2
votes
2answers
98 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
131 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
146 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
347 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
147 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
170 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
110 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
154 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
49 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
108 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
95 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
137 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
132 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
167 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
101 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
269 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
101 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
33 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
220 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
396 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
94 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
173 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
392 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
195 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
65 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
101 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
72 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
144 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 ...
2
votes
1answer
203 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
446 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
206 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
165 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
151 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
115 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
62 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
188 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
216 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
156 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
374 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
125 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
267 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
85 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
185 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
132 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
208 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
170 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
226 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 ...