Questions tagged [oc.optimization-and-control]

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

Filter by
Sorted by
Tagged with
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 $...

1
2 3 4 5
18