All Questions
564 questions with no upvoted or accepted answers
3
votes
0
answers
149
views
Copositivity under tensor products
Is there any symmetric real matrix $A$ such that $A^{\otimes n}$ is copositive for all positive integers $n$, but such that A is neither positive semidefinite nor has just non-negative entries?
...
- 31
3
votes
0
answers
466
views
An optimization problem over real symmetric matrices
Given an $n\times s$ matrix $P$ of positive real numbers and $T\geq n$, find (either by a formula or an algorithm) the real symmetric $n\times n$ Z-matrix $A$ which maximizes $\min\limits_{1\leq i<...
- 767
3
votes
0
answers
125
views
Copositivity in matrix pencils
Given two square symmetric matrices $A,B$ of the same order, the matrix pencil $P(A,B)$ is the set of linear combinations of $A$ and $B$. Finsler's theorem gives an elegant criterion for $P(A,B)$ to ...
- 6,962
3
votes
0
answers
629
views
minimize a cost function with matrix traces
Hi, I have a cost function of the form
$$F(X) = \operatorname{tr}(X'AX)+\operatorname{tr}(X'B),\quad\textrm{ s.t. }X'X=I.$$
$X$ is a $m\times n$ matrix, ($m>n$), with orthonormal columns. $A$ is ...
- 205
3
votes
0
answers
117
views
Multiple Number Partitioning / "Multiprocessor Scheduling"
Consider the well-known Number Partitioning / "Multiprocessor Scheduling Problem": You want to partition a set $S$ of objects (jobs) $i$ with weights $w_i$ (process time) into subsets $S_k$ (e.g. ...
- 1,846
3
votes
0
answers
3k
views
0,1 solution to system of linear integer equations
I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-matrix and $m$-vector of nonnegative integers (respectively).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...
- 149
3
votes
0
answers
220
views
Could SVD be used to optimize the partial inner-products?
Suppose a set $N$ of $n$ distinct points in $m-$dimensional space is given in $X\in\mathbb{R}^{n\times m}$. Also, suppose a subset $L\subset N$, $|L|=l<m<n$, with
$m-$dimensional coordinates in ...
- 131
3
votes
0
answers
312
views
Linear complementarity problem: principal pivoting algorithm
I'm trying to implement the "Dantzig; van de Panne and Whinston" principal pivoting algorithm for solving symmetric positive semi-definite LCPs from "The Linear Complementarity Problem" book (...
- 151
3
votes
0
answers
341
views
maximum variance unfolding
Consider positive weights $\pi_1, \ldots, \pi_n$ (one can suppose that they add up to $1$) and $n-1$ lengths $d_1, \ldots, d_{n-1}$.
Is there an analytical solution to the following problem:
find the ...
- 2,133
3
votes
0
answers
363
views
Convergence to a (unique?) fixed point?
Consider a given $N\times P$ matrix $X$ (full rank with columns ${\bf x}_p$, $p=1,\ldots,P$), a given vector ${\bf y}\in R^N$ and a thresholding function $\eta_\lambda(|x|)=(|x|-\lambda)_+$ with $\...
- 31
3
votes
0
answers
279
views
Nonlinear conjugate gradient update strategy by Dai and Yuan
In Nocedal and Wright book "Numerical Optimization", they describe on
page 123 (formula 5.49) an update strategy for the beta parameter in
the nonlinear conjugate gradient optimization, which was ...
- 221
2
votes
0
answers
175
views
Eigenvalues of Laplace operator and Schrödinger operator
When reading the paper Control for Schrödinger operators on tori by N.Burq and M.Zworski (Math. Res. Lett., 19(2):309–324, 2012), an inequality confused me:
Define the flat torus $\mathbb{T}^2=\mathbb{...
- 21
2
votes
0
answers
48
views
Characterization of multifunctions with globally asymptotically stable minimal invariant sets
Let $(X, d)$ be a compact connected metric space. Consider a compact-valued upper semicontinuous multifunction $F: X \rightrightarrows X$. The reachable set $R[x]$ of $F$ from $x\in X$ is defined as:
...
- 111
2
votes
0
answers
57
views
Mappings that preserve local or global minimum
In the most general form, I'm interested in any non-trivial results of the following question.
Consider metric space $X$ and $Y$, denote all real valued functions on $X$ and $Y$ as $\mathbb{R}^{X}$ ...
- 275
2
votes
0
answers
72
views
Gradient descent over the set of complex symmetric matrices
In the course of my research (somewhat related to compressive sensing), I am trying to determine a complex, symmetric matrix $L$ (i.e. $L = L^T$) through the following optimization formulation:
$$ \...
- 21
2
votes
0
answers
58
views
Optimal orbital tranfers: reference for statements & proofs
I know that Pontryagin's contribution to optimal control in the 1950'ies was allegedly inspired by the then-nascent rocket industry and the question of how to get a rocket into orbit with minimum fuel....
- 1,461
2
votes
0
answers
153
views
Spectrum of an almost Hamiltonian matrix
I have a complex-valued block matrix $N=\begin{bmatrix}
A & B \\
C & -A^*
\end{bmatrix}$, where $A$ is diagonal, $B=B^*$, and $C$ is rank-1 but not Hermitian.
If $C$ were Hermitian, $N$ would ...
- 116
2
votes
0
answers
119
views
Seeking insights on bounded set positive solutions for a set of linear systems in $\mathbb{R}^n$
Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (...
2
votes
0
answers
178
views
Regularity of linear Bellman equation
Let $f(x,t):B_1 \times [0,1] \to \mathbb{R}$ be Lipschitz function on both $x$ and $t$, $\varphi$ be Lipschitz function on both $x$ and $t$ on the parabolic boundary of $B_1 \times [0,1]$. Let $A$ be ...
- 54
2
votes
0
answers
147
views
Graph Laplacians, Riemannian manifolds, and object collisions
To preface this question, I am a part-time game developer and full-time optimization fiend.
I am working on object collisions at the moment and many resources I have found online are more-or-less just ...
- 21
2
votes
1
answer
263
views
The best probability distribution for the game of Number Master
In the game of Number Master, the player controls a number starting with $1$ and hits the other numbers one by one on the road.
If the player hits a number smaller or equal to the current controlling ...
- 53
2
votes
0
answers
93
views
Curve fitting with "rough" loss functions
Many real-valued classification and regression problems can be framed as minimization in the following way.
Setup:
Let $\Theta \in \mathbb{R}^p$ be the parameter space that we are searching over.
For ...
- 200
2
votes
0
answers
120
views
How to solve $\min_{\mathbf{x}\in \{\pm 1\}^N} \lVert \operatorname{sign}(\mathbf{Wx}) - \mathbf{y} \rVert_2^2$ where $\mathbf{y}\in \{\pm 1\}^N$?
Given the matrix $\mathbf{W} \in \mathbb{R}^{N \times N}$ and the vector $\mathbf{y} \in \{\pm 1\}^N$, how to solve
$$\min_{\mathbf{x}\in \{\pm 1\}^N} \left\| \operatorname{sign}(\mathbf{Wx}) - \...
- 175
2
votes
0
answers
81
views
Differential inequality with convex constraint
The following problem looks to be classical, but I fail to find a reference for it. If you know it, please help me.
Given a bounded measurable function $h:{\mathbb R}_+\to\mathbb R$ and a number $a\...
- 52.3k
2
votes
1
answer
877
views
Interpreting mincost flow dual variables
Consider the task of finding flow of size $b$ with minimum possible cost.
It may be formulated as linear programming in a following way:
$$\boxed{\begin{gather}
\min\limits_{f_{ij} \in \mathbb R} &...
- 1,171
2
votes
0
answers
94
views
Lyapunov function utility in stochastic optimal control
The article Optimal strategy of vaccination and treatment in an SIRS model with Markovian switching by (X.Mu, Q.Zhang) studies necessary and sufficient conditions on near-optimal controls.
In both ...
- 141
2
votes
0
answers
79
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 ...
- 6,853
2
votes
0
answers
119
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
71
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 ...
2
votes
0
answers
56
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 ...
- 2,772
2
votes
0
answers
104
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 $\...
- 503
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 ...
- 21
2
votes
0
answers
143
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},...
- 2,442
2
votes
0
answers
159
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 ...
- 21
2
votes
0
answers
76
views
Polyhedron coordinate bound
Given a polyhedron
$$Ax\leq b$$
where we assume $A\in\mathbb Q^{m\times n}$ and $b\in\mathbb Q^{m}$ and it takes $L$ bits to represent the inequalities what is a good bound on the quantity $\|y\|_\...
- 13.9k
2
votes
0
answers
208
views
Condition under which the Clarke's subdifferential is locally Lipschitzian
Given a locally Lipschitz continuous function $f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ and closed set $$\Omega =\left\lbrace x \in\mathbb{R}^n \ |\ f(x) \leq 0 \right\rbrace$$ such that f is semi-...
- 225
2
votes
0
answers
162
views
Lagrangian multipliers and a variant of Newton's method
A variant of Newton's method for solving the equality constrained problem
\begin{equation}
\begin{array}{ll}
\min &f(x) \\
\text{s.t.} & h(x) = 0
\end{array}
\end{equation}
is as follows:
\...
- 97
2
votes
0
answers
211
views
Best approximation of piecewise constant function by Lipschitz functions
Let $f=\sum_{n=1}^N k_n I_{E_n}$ where $E_n$ are Borel subsets of $\mathbb{R}^n$ and $k_n\in \mathbb{R}^m$ with non-negative entries, and let $\mu$ be a finite Borel measure on $\mathbb{R}^n$. What ...
- 5,405
2
votes
0
answers
60
views
How to constrain the integral of the control function to a fixed value?
In the following, I am referring to the general "Hamiltonian control theory" using the conventions defined here.
I am working on a very simple S($x_1$)I($x_2$)R($x_3$) model for infectious ...
2
votes
0
answers
166
views
How to solve a QCQP where constraints are balls?
I want to solve the following optimization problem in variables $\theta_1, \theta_2, \dots, \theta_K$
\begin{equation}
\begin{aligned}
& \underset{\theta}{\text{minimize}}
& & \...
2
votes
0
answers
131
views
Optimal way to group points in the plane into clusters
Consider a strictly decreasing sequence $d = (d_k)_{k\ge 1}$ of distances in $(0,1)$. Given a constant $C>2$, we say that $d$ has the $C$-grouping property if any finite non-empty subset $S$ (of ...
- 1,761
2
votes
0
answers
43
views
Weak relaxation of a strongly lower semi-continuous functional
Let $F$ be a lower semicontinuous functional on a Banach space $X$, wrt its strong topology. Is there a known form for the relaxation (lower semicontinuous envelope) of $F$ with respect to the weak ...
- 5,405
2
votes
0
answers
171
views
How to sweep the leaves efficiently?
A cleaner, denoted by $P$, aims to sweep $n\ge 1$ leaves that appear one by one in a courtyard modeled by a compact set $D\subset \mathbb R^2$. Denote by $x_0$ the initial position of $P$ and by $v>...
user128095
2
votes
0
answers
213
views
When does an infinite product of random matrices have finite expected norm?
Given a finite set of matrices $A_i$, sample $n$ matrices uniformly with replacement and compute $f_n=\|A_1 A_2\cdots A_n\|^2$. When is the following limit finite?
$$\lim_{n\to \infty} E[f_n]$$
I'm ...
- 2,442
2
votes
0
answers
121
views
intuition behind shape optimization using Hadamard's method
I'm trying to understand the intuition behind shape optimization using Hadamard's method. Please consider the following simple example:
Let $\lambda$ denote the Lebesgue measure on $\mathcal B(\...
- 167
2
votes
0
answers
46
views
Notion of distance between linear programs
Consider the linear programming problem
\begin{align}
\max_{x}&~c^Tx \\~s.t.~~a^Tx &\leq B~,~0\leq x_i \le1
\end{align}
where $c$ and $a$ are $n \times 1$ given non-negative vectors. $B$ is a ...
- 1,421
2
votes
0
answers
286
views
Modified variational formulation of heat equation
The heat kernel $u:\mathbb{R}^n\times (0,\infty)$ is defined as the solution to
$$
u_t = \Delta u,
$$
subject to certain boundary conditions and can alternatively be described, in variational form, as ...
- 5,405
2
votes
1
answer
240
views
Basis pursuit algorithms for exponentially large matrices?
Are there any efficient algorithms/heuristics for basis pursuit for exponentially large matrices?
That is
$$\begin{array}{ll} \underset{x \in \Bbb R^n}{\text{minimize}} & \lVert x \rVert_0\\ \text{...
- 21
2
votes
0
answers
66
views
Proving the existence of a dual for an infinite linear program
I am concerned with proving the existence of the dual of an infinite linear program. In addition to the writings of Rockafellar, Luenberger, and Boyd & Vandenberghe on: subdifferentials, Legendre-...
- 121
2
votes
1
answer
307
views
Positivity of quadratic form minus linear form on the simplex
Let $a_{ij}$ be the elements of a $n$-dimensional covariance matrix. Can we prove the following?
$$ 1-\sum_{k=1}^n a_{ik} \lambda_k + \sum_{j=1}^n \sum_{k=1}^n \lambda_j a_{jk} \lambda_k > 0, \...
- 21