# 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} \...

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 ...

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 ...

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 ...

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}{...

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 ...

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}\...

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 $...

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 ...

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}) - \...

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 \...

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

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(\...

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 \...

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\...

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 ...

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 ...

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) ...

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 ...

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)$ ...

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 ...

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 ...

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 ...

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 \...

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 ...

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 ...

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(...

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 ...

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} = \...

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 ...

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,...

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 ...

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 ...

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\...

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 ...

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)...

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\{...

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 ...

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}...

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, ...

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} & \...

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 ...

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 ...

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$, ...

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},\...