Questions tagged [oc.optimization-and-control]
Operations research, linear programming, control theory, systems theory, optimal control, game theory
1,140
questions
10
votes
1
answer
360
views
The drunken blind man’s walk
Consider a drunk, blind man starting in the middle of the two dimensional open unit ball. At each turn, the man chooses a direction to move a step of size $\delta > 0$ in. Unfortunately, he is very ...
0
votes
0
answers
43
views
Concentration of bilinear forms
This is a bit vague so I'll begin by indicating the motivation. I am looking for ways to [do something interesting or useful] with the self-attention in transformer models. Ultimately the self-...
2
votes
0
answers
30
views
0-1 knapsack problem with additional capacity
The 0-1 knapsack problem maximizes the profits of items under a capacity constraint (let's call this capacity $C$).
I am interested in an augmented setting where the algorithm is permitted to use a ...
1
vote
0
answers
55
views
Under which condition, such that all second-order critical points satisfy $\sum_j\cos(\theta_i-\theta_j)>0$ for all $i\in[n]$?
Consider the following non-convex function
$$E(\theta):=-\sum_{i,j}A_{ij}\cos(\theta_i-\theta_j)$$
where $A$ is a symmetric, diagonal-free matrix whose non-diagonal element are $\pm 1$. In other words,...
0
votes
0
answers
37
views
Max-flow modeling with unified vehicle and commodity variables
I am working on a network flow problem that involves routing through a time-space network. The network consists of:
A single source node and a single demand node.
A fleet of vehicles with specified ...
0
votes
0
answers
21
views
How to control the angles of Kuramoto model by controlling its order parameter?
Consider Homogenous Kuramoto model in this paper. In theorem 3.1, the author derive condition on $A$ such that all second-order critical points of $E(\theta)$ are in two opposite quadrants, by saying ...
1
vote
0
answers
43
views
Optimal orbital tranfers: reference for statements & proofs
I know that Pontryagin's contribution to optimal control in the 1950'ies was allegedly inspired by the then-nascent rocket industry and the question of how to get a rocket into orbit with minimum fuel....
2
votes
0
answers
153
views
Hunting an invisible target
An invisible target on the integer line starts at $0$. On each round it either stays put, moves to the left or moves to the right by $1$ with probability $\frac{1}{3}$ each. You are then asked to ...
20
votes
2
answers
3k
views
How to optimally bet on a biased coin?
A number $p$ is drawn uniformly at random from $[0, 1]$. You are then given a biased coin that turns up heads with probability $p$, but the number $p$ is not known to you.
You start with a total ...
2
votes
0
answers
135
views
Spectrum of an almost Hamiltonian matrix
I have a complex-valued block matrix $N=\begin{bmatrix}
A & B \\
C & -A^*
\end{bmatrix}$, where $A$ is diagonal, $B=B^*$, and $C$ is rank-1 but not Hermitian.
If $C$ were Hermitian, $N$ would ...
0
votes
0
answers
55
views
Existence of a measurable maximizer
Let $F$ be a continuous cdf with full support on $[0,1].$ Let $A$ be a compact subset of $\mathbb{R}$ and $\mathcal{M}$ be the set of measurable functions $\alpha:[0,1]\rightarrow A.$ Let $\bar \alpha ...
0
votes
0
answers
29
views
Efficient algorithms to find the global minimum of a non-convex quadratically-constrained quadratic program
I am working on a problem involving a non-convex quadratically-constrained quadratic program and am seeking efficient algorithms to find its global minimum. The problem is structured as follows:
Fix ...
0
votes
0
answers
35
views
Seeking help with a matrix optimization problem involving matrix exponentiation
I'm working on an optimization problem where I need to find matrices $P$, $Q$, and $C$ that minimize the norm of the difference between a given matrix $A$ and another matrix defined as $e^{P(Q + Q^T - ...
0
votes
0
answers
40
views
Formulate LABS problem as QUBO
I'm trying to formulate the LABS (low autocorrelation binary sequences) as a QUBO (quadratic unconstrained binary optimisation). The LABS problem is as follows:
Given a sequence $s_i \in \{-1,1\} $, ...
0
votes
0
answers
19
views
Approximation with "quantile-constraints"
Question:
given:
$$\begin{align}&\phantom{=}\lbrace \left(x_i,y_i\right),\ x_i\in\mathbb{X}, y_i\in \mathbb{R}\rbrace_{i=1}^n\\
&\phantom{=}f: (x\in\mathbb{X},\,p_1,\dots,\, p_k\in\mathbb{R})\...
0
votes
0
answers
79
views
Elliptic PDEs in BSDEs and in optimal control
This soft/reference question is related to this MO post of a similar nature.
What are some examples of elliptic PDEs appearing in control and BSDEs?
0
votes
0
answers
30
views
Convergence of numerical scheme for HJB equation
Convergence of numerical scheme for HJB equation has been widely studied, the key paper is the Barles's one. Essentially, the convergence is guarenteed if the scheme is:
Consistent
Stable
Monotony
...
1
vote
1
answer
72
views
Second order differentiability of solution operator to nonlinear boundary value problem
I am currently reading the paper [1]. The paper deals with the BVP:
\begin{align*}
\partial_t u - \Delta u + u(u-a) & = -qu \text{ in } ]0,T\mathclose[ \times \Omega \\[6pt]
\partial_{n}u & = ...
0
votes
0
answers
45
views
Numerically finding periodic solution to Riccati equation with a scalar unknown parameter
We have a Riccati equation with an unknown scalar parameter $a$. It is proven to have unique real solution pair $\{y(x), a\}$ exists so that $y$ is periodic:
$$
y'=ap_{0}(x)+q_{0}(x)+q_{1}(x)y+q_{2}(x)...
1
vote
1
answer
75
views
Norm bound in simultaneous stability to semidefinite program
In the context of robust control, I remember hearing that the two following problems are equivalent.
Find $P \succ 0$, such that $A P + P A^{\top} \prec 0$ for all $A \in \mathscr{A}$ where $$\...
0
votes
0
answers
35
views
Generalized envelope theorems
I'm looking for references for two generalizations of Danskin/envelope-type theorems for convex optimization. The first is for when the parameters are functions on a space rather than numbers. A ...
2
votes
2
answers
311
views
Uniqueness of sum of squares representation
Given a polynomial $f(x) \in \mathbb{R}[x] = \mathbb{R}[x_{1},\dots,x_{n}]$. We say $f(x)$ is sum of squares(SOS) if there are polynomials, $p_{1},\dots,p_{k}$ such that $f = p_{1}^{2} + \dots+p_{k}^{...
0
votes
0
answers
48
views
Alternatives to McCormick Envelope
I have an optimization problem for which I have the optimal solution obtained by the ILP.
However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
2
votes
0
answers
112
views
Seeking insights on bounded set positive solutions for a set of linear systems in $\mathbb{R}^n$
Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (...
0
votes
0
answers
25
views
Which penalization works for this optimisation problem?
Let $m,n$ be given integers. Set $K:=[0,1]^{mn}$ and define the function $L:K\times\mathbb R_+^m\times\mathbb R_+^n\to\mathbb R$ as follows : for $z=(z_{i,j})\in K$, $a=(a_i)\in\mathbb R_+^m$, $b=(...
9
votes
2
answers
528
views
Book for matroid polytopes
I have made a study of polytopes with the books of Ziegler and "Integer Programming" of Conforti, my main goal is to study matroid polytopes; to study matroids I have thought about the book &...
3
votes
1
answer
234
views
Is this constraint convex?
I have an optimization problem where the following constraint causes DCP Rule Error.
$$e^{x_n} \leq B \log _2\left(1+\frac{e^{\rho_n} g_n^2}{\sum_{i=1}^{n-1} e^{\...
0
votes
0
answers
90
views
Primal optimal attained implies dual optimal attained
Given some optimization problem
$$\min_{x \in S \subset \mathbb{R}^n} f_0(x) \quad \text{s.t.} \quad f_i(x) \leq 0, \quad 1\leq i\leq m$$
we can find the dual problem
$$\max_{\lambda\in\mathbb{R}^m} g(...
3
votes
1
answer
169
views
Convex optimization without Slater's condition
In nearly all convex optimization methods that I read about, it is assumed that the problem satisfies Slater's condition, that is, there is a point that strictly satisfies all constraints (the ...
2
votes
1
answer
126
views
Estimating $\max_{\|u\|=1} \frac{ E\left[\langle u\cdot x\rangle ^4\right]}{E\left[\langle u\cdot x\rangle ^2\right]}$
Suppose we have access to samples of $x$ distributed according to unknown multivariate Gaussian in $\mathbb{R}^d$. Estimate the following quantity:
$$\max_{\|u\|=1} \frac{ E\left[\langle u\cdot x\...
4
votes
2
answers
462
views
How to get this inequality in Santambrogio's book about optimal transport?
Let $\hat{\varrho}, \tilde{\varrho}$ be probability density functions on $\mathbb R^d$ where $\tilde{\varrho} \in L^{\infty} (\mathbb R^d)$. For $\varepsilon \in [0, 1]$, we define $\varrho_{\...
0
votes
0
answers
67
views
Computationally efficient solution for the measure of central tendency minimizing Lp loss for p > 1
We know that the measure of central tendency that minimizes the Lp loss is $\min_c \sum_{i=1}^n |x_i - c|^p$
For $p=1$ (L1 loss), this is the median. For $p=2$ (L2 loss), this is the mean. Both of ...
2
votes
1
answer
145
views
Conic hull of a rectangle
I have a simple question that appeared in research: For a rectangle $S :=[a_1,b_1] \times[a_2,b_2] \times \dots \times [a_n,b_n] \subset \mathbb{R}^n$. Let $p_0 = (a_1,a_2,\dots,a_n)$, and define $p_i ...
2
votes
0
answers
168
views
Regularity of linear Bellman equation
Let $f(x,t):B_1 \times [0,1] \to \mathbb{R}$ be Lipschitz function on both $x$ and $t$, $\varphi$ be Lipschitz function on both $x$ and $t$ on the parabolic boundary of $B_1 \times [0,1]$. Let $A$ be ...
0
votes
0
answers
33
views
Solving optimization problem restricted to non-convex subset
I have two continuous random variables that have pdfs with respect to the Lebesgue measure $p_{-1}(x), p_1(x)$.
Let $m(x) := \frac{p_{-1}(x)+p_1(x)}{2}$ be a mixture of these two distributions.
Let $B(...
0
votes
1
answer
127
views
Existence of cyclic subspace decompositions for pairs of commuting matrices
Let $\mathbb{K}$ be an arbitrary field (possibly finite). Let $V$ be a finite-dimensional vector space over $\mathbb{K}$, and let $A,B$ be two linear endomorphisms of $V$ which commute.
For $v\in V$, ...
2
votes
0
answers
118
views
Graph Laplacians, Riemannian manifolds, and object collisions
To preface this question, I am a part-time game developer and full-time optimization fiend.
I am working on object collisions at the moment and many resources I have found online are more-or-less just ...
1
vote
0
answers
129
views
Optimal transport-like problem where the objective depends on conditional probability distribution
$\DeclareMathOperator\marg{marg}$I would like to know if the following problem can be studied as an optimal transport problem, possibly imposing additional assumptions on the data.
Consider two sets $\...
13
votes
2
answers
1k
views
Optimal search puzzle
Consider the following puzzle: On the integer line from 1 to $t$ (top, let's say 1000 for this example), you have two operators: uniform random on 1 to $t$, and subtract 1. What is the optimal ...
0
votes
0
answers
70
views
Error bound for stochastic gradient descent method
To solve an optimization problem $\min_x G(x)$ using standard stochastic gradient descent method, we let $x_0$ be the initial point and $x_k$ be the $k$-th point such that
\begin{equation}
x_k = x_{k-...
1
vote
1
answer
81
views
optimization over moving domains
Let $A, B$ be Banach spaces, and for any $a\in A$, $B_a\in B$ is a measurable subset. Consider the following optimization problem:
$$L(a)=\inf_{b\in B_a}\ell(b),$$
where $\ell(b)$ is a infinite-times ...
0
votes
1
answer
139
views
nonlinear equation problem
Can you please help me solve the following nonlinear equation to determine the value of the vector $z$ :
$$
\boldsymbol{a}=\boldsymbol{z}^{2} \odot \boldsymbol{K}*\boldsymbol{z}^{-1}$$
Where:
$\...
1
vote
0
answers
49
views
LICQ vs MFCQ who is stronger [closed]
I want to ask you which constraint is stronger: MFCQ or LICQ.
0
votes
0
answers
46
views
Approximation factor for TSP Algorithm
The literature that I have reviewed shows examples of calculations of known approximation algorithms such as the Christofides' algorithm for the TSP. However, I have not been able to find information ...
0
votes
0
answers
18
views
Find condition of X such that I-XSA is nonsingular, where $S$ is skew-symmetric and $A$ is symmetric, nonsingular
Given $I_n$ is the identity matrix, $A \in \mathbb{R}^{n,n}$ is symmetric and nonsingular, and $B\in \mathbb{R}^{n,n}$ is skew-symmetric.\
a) For which condition of a matrix $X \in \mathbb{R}^{n,n}$, ...
0
votes
0
answers
58
views
Optimal top-k column subset
Let $V$ be a set of vectors over $\mathbb{R}^l$, $l\ge 1$, $\pi_i(V)$ be the permutation of vectors in $V$ such that they are ordered by their $i$th component (descending) in order for $\pi_i(V)(\...
2
votes
0
answers
108
views
Controlling the adjoint variables in a stochastically perturbed control problem
Suppose we have a deterministic control problem
$$dX_t = b(X_t, u_t) \, dt$$
on a finite timeframe with no terminal cost; i.e. the objective functional to be maximised is
$$\mathbb E \left [\int_{0}^T ...
2
votes
1
answer
146
views
Can we say this nonlinear integer programming problem is NP-hard?
I was wondering if the following nonlinear integer programming problem is NP-hard or not.
$$\max_{x_i \in \{0,1\}} \frac{\sum_{i=1}^{n}a_i x_i}{\sqrt{\sum_{i=1}^{n}b_i x_i}}$$
such that $\sum_{i=1}^{n}...
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
195
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 ...