Questions tagged [oc.optimization-and-control]
Operations research, linear programming, control theory, systems theory, optimal control, game theory
1,148
questions
2
votes
0
answers
41
views
Gradient descent over the set of complex symmetric matrices
In the course of my research (somewhat related to compressive sensing), I am trying to determine a complex, symmetric matrix $L$ (i.e. $L = L^T$) through the following optimization formulation:
$$ \...
- 60.4k
2
votes
2
answers
387
views
Upper bounds on the worst-case traveling salesman tours in the unit square
The paper [1] proves that, if we place $N$ points in the unit square, then the length $\ell$ of the euclidean TSP tour of those points must satisfy $$\ell \leq \sqrt{2N} + 7/4~~.$$ I'm wondering, can ...
- 101
3
votes
1
answer
272
views
Measuring how suboptimal control is
Suppose I have a linear dynamical system to control. I use PMP to find necessary conditions for the optimal control of the system wrt to some objective function. Now, suppose that the trajectory I ...
CommunityBot
- 1
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. ...
- 52.4k
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 ...
1
vote
1
answer
137
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,...
CommunityBot
- 1
22
votes
4
answers
5k
views
Is there an intuitive explanation for an extremal property of Chebyshev polynomials?
Consider the following optimization problem:
Problem: find a monic polynomial $p(x)$ of degree $n$ which minimizes $\max_{x \in [-1,1]} |p(x)|$.
The solution is given by Chebyshev polynomials:
Theorem:...
- 11.9k
-1
votes
1
answer
57
views
Minimizing expressions involving function subject to integral constraint [closed]
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^...
- 570
1
vote
1
answer
68
views
Complexity of calculating the optimal amalgamation of an optimal cycle-cover
Let $G(V,E)$ be a complete symmetric graph with positive edge weights and let further $\mathcal{C}=\lbrace C_1,\,\cdots\,C_k\rbrace$ be the minimum-weight vertex-disjoint cycle cover.
The set $E$ of ...
CommunityBot
- 1
4
votes
1
answer
7k
views
Matrix optimization problem
This is (probably) an easy one:
Given a positive definite matrix $M$, find the positive definite matrix $X$, which minimizes $\textrm{tr}(X M)$ subject to $\det(X) = 1$.
Looking for how to find X, ...
- 1,446
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 ...
- 2,758
0
votes
1
answer
168
views
Applications of linear fractional relationship
This may be the wrong forum, but are there any natural contexts (physics, economics, etc.) in which one might observe the relationship $y = ax/(bx+c)$ between a pair of variables $x$ and $y$? General ...
- 1,446
2
votes
1
answer
278
views
Positivity of quadratic form minus linear form on the simplex
Let $a_{ij}$ be the elements of a $n$-dimensional covariance matrix. Can we prove the following?
$$ 1-\sum_{k=1}^n a_{ik} \lambda_k + \sum_{j=1}^n \sum_{k=1}^n \lambda_j a_{jk} \lambda_k > 0, \...
CommunityBot
- 1
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 \...
- 4,618
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, ...
- 5,632
1
vote
2
answers
246
views
Optimal path with multiple costs
Given a graph $G=(V,E)$, each edge $e$ has $k$ costs $c_i(e)$, $1\le i\le k$. Correspondingly, a path $P$ is also characterized by $k$ costs where $c_i(P)=\sum_{e\in P} c_i(e)$. Given vertices $s$ and ...
- 5,169
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 $$\...
CommunityBot
- 1
5
votes
3
answers
1k
views
Constant rank theorem for Banach spaces
Is there a similar statement to the constant rank theorem for finite dimensional real smooth manifolds which holds for a smooth map $F:B \rightarrow M$ where $B$ is an infinite (countable) dimensional ...
- 11.4k
10
votes
1
answer
462
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 ...
- 7,434
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
1
vote
1
answer
235
views
Transport theorem in space craft control: tracking a reference angular velocity
I am reading the book named "Analytical mechanics aerospaces systems" by Schaub and Junkins.
In section 7.2, the task is to control the spacecraft to track a specified angular velocity $w_r$ ...
CommunityBot
- 1
3
votes
1
answer
255
views
Latent Dirichlet allocation and properties of digamma function
In the paper Blei, D. M., Ng, A. Y., & Jordan, M. I. (2003). Latent Dirichlet Allocation. Journal of Machine Learning Research, 3(4–5), 993–1022. http://www.jmlr.org/papers/volume3/blei03a/blei03a....
CommunityBot
- 1
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 ...
- 60.4k
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,...
- 21.8k
3
votes
2
answers
248
views
Probability that the solution to a combinatorial optimization problem changes after random modifications
Given a combinatorial optimization problem, say the Traveling Salesman Problem, the optimal solution is a set of elements (edges in this case) that satisfy certain constraints (constituting to a ...
CommunityBot
- 1
1
vote
1
answer
405
views
Looking for an efficient way of maximising 'pair scores' for subset of 30 selected from 50 to 10 000 objects
Context: I have a tiling program that uses a directed breadth first search algorithm. It is 'directed' by what I call 'pair scoring'. There are $N$ polyforms (pieces) used in the tiling. I have an $N\...
CommunityBot
- 1
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}^{...
- 13
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
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 ...
- 60.4k
1
vote
0
answers
46
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
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 ...
- 545
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
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
2
votes
1
answer
225
views
Basis pursuit algorithms for exponentially large matrices?
Are there any efficient algorithms/heuristics for basis pursuit for exponentially large matrices?
That is
$$\begin{array}{ll} \underset{x \in \Bbb R^n}{\text{minimize}} & \lVert x \rVert_0\\ \text{...
CommunityBot
- 1
4
votes
1
answer
195
views
A question on eigenvalue of parametric matrix
Is there a way to efficiently check if all matrices in the following set are Hurwitz stable (eigenvalues strictly in the left-hand plane)?$$\left\{ A \in \Bbb R^{n \times n} : \ell_{i,j}\leq A_{i,j} \...
CommunityBot
- 1
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 ...
- 178k
9
votes
1
answer
664
views
How do people prove $\Gamma$-convergence in more complicated settings?
This is a soft question, I guess. $\Gamma$-convergence is a notion of convergence of functionals so that if $F_n$ $\Gamma$-converges to $F$, then cluster points of $\arg\inf F_n$ are minimizers of $F$....
- 2,102
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
56
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
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\} $, ...
- 11.4k
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})\...
- 2,758
16
votes
1
answer
867
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, ...
- 18.4k
5
votes
2
answers
1k
views
Textbooks or lecture notes about mean field games
I am looking for a good introductory level textbook (or lecture notes) on mean field games that would be suitable for a graduate course. Ideally, it would include some brief words about optimal ...
- 178k
3
votes
1
answer
249
views
Optimal rule for multiple stopping times for defect finding
Suppose a quality inspector is inspecting $b$ black amongst which $d_B$ are known to be defective and $w$ white gadgets amongst which $d_W$ are known to be defective. The gadgets come down along an ...
CommunityBot
- 1
1
vote
1
answer
293
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 ...
CommunityBot
- 1
2
votes
1
answer
229
views
Minimizing quadratic objective under orthogonality constraints
The following problem is motivated from Generalized Procrustes Analysis. I am wondering if it is possible to obtain a closed form minimizer (which may involve SVD or some other decomposition of a ...
CommunityBot
- 1
11
votes
2
answers
752
views
A (linear) optimization problem subject to (linear) matrix inequality constraints
Let $A \in \mathbb{R}^{n \times n}$ be a Hurwitz matrix, i.e. $A$ satisfies $\mathrm{Re}\,\lambda_i< 0$, where $\{\lambda_i\}_{i=1}^n$ is the set of eigenvalues of $A$. Suppose that the trace of $A$...
CommunityBot
- 1