Questions tagged [oc.optimization-and-control]
Operations research, linear programming, control theory, systems theory, optimal control, game theory
415
questions with no upvoted or accepted answers
32
votes
0
answers
2k
views
A Combinatorial Abstraction for The "Polynomial Hirsch Conjecture"
Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ .
Suppose that
(*)
For every $i \lt j \lt k$
and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$,
...
14
votes
0
answers
248
views
Dividing a convex region to minimize average distances
Let $C$ be a convex region in the plane with area 1 that contains distinct points $p_1,\dots,p_n$. Say I'd like to divide $C$ into $n$ pieces $C_1,\dots,C_n$, each of area $1/n$, and I'd like to ...
11
votes
2
answers
752
views
A (linear) optimization problem subject to (linear) matrix inequality constraints
Let $A \in \mathbb{R}^{n \times n}$ be a Hurwitz matrix, i.e. $A$ satisfies $\mathrm{Re}\,\lambda_i< 0$, where $\{\lambda_i\}_{i=1}^n$ is the set of eigenvalues of $A$. Suppose that the trace of $A$...
11
votes
0
answers
748
views
Hamilton-Jacobi equations: Method of characteristics
In Cannarsa-Sinestrari's book 'Semiconcave Functions, Hamilton-Jacobi Equations, and Optimal Control' there is a proof, via the Method of Characteristics, of global-in-time existence of classical ...
11
votes
0
answers
290
views
$L_2$ minimizing makespan vs. $L_\infty$ minimizing makespan
There are $n$ positive real numbers. We partition these numbers into $m$ parts, the size of each part is the sum the numbers in this part. Maximum size of the parts is called a makespan of a partition....
8
votes
0
answers
229
views
Decay of orthogonal contributions in a random set of vectors
Suppose we sample $k$ vectors $v$ from normal distribution centered at zero and diagonal covariance with diagonal entries $1,\frac{1}{2},\ldots,\frac{1}{d}$ and normalize $v$:
$$\frac{v_1}{\|v_1\|},\...
8
votes
0
answers
540
views
Hasse-Weil Bound and Chebyshev Inequality
I was reading about the Hasse-Weil bound for the number of points in on a curve over the finite field $\mathbb{F}_q$.
$$ \big| |C(\mathbb{F}_q)| - (q+1) \big| \leq 2g \sqrt{q} $$
However, this ...
7
votes
0
answers
426
views
Geometric bang-bang theorem for nonlinear optimal control
The classical bang-bang theorem is usually stated for linear systems (e.g. Control Theory from the Geometric Viewpoint by Agrachev-Sachkov, p. 209). Sussman proved a nice generalization for systems ...
7
votes
0
answers
208
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 ...
7
votes
0
answers
881
views
Maximizing the matrix norm
Hi all,
I wish to find a 3x3 rotation (orthogonal) matrix $\mathbf{R}$ such that it maximizes the following matrix norm:
$||\mathbf{A} \mathbf{D}_r \mathbf{D}_b ||_2$
where $\mathbf{A}$ is a known $...
6
votes
0
answers
70
views
Roundest polyhedra: how well can we bound the edge count of their faces?
By "roundest" I mean having the lowest surface area for the highest volume, given a fixed number of faces $n$. There've been a few questions about them on here (including from me), but I'm ...
6
votes
0
answers
210
views
Optimal configurations on the flat torus
I'm studying (with my colleagues R.Piergallini and S.Isola) configurations of points on the flat torus which minimize an attractive or repulsive potential depending on the distance. Two model cases ...
6
votes
0
answers
92
views
Finding the optimal mixture of two convex functions
I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where $x_1,x_2\...
6
votes
0
answers
148
views
Minmax problem for polygons
Let $\text{Pol}_n$ be the set of all convex polygons on a plane with $n$ vertices. For $P\in \text{Pol}_n$ denote by $\text{Tr}(P)$ the set of all triangles which vertices are some vertices of $P$. I ...
5
votes
0
answers
196
views
Difficulty of solving $Ax=b$ in terms of limiting spectral density of $A$?
Suppose $A$ is a random real-valued $n\times n$ matrix and we want to know the difficulty of solving $Ax=b$ when entries of $b$ are sampled IID from Normal$(0,1)$.
Can we say anything about the ...
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=...
5
votes
0
answers
121
views
Projection of a function $f\in L^1(\Omega)$ onto a finite dimensional subspace
Suppose $\Omega \subset \Bbb R^n$ be a domain such that $|\Omega|<\infty$, $f\in L^1(\Omega)$. Let $Y= \text{span}\{g_1,\dots, g_k\}$.
Is there a characterization of the set of projections of $f$...
5
votes
0
answers
96
views
Non-convex optimization problem involving minimum spanning trees
Suppose I am given $n$ points $p_1,\dots,p_n\in \mathbb{R}^2$, as well as two positive coefficients $a_1$ and $a_2$, and I am trying to select $n$ points $x_1,\dots,x_n$ to solve the following ...
5
votes
0
answers
2k
views
Find the axis of symmetry in a point cloud
I have some dataset which describes a spherical cloud of points in 4D space. Actually, the coordinates of the points are the coefficients of unit quaternions, so you get the idea on what the data is ...
5
votes
0
answers
266
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 ...
5
votes
0
answers
421
views
The Gömböc and monostatic objects
This made the popular news a few years ago. Summary: it's the first homogeneous, convex solid to be found with only one stable and one unstable mechanical equilibrium when resting on a flat surface. I ...
4
votes
0
answers
188
views
Schrödinger Bridge for other costs
Stochastic control formulations of the Schrödinger bridge problem between $\mu,\nu$ are well known (e.g Chen et al Eq. 4.23)
$$\inf \limits_{p_t, v_t} \int_0^T \int \frac{1}{2}\lvert v_t\rvert^2 p_t ...
4
votes
0
answers
205
views
Does the refined Slater's condition hold also in the infinite-dimensional case?
Let $X$ be an infinite-dimensional Banach space. I have the following optimization problem.
$$\begin{array}{ll} \underset{x \in X}{\text{minimize}} & f(x)\\ \text{subject to} & g_1(x) \leq 0\\ ...
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} \...
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.
...
4
votes
0
answers
111
views
Looking for an electronic copy of Lebeau's paper
I would like to know if anyone has an electronic copy of the paper "Gilles Lebeau - Contrôle De L'Équation De Schrödinger"? This article appeared in Journal de Mathématiques Pures et ...
4
votes
0
answers
54
views
Least squares with matrix product constraints
I am encountering a constrained LS problem with the following structure:
$$
\text{min}_Q\ \sum_{i=1}^M ||Q_i X_i-Y_i||_F^2
$$
$$
\text{s.t. }\ Q_M Q_{M-1}\cdots Q_1=I,
$$
where $Q_i,X_i,Y_i\in \mathbb{...
4
votes
0
answers
175
views
Is the Weber problem a NP-hard problem?
The Weber problem is a special case of a facilities location problem : In a basic formulation, the facility location problem consists of a set of potential facility sites L where a facility can be ...
4
votes
0
answers
66
views
Can a nonlinear dynamical system be rewritten in terms of constraints?
My question is based on thoughts after reading to a specific section in the paper "On Contraction Analysis for Nonlinear Systems" by W. Lohmiller and JJ. Slotine, Section 4.2 Constrained Systems. ...
4
votes
0
answers
242
views
Is every stable matrix orthogonally similar to a $D$-skew-symmetric matrix?
Let $\mathrm{diag}(A)$ denote the diagonal matrix with diagonal entries of $A\in\mathbb{R}^{n\times n}$ and let $\succeq$ denote the standard partial order in the cone of (symmetric) positive definite ...
4
votes
0
answers
215
views
Optimal control of SDEs
I've set up a system of stochastic differential equations that I'd like to control. I'm new to optimal control theory and SDEs (and, admittedly, weak on PDEs), so I'm not certain if I've set this up ...
4
votes
0
answers
82
views
Non-singularity of a series of matrices
Let $A_1$, $A_2$ be $n\times n$ real matrices. Suppose that $A_1$ and $A_2$ are Schur stable (i.e., their eigenvalues are strictly inside the unit circle in the complex plane). Let $B_1$, $B_2$ be two ...
4
votes
0
answers
500
views
Using Linear Programming as an iterative procedure
Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
4
votes
0
answers
139
views
Asymptotic behavior of gradient descent on a smooth, convex, non-negative function with no finite minimum - part II
Let $f: \mathbb{R}^d\rightarrow\mathbb{R}_{\geq 0}$ be a function which is convex and smooth (i.e., in $C^{\infty}$). If $x^* \in \mathbb{R}^d$ is the (global) minimum of $f$, it is well known that ...
4
votes
0
answers
237
views
Stochastic subgradient descent almost sure convergence
I was reading up on stochastic subgradient descent, and most sources i could find via google search give quick proofs on convergence in expectation and probability, and say that proofs of almost sure ...
4
votes
0
answers
129
views
Covering Number of a Positive Semidefinite Cone (Approximate the Objective of a SDP)
I was wondering what the covering number of a positive semidefinite cone is. Consider the semidefinite optimization program
\begin{align}
\max\langle \mathbf{C}, \mathbf{X} \rangle~~\text{subject to}~...
4
votes
0
answers
182
views
This function looks quasiconvex, can't understand why
Suppose that $\mathbf{C}$ is a given matrix with non-negative entries in $\mathbb{R}^{m\times n}$ and $d$ is a given scalar, and let $g(\mathbf{y})$ be defined by $$g(\mathbf{y}):=\max_{\mathbf{x}\in\...
4
votes
0
answers
166
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 ...
4
votes
0
answers
115
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 ...
4
votes
0
answers
159
views
Convexified threshold of a function
Upd. The question in a nutshell: find convex set on plane which is «closest» to a given non-convex set.
It is given integrable function $0\leq f(x,y)\leq 1$ with bounded support: $f(x,y)=0$ when $x^2+...
4
votes
0
answers
101
views
Applications of k-medians with moment constraints
Suppose I have a collection of points $p_1,\dots,p_N$ in the plane. In the Euclidean $k$-medians (or $k$-means) problems, our objective is to distribute a set of $k$ points $x_1,\dots,x_k$ in the ...
4
votes
0
answers
195
views
restricting "dances of minimal cost" (optimization on braids/permutations?)
Consider applying the permutation (1,3,0,5,2,7,4,6) to the integers (0,1,2,3,4,5,6,7) three times.
I call this a "dance of minimal cost" because all unordered pairs in {0..7} meet each other, and the
...
4
votes
0
answers
338
views
Can the Littlewood-Richardson cone be used for combinatorial optimization?
The Littlewood-Richardson cone $LR_{n, k}$ consists of all $k-$tuples $(a_1, a_2, \dots, a_k)$ of real $n-$vectors with monotonically decreasing entries such that there exist $k$ $n \times n-$...
4
votes
0
answers
689
views
Dynamic programming principle (DPP)
In stochastic control problem, one shall use the measurable selection theorem to prove DPP. It was discussed in discrete time case in [Bertsekas and Shreve 1978]. Is there unified framework in ...
3
votes
0
answers
164
views
Asymptotics for optimal survival time in a stochastic control problem
An individual, henceforth called the runner starts at the center of an open ball $\Omega_r \subset \mathbb R^2$ of radius $r > 1$.
At each turn, a vector $x \in S^1$ is chosen uniformly at random, ...
3
votes
0
answers
84
views
Sum-of-guesses-minimization problem (also does this problem already exist in the literature)?
Inspired by some recent real-world situations, I thought of this problem:
An adversary has selected a positive real number $p \ge 1$ not known to you. You have to pick numbers $x_1, x_2, \dots$ in ...
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 ...
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 ...
3
votes
0
answers
110
views
Matrix inequality $a X \succeq arcsin(X)$ for some $a > 0$
Let $X \in S^{n}_{+}$ be a positive semi-definite matrix with $X_{ii} = 1$ for all $i \leq n$ (thus $X$ is a correlation matrix).
Since $X$ is positive semi-definite, we have $|X_{ij}| \leq 1$ for any ...
3
votes
0
answers
87
views
Bounds on minimum solutions to empirical and theoretical objective functions
Let $P$ and $Q$ be two probability distributions and let
$$S_0 = \min_{f,g} \left[ \int f(x)\, dP(x) + \int g(y)\, dQ(y) \right]$$ such that $f(x)+g(y) \geq \langle{x,y\rangle}$ where $f,g$ are ...