Questions tagged [oc.optimization-and-control]

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

Filter by
Sorted by
Tagged with
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 ...
user avatar
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\|},\...
user avatar
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 ...
user avatar
  • 133
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 :...
user avatar
  • 5,830
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}}^{\...
user avatar
  • 79
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}^\...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 307
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||...
user avatar
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 ...
user avatar
  • 33
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 ...
user avatar
  • 41
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 ...
user avatar
  • 8,284
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$...
user avatar
  • 521
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 ...
user avatar
  • 131
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 ...
user avatar
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 ...
user avatar
  • 11
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 5,830
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 $\...
user avatar
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 ...
user avatar
  • 73
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 ...
user avatar
  • 7,040
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 ...
user avatar
  • 173
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}...
user avatar
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 ...
user avatar
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\\ ...
user avatar
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 ...
user avatar
  • 195
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_{}^{} \...
user avatar
  • 143
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 \...
user avatar
  • 11
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 ...
user avatar
  • 63
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. ...
user avatar
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 ...
user avatar
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} ...
user avatar
  • 1,269
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 ...
user avatar
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 ...
user avatar
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{...
user avatar
  • 79
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 $\...
user avatar
  • 79
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 \...
user avatar
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 $$ ...
user avatar
  • 101
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} & \...
user avatar
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 ...
user avatar
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 ...
user avatar
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$ ...
user avatar
  • 11
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)...
user avatar
  • 2,620
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 ...
user avatar
  • 3,011
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>...
user avatar
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\\ ...
user avatar
  • 11.2k
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(...
user avatar
  • 715
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} \...
user avatar
  • 1,136

1
2 3 4 5
21