Questions tagged [oc.optimization-and-control]
Operations research, linear programming, control theory, systems theory, optimal control, game theory
1,147
questions
0
votes
0
answers
19
views
control of bifurcation in dynamical system by using normal form and feedback
enter image description here
enter image description here
the book "Approved for public release; distribution is unlimited.
THE CONTROL OF BIFURCATIONS
WITH ENGINEERING APPLICATIONS
by
Osa E. ...
6
votes
1
answer
190
views
Can the Chebyshev polynomials be constructed from the extremal property?
It is a known fact that the Chebyshev polynomials, defined as $T_n := \cos(n \arccos x)$, have the following extremal property:
Theorem: Of all monic degree $n$ polynomials, $\frac1{2^{n-1}} T_n$ has ...
- 63
-1
votes
1
answer
56
views
Minimizing expressions involving function subject to integral constraint
Fix a positive constant $q=O(1)$ (say $1.5$). I am trying to find a function $\ell(x):[0, 1] \to \mathbb{R}_{\geq 0}$ that satisfies $\int_0^1 \ell(x) dx \leq q$ and minimizes the expression
$$\int_0^...
0
votes
0
answers
32
views
Generalizations of Berge's maximum theorem
I have a parameterized optimization problem
\begin{eqnarray}
\max_{x\in D(\theta)} f(x,\theta).
\end{eqnarray}
Assumptions of the standard Berge's maximum theorem are satisfied, so the value function $...
1
vote
0
answers
25
views
When does an optimal input sequence for a discrete-time system exist?
Suppose an LTI discrete-time system is given by the equations
$$
x_{k+1} = Ax_k + Bu_k,\\
y_{k} = Cx_k + Du_k
$$
with $x_k\in\mathbb{R}^{m}$, $y_k\in\mathbb{R}^{n}$ and $u_k\in\mathbb{R}^{p}$ and $\...
1
vote
0
answers
29
views
Variants of cutting plane method for convex optimization
The cutting plane approach in convex optimization is a general recipe for minimizing a convex function. The argument relies on the fact that using the gradient vector, we can cut the feasible set into ...
- 139
1
vote
0
answers
50
views
Pontryagin's maximum principle for discrete systems: reference request for general case [closed]
I am reading the articles:
Optimal control for systems described by difference systems, Hubert Halkin, Advances in Control Systems, Vol 1, Academic Press, New York-London, 1964, Pages 173-196, ...
- 111
0
votes
0
answers
43
views
Gradient-based optimization of $n$ functions
I appreciate the willingness of everyone to assist me in advance.
I am faced with a set of $n$ distinct convex optimization problems, each defined as follows:
\begin{equation}
\max\limits_{x \in \...
- 1
10
votes
1
answer
460
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 ...
- 4,832
0
votes
0
answers
49
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-...
- 6,882
2
votes
0
answers
32
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 ...
- 21
1
vote
0
answers
58
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,...
- 39
0
votes
0
answers
38
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 ...
- 101
0
votes
0
answers
24
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 ...
- 39
1
vote
0
answers
45
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....
- 1,451
2
votes
0
answers
159
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 ...
- 4,832
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 ...
- 4,832
2
votes
0
answers
136
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 ...
- 116
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 ...
- 1
0
votes
0
answers
30
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
38
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
44
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})\...
- 12.7k
0
votes
0
answers
80
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?
- 4,969
0
votes
0
answers
31
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
...
- 175
1
vote
1
answer
76
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 & = ...
- 161
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
80
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 $$\...
- 195
0
votes
0
answers
36
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 ...
- 4,017
2
votes
2
answers
319
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}^{...
- 195
0
votes
0
answers
52
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 ...
- 3
2
votes
0
answers
114
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=(...
- 975
9
votes
2
answers
537
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 &...
- 201
3
votes
1
answer
239
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^{\...
- 31
0
votes
0
answers
92
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(...
- 195
3
votes
1
answer
198
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 ...
- 3,585
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\...
- 2,380
4
votes
2
answers
464
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_{\...
- 851
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 ...
- 109
2
votes
1
answer
147
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 ...
- 195
2
votes
0
answers
171
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 ...
- 44
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(...
- 1,861
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$, ...
- 21.8k
2
votes
0
answers
119
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 ...
- 21
1
vote
0
answers
134
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 ...
- 265
0
votes
0
answers
72
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-...
- 771
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 ...
- 87
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:
$\...
- 11