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

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

1,025
questions

0
votes

0
answers

82
views

### Relegation of Farkas' fundamental theorem to 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

36
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

37
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

49
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

31
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

54
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

142
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

60
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

70
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

63
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

85
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

51
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

53
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

119
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

49
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

62
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

99
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

90
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

76
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

49
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

232
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

54
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

52
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

30
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

122
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

20
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

116
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

115
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

22
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

93
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

0
answers

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

2
votes

1
answer

127
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 ...

2
votes

0
answers

44
views

### A variant of the elliptope relaxation

Given a p.s.d. matrix $A$, one may want to find:
$$
\max_x x^t A x \mbox{ such that } x \mbox{ has entries }1 \mbox{ or } {-1}.
$$
This hard problem has a well known relaxation based on the so called ...

3
votes

0
answers

74
views

### What is the name for this type of optimization problem?

As we all know, a classic optimization problem can be represented in the following way:
Given a function $f: A \to \mathbb{R}$, find an element $x_0 \in A$ such that $f(x_0) \le f(x)$ for all $x \in ...

0
votes

0
answers

66
views

### On least-squares with positive semidefinite constraints

Given real symmetric matrix $\mathbf{R} \in \mathbb{S}^{n\times n}$ and matrices $\mathbf{X}_n, \mathbf{X}_{n-1} \in \mathbb{R}^{n \times m}$,
$$\begin{array}{ll} \underset{\mathbf{A} \in \mathbb{R}^{...

1
vote

2
answers

135
views

### Partitioning unit square with equal frequency rectangles

If I had to partition the unit square $[0,1]\times[0,1]$ into $k^2$ rectangles such that the sum of their diagonals is minimum possible, I would simply choose the $k \times k$ grid of squares. Now ...

0
votes

0
answers

39
views

### Simplest sensitivity analysis in semi-infinite linear programming

Consider a standard linear program of the form
\begin{align*}
\min_{x}c^{\top}x & \,\,\text{subject to}\\
Ax & =b\\
b & \geq0\,.
\end{align*}
It is well-known that if we perturb the right-...

16
votes

2
answers

735
views

### What tools should I use for this problem?

Suppose we have $d$ cylindrical metal bars, with radius $l$, attached orthogonal to a support in random places:
Now we have to attach bars with radius $k$ EVENLY SPACED, with distance $p$ between ...

0
votes

0
answers

29
views

### What's "Arrow-Hurwicz method" for solving saddle point optimization problems?

I have seen some papers on convex-concave optimization citing the "Arrow-Hurwicz method" from the paper [1] in different ways. However, since I cannot find a pdf version of this paper and ...

3
votes

0
answers

65
views

### Projection onto level set of convex functional

Fix a probability space $(\Omega,\mathcal{F},\mathbb{P})$ and let $F:L^2_{\mathbb{P}}(\mathcal{F})\rightarrow (-\infty,\infty]$ be bounded-blow, convex, lower semi-continuous, and not identically ...

0
votes

0
answers

73
views

### Why is Gaussian distribution always chosen for smoothed analysis?

I came across the algorithmic perfomance analysis model of smoothed analysis. In all references that I read a Gaussian distribution was used for perturbation (e.g. Spielman and Teng 2004 for the ...

2
votes

1
answer

90
views

### Minimization of an entropy type functional with biased expectation constraint

This question is a continuation of Minimization of an entropy type functional
Let $\mathcal P_c$ be the set of probability densities on $[0,1]$ with mean $c\in [0,1]$, i.e. $p\in \mathcal P_c$ iff
$$\...

3
votes

1
answer

123
views

### Minimization of an entropy type functional

Let $\mathcal P$ be the set of probability densities on $[0,1]$ with mean $1/2$, i.e. $p\in \mathcal P$ iff
$$\int_0^1 p(x)dx=1,\quad \int_0^1 xp(x)dx=\frac{1}{2}\quad \mbox{and}\quad p(x)\ge 0, ~~\...

0
votes

0
answers

87
views

### Optimization problem where the objective function returns a function instead of a real number

As we all know, a classic optimization problem can be represented in the following way:
Given: a function $f: A \rightarrow \mathbb{R}$ from some set $A$ to the real numbers
Sought: an element $x_0 ∈ ...

0
votes

0
answers

70
views

### Convergence of steepest descent in the nonquadratic case - formal proof of Theorem 3.4 in Nocedal & Wright's book

On page 43 of Nocedal & Wright's Numerical Optimization, the authors provide the following Theorem 3.4 without any proof:
Suppose that $f:\mathbb{R}^n\rightarrow \mathbb{R}$ is twice
continuously ...

2
votes

1
answer

166
views

### Is there a version of Arrow's theorem without unrestricted domain?

To recall Arrow's theorem:
Suppose we have a finite set $X$ of voters and a finite set $Y$ of candidates.
An election is a map $\phi: X \rightarrow T$ where $T$ is the space of total orderings of $Y$. ...