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
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 $\...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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}...
user avatar
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 ...
user avatar
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\\ ...
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
  • 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_{}^{} \...
user avatar
  • 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 \...
user avatar
  • 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 ...
user avatar
  • 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. ...
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
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} ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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{...
user avatar
  • 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 $\...
user avatar
  • 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 \...
user avatar
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 $$ ...
user avatar
  • 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} & \...
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
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 ...
user avatar
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$ ...
user avatar
  • 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)...
user avatar
  • 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 ...
user avatar
  • 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>...
user avatar
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\\ ...
user avatar
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(...
user avatar
  • 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} \...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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}^{...
user avatar
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 ...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 $$\...
user avatar
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, ~~\...
user avatar
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 ∈ ...
user avatar
  • 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 ...
user avatar
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$. ...
user avatar
  • 3,686

1
2 3 4 5
21