Questions tagged [oc.optimization-and-control]
Operations research, linear programming, control theory, systems theory, optimal control, game theory
1,142
questions
0
votes
0
answers
105
views
The best unitary matrices that approximate a matrix product
Let $\mathbf{A}$ be an arbitrary $N\times N$ complex matrix. Moreover, $\mathcal{U}_1$ and $\mathcal{U}_2$ are distinct subsets of all unitary matrices. Suppose the matrices $\mathbf{U}_1$ and $\...
1
vote
2
answers
259
views
Optimization of a integral function
I have a function $h(y,x_1,x_2,\ldots,x_n)$. It is known that the minimum value of $h$ for any $y$ is attained when $x_1 = x_n$ and $x_2 = x_3 = \cdots = x_{n-1}$. Now consider the following function
\...
0
votes
0
answers
150
views
Double summation of matrices as constraints in convex optimization in CVX
I want to implement the following optimization problem from the following paper Randomized Gossip Algorithms, Page 10 Eq 53:
\begin{align}
\text{minimize} &\qquad s\\
\text{subject to} & \...
1
vote
1
answer
137
views
Adding valid cuts for integer feasibility problem under Benders decomposition framework?
Traditional infeasibility cut is derived under the assumption that the feasibility problem is LP instead of ILP and relies on the dual form of the LP.
Is there a systematic way of adding valid cuts ...
1
vote
1
answer
130
views
Stability of certain second order ODE
I am having a hard time determining the motion of $X$ in the ODE $X''+\nabla f(X)=0$ with initial conditions arbitrary $X(0)$ and zero velocity, i.e. $X'(0) = 0$. $X$ is in $\mathbb{R}^{n}$, and $f$ ...
1
vote
0
answers
30
views
Eigenvalue assignment via state feedback: existence proof
Consider the linear time invariant system:
$$\tag{1}\label{eq1}
\dot{x}(t) = Ax(t) + Bu(t), \ \ x(0)=x_0\in\mathbb{R}^n,
$$
where $A\in\mathbb{R}^{n\times n}$, $B\in\mathbb{R}^{n\times m}$. Let $p_M(s)...
1
vote
1
answer
171
views
Boolean function : approximation by a linear function
Let $f$ be a balanced Boolean function.
Are there $g$ linear functions, with $$\frac1{2^n}\mathrm{card} \big(\big\{\mathrm{sign} (g (x)) = 2f (x) -1, x \in \{0,1\}^n\big\}\big) > 0.55\quad ?$$
$g ...
1
vote
0
answers
135
views
Is $x\cdot f(x)$ quasiconvex for $x>0$, if $f(x)$ is monotonically decreasing, convex, and positive? [closed]
Original question
Given $f(x):\mathbb{R}^+\to\mathbb{R}^+$, which is monotonically decreasing and convex. Then define a function $g(x) = xf(x)$, I am wondering whether $g(x)$ is quasiconvex for $x>...
1
vote
0
answers
32
views
How to chose the start vector for the MTZ variables
In the context of LP-formulations for the Traveling Salesman Problem the MTZ constraints prevent subtours via $n$ (i.e. effectively $n-1$) additional variables $$u_1=1\\2\le u_2,\,\dots ,\,u_n\le n\\ ...
3
votes
2
answers
119
views
Link between controllability of ODEs and controllability of transport equations
What is the relationship between the controllability of the ODE
$$\dot x(t) = v(x) + u(t)$$
using a control $u$ and the controllabilty of the transport equation
$$\rho_t(t,x) + \mathrm{div}(v(x) \rho(...
4
votes
1
answer
193
views
A question on eigenvalue of parametric matrix
Is there a way to efficiently check if all matrices in the following set are Hurwitz stable (eigenvalues strictly in the left-hand plane)?$$\left\{ A \in \Bbb R^{n \times n} : \ell_{i,j}\leq A_{i,j} \...
2
votes
1
answer
227
views
Minimizing quadratic objective under orthogonality constraints
The following problem is motivated from Generalized Procrustes Analysis. I am wondering if it is possible to obtain a closed form minimizer (which may involve SVD or some other decomposition of a ...
2
votes
0
answers
55
views
A variant of the elliptope relaxation
Given a p.s.d. matrix $A$, one may want to find:
$$
\max_x x^t A x \mbox{ such that } x \mbox{ has entries }1 \mbox{ or } {-1}.
$$
This hard problem has a well known relaxation based on the so called ...
3
votes
0
answers
87
views
What is the name for this type of optimization problem?
As we all know, a classic optimization problem can be represented in the following way:
Given a function $f: A \to \mathbb{R}$, find an element $x_0 \in A$ such that $f(x_0) \le f(x)$ for all $x \in ...
0
votes
0
answers
118
views
On least-squares with positive semidefinite constraints
Given real symmetric matrix $\mathbf{R} \in \mathbb{S}^{n\times n}$ and matrices $\mathbf{X}_n, \mathbf{X}_{n-1} \in \mathbb{R}^{n \times m}$,
$$\begin{array}{ll} \underset{\mathbf{A} \in \mathbb{R}^{...
1
vote
2
answers
175
views
Partitioning unit square with equal frequency rectangles
If I had to partition the unit square $[0,1]\times[0,1]$ into $k^2$ rectangles such that the sum of their diagonals is minimum possible, I would simply choose the $k \times k$ grid of squares. Now ...
16
votes
2
answers
781
views
What tools should I use for this problem?
Suppose we have $d$ cylindrical metal bars, with radius $l$, attached orthogonal to a support in random places:
Now we have to attach bars with radius $k$ EVENLY SPACED, with distance $p$ between ...
3
votes
0
answers
87
views
Projection onto level set of convex functional
Fix a probability space $(\Omega,\mathcal{F},\mathbb{P})$ and let $F:L^2_{\mathbb{P}}(\mathcal{F})\rightarrow (-\infty,\infty]$ be bounded-blow, convex, lower semi-continuous, and not identically ...
0
votes
0
answers
87
views
Why is Gaussian distribution always chosen for smoothed analysis?
I came across the algorithmic perfomance analysis model of smoothed analysis. In all references that I read a Gaussian distribution was used for perturbation (e.g. Spielman and Teng 2004 for the ...
2
votes
1
answer
113
views
Minimization of an entropy type functional with biased expectation constraint
This question is a continuation of Minimization of an entropy type functional
Let $\mathcal P_c$ be the set of probability densities on $[0,1]$ with mean $c\in [0,1]$, i.e. $p\in \mathcal P_c$ iff
$$\...
3
votes
1
answer
134
views
Minimization of an entropy type functional
Let $\mathcal P$ be the set of probability densities on $[0,1]$ with mean $1/2$, i.e. $p\in \mathcal P$ iff
$$\int_0^1 p(x)dx=1,\quad \int_0^1 xp(x)dx=\frac{1}{2}\quad \mbox{and}\quad p(x)\ge 0, ~~\...
0
votes
0
answers
92
views
Optimization problem where the objective function returns a function instead of a real number
As we all know, a classic optimization problem can be represented in the following way:
Given: a function $f: A \rightarrow \mathbb{R}$ from some set $A$ to the real numbers
Sought: an element $x_0 ∈ ...
2
votes
1
answer
201
views
Is there a version of Arrow's theorem without unrestricted domain?
To recall Arrow's theorem:
Suppose we have a finite set $X$ of voters and a finite set $Y$ of candidates.
An election is a map $\phi: X \rightarrow T$ where $T$ is the space of total orderings of $Y$. ...
2
votes
0
answers
100
views
Coercivity of an integral operator in control theory
Let us consider the integral operator $T:\mathbb{R}^{n\times d}\to [0,\infty)$ such that for all $K\in \mathbb{R}^{n\times d}$,
$$
T(K)=\int_0^1 \operatorname{tr}(KK^\top \Sigma_t) \,d t,
$$
where $\...
1
vote
0
answers
59
views
Minimizing square roots with the consecutive ones property
Let $A=[a_{ik}]$ be a matrix with the consecutive ones property in each column, i.e. each column consists of a single consecutive block of $1$'s (with zeros everywhere else). Is there anything at all ...
1
vote
0
answers
134
views
Factorization of argmax
We consider a function $f(s_{1:p}, a_{1:p})$, where $p>1$ is an integer, $s_{1:p}$ denotes $(s_1,\ldots,s_p)^\top \in R^p$, and $a_{1:p}$ denotes $(a_1,\ldots,a_p)^\top \in R^p$.
Question: What is ...
1
vote
0
answers
83
views
Reference request: Optimal controls can be assumed to take values in a convex set
Consider the deterministic controlled system:
$$\dot x(t) = Ax(t) + Bu(t), \ t \in [0, T]$$
$$x(0) = x_0$$
where $x: [0, T] \to \mathbb R^n$ is the controlled state process, $A \in \mathbb R^{n \times ...
1
vote
1
answer
149
views
Does coercivity/supercoercivity conjugates?
According to Wikipedia, a function $f: \mathbb{R}^n \to \mathbb{R} \cup \{-\infty, +\infty\}$ is called coercive if,
$$f(x) \to +\infty \text{ as } \|x\| \to +\infty$$
and it is super-coercive if
$$\...
4
votes
2
answers
302
views
Average value of $\frac{x'A^2x}{x'A^3x}$ over surface of $n$-dimensional sphere
Suppose $A$ is a diagonal matrix with eigenvalues $1,\frac{1}{2},\frac{1}{3},\ldots,\frac{1}{n}$ and $x$ is drawn from standard Gaussian in $n$ dimensions. Define $z_n$ as follows
$$z_n=E_{x\sim \...
1
vote
0
answers
311
views
Reference request: Introduction to stochastic control theory
I’m looking for a nice readable introductory text to stochastic control theory. Background wise, I know some general stochastic analysis and deterministic optimal control theory.
Some criterion I’m ...
5
votes
0
answers
78
views
Differentiability/continuity of stabilizing solution to algebraic Riccati equation with respect to matrix parameters
When solving the LQR problem to find the optimal feedback matrix $K^*$, i.e. solving
\begin{align*}
\min_K &\int_0^\infty \left(x^TQx + u^TRu\right)dt,\\
\text{s.t. }&\dot{x} = Ax+Bu,\\
&u=...
8
votes
1
answer
613
views
Maximizing sum of vector norms
Given matrices $A, B \in \mathbb{R}^{n\times n}$, I would like to solve the following optimization problem,
$$\begin{array}{ll} \underset{v \in \mathbb{R}^n}{\text{maximize}} & \|Av\|_2+\|Bv\|_2\\ ...
2
votes
0
answers
47
views
Why not use global optimization algorithms like PSO to solve decentralized control problems?
I do not see many works that use global optimization algorithms to solve decentralized control problems. Here the decentralized control problem means some entries of the feedback matrix are ...
0
votes
1
answer
87
views
How to find $y_u?$
In the paper Semi-supervised learning by mixed label propagation Wei Tong and Rong Jin define
$S$ as the similarity(adjacency) matrix
$D = \operatorname{diag}(D_1, D_2, \ldots, D_n)$ where $D_i = \...
0
votes
0
answers
145
views
Minimum circumscribed ellipsoid of $\mathcal H$-polytope
Given matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^n$, consider the $\mathcal H$-polytope $P$ defined as follows
$$ P := \left\{ x \in \mathbb{R}^n : Ax \leq b \right\} $$
I ...
0
votes
0
answers
134
views
Any technique for linearization, or linear approximation?
Consider the following Matrix constraint:
$$
\begin{bmatrix} -U+\psi\Sigma_b^{-1} & V \\ V^T & -V^TU^{-1}V+\tau_2 -\psi \end{bmatrix} \leq 0
$$
where $\Sigma_b$ is a known positive definite ...
8
votes
2
answers
324
views
Projecting onto space of matrices with spectral radius less than one
Consider the space
$$ S = \left\{ A \in \mathbb{R}^{n \times n} : \mathrm{SpectralRadius}(|A|) \leq 1 \right\}$$
where $|A|$ is the entry-wise absolute value. Given a matrix $M \in \mathbb{R}^{n\times ...
5
votes
2
answers
1k
views
Textbooks or lecture notes about mean field games
I am looking for a good introductory level textbook (or lecture notes) on mean field games that would be suitable for a graduate course. Ideally, it would include some brief words about optimal ...
2
votes
0
answers
138
views
inverse of moment-generating function in terms of moments
Let $\{h_i\}$ be decreasing sequence of $n$ positive reals. Define distribution $p(X=h_i)\propto h_i$ and let $g(s)=E_X[e^{sX}]$ be the moment generating function. For instance, for $h=\{1,\frac{1}{4},...
2
votes
0
answers
129
views
Complexity of Quadratic Programming where the symmetric matrix Q is positive semidefinite only in the feasible directions
playing around with stuff for my dissertation, I derived a quadratic problem in the general form
\begin{equation}
\begin{aligned}
\min_{x} \quad & x^TQx + c^Tx \\
\textrm{s.t.} \quad & Ax \leq ...
4
votes
0
answers
131
views
An inequality for three iid random variables with a log-concave density
It was previously shown that
$$H\ge cG,\tag{1}$$
where $c:=1/14334$,
$$G:=E|X-Y|,\quad H:=E|X-Y|-\tfrac12\,E|X+Y-2Z|,$$
and $X,Y,Z$ are independent random variables with the same log-concave density.
...
1
vote
0
answers
35
views
Solution to dynamic program-type recursion
I have the following dynamic programming principle-type problem.
Suppose that we are given a sequence $\beta_1,\dots,\beta_n\in (0,\infty)$, some target $y\in (0,\infty)$ with $y>\sum_{t=1}^N \...
1
vote
1
answer
983
views
Prove that absolute value of eigenvalue is smaller than 1 [closed]
I want to prove that the absolute value of the eigenvalues of a matrix A are smaller than 1 for $$A=\left(\begin{array}{cc}
0 & -H_{11}^{-1} H_{12} \\
-H_{22}^{-1} H_{21} & 0
\end{array}\right)...
0
votes
1
answer
248
views
Non-asymptotic convergence rates for gradient descent
I'd like to know how the number of steps needed for gradient descent depend on properties of the Hessian in non-asymptotic regime.
More specifically, number of gradient descent steps needed to obtain ...
0
votes
0
answers
38
views
Lipschitz solutions to linear complementarity problems (LCP)
Let $M\in\mathbb{R}^{n\times n}$.
For $q\in\mathbb{R}^n$, define the set:
$$S_M(q)=\{y\in\mathbb{R}^n|y\ge 0,q+My\ge 0, y^\top (q+My)=0\}.$$
This is the set of solutions to the LCP $(q,M)$.
We say $...
1
vote
1
answer
234
views
Transport theorem in space craft control: tracking a reference angular velocity
I am reading the book named "Analytical mechanics aerospaces systems" by Schaub and Junkins.
In section 7.2, the task is to control the spacecraft to track a specified angular velocity $w_r$ ...
0
votes
0
answers
164
views
Rewriting Kronecker product
im considering a pole placement problem in control theory and my controler has a specific form:
$$R=I_n\otimes q$$
where $I_n$ is the identitiy matrix of size $n$ and $q\in\Re^k$ is a vector of the ...
1
vote
0
answers
70
views
Symmetry for bilinear optimization problem related to Gromov Wasserstein distance
The following question came up when trying to numerically solve some variants of the Gromov-Wasserstein distance.
Setting:
Let $(X_1, d_1), (X_2, d_2)$ be two compact, separable and complete metric ...
1
vote
0
answers
56
views
Pontryagin's principle with Lebesgue-integrable control
Does there exist a (weak) version of Pontryagin's minimum principle in which the control is allowed to be just Lebesgue integrable? I am mostly familiar with the 1975 text of Fleming & Rishel, ...
7
votes
4
answers
2k
views
How to show a $3\times3$ matrix has three distinct eigenvalues?
Here is a question I heared from others:
Given four distinct positive real numbers $a_1,a_2,a_3,a_4$ and set $$a:=\sqrt{\sum_{1\leq i\leq 4}a_i^2}$$
$A=(x_{i,j})_{1\leq i\leq3,1\leq j\leq4}$ is a $3\...