All Questions
563 questions with no upvoted or accepted answers
2
votes
0
answers
76
views
Minimizing $\int\lambda({\rm d}y)\frac{\left|g(y)-\frac{p(y)}c\lambda g\right|^2}{r((i,x),y)}$ with respect to discrete parameter $i$
Let $I\subseteq\mathbb N$ be finite and nonempty, $(E,\mathcal E,\lambda)$ be a $\sigma$-finite measure space, $$\lambda f:=\int f\:{\rm d}\lambda$$ for $\lambda$-integrable $f:E\to\mathbb R$, $p:E\to(...
- 167
2
votes
0
answers
406
views
Pros and cons of using integer programming alone or combined integer and global optimization?
First, I am not sure if this is the right question to ask in this forum. But I have been looking for answers for a long time and I have been also asking my university's "engineering" professors but I ...
2
votes
0
answers
52
views
Zeroth order method with near-optimal rate that works in practice?
I want to find a ZO (zeroth-order, i.e. no access to gradient) algorithm to minimize a strongly-convex deterministic objective (say, as a sum of smooth and nonsmooth proximable functions). I want such ...
- 41
2
votes
0
answers
69
views
References for numerical approach of Hilbert uniqueness method (HUM)
Finding of the control that achieves the exact controllability of the wave equation (Neumann boundary conditions) using the HUM method (see: J.L. Lions, Controlabilité exacte perturbations et ...
- 21
2
votes
0
answers
760
views
Can this quadratic program be solved analyticaly?
I have a convex quadratic program wich is structured as follows :
\begin{align*}
\operatorname{argmin}_{p} &\hspace{0.5em} p' A p - 2 p' b \\
\mathrm{s.t.} &\hspace{0.5em} Ep=f \\
...
- 686
2
votes
0
answers
47
views
A linear program where coordinate descent works pretty well
I am working with a polytope $P\subset \mathbb{R}_+^n$ with the property that there are at about $n!$ minimizers of $\sum_{i=1}^n x_i$, in the following sense:
Select any coordinate $j$ and set $...
- 21
2
votes
0
answers
131
views
Can we conclude $\sup_g\int f_1g\le\sup_g\int f_2g$ from $\int f_1\le\int f_2$ in this situation?
Disclaimer: Please bear with me, the question isn't as complicated as it looks like, but I wasn't able to find any simplification for which no counterexample comes to my find.
Let $(E,\mathcal E,\...
- 167
2
votes
0
answers
111
views
Maximization of an integral functional over a closed convex set
I want to maximize $$F(w):=\sum_{1\le i,\:j\le2}\int\lambda^{\otimes2}({\rm d}(x,y))\left(w_i(x)f_j(x,y)\wedge w_j(y)f_i(y,x)\right)g_{ij}(x,y)$$ over the closed convex set $$S:=\left\{w\in{\mathcal L^...
- 167
2
votes
1
answer
329
views
Worst case performance of heuristic for the non-Eulerian windy postman problem
The windy postman problem seeks the cheapest tour in a complete undirected graph, that traverses each edge at least once; the cost of traversing an edge is positive and may depend on the direction, in ...
- 13.2k
2
votes
0
answers
98
views
State-of-the-Art algorithms for bilevel optimization
I want to numerically solve a bilevel optimization problem of the form
$$ \min_y f(y, \hat x(y)), \qquad \hat x(y) = \arg\min_x g(x, y) $$
(for simplicity assume that $\min_x g(x, y)$ exists and is ...
- 121
2
votes
0
answers
148
views
Generalization of Farkas' Lemma to Hermitian Matrices
I recently stumbled upon a well-known version of Farkas' Lemma which, roughly speaking, I would like to generalize from real vectors to hermitian matrices, as it seems promising for something else I ...
2
votes
1
answer
710
views
$0$-"norm" minimization with least-squares regularization
I have the following optimization problem in $\mathbf{x} \in \mathbb{R}^{K \times 1}$
$$\min_{\mathbf{x}>0} \quad \|\mathbf{A}\mathbf{x}\|_0 + \alpha \|\mathbf{B}\mathbf{x}-\mathbf{c}\|_2^2$$
...
2
votes
0
answers
61
views
Strong stability of the wave equation with time depending potential
It is well known that the wave equation with frictional damping
$$\eqalign{
& {y_{tt}} = {y_{xx}} - a(t,x){y_t}{\text{ }}{\text{,(t}}{\text{,x)}} \in {\text{ }}(0,\infty ) \times (0,1) \cr
...
- 617
2
votes
0
answers
81
views
Solving Mixed-Integer Non-Linear Optimization Problem
I would like to solve the following optimization problem:
\begin{array}{ll}
\underset{x_{i}\geq0,\, \pi_{i}\in\{0,1\}}{\text{minimize}} & \displaystyle\sum_{i=1}^n x_i\\
\text{subject to} & ...
- 21
2
votes
0
answers
74
views
What is the most efficient path for a robot without turning radius?
I recently programmed a most efficient path for a robot going from $(x_1, y_1 , \theta_1)$ to $(x_2, y_2)$. The bot does a combination of turning and moving at any given point, based on the difference ...
2
votes
0
answers
248
views
A parametrization of stable matrices
Let $A\in\mathbb{R}^{n\times n}$ be a diagonalizable matrix with real and strictly negative eigenvalues. Furthermore, suppose that $\mathrm{tr}(A)=-1$.
My question. I'm wondering whether it is ...
- 2,712
2
votes
0
answers
145
views
Observability inequality for the heat equation
I want to ask about the observability inequality for the heat equation ( internal control), we consider the backward heat equation with Dirichlet boundary conditions:
\begin{array}{c}
\varphi _{t}+\...
- 617
2
votes
0
answers
46
views
Optimization with bounds on the control and its derivative
I would like to understand the following optimization problem. Let $F(t,x)$ be a continuous function defined on $[0,1]\times [0,1]$, which is increasing in $t$ and convex in $x$ (I have in mind $F(t,x)...
- 41
2
votes
0
answers
283
views
Derivative with multiple summation operators
I have a defined utility function as Eq.(1), and I am seeking the minimized utility subjects to some constraints. The notation used is as following:
\linebreak
$V$ is the set of nodes, $v_i\in V$; $O$...
- 21
2
votes
0
answers
43
views
How sensitive is ML-estimation of the expected value if the covariance matrix is not correct?
Suppose, we have a random variable $Y \sim \mathrm{N}\left( Ax, \, \Sigma \right)$ and realisations $y$. I would like to estimate $x$, the parameter of the expected value.
The loglikelihood function ...
- 21
2
votes
0
answers
70
views
Optimal curves on planar annular regions
I am looking for references on optimal curves in planar annular regions
More precisely, on simple closed curves of class $C^2$ which simultaneously minimizes a finite number of functionals from the ...
- 121
2
votes
0
answers
43
views
Partitioning $n$-space based on linear combinations
I'm trying to figure out the approximate number of areas the positive $n$-space will be divided into if we partition it as follows: we have $k$ linear functions $F_1$, $F_2$, ..., $F_k$ on $n$ ...
- 21
2
votes
0
answers
100
views
Fixed point of dynamic system
Let $F(\cdot, \cdot)\colon \mathbb{R}^n \times \mathbb{R}^n\rightarrow \mathbb{R}$ be a bivariate and nonnegative function. Suppose $F(x,y)$ is not convex with repect to $x$ or $y$. Moreover, asusme $...
- 1,127
2
votes
0
answers
75
views
existence of minimizer to the dual problem of a martingale optimal transport type problem
Let $\nu$ be a given probability measure on $\mathbb R^2$ and consider function of the following form:
$$L(f)(x_1,x_2)=\sup_{y\,=\,(y_1,y_2)\,\in\, \operatorname{Graph} (f)} \{ x_1 y_2 + x_2 y_1 - ...
- 325
2
votes
0
answers
176
views
Positively invariant with respect to nonlinear dynamics
I have the set of nonlinear differential equations describing a system I modeled for my research (spread of epidemics or information for instance):
$$\begin{array}{rl} \dot{p}(t) &= \gamma r(t)-u(...
- 21
2
votes
0
answers
2k
views
How to find a positive solution to an under-determined linear system (if such a solution exists)?
Like the title says, if an under-determined system of linear equations does have at least one positive solution, how to find it efficiently?
Suppose we have an under-determined system:
$$Ax = b$$
...
- 121
2
votes
0
answers
80
views
Making a polyhedron integral by selecting value for a specific co-ordinate of constraint vector
I am currently trying to solve a binary integer programming(maximization) problem, where the first row of the constraint matrix corresponds to the constraints on the total number of 1's in the vector ...
- 123
2
votes
0
answers
105
views
Optimization over a convex cone generated by a set is equal to optimization over the set
Within my research I found an important doubt and that prevents me from advancing, the context of my doubt is as follows:
We considerer the following optimization problem
$$
\left\{\begin{array}{cl} \...
- 159
2
votes
0
answers
380
views
Matrix optimization of a random quadratic form
I am interested in maximizing a quadratic form which looks like
$$f(\Sigma) = E(\operatorname{trace}(SJ)) = E(1^{\top} S 1)$$
where $J$ is a matrix of $1$'s, $S= \Sigma_{mm} - \Sigma_{mo} \Sigma_{oo}...
- 21
2
votes
0
answers
344
views
Linear programming with an infinite matrix
I would like to solve the following infinite linear system subject to $x_i \ge 0$ that minimizes $x_3$.
The third column contains no additional nonzero values beyond what is shown. Though the first ...
- 283
2
votes
0
answers
95
views
"Almost everywhere" in the Pontryagin Maximum Principle?
In several accounts of the Pontryagin Maximum Principle, I have found that the statement says that the conclusion must hold for almost all $t$ (e.g., books by Clarke, Agrachev-Sachkov, etc.), and in ...
- 445
2
votes
0
answers
94
views
Maximize a tricky function on $SU(n)$
Given non-zero $\xi \in \mathfrak{su}(n)$ and $G \in SU(n)$, consider the function:
$Q(U) = Tr(G^{\dagger}U)GU^{\dagger} - Tr(U^{\dagger}G) UG^{\dagger}$
(which just happens to be the gradient of $|...
2
votes
0
answers
100
views
Null controllability of the heat equation with an internal control (for positive solutions)
Let $\Omega$ a bounded open regular subset of $R^N$ and $\omega$ an open subset such that $\omega \subset \Omega$. Let $T >0$.
Let $y_0$ in $L^2(\Omega)$.
It's a well-known fact in the theory of ...
- 51
2
votes
0
answers
126
views
Unveiling hidden structures
One way to unveil a hidden structure of a undirected graph - given as an adjacency matrix - is to permute the rows and columns until a pattern with a maximal geometrical symmetry is found. (The ...
- 9,720
2
votes
0
answers
143
views
variational calculus problem
I have two functions $f_1(x)$ and $f_2(x)$ defined for $0\leq x \leq 1$.
Let $$L^HL = \left[\begin{array}{cc} 1 & \rho \\ \rho & 1\end{array} \right].$$
Define $$R(x) = \log\left(1 + \frac{...
2
votes
0
answers
52
views
Minimizer of a class of SDEs
Setup
Let $\mathscr{H}$ be a separable Hilbert space, $\mathcal{X}\triangleq \langle \Omega,\mathscr{F},\mathscr{F}_t,\mathbb{P}\rangle$ be a stochastic base and $X_t$ be an $H$-valued stochastic ...
- 5,405
2
votes
0
answers
46
views
What is known about the relation of the multiple salesman problem and the travelling saelsman problem?
The travelling salesman problem (TSP) is well known (https://en.wikipedia.org/wiki/Travelling_salesman_problem). Let us look at the Euclidean TSP throughout this question.
There is a generalization ...
- 61
2
votes
0
answers
68
views
Reference to Semi-Statistical Optimal Control Theory
I don't know what to call what I want to do, so I'll explain and please refer me to texts and papers.
Given a standard control problem,
\begin{align}
\min_{u(t), W} &\int dt\ f(x(t), u(t); W) \\
\...
user66731
2
votes
0
answers
299
views
Practical application of envelope theorem for linear programs
Assume that we have solved a (standard) linear program
$$
\text{minimize}_{x\in {\mathbb R^n}}\,\, c_0^Tx, \,\,\,\,\, \text{s.t. } A_0x \leq b_0,
$$
and would like to know how sensitive is the optimal ...
- 7,182
2
votes
0
answers
64
views
Finding orthogonal basis with constraint
Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$
with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$.
And is there any condition on $V_i,i\leq ...
- 909
2
votes
0
answers
71
views
Existence of probability distribution satisfying upper/lower bounds on events
Suppose we have a finite sample space $S$ and some events $A_1, \dots, A_k \subseteq S$. We would like to put a probability distribution on $S$ so that no element has probability greater than a ...
- 21
2
votes
0
answers
114
views
approximation of rational functions
Suppose $\hat{p}/\hat{q}$ and $p/q$ are two rational functions where $p,q,\hat{p},\hat{q}$ are of degree $n$. Suppose they satisfy that $|p(z)/q(z) - \hat{p}(z)/\hat{q}(z)| < \epsilon$ for any $z$ ...
- 181
2
votes
0
answers
105
views
Is there a name for this variant of the MST and the TSP?
Suppose I am given a weighted graph $G$ that contains a "start vertex" $v_0$, and my goal is to construct a set of paths that all originate at $v_0$ and touch all of the vertices of $G$, with as ...
- 4,049
2
votes
0
answers
177
views
Formulating shortest path as submodular minimization
I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function.
The answer ...
- 21
2
votes
0
answers
115
views
Are singular critical points isolated for control systems on compact semisimple Lie groups
Given a control system on $\mathrm{SU}(n)$ (or any other compact, semi-simple Lie group I suspect) of the form:
$\frac{d U_t}{dt} = (A + w(t)B)U_t$
where $A,B \in \mathfrak{su}(n)$ generate the ...
- 2,099
2
votes
0
answers
104
views
A (non-convex) minimization quadratic programming problem with d constraints
Minimize $0<\omega_{dd}<2$ subject to
$$\sum_{j=1}^{d}(\omega_{dj} - \omega_{ij})^{2} \geq 4, i=0,1,...,d-1,$$
where $-2<\omega_{ij}<2$ is known for $0 \leq i \leq d-1$ and $1 \leq j \leq ...
- 1,431
2
votes
0
answers
90
views
Singularities of the Quantum propagator (baby version)
Given $a,b \in \mathfrak{su}(4)$ which are taken to generate the whole algebra, consider the following map $V:\mathbb{R}^{2} \rightarrow SU(4)$:
$V : (w_1, w_{2}) \mapsto e^{(a+w_2 b)} e^{(a+w_1 b)}$
...
- 2,099
2
votes
0
answers
214
views
About optimizing a convex function on a hypercube
Given a real valued convex function $g$ on $[-1,1]^n$, let $f$ be the restriction of it on the hypercube $\{-1,1\}^n$. I want to find a vertex on the hypercube $\{-1,1\}^n$ on which either (1) $f$ ...
2
votes
0
answers
154
views
Listing all Lattice Points in a Box
Let $B := [-1,1]^n$ be an $n$-dimensional box. Moreover, let $v_1,\ldots,v_n \in \mathbb{R}^n$ form a basis of $\mathbb{R}^n$, where the entries of the $v_i$ are explicitly irrational. We can assume ...
- 173
2
votes
0
answers
210
views
Finding optimal linear transformation for intersection of convex polytopes
I previously posted this on MathSE and am now trying here.
I have the following situation, as shown in the following diagram:
$W=\{w_i\}_{i=1..|W|}$ is a set of vertices (show in diagram in blue) ...
- 695