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
185
views
How expensive is a proximal operation?
In optimization, a proximal step is usually considered as cheap as a gradient step. I'm quite confused by this. Why are people taking this convention at all?
A typical proximal step indeed incurs a ...
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 ...
1
vote
1
answer
279
views
Optimal transport between two matrices
I'm investigating the use of optimal transport to define a distance between non-negative matrices that satisfy the condition $\mathbf e^\top\mathbf M\mathbf e = 1$ (i.e., the sum of all elements in ...
0
votes
0
answers
127
views
Convex conjugate of the sum of smallest elements
I recently came across this problem to find the conjugate function of the sum of $r$ smallest elements in a vector
$$f(x) = \sum_{i=n-r+1}^{n}x_{[i]} \text{ for } x \in \mathbb{R}^n$$
where $x_{[i]}$ ...
0
votes
0
answers
54
views
Relationship of optimal solutions between the total function and the sub function
This is an unconstrained convex optimization problem. Let $\mathcal{N}=\left\{1,\ldots,n\right\}$, $2\leq n<\infty$. Suppose there are many strongly convex functions $f_i(x)$, where $x\in\mathbb{R}^...
0
votes
0
answers
70
views
How to solve mckp (multiple-choice knapsack problem) problem with non-linear constraint
How to solve the below optimization problem? $P$ is a probability matrix, $0\le P_{ij}\le 1$. Are there any developed tools to solve this? Thanks a lot.
\begin{equation*}
\begin{aligned}
&\...
3
votes
1
answer
130
views
How to turn $\{-1, 0, 1\}$-valued optimization problem into integer program?
For an $n \times n$ matrix $M$, the $\infty\to 1$ and cut norms are given by
$$\|M\|_{\infty \to 1} := \max\limits_{x, y \in \{\pm 1\}^n} \sum\limits_{i, j} m_{i, j} x_i y_j, \qquad \|M\|_{\square} :=...
0
votes
0
answers
56
views
An optimization problem defined by optimal transportation
Let $\mu,\nu$ be two probability measures on $E:=\mathbb R^d$ and denote by $\gamma:=\mu\otimes \nu$ the product measure on $E\times E$. Define $\mathcal K$ to be the class of continuous functions $k:...
1
vote
1
answer
111
views
Exponential optimization problem
\begin{eqnarray}
\arg\max_{k}\sum_{i=1}^{p}\sum_{j=1}^{p}\exp\left(-{\frac{\left(X(i,j)-{U_k}(i,j)\right)^2}{2}}\right),\:\: k=0,\dots,p
\end{eqnarray}
where $X$ and $U_k$ are the $p\times p$ matrices,...
1
vote
0
answers
33
views
Minimizing a ratio related to scalar subset sums
Let $a = (a_1, a_2, \cdots, a_n)$ be non-zero real numbers. Let $[n] = \{1,2,\cdots,n\}$ be a set of indices. Define the maximum absolute subset sum of the array $a$ as:
$$\mathrm{MASS}(a) = \max_{T \...
0
votes
0
answers
87
views
The best probability distribution for the game of Number Master
In the game of Number Master, the player controls a number starting with $1$ and hits the other numbers one by one on the road.
If the player hits a number smaller or equal to the current controlling ...
0
votes
0
answers
47
views
Seeking advice on numerical solutions for a quadrotor soft landing optimization control problem
I am working on an optimization control problem concerning the soft landing of a quadrotor. The dynamic model and performance index are given as follows:
Its dynamic model is:
$$\dot{r}=v$$
$$\dot{v}=...
3
votes
1
answer
200
views
Interesting question about the Thomson problem for arbitrary number of electrons
This question is crossposted from here I believe this is a pretty hard question and so I decided to repost the question in the Math Overflow forum. If there is something wrong with doing this, I am ...
0
votes
0
answers
48
views
Bounding the ratio of two functions given their Laplace Transforms
Suppose $h(i)$ is a probability density that's "nice" in some sense, and $g(i)=E[f(i,x)]=\int \mathrm{d}i\ h(i)f(i,x)$
How could I bound the following ratio $r(t)$ from above?
$$
r(t)=\frac{...
4
votes
1
answer
211
views
Equivalence of bounded gradient flow solutions and uniformly bounded gradient descent trajectories for definable functions
I am reading paper [1] by C. Josz regarding the global convergence of the gradient method. The main result is the following:
$\textbf{Theorem}$: For a definable differentiable function $f : \mathbb{R}^...
0
votes
0
answers
28
views
Adjust X to strengthen the linearity to Y, in regression model
Assume that we have 2 series X and Y, and obvious we can fit a linear regression model and get all the statistics. I am seeking for some transformation / adjustment which will adjust the value of X, ...
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
3
answers
198
views
How to convexify or reformulate this non-convex MIP?
I am interested in this non-convex mixed-integer program:
\begin{array}{cl}
\displaystyle\min_{(x_{i},y_{i})\in\mathbb{Z}^{+}\times\mathbb{Z}^{+}}&\displaystyle\sum_{i=1}^{K}y_{i}\left(\...
1
vote
0
answers
67
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} \...
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 ...
0
votes
1
answer
175
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 ...
1
vote
0
answers
57
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 ...
5
votes
1
answer
197
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}{...
1
vote
0
answers
50
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 ...
1
vote
0
answers
41
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}\...
1
vote
0
answers
100
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 $...
3
votes
1
answer
130
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 ...
2
votes
0
answers
118
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}) - \...
0
votes
0
answers
31
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
206
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 \...
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 ...
0
votes
1
answer
79
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(\...
0
votes
1
answer
88
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 \...
1
vote
1
answer
300
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
75
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\...
1
vote
1
answer
104
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 ...
3
votes
1
answer
144
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 ...
0
votes
0
answers
91
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) ...
1
vote
0
answers
90
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 ...
1
vote
0
answers
82
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)$ ...
1
vote
2
answers
59
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 ...
1
vote
1
answer
85
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
vote
1
answer
256
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 ...
1
vote
1
answer
209
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 ...
0
votes
1
answer
127
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
125
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(...
14
votes
2
answers
656
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 ...
1
vote
0
answers
41
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} = \...
2
votes
1
answer
190
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 ...
6
votes
3
answers
919
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,...