# Questions tagged [oc.optimization-and-control]

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

1,036
questions

0
votes

0
answers

23
views

### Literature request: proving or disproving convexity of the optimal value function of semidefinite program (SDP) or convex optimization in general

Suppose I have a function $f:\mathbb{R}\rightarrow \mathbb{R}$ defined as the following parametric optimization problem:
$$f(p) = \inf_xf_0(x) \quad \text{subject to } \quad G(x,p)\leq 0,$$
where ...

8
votes

0
answers

177
views

### Decay of orthogonal contributions in a random set of vectors

Suppose we sample $k$ vectors $v$ from normal distribution centered at zero and diagonal covariance with diagonal entries $1,\frac{1}{2},\ldots,\frac{1}{d}$ and normalize $v$:
$$\frac{v_1}{\|v_1\|},\...

3
votes

1
answer

136
views

### Optimal transport for applied mathematicians: how does $\varphi (x) = \inf_{y \in Y} [c(x, y) - \psi (y)] \neq -\infty$ follow in Theorem 1.37?

I'm reading a proof of Theorem 1.37 from Santambrogio's Optimal transport for applied mathematicians: calculus of variations, PDEs, and modeling. First, I quote related definitions. Let $X,Y$ be ...

0
votes

0
answers

35
views

### Minimal value of $f(x) := \|x-x_0\|_S^2 + a\|x-x_0\|_S\|x\| + b\|x\|^2$

Fix $x_0 \in \mathbb R^n$, $a,b \ge 0$ and an $n \times n$ positive-definite matrix $S$. For any $x \in \mathbb R^n$, define
$$
f(x) := \|x-x_0\|_S^2 + a\|x-x_0\|_S\|x\| + b\|x\|^2,
$$
where $\|z\|_S :...

0
votes

0
answers

154
views

### Optimal solution of complex optimization problem

Let $Q(x)=a(x)e^{jb(x)}$ be a complex function of $x$. We want to approximate this function with $R(x)=\alpha e^{jx\beta}$ such that
\begin{align}
\text{arg}\min_{\alpha,\beta} \int_{-\frac{A}{2}}^{\...

0
votes

0
answers

39
views

### Reconstruction conditions for coordinates in dynamical systems

I write this post in an attempt to find necessary and sufficient conditions for the below statement. Any condition may be helpful and any who contributes may benefit from it:
Imagine a $\mathcal{C}^\...

2
votes

1
answer

31
views

### On the relation between solution of random least squares and expected least squares with constraints

Let $v\in \mathbb{R}^d$ be a random vector such that $\mathbb{E}v = y$, and $X$ be a given $\mathbb{R}^{d\times d}$ real fixed matrix. We assume that the following optimization problem has a unique ...

1
vote

1
answer

33
views

### Resources/Reading Materials on PASA (optimal control theory)

I am currently working on my undergraduate thesis, and my adviser suggested that I look into a Polyhedral Active Set Algorithm (PASA) for my paper. I have been trying to find resources/materials on it ...

1
vote

1
answer

71
views

### UMVUE as an optimization problem

Finding UMVUE (Minimum-variance unbiased estimator) looks like an optimisation problem (minimise the variance of $\hat{\theta}$ given the constraint $\text{E}_\theta\hat{\theta}=\theta.$
I tried to ...

1
vote

0
answers

59
views

### Non-negative least squares: how bad is this heuristic?

The non-negative least squares (NNLS) optimization problem is as follows: for given $A \in \mathbb{R}^{n \times m}$, $y \in \mathbb{R}^n$, find $x \in \mathbb{R}_{\geq 0}^m$ that minimizes $||Ax - y||...

1
vote

0
answers

71
views

### Gap to fill in the Aubin–Ekeland proof of the mountain-pass theorem

Working through the proof of the mountain-pass theorem given in Applied Nonlinear Analysis by Aubin & Ekeland, at what seems to be a critical point of the proof (the top of page 274) they refer to ...

1
vote

0
answers

91
views

### Limit cycles or stable solutions for k-dimensional piece-wise linear ODEs

As a branch of reinforcement learning, restless multi-armed bandits have been shown PSPACE-HARD but Whittle has offered an implementable solution called the Whittle Index Policy. Weber and Weiss ...

2
votes

1
answer

181
views

### Solving linear programming without solving linear programming

Let $v_1, \cdots, v_n$ be vectors in $\mathbb R^k$, and let $M$ be the Gram matrix of them.
It's possible to determine from $M$ and $k$ whether the only vector that has nonnegative inner product with ...

4
votes

1
answer

123
views

### How to find an optimal sequence of merging operations?

Given a set of items, each characterized by a quality $q_i\in(0,1)$. We can merge two items of quality $q_i$ and $q_j$ to a single item $k$ of quality $q_k=f(q_i,q_j)$, where $f$ is increasing in $q_i$...

2
votes

0
answers

60
views

### Lyapunov function utility in stochastic optimal control

The article Optimal strategy of vaccination and treatment in an SIRS model with Markovian switching by (X.Mu, Q.Zhang) studies necessary and sufficient conditions on near-optimal controls.
In both ...

1
vote

1
answer

254
views

### Who called Farkas' fundamental theorem a lemma?

Farkas proved his famous result (which, nowadays, is fundamental in optimization theory) in 1902 and called it Grundsatz der einfachen Ungleichung which may be translated as fundamental theorem of ...

1
vote

0
answers

38
views

### Problems with known optimal solution [closed]

I am looking for some problems in which we know the value of optimal solution and should find just a vector of variables. For example in N-Queens problem we know the value of optimal solution (that is ...

1
vote

0
answers

39
views

### Find $\max_V \text{Tr} \left((\rho_2 (V \otimes I) \rho_1 (V^\dagger \otimes I)\right)$

I am doing a quantum optimization where the final problem has the following form
$$\max_V \text{Tr} \left((\rho_2 (V \otimes I) \rho_1 (V^\dagger \otimes I)\right),$$
where $V \in \mathbb{C}^{d\times ...

5
votes

0
answers

54
views

### Roundest polyhedra: how well can we bound the edge count of their faces?

By "roundest" I mean having the lowest surface area for the highest volume, given a fixed number of faces $n$. There've been a few questions about them on here (including from me), but I'm ...

2
votes

0
answers

35
views

### Convex optimization over compact sets defined as Aumann set-valued integrals

Let $(X,P)$ be a probability measure space. Let $K$ be a convex compact subset of $\mathbb R^d$ and let $F:X \to 2^{K}$ be a set-valued map. Assume that $F$ is:
closed (i.e $F(x)$ is closed for ...

1
vote

0
answers

99
views

### Maximizing a parametric integral over the unit sphere

I am trying to compute the nonnegative quantity
$$
\underset{y\in\mathbb{S}^{d-1}}{\sup}\int_{0}^{t}(\Vert A(\tau)y\Vert_{1}- \Vert A(\tau)y\Vert_{q})d\tau, \quad 1 < q < \infty
$$
where $\...

1
vote

2
answers

153
views

### Can we substitute this KKT condition into this optimization problem to reformulate the optimization problem?

Suppose I have the following optimization problem
$$ \min\limits_{\mathbf{x},\mathbf{y}} f(\mathbf{x},\mathbf{y}) \tag{1} $$
It is already known that the target function $f$ is continuous and ...

3
votes

0
answers

61
views

### Sum-of-guesses-minimization problem (also does this problem already exist in the literature)?

Inspired by some recent real-world situations, I thought of this problem:
An adversary has selected a positive real number $p \ge 1$ not known to you. You have to pick numbers $x_1, x_2, \dots$ in ...

1
vote

0
answers

23
views

### Non-differentiability of the set of optima of certain optimization problems

Let $X \subseteq \mathbb{R}^n$ be compact and say the function $f \colon X \to \mathbb{R}$ is locally Lipschitz continuous. Say $\mathcal{X}$ is the set of all solutions of the following optimization ...

2
votes

0
answers

71
views

### Modified quadratic assignment problem

Let $Y,Z$ be $n\times k$ matrices and assume all columns have been standardized such that their means are zero and variances 1. I seek an $n\times n$ permutation matrix $P$ such that
$$\left\Vert Y^{T}...

2
votes

0
answers

64
views

### Chow's theorem for time one flows

Chow's theorem gives a criterion for the reachable set of the points of a manifold $M$ to be full. Specifically, if we have a distribution $D$ whose iterated commutators span the tangent bundle then ...

4
votes

0
answers

92
views

### Does the refined Slater's condition hold also in the infinite-dimensional case?

Let $X$ be an infinite-dimensional Banach space. I have the following optimization problem.
$$\begin{array}{ll} \underset{x \in X}{\text{minimize}} & f(x)\\ \text{subject to} & g_1(x) \leq 0\\ ...

0
votes

0
answers

12
views

### Convergence of solutions of regularised least square problems

Let $\mathcal{H}_1$ and $\mathcal{H}_2$ be two Hilbert spaces ($\mathcal{H_2}$ being finite dimensional, but I don't think that it matters). Consider $(A_{\lambda})_{\lambda>0}$ a familly of ...

0
votes

0
answers

53
views

### Get a specific number of points from a density distribution area to minimize the average distances

Assuming that an area $A$ on the plane has a known density distribution function $\rho (x, y)\geqslant 0$, now the goal is to obtain $n$ points $p_1, p_2, ..., p_n$ on the area so that $\iint_{}^{} \...

1
vote

1
answer

58
views

### Estimate $\Vert \Delta u(t)\Vert_{2}$ in term of energy

We consider the wave equation
$$\left\{
\begin{array}{ll}
u_{tt}(x,t)-\Delta u(x,t)=0, x \in \Omega, t>0\\
u=0, \quad u \in \partial \Omega, t>0 \\
u(0,x)=u_{0}(x), \quad u_{t}(0,x)=u_{1}(x), x \...

4
votes

1
answer

164
views

### The ODE modeling for gradient descent with decreasing step sizes

The gradient descent (GD) with constant stepsize $\alpha^{k}=\alpha$ takes the form
$$x^{k+1} = x^{k} -\alpha\nabla f(x^{k}).$$
Then, by constructing a continuous-time version of GD iterates ...

1
vote

0
answers

50
views

### Minimising risk in dynamical systems

I have been reading the paper of Goerner and Ulancowicz - "Quantifying economic sustainability" in which it is suggested that there is a tradeoff between sustainability and efficiency. ...

1
vote

0
answers

55
views

### Notation for jet bundles of mixed order?

This question is motivated by the consideration of linear control systems in Brunovsky normal form. The idea is that you have $m$ smooth functions with unconstrained dynamics, and the control input ...

1
vote

0
answers

64
views

### Principal component analysis with boundedness constraints

Let $A$ be an $m\times n$ matrix with entries in $F$ ($F=\mathbb{R}$ or $F=\mathbb{C}$).
It is well-known that $A$ has decompositions of the form
$$\displaystyle A = \sum_{k=1}^r\lambda_k\hspace{2mm} ...

0
votes

1
answer

144
views

### Best algorithm for meeting scheduling optimization so that total number of held meetings is minimized

Problem Description
I want to hold meetings where some given number of people will participate.
They have some vacant dates respectively but they don't have the same date on which all of them can ...

1
vote

0
answers

92
views

### How to quantify the non-commutativity of human body motion? [closed]

Some years ago, there was that question on this forum:"How to quantify noncommutativity?".
I am asking that question in a context, human movement, which implies kinematic chains (like in ...

1
vote

0
answers

81
views

### Solution of a simple optimization problem

Let $\mathbf{U}_1$ and $\mathbf{U}_2$ be two arbitrary unitary matrices and $\mathbf{D}$ be a diagonal matrix. What is the solution of the following optimization problem?
\begin{align}
\min_{\mathbf{...

0
votes

0
answers

56
views

### The best unitary matrices that approximate a matrix product

Let $\mathbf{A}$ be an arbitrary $N\times N$ complex matrix. Moreover, $\mathcal{U}_1$ and $\mathcal{U}_2$ are distinct subsets of all unitary matrices. Suppose the matrices $\mathbf{U}_1$ and $\...

1
vote

2
answers

238
views

### Optimization of a integral function

I have a function $h(y,x_1,x_2,\ldots,x_n)$. It is known that the minimum value of $h$ for any $y$ is attained when $x_1 = x_n$ and $x_2 = x_3 = \cdots = x_{n-1}$. Now consider the following function
\...

0
votes

0
answers

66
views

### Constrained argmin of a trace

Let $A \in \mathbb{R}^{4 \times 3}$. I am trying to compute
$$\hat{X} = \arg\min_{X \in \mathbb{R}^{3 \times 4}} \frac{\partial\text{Tr}(AX)}{\partial X}$$
with the following equality constraints
$$ ...

0
votes

0
answers

63
views

### Double summation of matrices as constraints in convex optimization in CVX

I want to implement the following optimization problem from the following paper Randomized Gossip Algorithms, Page 10 Eq 53:
\begin{align}
\text{minimize} &\qquad s\\
\text{subject to} & \...

0
votes

0
answers

15
views

### Family of Markov control processes converging to limit Markov control process

Suppose that we have a family of Markov control processes (MCPs) $(\mathscr{Z},\mathscr{A}_\delta,P,r)$, with the action spaces $\mathscr{A}_\delta$ indexed by a parameter $\delta\in [0,1]$.
In the ...

1
vote

1
answer

39
views

### Adding valid cuts for integer feasibility problem under Benders decomposition framework?

Traditional infeasibility cut is derived under the assumption that the feasibility problem is LP instead of ILP and relies on the dual form of the LP.
Is there a systematic way of adding valid cuts ...

1
vote

1
answer

123
views

### Stability of certain second order ODE

I am having a hard time determining the motion of $X$ in the ODE $X''+\nabla f(X)=0$ with initial conditions arbitrary $X(0)$ and zero velocity, i.e. $X'(0) = 0$. $X$ is in $\mathbb{R}^{n}$, and $f$ ...

1
vote

0
answers

23
views

### Eigenvalue assignment via state feedback: existence proof

Consider the linear time invariant system:
$$\tag{1}\label{eq1}
\dot{x}(t) = Ax(t) + Bu(t), \ \ x(0)=x_0\in\mathbb{R}^n,
$$
where $A\in\mathbb{R}^{n\times n}$, $B\in\mathbb{R}^{n\times m}$. Let $p_M(s)...

1
vote

1
answer

121
views

### Boolean function : approximation by a linear function

Let $f$ be a balanced Boolean function.
Are there $g$ linear functions, with $$\frac1{2^n}\mathrm{card} \big(\big\{\mathrm{sign} (g (x)) = 2f (x) -1, x \in \{0,1\}^n\big\}\big) > 0.55\quad ?$$
$g ...

1
vote

0
answers

116
views

### Is $x\cdot f(x)$ quasiconvex for $x>0$, if $f(x)$ is monotonically decreasing, convex, and positive? [closed]

Original question
Given $f(x):\mathbb{R}^+\to\mathbb{R}^+$, which is monotonically decreasing and convex. Then define a function $g(x) = xf(x)$, I am wondering whether $g(x)$ is quasiconvex for $x>...

1
vote

0
answers

23
views

### How to chose the start vector for the MTZ variables

In the context of LP-formulations for the Traveling Salesman Problem the MTZ constraints prevent subtours via $n$ (i.e. effectively $n-1$) additional variables $$u_1=1\\2\le u_2,\,\dots ,\,u_n\le n\\ ...

3
votes

2
answers

96
views

### Link between controllability of ODEs and controllability of transport equations

What is the relationship between the controllability of the ODE
$$\dot x(t) = v(x) + u(t)$$
using a control $u$ and the controllabilty of the transport equation
$$\rho_t(t,x) + \mathrm{div}(v(x) \rho(...

1
vote

1
answer

81
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} \...