Questions tagged [oc.optimization-and-control]

Operations research, linear programming, control theory, systems theory, optimal control, game theory

Filter by
Sorted by
Tagged with
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 ...
T. W.'s user avatar
  • 31
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 ...
Yaroslav Bulatov's user avatar
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 ...
Peyman's user avatar
  • 243
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]}$ ...
Ben Carter Jr.'s user avatar
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}^...
lzzz's user avatar
  • 1
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} &\...
Yi-Yu Peng's user avatar
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} :=...
Display name's user avatar
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:...
Fawen90's user avatar
  • 975
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,...
Ham's user avatar
  • 11
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 \...
Nango's user avatar
  • 11
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 ...
Y. Yang's user avatar
  • 83
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}=...
Octane's user avatar
  • 1
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 ...
Rodrigo's user avatar
  • 51
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{...
Yaroslav Bulatov's user avatar
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}^...
Andreea M's user avatar
  • 131
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, ...
Pique's user avatar
  • 9
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, ...
Nate River's user avatar
  • 4,822
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(\...
SPARSE's user avatar
  • 35
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} \...
AspiringMat's user avatar
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 ...
nico's user avatar
  • 91
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 ...
zeta's user avatar
  • 337
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 ...
Simon Kuang's user avatar
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}{...
Yaroslav Bulatov's user avatar
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 ...
elmas's user avatar
  • 55
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}\...
elmas's user avatar
  • 55
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 $...
Fawen90's user avatar
  • 975
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 ...
Zishuo's user avatar
  • 33
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}) - \...
user3750444's user avatar
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 ...
SREEJEET MAITY's user avatar
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 \...
Hyperbolic PDE friend's user avatar
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 ...
Jap88's user avatar
  • 431
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(\...
anon.for's user avatar
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 \...
Hyperbolic PDE friend's user avatar
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 ...
Dmitry Vilensky's user avatar
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\...
Denis Serre's user avatar
  • 51.5k
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 ...
user72829's user avatar
  • 552
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 ...
gcy's user avatar
  • 33
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) ...
Fawen90's user avatar
  • 975
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 ...
MathManiac5772's user avatar
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)$ ...
shahulhameed's user avatar
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 ...
πr8's user avatar
  • 688
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 ...
math-Student's user avatar
  • 1,109
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 ...
KBS's user avatar
  • 13
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 ...
Akira's user avatar
  • 815
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, ...
Bipolo's user avatar
  • 3
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(...
Manoel Reis's user avatar
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 ...
Caio Tomás's user avatar
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} = \...
Leo's user avatar
  • 11
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 ...
Hass Boyouk's user avatar
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,...
BAYMAX's user avatar
  • 51

1
2
3 4 5
23