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
105 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 $\...
Math_Y's user avatar
  • 311
1 vote
2 answers
259 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 \...
Satya Prakash's user avatar
0 votes
0 answers
150 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} & \...
Spring Breeze's user avatar
1 vote
1 answer
137 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 ...
Michael Fan Zhang's user avatar
1 vote
1 answer
130 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$ ...
MMH..'s user avatar
  • 11
1 vote
0 answers
30 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)...
Ludwig's user avatar
  • 2,682
1 vote
1 answer
171 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 ...
Dattier's user avatar
  • 3,737
1 vote
0 answers
135 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>...
Lee White's user avatar
1 vote
0 answers
32 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\\ ...
Manfred Weis's user avatar
  • 12.6k
3 votes
2 answers
119 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(...
Riku's user avatar
  • 819
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
2 votes
1 answer
227 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 ...
Dhruv Kohli's user avatar
2 votes
0 answers
55 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 ...
alesia's user avatar
  • 2,582
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
0 votes
0 answers
118 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}^{...
Universal_Bulin's user avatar
1 vote
2 answers
175 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 ...
bleh's user avatar
  • 153
16 votes
2 answers
781 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 ...
Diego Santos's user avatar
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
0 votes
0 answers
87 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 ...
mc.math's user avatar
2 votes
1 answer
113 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
134 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
92 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 ∈ ...
Shaun Han's user avatar
  • 141
2 votes
1 answer
201 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$. ...
Kim's user avatar
  • 4,034
2 votes
0 answers
100 views

Coercivity of an integral operator in control theory

Let us consider the integral operator $T:\mathbb{R}^{n\times d}\to [0,\infty)$ such that for all $K\in \mathbb{R}^{n\times d}$, $$ T(K)=\int_0^1 \operatorname{tr}(KK^\top \Sigma_t) \,d t, $$ where $\...
John's user avatar
  • 483
1 vote
0 answers
59 views

Minimizing square roots with the consecutive ones property

Let $A=[a_{ik}]$ be a matrix with the consecutive ones property in each column, i.e. each column consists of a single consecutive block of $1$'s (with zeros everywhere else). Is there anything at all ...
Tom Solberg's user avatar
  • 3,929
1 vote
0 answers
134 views

Factorization of argmax

We consider a function $f(s_{1:p}, a_{1:p})$, where $p>1$ is an integer, $s_{1:p}$ denotes $(s_1,\ldots,s_p)^\top \in R^p$, and $a_{1:p}$ denotes $(a_1,\ldots,a_p)^\top \in R^p$. Question: What is ...
Minkov's user avatar
  • 1,117
1 vote
0 answers
83 views

Reference request: Optimal controls can be assumed to take values in a convex set

Consider the deterministic controlled system: $$\dot x(t) = Ax(t) + Bu(t), \ t \in [0, T]$$ $$x(0) = x_0$$ where $x: [0, T] \to \mathbb R^n$ is the controlled state process, $A \in \mathbb R^{n \times ...
Nate River's user avatar
  • 4,822
1 vote
1 answer
149 views

Does coercivity/supercoercivity conjugates?

According to Wikipedia, a function $f: \mathbb{R}^n \to \mathbb{R} \cup \{-\infty, +\infty\}$ is called coercive if, $$f(x) \to +\infty \text{ as } \|x\| \to +\infty$$ and it is super-coercive if $$\...
Norman's user avatar
  • 125
4 votes
2 answers
302 views

Average value of $\frac{x'A^2x}{x'A^3x}$ over surface of $n$-dimensional sphere

Suppose $A$ is a diagonal matrix with eigenvalues $1,\frac{1}{2},\frac{1}{3},\ldots,\frac{1}{n}$ and $x$ is drawn from standard Gaussian in $n$ dimensions. Define $z_n$ as follows $$z_n=E_{x\sim \...
Yaroslav Bulatov's user avatar
1 vote
0 answers
311 views

Reference request: Introduction to stochastic control theory

I’m looking for a nice readable introductory text to stochastic control theory. Background wise, I know some general stochastic analysis and deterministic optimal control theory. Some criterion I’m ...
Nate River's user avatar
  • 4,822
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
8 votes
1 answer
613 views

Maximizing sum of vector norms

Given matrices $A, B \in \mathbb{R}^{n\times n}$, I would like to solve the following optimization problem, $$\begin{array}{ll} \underset{v \in \mathbb{R}^n}{\text{maximize}} & \|Av\|_2+\|Bv\|_2\\ ...
Alex Meiburg's user avatar
  • 1,193
2 votes
0 answers
47 views

Why not use global optimization algorithms like PSO to solve decentralized control problems?

I do not see many works that use global optimization algorithms to solve decentralized control problems. Here the decentralized control problem means some entries of the feedback matrix are ...
fibon's user avatar
  • 21
0 votes
1 answer
87 views

How to find $y_u?$

In the paper Semi-supervised learning by mixed label propagation Wei Tong and Rong Jin define $S$ as the similarity(adjacency) matrix $D = \operatorname{diag}(D_1, D_2, \ldots, D_n)$ where $D_i = \...
willtryagain's user avatar
0 votes
0 answers
145 views

Minimum circumscribed ellipsoid of $\mathcal H$-polytope

Given matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^n$, consider the $\mathcal H$-polytope $P$ defined as follows $$ P := \left\{ x \in \mathbb{R}^n : Ax \leq b \right\} $$ I ...
Daniel Turizo's user avatar
0 votes
0 answers
134 views

Any technique for linearization, or linear approximation?

Consider the following Matrix constraint: $$ \begin{bmatrix} -U+\psi\Sigma_b^{-1} & V \\ V^T & -V^TU^{-1}V+\tau_2 -\psi \end{bmatrix} \leq 0 $$ where $\Sigma_b$ is a known positive definite ...
Navid Hashemi's user avatar
8 votes
2 answers
324 views

Projecting onto space of matrices with spectral radius less than one

Consider the space $$ S = \left\{ A \in \mathbb{R}^{n \times n} : \mathrm{SpectralRadius}(|A|) \leq 1 \right\}$$ where $|A|$ is the entry-wise absolute value. Given a matrix $M \in \mathbb{R}^{n\times ...
CComp's user avatar
  • 111
5 votes
2 answers
1k views

Textbooks or lecture notes about mean field games

I am looking for a good introductory level textbook (or lecture notes) on mean field games that would be suitable for a graduate course. Ideally, it would include some brief words about optimal ...
Anita Poller's user avatar
2 votes
0 answers
138 views

inverse of moment-generating function in terms of moments

Let $\{h_i\}$ be decreasing sequence of $n$ positive reals. Define distribution $p(X=h_i)\propto h_i$ and let $g(s)=E_X[e^{sX}]$ be the moment generating function. For instance, for $h=\{1,\frac{1}{4},...
Yaroslav Bulatov's user avatar
2 votes
0 answers
129 views

Complexity of Quadratic Programming where the symmetric matrix Q is positive semidefinite only in the feasible directions

playing around with stuff for my dissertation, I derived a quadratic problem in the general form \begin{equation} \begin{aligned} \min_{x} \quad & x^TQx + c^Tx \\ \textrm{s.t.} \quad & Ax \leq ...
Emanuel's user avatar
  • 21
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
1 vote
0 answers
35 views

Solution to dynamic program-type recursion

I have the following dynamic programming principle-type problem. Suppose that we are given a sequence $\beta_1,\dots,\beta_n\in (0,\infty)$, some target $y\in (0,\infty)$ with $y>\sum_{t=1}^N \...
John_Algorithm's user avatar
1 vote
1 answer
983 views

Prove that absolute value of eigenvalue is smaller than 1 [closed]

I want to prove that the absolute value of the eigenvalues of a matrix A are smaller than 1 for $$A=\left(\begin{array}{cc} 0 & -H_{11}^{-1} H_{12} \\ -H_{22}^{-1} H_{21} & 0 \end{array}\right)...
anonymousguyfromtheworld's user avatar
0 votes
1 answer
248 views

Non-asymptotic convergence rates for gradient descent

I'd like to know how the number of steps needed for gradient descent depend on properties of the Hessian in non-asymptotic regime. More specifically, number of gradient descent steps needed to obtain ...
Yaroslav Bulatov's user avatar
0 votes
0 answers
38 views

Lipschitz solutions to linear complementarity problems (LCP)

Let $M\in\mathbb{R}^{n\times n}$. For $q\in\mathbb{R}^n$, define the set: $$S_M(q)=\{y\in\mathbb{R}^n|y\ge 0,q+My\ge 0, y^\top (q+My)=0\}.$$ This is the set of solutions to the LCP $(q,M)$. We say $...
cfp's user avatar
  • 183
1 vote
1 answer
234 views

Transport theorem in space craft control: tracking a reference angular velocity

I am reading the book named "Analytical mechanics aerospaces systems" by Schaub and Junkins. In section 7.2, the task is to control the spacecraft to track a specified angular velocity $w_r$ ...
sunxd's user avatar
  • 191
0 votes
0 answers
164 views

Rewriting Kronecker product

im considering a pole placement problem in control theory and my controler has a specific form: $$R=I_n\otimes q$$ where $I_n$ is the identitiy matrix of size $n$ and $q\in\Re^k$ is a vector of the ...
BigL's user avatar
  • 1
1 vote
0 answers
70 views

Symmetry for bilinear optimization problem related to Gromov Wasserstein distance

The following question came up when trying to numerically solve some variants of the Gromov-Wasserstein distance. Setting: Let $(X_1, d_1), (X_2, d_2)$ be two compact, separable and complete metric ...
Steve's user avatar
  • 1,085
1 vote
0 answers
56 views

Pontryagin's principle with Lebesgue-integrable control

Does there exist a (weak) version of Pontryagin's minimum principle in which the control is allowed to be just Lebesgue integrable? I am mostly familiar with the 1975 text of Fleming & Rishel, ...
David Ketcheson's user avatar
7 votes
4 answers
2k views

How to show a $3\times3$ matrix has three distinct eigenvalues?

Here is a question I heared from others: Given four distinct positive real numbers $a_1,a_2,a_3,a_4$ and set $$a:=\sqrt{\sum_{1\leq i\leq 4}a_i^2}$$ $A=(x_{i,j})_{1\leq i\leq3,1\leq j\leq4}$ is a $3\...
user avatar

1 2 3
4
5
23