Questions tagged [oc.optimization-and-control]
Operations research, linear programming, control theory, systems theory, optimal control, game theory
857
questions
21
votes
4answers
1k views
Why do bees create hexagonal cells ? (Mathematical reasons)
Question 0 Are there any mathematical phenomena which are related to the form of honeycomb cells ?
Question 1 May be hexagonal lattice satisfy certain optimality condition(s) which are related to ...
0
votes
0answers
25 views
How can I deploy a CG-Steihaug algorithm for trust region sub-problem solving?
I'm studying various optimization methods and on this occasion, I'm trying to tackle the Trust Region Problem by solving the sub-region problem with the Steihaug-CG algorithm in Python. I'm using the ...
4
votes
0answers
83 views
Does the plane clustered to minimize sum distances^2 to clusters centers ( inertia / “K-means”) produce hexagonal clusters / hexagonal lattice?
"K-means" is the most simple and famous clustering algorithm, which has numerous applications.
For a given as an input number of clusters it segments set of points in R^n to that given number of ...
3
votes
2answers
111 views
Intuition behind Gubinelli derivative
I apologise for the confusion of the following sentences. I'm lazy to give more information about Rough path theory as Is a fairly broad subject.
On page 14 of "A Course on Rough Paths
With an ...
1
vote
2answers
144 views
+50
How to solve this stochastic optimization problem?
How one can solve the following stochastic optimization problem?
\begin{align}
\max\quad& \mathbb{E}[\mathbf{1}^{\mathrm{T}}X]\\
\text{s.t.} \quad& \mathbb{E}[\mathbf{A}X]\leq\mathbf{1}_{m\...
25
votes
1answer
1k views
SOS polynomials with integer coefficients
A well known theorem of Polya and Szego says that every non-negative univariate polynomial $p(x)$ can be expressed as the sum of exactly two squares: $p(x) = (f(x))^2 + (g(x))^2$ for some $f, g$. ...
3
votes
1answer
159 views
Reference request: Variational techniques for complex “iterated” Lagrangians
I am interested in solving variational problems of the form
$$
\min_u \int \Big\{L(x,y,u(x,y)) + \phi\Big(\int J(z,y,u(z,y))\,dz\Big)\Big\} p(x,y)\,dx\,dy.
$$
for some known, smooth functions $L,J,\...
0
votes
1answer
56 views
Minimum mean over all random variables subject to logarithm constraint
Does the following problem have a solution?
$$
\min_X \mathbb{E} X
\quad\text{subject to}\quad
\mathbb{E} \log X = C.
$$
Here, the minimization is with respect to all integrable random variables $X$ ...
1
vote
1answer
86 views
Sampling i.i.d. variables with restrictions
General Problem: Suppose $X_1,\ldots,X_n \sim \mathbb{P}_X^{\otimes n}$ is a finite sequence of i.i.d. (real- or integer-valued) random variables. Suppose $A\subseteq \mathbb{R}^n$ is a set of "...
0
votes
0answers
23 views
Clarification of second order condition on orthogonal optimization
In the paper A Feasible Method for Optimization with Orthogonality Constraints, the arthors write:
where
I am confused about the notation $\mathcal{D}(\mathcal{D}\mathcal{F}(X))[Z]$.
My ...
2
votes
1answer
32 views
Does a scalar LTV system with odd-periodic coefficients and even-periodic inputs have no periodic solutions?
Problem Setup
Suppose we have the following scalar, linear time-varying (LTV) system with parameter $\mu \in [0,\pi[$:
\begin{cases}
\dot{x_1}(t,\mu) = a(t,\mu)x_1(t,\mu) + b(t,\mu) \\
x_1(0,\mu) = ...
0
votes
0answers
13 views
Constrained maximin optimisation problem
Let
i) $\mu = [\mu_1,\mu_2,\mu_3]\in\mathbb{R}^3$, such that $\mu_2 > \mu_1$, $\mu_2 >\mu_3$ fixed,
ii) $\lambda = [\lambda_1,\lambda_2,\lambda_3] \in \mathbb{R}^3$ such that $\lambda_1 \geq \...
4
votes
2answers
237 views
Eigenvalues of a matrix sum
I have a control system problem, which ends up in that the eigenvalues of the system matrix should have a negative real part, then the system is stable.
The system matrix is real but not symmetric. ...
1
vote
1answer
49 views
Conditions for optimal stationary strategies in MDPs
I have a specific markov decision process (MDP) which is generated from a problem in another domain. What I would like to show is that under the limit of means criterion (no discounting) the optimal ...
0
votes
0answers
86 views
A minimax optimization with expectation operator
Let $\mathbf{X}$ be an $m\times n$ random matrix with Gaussian i.i.d entries with zero mean and unit variance. How we can think about the following optimization
\begin{align}
\max_m\mathbb{E}_\mathbf{...
0
votes
0answers
37 views
A nonlinear PDE on a matrix domain involving a maximum eigenvalue operator
In a research problem in optimal control
$^{\ast}$ I came across the following nonlinear first-order PDE:
$$\frac{\partial V}{\partial t}=\max\text{eig}\left[\sum_{i=1}^m P_i\frac{\partial V}{\partial ...
2
votes
1answer
59 views
Max-norm projection of a Hermitian matrix onto the set of positive semidefinite matrices
For a given Hermitian matrix $A$ (i.e. complex matrix with $A_{ij}^{\ast}=A_{ji}$) find its max-norm projection onto the set of complex positive semi-definite matrices:
$$\Pi(A)=\mathrm{argmin}_{M\...
1
vote
1answer
65 views
$\arg\max$ in the dual norm of the nuclear norm
Given a matrix $X \in \mathbb{R}^{m \times n},$ then the spectral norm is defined by
$$\left \| X\right\| := \max\limits_{i \in \{1, \dots, \min\{m,n\}\} }\sigma_i (X)$$
whereas the nuclear norm is ...
1
vote
1answer
65 views
Maximizing the length of a sequence under constraints
Fix $\{w_n\}_n$ a sequence of positive real numbers, fix positive integers $N,K$, and fix $\eta>1$. I'm looking for a sequence of integers $\{k_n\}_n$ optimizing the following problem:
$$
\begin{...
2
votes
1answer
86 views
Optimal transport: find cost function given observed transport
Could you advise me please on what to read on the "inverse" problem: suppose I have a source measure, a target measure and I observe the solution to optimal transport problem -- can I "back out" the ...
0
votes
0answers
65 views
Convergence of heavy-ball method for non-convex optimization
The heavy-ball method (also called gradient descent with momentum) is commonly used in optimization. The update rule can be written as:
$$x_{t+1}=x_t-\eta\nabla f(x_t)-\beta (x_t-x_{t-1})$$
Suppose $\...
0
votes
1answer
48 views
Minimize overlap penalty between paths in graph
Suppose we have a weighted undirected graph $G(V,E)$. We are given the information that $V_a \cap V_b = \emptyset$ and $V_a,V_b \subset V$.
We want to find paths from all vertices in $V_a$ to all ...
25
votes
1answer
725 views
The lion and the zebras
The lion plays a deadly game against a group of $N$ zebras that takes place in the steppe (= an infinite plane). The lion starts in the origin with coordinates $(0,0)$, while the $N$ zebras may ...
2
votes
0answers
120 views
Optimization with parametric constraints: solution maps
For constrained optimization problems
$$ \begin{array}{ll} \min\limits_{x \in \mathbb R^n} & f(p, x) \\
\text{s.t.} & x \in C \end{array} $$
where $p \in \mathbb R$ is a parameter, we can ...
2
votes
0answers
56 views
Showing an “obviously-optimal” control is optimal (without smoothness assumptions)
Let $\mathcal{A}\subseteq\mathbb R$ be a compact interval, $T\in\mathbb R_+$ be a finite horizon, and $g:\mathbb R\to\mathbb R_+$ be a continuous function with $g\leq 1+|\cdot|$. Consider an optimal ...
0
votes
0answers
29 views
Existence of an optimal control
I am looking for an existence result for the following control problem:
Fix a probability space $\langle \Omega, \mathcal F, \{\mathcal F_t\}_t, \mathbb{P}\rangle$ that satisfies the usual ...
0
votes
0answers
26 views
Find a complex matrix on a unit sub-spheres
I am new to optimization theory. I have a following question. For a given $X = [x_1 x_2 \ldots x_N] \in \mathbb{C}^{N \times N}$, where $x_i \in \mathbb{C}^{N\times 1}$ for $i \in \{1,\ldots,N\}$, $U =...
0
votes
0answers
45 views
Lagrange multiplier theorem for nonnegative integral functional (fix issue with infinite integral)
Let
$(E,\mathcal E,\lambda)$ be a $\sigma$-finite measure space;
$N\in\mathbb N$;
$p_i$ be a probability density on $(E,\mathcal E,\lambda)$ for $i\in\{1,\ldots,N\}$;
$w_i:E\to\mathbb R$ be $\mathcal ...
0
votes
0answers
46 views
Find minimizer of nonnegative integral functional over a closed convex subset of $L^2$
Let
$(E,\mathcal E,\lambda)$ be a $\sigma$-finite measure space and $$\lambda f:=\int f\:{\rm d}\lambda$$ for $\lambda$-integrable $f:E\to\mathbb R$;
$p:E\to[0,\infty)$ be $\mathcal E$-measurable ...
4
votes
3answers
97 views
Find distribution that minimises a function of its moments
Imagine a probability density function $f(x)$, defined for positive $x$, and let's note its $n$th non-centred moment $x_{n}$. The mean $x_{1}$ is fixed (and positive).
How can I find $f(x)$ that ...
0
votes
0answers
36 views
Computational complexity of optimization algorithms using random algorithm theory
A fundamental and undoubtedly much-studied problem is that of determining not only whether or not an optimization algorithm converges to its optimum but also how fast it converges (see a discussion on ...
2
votes
0answers
66 views
Minimizing $\int\lambda({\rm d}y)\frac{\left|g(y)-\frac{p(y)}c\lambda g\right|^2}{r((i,x),y)}$ with respect to discrete parameter $i$
Let $I\subseteq\mathbb N$ be finite and nonempty, $(E,\mathcal E,\lambda)$ be a $\sigma$-finite measure space, $$\lambda f:=\int f\:{\rm d}\lambda$$ for $\lambda$-integrable $f:E\to\mathbb R$, $p:E\to(...
0
votes
0answers
21 views
Approaches and approximations for specific non-convex low-rank optimization problem
I have recently begun looking at an optimization problem in the context of Wiener filtering and lower-dimensional representations. Assume $ X $ is a random vector of length $ n $ and $ Y $ is a random ...
0
votes
0answers
18 views
Backstepping control of second order nonlinear system
$\dot{x_{1}}=x_{2}^2-3sin(x_{1})x_{2}$
$\dot{x_{2}}=x_{1}^3-3x_{2}cos(x_{1})+u^\frac{1}{2}$
Question: Using the backstepping method and Lyapunov function, design the controller $u$ that will make ...
1
vote
0answers
35 views
Pros and cons of using integer programming alone or combined integer and global optimization?
First, I am not sure if this is the right question to ask in this forum. But I have been looking for answers for a long time and I have been also asking my university's "engineering" professors but I ...
1
vote
0answers
27 views
Solve optimal control problem whose associated system is nonlinear
Solve the optimal control problem of the LQR kind
$$
\min_u \int_0^{+\infty} x_1^2+x_2^2+\gamma(u_1^2+u_2^2) \, dt \quad\text{such that}\quad \begin{cases}\dot x_1=\alpha(x_2-x_1)+u_1,& x_1(0)...
3
votes
1answer
113 views
Maximum of sum of exponential function
Let $x_1,\dots,x_n$ be a set of given vectors in $\mathbb{R}_{+}^d$. Let $c_1,\dots,c_n$ be given positive constants. I am interested in finding the vectors $w_1,\dots,w_n$ in $\mathbb{R}_{+}^d$ that ...
0
votes
0answers
27 views
Consistency results of optimal control solutions using direct transcription
I have read a number of books on discrete time solutions to continuous time optimal control problems.
What is not clear to me is what consistency results exist with respect to showing the discretized ...
0
votes
0answers
59 views
Compute weights (analytically or numerically) so that they minimize an integral
I have a measurable function $f:E\to[0,\infty)$, measurable weights $w_1,\ldots,w_k:E\to[0,1]$ with $\sum_{i=1}^kw_i=1$, positive probability densities $q_1,\ldots,q_k:E\to[0,\infty)$ and measurable ...
4
votes
0answers
48 views
Least squares with matrix product constraints
I am encountering a constrained LS problem with the following structure:
$$
\text{min}_Q\ \sum_{i=1}^M ||Q_i X_i-Y_i||_F^2
$$
$$
\text{s.t. }\ Q_M Q_{M-1}\cdots Q_1=I,
$$
where $Q_i,X_i,Y_i\in \mathbb{...
2
votes
1answer
98 views
Hardness of concave minimization problem
I have an optimization problem $\underset{x}{\min} ~ c(x) - k \cdot x$ where $c(x)$ is a non-decreasing concave function with $c(0) = 0$, $x \in C \subseteq \mathbb{R}^d_{\geq 0}$. By non-decreasing, ...
1
vote
1answer
68 views
Solve a 2-dimensional optimal control problem via Riccati nonlinear equation
Consider the 2-dimensional optimal control problem of the LQR kind
$$
\min_u \int_0^\infty (x^T Q x + u^TRu) \, dt \quad\text{such that}\quad \begin{cases}\dot x(t) = Ax(t)+Bu(t) \\ x(0) = \...
0
votes
0answers
106 views
Compute which of a finite number of integrals is minimal
Let
$(E,\mathcal E,\lambda)$ be a $\sigma$-finite measure space;
$f:E\to[0,\infty)^3$ be a bounded Bochner integrable function on $(E,\mathcal E,\lambda)$ and $p:=\alpha_1f_1+\alpha_2f_2+\alpha_3f_3$ ...
5
votes
1answer
177 views
Generalization of minimal selection theorem
Consider a metric space $X$ and a set-valued map $F : X \to \mathbb{R}^{n}$. We define the minimal selection
\begin{equation*}
m(F(x)) := \arg\min \big\{ \lvert u \rvert : u \in F(x) \big\},
\end{...
0
votes
1answer
48 views
Connected graphs $G$ with $\delta(G) > 1$ and long minimum size roundtrips
Let $G = (V,E)$ be a finite, connected, simple, undirected graph. By a roundtrip of $G$ we mean a map $r:\{0,\ldots,n\} \to V$ for some $n\in\mathbb{N}$ with the following properties:
$r$ is ...
2
votes
1answer
128 views
Optimal function existence? what is it?
It's a problem abstracted from a real engineering project.
I want to find the best curve $y=y(x)$, $x \in [0,1]$: $y$ doesn't have to be a continuous function.
The constraint is
$$
L=\int_{0}^{1} \...
0
votes
0answers
53 views
Low rank approximation
Can we solve low rank approximation problem by using concept of Gröbner basis? I was trying to find it by Macaulay2 but didn't find the answer. I was trying to do by toric ideals as for them Gröbner ...
1
vote
1answer
89 views
A close-form solution for a simple quadratic optimization problem
Is there any closed form solution for the following optimization problem:
\begin{align}
&\min_{\mathbf{X},\alpha} \mathrm{Tr}[(\mathbf{A}-\mathbf{B}\mathbf{X})(\mathbf{A}-\mathbf{B}\mathbf{X})^{\...
1
vote
0answers
54 views
Linear algebra - For symmetric matrix X $\in S^n$, prove the $a^T X a$ = $\det X \det(X_{n-1})$ , where $a_i$ = $(-1)^i M_{in} $ [closed]
Suppose we have a symmetric matrix X$\in S^n$, and $X_k$ denotes the submatrix consists of first $k$ rows and columns of X. If $\det X < 0$, but $\det X_1, ..., \det X_{n-1} > 0$. Let $a_i=(-1)^...
1
vote
1answer
238 views
Steering an ODE out of a ball
Suppose that $b:\mathbb{R}\to\mathbb{R}$ is locally Lipschitz and of polynomial growth. Suppose further that there are constants $C_1,C_2>0$ such that $(x-y)(b(x)-b(y))\leq C_1-C_2(x-y)^2$ for all $...
