Questions tagged [oc.optimization-and-control]
Operations research, linear programming, control theory, systems theory, optimal control, game theory
1,085
questions
1
vote
0
answers
60
views
Expressing a double Riemann Sum as a definite integral
I am reading a paper where the authors rewrite the following expression (for a continious function $\alpha$) into an integral:
$$\lim_{n\to \infty} \left(\min_{1\leq j \leq n}\left(\sum_{k=1}^{j-1} \...
- 452
3
votes
0
answers
90
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 ...
- 71
0
votes
1
answer
122
views
Leech lattice shortest vector vs other 23 cases and E8 cases
In this paper by Viazovska, she said that:
"The E8-lattice sphere packing 𝒫E8 is the union of open Euclidean balls with centers at
the lattice points and radius $1/\sqrt{2}$." So I think ...
- 61
1
vote
0
answers
24
views
Curve fitting with "rough" loss functions
Many real-valued classification and regression problems can be framed as minimization in the following way.
Setup:
Let $\Theta \in \mathbb{R}^p$ be the parameter space that we are searching over.
For ...
- 190
5
votes
1
answer
177
views
Upper bound for an inverse Laplace transform
Can anyone see how to get a tight upper bound for the function defined in terms of the inverse Laplace transform below?
$$g_\text{sgd}(t)=\mathcal{L}^{-1}\left[\left(\frac{s}{2}+\frac{5 \sqrt{\frac{2}{...
- 2,118
1
vote
0
answers
41
views
On Designing Some Optimal Control Problems
In the context of a dynamical systems, some states may not be attainable with scalar controls from $L^1(0,T)$, but they may be reachable with feedback controls.
If we know that the system is null ...
- 21
1
vote
0
answers
32
views
The existence of an optimal distributed control problem
Consider $\Omega$ as a bounded interval of $\mathbb{R}$, and let $y\in L^{\infty}(\Omega \times (0,T))$ be a mild solution of the following parabolic partial differential equation:
\begin{equation}\...
- 21
1
vote
0
answers
79
views
Maximisation of a convex (quadratic) function
This post is a continuation of A variant of (discrete) optimal transport problem
For $\alpha=(\alpha_1,\ldots,\alpha_m)\subset\mathbb R^m_+$, $\beta=(\beta_1,\ldots,\beta_n)\subset\mathbb R^n_+$ and $...
- 437
3
votes
1
answer
85
views
Condition for 3×3 block matrix to be stable
Given a square symmetric matrix $H\in\mathbb{R}^{n\times n}$, design a symmetric positive definite matrix $M\in\mathbb{R}^{n\times n}$ and positive scalar $\alpha$ such that the following ${3n\times ...
- 33
2
votes
0
answers
109
views
How to solve $\min_{\mathbf{x}\in \{\pm 1\}^N} \lVert \operatorname{sign}(\mathbf{Wx}) - \mathbf{y} \rVert_2^2$ where $\mathbf{y}\in \{\pm 1\}^N$?
Given the matrix $\mathbf{W} \in \mathbb{R}^{N \times N}$ and the vector $\mathbf{y} \in \{\pm 1\}^N$, how to solve
$$\min_{\mathbf{x}\in \{\pm 1\}^N} \left\| \operatorname{sign}(\mathbf{Wx}) - \...
- 175
0
votes
0
answers
22
views
Relation between the left-dominant eigenvectors (eigenvector corresponding to 0 eigenvalue) of two Laplacian matrices
Let $G_1=(v,\epsilon_1)$,$G_2=(v,\epsilon_2)$ be two graphs with the same set of vertices and $\epsilon_1 \subset \epsilon_2$. $L_1$ and $L_2$ be the Laplacian matrices associated with graph $G_1$ and ...
1
vote
2
answers
179
views
How much "room" in inequality $\displaystyle \int_a^b \varphi' ov ~\mathrm{d}x \leq 0$
Let $[a, b]$ be a nonempty interval, $o \in C^1([a, b])$ be such that $o>0$ and $o'<0$ and assume we found some $v \in L^\infty(\mathbb{R})$ such that
\begin{equation}\tag{1}\label{1}
\int_a^b \...
- 115
29
votes
1
answer
1k
views
Can a real quartic polynomial in two variables have more than 4 isolated local minima?
This question: "Can a real quartic polynomial in two variables have at most 4 isolated local minima?" came up in this post on Math SE but with no answer so far.
Finding examples of 4 ...
- 431
0
votes
1
answer
70
views
Derivative in Sobolev space extended by zero
Let $u(x) \in H^1_0$ is a complex function in sobolev space extension by zero.
How to find $J'(u)$ for
$$
J(u)= \int\limits_0^l |u(x)|^2\operatorname{d\!}x\;??
$$
In $L_2$ it's easy:
$$
J'(u) = \left(\...
- 3
0
votes
1
answer
62
views
Constrained linear optimization problem on $C^1$
I am dealing with a problem of the form ($a<b$)
$$
\displaystyle \max_{v \in C^1([a, b])} \int_a^b v(x)~\mathrm{d}x, \quad \mathrm{s.t.} \int^b_a \big(-o'(x)v(x)-v'(x)o(x)\big)f(x)~\mathrm{d}x \...
- 115
1
vote
1
answer
161
views
Is non-convex optimisation really in NP class?
Crossposted on Mathematics SE
I've seen in many optimisation papers the statement that general non-convex optimisation problem is NP-hard. If we assume that non-convex optimisation is in NP class, it ...
2
votes
0
answers
71
views
Differential inequality with convex constraint
The following problem looks to be classical, but I fail to find a reference for it. If you know it, please help me.
Given a bounded measurable function $h:{\mathbb R}_+\to\mathbb R$ and a number $a\...
- 49.5k
1
vote
1
answer
82
views
Existence of minimal Steiner tree
I am looking for a reference proving the existence of the minimal Steiner tree in the Euclidean Steiner tree problem:
Given N points in the d-dimensional Euclidean space, the goal is to connect them ...
- 508
3
votes
1
answer
64
views
Sensitivity of the solution of QP with respect to parameters
Given a quadratic program,
$$\begin{array}{ll} \text{minimize} & \displaystyle \frac12 x^TAx + b^Tx \\ \text{subject to} & Cx \le d \end{array}$$
Suppose $A \succ 0$, so the program strongly ...
- 33
0
votes
0
answers
76
views
On a stochastic control problem
Let $(\Omega,\mathcal F, \mathbb P)$ be a probability space on which a Brownian motion $W$ is defined, and $\mathcal U$ be the set of progressively measurable (w.r.t. the Brownian filtration) ...
- 437
1
vote
0
answers
82
views
Traveling Salesman: Optimization over cities, not distance
In the classical traveling salesman problem, we are given a graph of cities with distances between each city and are asked to find the shortest path that traverses all of the cities. Meaning that the ...
- 129
1
vote
0
answers
63
views
On optimizing a multivariate quadratic function subject to certain conditions
The problem is to maximize $f(x_1,x_2,\cdots,x_n)=\sum\limits_{i=1}^{n}\Big(x_i-k_i\Big)^2$ for $n\ge 3$ subject to the conditions (1) $\sum\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}k_i\le n(n-1)$ ...
- 61
1
vote
2
answers
49
views
Monotonicity of kernel matrices with respect to hyperparameters
Let $\mathcal{X}$ be some nice space, let $\Phi$ be some ordered space, and let $K :\mathcal{X} \times \mathcal{X} \times \Phi \to \mathbf{R}$ be a positive-semidefinite kernel indexed by a ...
- 559
1
vote
1
answer
66
views
An inequality relating $\ell_1$ distance of input and output of a Markov krnel
Let $K$ be a Markov kernel from $\mathcal{X}$ to $\mathcal{Y}$, i.e., $K(\cdot|x)$ is a probability measure on $\mathcal{Y}$ for all $x\in \mathcal{X}$.
Let $\mu$ and $\nu$ be two probability measures ...
- 1,089
0
votes
0
answers
83
views
How to find a specific clique cover set?
Let $G(\mathcal{V},\mathcal{E})$ be a graph with vertex set $\mathcal{V}$ and edge set $\mathcal{E}$. Also, non-negative weights $w_i$ are assigned to each vertex $i\in\{1,\ldots,n\}$. Suppose the ...
- 127
0
votes
0
answers
102
views
A property of quadratic optimization solution map
Define for a given $\mathbf{b}$ the quadratic optimization solution map by
$$
\mathcal{S} \ \colon \ U \mapsto \mathbf{x} \ \colon \ \mathbf{x}^\top \, U^{-1} \, \mathbf{x} = \min_{\mathbf{y} \geq \...
- 109
1
vote
1
answer
146
views
Role of verification theorems in stochastic optimal control?
I am currently working on the optimal control of certain classes of stochastic processes and I have difficulties understanding the roles of verification theorems.
My problem is the following: I am not ...
- 13
1
vote
1
answer
71
views
Strict convexity of the cost function is enough to ensure the existence and uniqueness of the optimal transport map
Let $X=Y = \mathbb R^d$ and $c:X \times Y \to [0, \infty)$ be Borel measurable. Let $\mu, \nu$ be Borel probability measures on $X,Y$ respectively. Let $\mathcal T$ be the set of all Borel measurable ...
- 713
0
votes
1
answer
97
views
Is there a redundant constraint in linear programming? [closed]
From wikipedia:
But... Why do we need the $x\ge 0$ part? We can instead do $-x\le 0$, and thus saving a line in the definition (which is not a big deal but nevertheless nice).
(In order to do that, ...
1
vote
1
answer
92
views
Some calculations with polynomials in the proof of the Routh-Hurwitz test
In an article on the Routh-Hurwitz test, I couldn't see why the following result is true:
Let $$p(s)=a_ns^n+a_{n-1}s^{n-1}+\dots+a_{1}s+a_0$$ and $$ \eta_{*} = \frac{a_n}{a_{n-1}}$$ $$g_{\eta}(s):=p(...
- 11
13
votes
2
answers
551
views
How to characterize the regularity of a polygon?
In my research, I've recently started to play with Voronoi tessellations. I currently have a Python code that creates the tessellation and I am trying to color the polygonal regions according to their ...
- 141
1
vote
0
answers
29
views
Bounds on Eigenvalues After Skew-Symmetric Perturbation
Consider two matrices $\mathbf{J} \in \mathbb{R}^{n \times n}$ and $\mathbf{L} = -\mathbf{L}^T \in \mathbb{R}^{n \times n}$. I am trying to upper bound the eigenvalues of their sum:
$$\mathbf{A} = \...
- 11
2
votes
1
answer
173
views
Nash equilibrium at another level
This is a variant of the Nash equilibrium. Let's say that there are 3 prizes: A Ferrari, a diamond watch, and a new boat. There are 6 players. 3 players with a motive while 3 players with another ...
- 41
6
votes
3
answers
881
views
Proof of a matrix implication
If $A = \begin{bmatrix} x & 1\\ y & 0\end{bmatrix}, B = \begin{bmatrix} z & 1\\ w & 0\end{bmatrix}$, for $x,y,z,w \in \Bbb{R}$.
I have observed by considering many examples of $x,y,z,...
- 51
1
vote
1
answer
119
views
Optimal transport: the existence of an optimal pair of $c$-conjugate functions
$\newcommand{\diff}{ \, \mathrm d}$
Let
$X,Y$ be Polish spaces,
$\mathcal C_b(X)$ the space of all real-valued bounded continuous functions on $X$,
$\mathcal P(X)$ the space of Borel probability ...
- 713
0
votes
0
answers
19
views
Is there an approximation algo for packing interlinked 3d shapes?
Is there an approximation algorithm for packing interlinked 3d shapes?
This feels like it should be possible to approximate, but I'm not sure if it has been researched, or if it has, what it would be ...
- 101
1
vote
3
answers
223
views
How to optimize for the best fit nonuniform-scale-rotation to a given 3×3 matrix?
Given a matrix $L\in \mathbb{R}^{3 \times 3}$, I'm looking for a method to find the closest (in a least squares sense) product of a non-uniform scaling matrix and a rotation matrix:
$$
\min_{s\in\...
- 673
1
vote
0
answers
133
views
How to maximize certain function of hundreds variables related to correlations between sets vectors ? (and win Kaggle :))
It might be helpful for data science/bioinformatics challenge.
Consider for simplicity three rectangular matrices $Y_{true}$ , $Y_{predict0},Y_{predict1}$ of the same sizes say 70000*140.
Let us ...
- 22.6k
1
vote
0
answers
23
views
Convergence of a sequence of minima of a family of optimal control problems
Let $(\lambda_k)$ be an unbounded and increasing sequence of real numbers, and $f:\mathbb{R}^n \ \times \mathbb{R}^m \rightarrow \mathbb{R}^n$ be sufficiently smooth such that $\dot{x}(t) = f(x(t),u(t)...
- 1,532
0
votes
1
answer
60
views
How quickly can this IQP or its MILP relaxation be solved
Let $A\in\{0,1\}^{(n,n)}$ be a $n$ by $n$ boolean matrix (in particular think of an adjacency matrix of a graph), and consider the following optimization problem:
$$\begin{align*}&&\max_{P\in\{...
- 71
1
vote
0
answers
57
views
A stochastic control problem with costly information
Motivation:
Nate is holding an asset he knows is overpriced. At the moment there is an upward trend due to hype, but he is aware that at some point in time, the bubble will burst, leading to a crash ...
- 2,486
1
vote
0
answers
93
views
How to solve the following optimization problem?
Let $G=(V,E)$ be a connected network with $|V|=n$. Consider the following optimization problem
I'm trying to know under which conditions the following minimization problem has solution :
$${\sum _{i=1}...
- 47
10
votes
0
answers
560
views
A simple stochastic game
An individual, henceforth called the runner starts at the center of an open two dimensional square $\Omega$ of side length $r \geq 2$.
At each turn, a vector $x \in S^1$ is chosen uniformly at random, ...
- 2,486
0
votes
0
answers
30
views
Matrix optimization to find ideal embedding
Basically, I am trying to find the embeddings so I can approximate $K \approx M(\vec{\phi})$. The embeddings are for each one of my samples $\vec{\phi}(x_i) \in \mathbb{R}^D$ so I thought it should ...
0
votes
1
answer
95
views
Method for (binary) optimization under constraints
I would like to know if there is a method to solve the Problem.
Problem:
Maximize the following function: $$f(p_{1,i},p_{2,i},\dotsc,p_{m,i})=\sum_{i=1}^{n}\begin{bmatrix}p_{1,i} & p_{2,i} & \...
- 3
1
vote
0
answers
91
views
Can I minimize a mysterious function by running a gradient decent on her neural net approximations? [closed]
A cross post from on AI StackExchange.
So I have this function let call her $F:[0,1]^n \rightarrow \mathbb{R}$ and say $10 \le n \le 100$. I want to find some $x_0 \in [0,1]^n$ such that $F(x_0)$ is ...
- 850
3
votes
2
answers
209
views
$\min(\det(\mathbf{A}))$ for special matrix $\mathbf{A}$
(The construction of matrix $\mathbf{A}$ is not difficult to be understood. You can first jump to A Toy Example to take a glance. Any idea or suggestion would be appealing for me.)
The Original ...
- 133
1
vote
0
answers
31
views
How do I incorporate Ito's lemma into the solution for a finite-horizon stochastic cake-eating problem?
I'm interested in finite-horizon, continuous-time cake-eating problems in which the agent has a time-horizon $W$ over which to eat the cake, and then chooses an optimal consumption path $\{h_t\}_0^W$, ...
- 11
0
votes
0
answers
21
views
Feasibility of a basis of a linear program and a relaxed subproblem
I tend to assume that given $$\min c^\top x \\\ Mx=q$$
$$
\text{where} \\ q = \begin{pmatrix}b \in \mathbb R^m\\d \in \mathbb R^n\end{pmatrix},\\M \in \mathbb R^{(m+n)×2n},\\M=\begin{pmatrix}A\\Q\end{...
1
vote
1
answer
57
views
Given a set of vectors how to pick $M$ such that sum of maximums of coordinates is maximized?
I asked the same on math.Stackexchange.
I have $n$ (say $n = 300$) vectors $v_1,\dots,v_n$. Each of them has $K$ coordinates (say $K = 30$). For vector $v_j$ I denote it's coordinates as $v_{j1},\...
- 850