Questions tagged [oc.optimization-and-control]

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

415 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
32 votes
0 answers
2k views

A Combinatorial Abstraction for The "Polynomial Hirsch Conjecture"

Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ . Suppose that (*) For every $i \lt j \lt k$ and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, ...
Gil Kalai's user avatar
  • 24.2k
14 votes
0 answers
248 views

Dividing a convex region to minimize average distances

Let $C$ be a convex region in the plane with area 1 that contains distinct points $p_1,\dots,p_n$. Say I'd like to divide $C$ into $n$ pieces $C_1,\dots,C_n$, each of area $1/n$, and I'd like to ...
Tom Solberg's user avatar
  • 3,929
11 votes
2 answers
752 views

A (linear) optimization problem subject to (linear) matrix inequality constraints

Let $A \in \mathbb{R}^{n \times n}$ be a Hurwitz matrix, i.e. $A$ satisfies $\mathrm{Re}\,\lambda_i< 0$, where $\{\lambda_i\}_{i=1}^n$ is the set of eigenvalues of $A$. Suppose that the trace of $A$...
Ludwig's user avatar
  • 2,682
11 votes
0 answers
748 views

Hamilton-Jacobi equations: Method of characteristics

In Cannarsa-Sinestrari's book 'Semiconcave Functions, Hamilton-Jacobi Equations, and Optimal Control' there is a proof, via the Method of Characteristics, of global-in-time existence of classical ...
TØS's user avatar
  • 101
11 votes
0 answers
290 views

$L_2$ minimizing makespan vs. $L_\infty$ minimizing makespan

There are $n$ positive real numbers. We partition these numbers into $m$ parts, the size of each part is the sum the numbers in this part. Maximum size of the parts is called a makespan of a partition....
kakia's user avatar
  • 389
8 votes
0 answers
229 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\|},\...
Yaroslav Bulatov's user avatar
8 votes
0 answers
540 views

Hasse-Weil Bound and Chebyshev Inequality

I was reading about the Hasse-Weil bound for the number of points in on a curve over the finite field $\mathbb{F}_q$. $$ \big| |C(\mathbb{F}_q)| - (q+1) \big| \leq 2g \sqrt{q} $$ However, this ...
john mangual's user avatar
  • 22.6k
7 votes
0 answers
426 views

Geometric bang-bang theorem for nonlinear optimal control

The classical bang-bang theorem is usually stated for linear systems (e.g. Control Theory from the Geometric Viewpoint by Agrachev-Sachkov, p. 209). Sussman proved a nice generalization for systems ...
Conifold's user avatar
  • 1,599
7 votes
0 answers
208 views

Numerical linear algebra: how to compute $B^TC^{−1}B$ efficiently

Hi, my question is similar to this one. I have to compute $B^TC^{−1}B$, where $C$ is a strictly positive definite $n\times n$ matrix and $B$ is $n\times m$. The matrix $C$ is huge ($n$ up to a ...
Manuel Schmidt's user avatar
7 votes
0 answers
881 views

Maximizing the matrix norm

Hi all, I wish to find a 3x3 rotation (orthogonal) matrix $\mathbf{R}$ such that it maximizes the following matrix norm: $||\mathbf{A} \mathbf{D}_r \mathbf{D}_b ||_2$ where $\mathbf{A}$ is a known $...
Danny Kane's user avatar
6 votes
0 answers
70 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 ...
Robin Saunders's user avatar
6 votes
0 answers
210 views

Optimal configurations on the flat torus

I'm studying (with my colleagues R.Piergallini and S.Isola) configurations of points on the flat torus which minimize an attractive or repulsive potential depending on the distance. Two model cases ...
Alessandro Della Corte's user avatar
6 votes
0 answers
92 views

Finding the optimal mixture of two convex functions

I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where $x_1,x_2\...
Robert Lowell's user avatar
6 votes
0 answers
148 views

Minmax problem for polygons

Let $\text{Pol}_n$ be the set of all convex polygons on a plane with $n$ vertices. For $P\in \text{Pol}_n$ denote by $\text{Tr}(P)$ the set of all triangles which vertices are some vertices of $P$. I ...
Norbert's user avatar
  • 1,687
5 votes
0 answers
196 views

Difficulty of solving $Ax=b$ in terms of limiting spectral density of $A$?

Suppose $A$ is a random real-valued $n\times n$ matrix and we want to know the difficulty of solving $Ax=b$ when entries of $b$ are sampled IID from Normal$(0,1)$. Can we say anything about the ...
Yaroslav Bulatov's user avatar
5 votes
0 answers
78 views

Differentiability/continuity of stabilizing solution to algebraic Riccati equation with respect to matrix parameters

When solving the LQR problem to find the optimal feedback matrix $K^*$, i.e. solving \begin{align*} \min_K &\int_0^\infty \left(x^TQx + u^TRu\right)dt,\\ \text{s.t. }&\dot{x} = Ax+Bu,\\ &u=...
VGD's user avatar
  • 151
5 votes
0 answers
121 views

Projection of a function $f\in L^1(\Omega)$ onto a finite dimensional subspace

Suppose $\Omega \subset \Bbb R^n$ be a domain such that $|\Omega|<\infty$, $f\in L^1(\Omega)$. Let $Y= \text{span}\{g_1,\dots, g_k\}$. Is there a characterization of the set of projections of $f$...
BigbearZzz's user avatar
  • 1,245
5 votes
0 answers
96 views

Non-convex optimization problem involving minimum spanning trees

Suppose I am given $n$ points $p_1,\dots,p_n\in \mathbb{R}^2$, as well as two positive coefficients $a_1$ and $a_2$, and I am trying to select $n$ points $x_1,\dots,x_n$ to solve the following ...
Tom Solberg's user avatar
  • 3,929
5 votes
0 answers
2k views

Find the axis of symmetry in a point cloud

I have some dataset which describes a spherical cloud of points in 4D space. Actually, the coordinates of the points are the coefficients of unit quaternions, so you get the idea on what the data is ...
noncom's user avatar
  • 151
5 votes
0 answers
266 views

stochastic control / geometric mean

Consider the following problem: Given $\Omega$ and $U$ two symmetric definite positive matrices, choose a matrix $K$ to minimize the expectation $x' \Omega x + x'K'UKx$ when $x$ follows the invariant ...
Bernard 's user avatar
5 votes
0 answers
421 views

The Gömböc and monostatic objects

This made the popular news a few years ago. Summary: it's the first homogeneous, convex solid to be found with only one stable and one unstable mechanical equilibrium when resting on a flat surface. I ...
Robin Saunders's user avatar
4 votes
0 answers
188 views

Schrödinger Bridge for other costs

Stochastic control formulations of the Schrödinger bridge problem between $\mu,\nu$ are well known (e.g Chen et al Eq. 4.23) $$\inf \limits_{p_t, v_t} \int_0^T \int \frac{1}{2}\lvert v_t\rvert^2 p_t ...
nico's user avatar
  • 91
4 votes
0 answers
205 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\\ ...
Abumze978's user avatar
4 votes
1 answer
193 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} \...
DSM's user avatar
  • 1,196
4 votes
0 answers
131 views

An inequality for three iid random variables with a log-concave density

It was previously shown that $$H\ge cG,\tag{1}$$ where $c:=1/14334$, $$G:=E|X-Y|,\quad H:=E|X-Y|-\tfrac12\,E|X+Y-2Z|,$$ and $X,Y,Z$ are independent random variables with the same log-concave density. ...
Iosif Pinelis's user avatar
4 votes
0 answers
111 views

Looking for an electronic copy of Lebeau's paper

I would like to know if anyone has an electronic copy of the paper "Gilles Lebeau - Contrôle De L'Équation De Schrödinger"? This article appeared in Journal de Mathématiques Pures et ...
Math's user avatar
  • 481
4 votes
0 answers
54 views

Least squares with matrix product constraints

I am encountering a constrained LS problem with the following structure: $$ \text{min}_Q\ \sum_{i=1}^M ||Q_i X_i-Y_i||_F^2 $$ $$ \text{s.t. }\ Q_M Q_{M-1}\cdots Q_1=I, $$ where $Q_i,X_i,Y_i\in \mathbb{...
Yin Mingzhou's user avatar
4 votes
0 answers
175 views

Is the Weber problem a NP-hard problem?

The Weber problem is a special case of a facilities location problem : In a basic formulation, the facility location problem consists of a set of potential facility sites L where a facility can be ...
Julien's user avatar
  • 141
4 votes
0 answers
66 views

Can a nonlinear dynamical system be rewritten in terms of constraints?

My question is based on thoughts after reading to a specific section in the paper "On Contraction Analysis for Nonlinear Systems" by W. Lohmiller and JJ. Slotine, Section 4.2 Constrained Systems. ...
AzJ's user avatar
  • 141
4 votes
0 answers
242 views

Is every stable matrix orthogonally similar to a $D$-skew-symmetric matrix?

Let $\mathrm{diag}(A)$ denote the diagonal matrix with diagonal entries of $A\in\mathbb{R}^{n\times n}$ and let $\succeq$ denote the standard partial order in the cone of (symmetric) positive definite ...
Ludwig's user avatar
  • 2,682
4 votes
0 answers
215 views

Optimal control of SDEs

I've set up a system of stochastic differential equations that I'd like to control. I'm new to optimal control theory and SDEs (and, admittedly, weak on PDEs), so I'm not certain if I've set this up ...
Hruodland's user avatar
4 votes
0 answers
82 views

Non-singularity of a series of matrices

Let $A_1$, $A_2$ be $n\times n$ real matrices. Suppose that $A_1$ and $A_2$ are Schur stable (i.e., their eigenvalues are strictly inside the unit circle in the complex plane). Let $B_1$, $B_2$ be two ...
Ludwig's user avatar
  • 2,682
4 votes
0 answers
500 views

Using Linear Programming as an iterative procedure

Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
D. Rusin's user avatar
  • 381
4 votes
0 answers
139 views

Asymptotic behavior of gradient descent on a smooth, convex, non-negative function with no finite minimum - part II

Let $f: \mathbb{R}^d\rightarrow\mathbb{R}_{\geq 0}$ be a function which is convex and smooth (i.e., in $C^{\infty}$). If $x^* \in \mathbb{R}^d$ is the (global) minimum of $f$, it is well known that ...
Daniel Soudry's user avatar
4 votes
0 answers
237 views

Stochastic subgradient descent almost sure convergence

I was reading up on stochastic subgradient descent, and most sources i could find via google search give quick proofs on convergence in expectation and probability, and say that proofs of almost sure ...
user1539279's user avatar
4 votes
0 answers
129 views

Covering Number of a Positive Semidefinite Cone (Approximate the Objective of a SDP)

I was wondering what the covering number of a positive semidefinite cone is. Consider the semidefinite optimization program \begin{align} \max\langle \mathbf{C}, \mathbf{X} \rangle~~\text{subject to}~...
Steve's user avatar
  • 1,117
4 votes
0 answers
182 views

This function looks quasiconvex, can't understand why

Suppose that $\mathbf{C}$ is a given matrix with non-negative entries in $\mathbb{R}^{m\times n}$ and $d$ is a given scalar, and let $g(\mathbf{y})$ be defined by $$g(\mathbf{y}):=\max_{\mathbf{x}\in\...
Richard Senn's user avatar
4 votes
0 answers
166 views

Are there some numerical test to check if a map is a contraction?

Let's say I have a multivariate function $$ f:D \to D, D \subset \mathbb R ^n, D \text{ compact}, $$ for which there is no closed form. That is the only way to evaluate the function is to do it ...
user avatar
4 votes
0 answers
115 views

Sufficiency of stationary policy for negative stochastic dynamic programming

Consider a Markov Decision Process with Borel state space $X$ and Borel action space $U$, like the one defined in the book "Stochastic Optimal Control: Discrete-time case" by Bertsekas and Shreve. All ...
SBF's user avatar
  • 1,605
4 votes
0 answers
159 views

Convexified threshold of a function

Upd. The question in a nutshell: find convex set on plane which is «closest» to a given non-convex set. It is given integrable function $0\leq f(x,y)\leq 1$ with bounded support: $f(x,y)=0$ when $x^2+...
Anton Sukhinov's user avatar
4 votes
0 answers
101 views

Applications of k-medians with moment constraints

Suppose I have a collection of points $p_1,\dots,p_N$ in the plane. In the Euclidean $k$-medians (or $k$-means) problems, our objective is to distribute a set of $k$ points $x_1,\dots,x_k$ in the ...
John Gunnar Carlsson's user avatar
4 votes
0 answers
195 views

restricting "dances of minimal cost" (optimization on braids/permutations?)

Consider applying the permutation (1,3,0,5,2,7,4,6) to the integers (0,1,2,3,4,5,6,7) three times. I call this a "dance of minimal cost" because all unordered pairs in {0..7} meet each other, and the ...
Fumiyo Eda's user avatar
4 votes
0 answers
338 views

Can the Littlewood-Richardson cone be used for combinatorial optimization?

The Littlewood-Richardson cone $LR_{n, k}$ consists of all $k-$tuples $(a_1, a_2, \dots, a_k)$ of real $n-$vectors with monotonically decreasing entries such that there exist $k$ $n \times n-$...
Hari's user avatar
  • 313
4 votes
0 answers
689 views

Dynamic programming principle (DPP)

In stochastic control problem, one shall use the measurable selection theorem to prove DPP. It was discussed in discrete time case in [Bertsekas and Shreve 1978]. Is there unified framework in ...
kenneth's user avatar
  • 1,369
3 votes
0 answers
164 views

Asymptotics for optimal survival time in a stochastic control problem

An individual, henceforth called the runner starts at the center of an open ball $\Omega_r \subset \mathbb R^2$ of radius $r > 1$. At each turn, a vector $x \in S^1$ is chosen uniformly at random, ...
Nate River's user avatar
  • 4,822
3 votes
0 answers
84 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 ...
Vipul Naik's user avatar
  • 7,230
3 votes
0 answers
87 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 ...
Shaun Han's user avatar
  • 141
3 votes
0 answers
87 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 ...
ABIM's user avatar
  • 5,019
3 votes
0 answers
110 views

Matrix inequality $a X \succeq arcsin(X)$ for some $a > 0$

Let $X \in S^{n}_{+}$ be a positive semi-definite matrix with $X_{ii} = 1$ for all $i \leq n$ (thus $X$ is a correlation matrix). Since $X$ is positive semi-definite, we have $|X_{ij}| \leq 1$ for any ...
zxzx179's user avatar
  • 205
3 votes
0 answers
87 views

Bounds on minimum solutions to empirical and theoretical objective functions

Let $P$ and $Q$ be two probability distributions and let $$S_0 = \min_{f,g} \left[ \int f(x)\, dP(x) + \int g(y)\, dQ(y) \right]$$ such that $f(x)+g(y) \geq \langle{x,y\rangle}$ where $f,g$ are ...
Kashif's user avatar
  • 363

1
2 3 4 5
9