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 ...
- 13.4k
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 ...
- 11
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 ...
- 11
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 ...
- 3,138
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 ...
- 5,580
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,213
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 ...
- 81
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 ...
- 7,030
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 ...
- 173
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}...
- 133
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\\ ...
- 41
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 ...
- 143
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_{}^{} \...
- 143
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 \...
- 11
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 ...
- 63
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. ...
user478214
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 ...
- 818
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} ...
- 1,197
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{...
- 129
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 $\...
- 129
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
\...
- 167
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
$$ ...
- 101
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 ...
- 111
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$ ...
- 11
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)...
- 2,610
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 ...
- 3,013
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>...
- 11
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\\ ...
- 11k
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(...
- 743
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} \...
- 1,126
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 ...
- 141
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 ...
- 1,931
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 ...
- 141
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 ...
- 153
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-...
- 3,668
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 ...
- 403
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 ...
- 75
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 ...
- 1
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 ...
- 11
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
$$\...
user128095
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, ~~\...
user128095
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 ∈ ...
- 141
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 ...
- 1
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$. ...
- 3,686