All Questions
1,732 questions
0
votes
0
answers
30
views
Application of greedy approach for optimization
I want to maximize an objective given by $$\max_{\{q_n,p_n\}} \sum_{n=0}^\infty (\alpha_1 - \beta_1 n) p_n + (\alpha_2 - \beta_2 n) q_n$$
where $\alpha_1 > \beta_1 >0$ and $\alpha_2 > \beta_2 ...
- 23
0
votes
0
answers
34
views
Ensuring symmetry in mixed derivatives using RBF-FD method
I'm working on a numerical problem where I have the first-order partial derivatives $\frac{\partial f}{\partial x}$ and $\frac{\partial f}{\partial y}$ of a bivariate function $f(x, y)$ at a set of ...
- 1
0
votes
0
answers
36
views
Convergence of numerical scheme for HJB equation
Convergence of numerical scheme for HJB equation has been widely studied, the key paper is the Barles's one. Essentially, the convergence is guarenteed if the scheme is:
Consistent
Stable
Monotony
...
- 393
0
votes
0
answers
56
views
Godunov splitting convergence research
The approximation of Godunov splitting on certain differential equations is known to be first order accurate. In 2011, a paper has also shown that it is first order accurate for nonlinear ordinary ...
- 101
0
votes
0
answers
36
views
ILPs with square constraint matrix
Given the Integer Linear Programming ($\text{ILP}$) problem
\begin{array}{ll}
\text{minimize} & c^T x \\
\text{subject to}& \mathbf{A}^T x \ge b \\
\text{where}&c,x,b\in\mathbb{N}_0^n,\\ &...
- 13.2k
0
votes
0
answers
87
views
How to solve with FEM a semilinear elliptic equation?
I searched in many books regarding FEM how to solve semilinear elliptic equation, but I did not find too many things. They mostly treat linear and simple problems. For example in P.Ciarlet-The finite ...
- 1,759
0
votes
0
answers
26
views
Monotony of enforced subtour merging
Is it true that for a symmetric TSP instance in the sequence of edges generated by successively:
calculating the optimal 2-factor
adding cardinality constraints on the edgesets of the 2-factor's ...
- 13.2k
0
votes
0
answers
171
views
Solve NP-hard type problems with linear programming
I would like to know if there is any way to solve an NP-hard type problem, for example, the TSP, sum of subsets or knapsack problem, by using linear programming and not by brute force.
I ask this ...
0
votes
0
answers
64
views
Alternatives to McCormick Envelope
I have an optimization problem for which I have the optimal solution obtained by the ILP.
However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
- 3
0
votes
0
answers
164
views
Inf-convolution of norm 1 and norm 2 square
The inf-convolution of the functions $f$ and $g$ defined on $\mathbb{R}^n$ is
$$
h(x)=\inf _{y \in \mathbb{R}^n} f(y)+g(x-y) .
$$
We can prove that if $f,g$ are convex functions, then $h$ is convex.
...
- 129
0
votes
1
answer
114
views
Mixed integer program and continuous Diophantine approximation
Let $n\in\mathbb{N}$ such that $n\geq 2$ and let $0<r<1$ be a real number. We wish to solve the following problem.
$$\min_{(t,(z_j)_{j=2}^n) \in \mathbb{R}\times \mathbb{Z}^{n-1}} t$$
subject to ...
0
votes
0
answers
55
views
Relationship of optimal solutions between the total function and the sub function
This is an unconstrained convex optimization problem. Let $\mathcal{N}=\left\{1,\ldots,n\right\}$, $2\leq n<\infty$. Suppose there are many strongly convex functions $f_i(x)$, where $x\in\mathbb{R}^...
- 1
0
votes
0
answers
85
views
Show that $\max_{P_X : X\in (0,1) } \left| \frac{\mathbb{E} [ f'(X) ]}{ \mathbb{E} [ f(X) ] } \right|$ is maximized by at most two mass points
Let $f$ be some given well-behaved function. Consider the following optimization problem overall probability distribution on $[0,1]$
\begin{align}
\max_{P_X : X\in [0,1] } \left| \frac{\mathbb{E} [ ...
- 671
0
votes
0
answers
80
views
Non-triviality of the sum of simple rational functions
Recently, in the study of unicity problems in complex analysis, I met a problem that can be stated in the following way,
Let $\{m_i\}_{i=0}^{3}$ and $\{n_i\}_{i=0}^{3}$ be eight integers in $\mathbb{Z}...
- 1,706
0
votes
0
answers
104
views
Can the best constants in harmonic analysis be approximated in principle?
Consider the trivial example of Holder's inequality $\|f\|_p\,\|g\|_q\geq |fg|_1$ if $\frac{1}{p}+\frac{1}{q}=1, p,q\geq 1$ and $f,g$ are functions on $\mathbb{R}^n$. Let's suppose we don't know how ...
- 265
0
votes
0
answers
85
views
Lagrange's interpolating polynomial
Let $f:[a,b]\rightarrow R$ be a function that is not $C^{(n+1)}$ on $[a,b]$ but its $n$-th derivative is a Lipschitz function? How does the Lagrange's interpolating polynomial formula change? How does ...
- 1
0
votes
0
answers
226
views
Numerical approaches to functional equations
I'm interested in finding numerical approaches to solving functional equations such as
f(xy)=f(x)+f(y),
where the equations had no derivatives or integrals, and contains arguments involving x
and y
.
...
- 21
0
votes
0
answers
145
views
Bound on solutions of $Ax \ge b$
Let $A \in \mathbb{Z}^{m \times n}, b \in \mathbb{Z}^{m \times 1}$.
One can show that if there is a solution of $Ax \ge b, x \in \mathbb{R}^n$ then there is one such that $\|x\|_{\infty} \le c (\|A\|_{...
- 439
0
votes
0
answers
84
views
1-degree SOS proof refutes Linear Programming
I am trying to understand Sums-of-Squares proof systems.
A degree $d$ Sums-of-Squares refutation for a set of polynomial equations $P = \{p_1(x) = 0, ..., p_m(x) = 0\}$ is defined as
$\sum_{i=1}^m g_i(...
0
votes
0
answers
272
views
Finding the eigenvectors of a submatrix
Let $A=(a_{kl})$ be a matrix in $M_n(\mathbb{R})$ when $n$ is even. Let $B=(b_{kl})$ be the symmetric $2n$ by $2n$ matrix whose entries are given by,
$b_{k,l}=a_{kl}$ if $1\leq k,l\leq n$.
$b_{n+k,l}=...
- 4,058
0
votes
1
answer
83
views
Combining Dantzig-Wolfe and Benders decomposition
I'm now solving an LP that has a few coupling rows (as in Dantzig-Wolfe decomposition) and a few coupling columns (as in Benders decomposition) simultaneously; other rows and columns are block-angular....
- 3
0
votes
0
answers
94
views
Boolean operation on n dimensional polyhedron
A polyhedron in $R^n$ is defined by a set of half-planes: $P = \{x \in R^n \mid Ax - b \le 0\}$.
Given a set of polyhedra in $R^n$, $ P_1, P_2, \dotsc, P_k$, is there an algorithm/implementation that ...
- 21
0
votes
0
answers
63
views
Direct (first-order ?) algorithm to minimize $u(x) := \|x-a\|_C + r\|x\|_p$
Fix $a \in \mathbb R^n$, $r \ge 0$, $p \in \{1,2\}$, and a positive-definite matrix $C$ of order $n$. Define $u:\mathbb R^n \to \mathbb R$ by $u(x) := \|x-a\|_C + r\|x\|_p$, where $\|z\|_C := \sqrt{z^\...
- 6,853
0
votes
0
answers
54
views
Numerically expanding a function in a rational-power "basis"
I have some scientific code which interfaces with a library which accepts real functions specified as any number of additive terms with exponential powers. For instance, it is capable of accepting ...
- 173
0
votes
0
answers
108
views
Solving a nonlinear equation maybe with Lambert W function
Can you please help me solve the following nonlinear equation?
\begin{equation}
\boldsymbol{z} \odot\left(\boldsymbol{\Gamma}^{\top} \boldsymbol{y}\right)=(\beta)^{\frac{1}{m-1}}\left(\frac{m-1}{...
- 11
0
votes
1
answer
64
views
Round Robin volleyball Tournament [closed]
Consider a set of N teams (N even number) that must make a
Round Robin Tournament. To each pair i; j, i ≠ j, of teams there is associated level
of interest si,j ∈ {1;2;3} of the match between them (1 =...
0
votes
0
answers
114
views
Degeneracies in linear combination of tensor product of Pauli matrices
Let $P_i \in \{I,X,Y,Z\}^{\otimes n} $, that is $P_i = \bigotimes_{i =1 }^n \sigma_i$ with $\sigma_i \in \{I,X,Y,Z\}$, where
$$
I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \hspace{1cm} X =...
- 131
0
votes
1
answer
271
views
Solving (or approximating) a certain delay differential equation
I'm interested in finding the (unique?) solution to the set of delay differential equations
$$f_w(w,x) = xf(w,w^2x)+w^3x^2f(w,w^4x), $$
$$f_x(w,x) = wf(w,w^2x)$$
With the initial condition $f(1,x) = e^...
- 1,730
0
votes
0
answers
579
views
Convex maximization over the boundary of a convex set
Let $f: \mathbb{R}^n \rightarrow \mathbb{R}$ be the objective function that is strictly convex. We would to like maximize $f$ over a convex compact set $S \subseteq \mathbb{R}^n$. Assume that $f$ has ...
- 261
0
votes
1
answer
397
views
What is the best way to choose initial basis when applying simplex method to an equality form of LP?
Currently I'm trying to write a practically fast LP solver for a sparse instance, which is by simplex method with LU decomposition and eta-matrix update. In the development I realized that I'm not ...
- 1
0
votes
0
answers
89
views
3D interpolation function
I've got a 3D figure created using around 30k points and has different regions colored in an specific way according to some unrelated variables that come from a project I'm creating. Taking in ...
0
votes
0
answers
115
views
Explicit equation for border of the Minkowski sum of sets
Assume we have sets of the form
$$
M_j = \{x\in\mathbb{R}^d : f_j(x) \le 0,x \ge 0\}
$$
where $x\ge 0$ means $x_i \ge 0 \quad \forall i=1,\dots, d$.
Goal
I am looking for an (explicit) representation ...
- 385
0
votes
0
answers
124
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 $\...
- 287
0
votes
0
answers
109
views
How to find a set given its support function
Let $\mathcal{U}$ be a convex and compact set. Its support function is defined as $\delta^*(v|\mathcal{U})=\sup_{u\in \mathcal{U}} v^T u$. Assume that we are given the support function $\delta^*(v|\...
- 53
0
votes
0
answers
40
views
Subtour-gluing constraints for ILP formulation of TSPs
If one doesn't want to introduce additional variables to the ILP of a TSP instance, one has to add exponentially many so-called subtour-elimination constraints; in practical calculations subtour-...
- 13.2k
0
votes
0
answers
96
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 ...
- 29
0
votes
0
answers
135
views
Is there an efficient algorithm to project a vector onto the eigenbasis of a symmetric matrix?
Let $H$ be a symmetric matrix over $\mathbb R^n$. Given some vector $u$, I would like to express $u$ in the eigenbasis for $H$. Can this be done efficiently, perhaps using some kind of iterative ...
- 623
0
votes
0
answers
195
views
Why does explicit Runge-Kutta 4 allow positive eigenvalues?
When solving a system of ODEs:
$$\dot{x} = A x,$$
we call the system unstable when the eigenvalues of A have a positive real part.
However, the stability region of the explicit Runge-Kutta 4 method ...
- 17
0
votes
0
answers
165
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 ...
- 235
0
votes
0
answers
137
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 ...
0
votes
0
answers
227
views
Decomposition of symmetric block matrix
I came across this question and got really interested about it. There, the OP asks whether is possible to decompose a $2n \times 2n$ block matrix:
$$ \begin{pmatrix}
X & I \\
I & Y
\end{...
0
votes
1
answer
266
views
Using QR or SVD to sum up finite number of matrices
Problem
I was wondering if there are any theoretical results that tackle the following problem:
Construct the following matrices $\mathbf{\mathcal{S}_{1}},\mathbf{\mathcal{S}_{2}},\ldots,\mathbf{\...
0
votes
1
answer
116
views
Iterations of Dantzig-Wolfe Decomposition for a Simple Linear Programming problem
This arises from an engineering problem I am working on. Let $\mathbf{c}_i,\mathbf{a}_i,\mathbf{b}_i\in \mathbb{R}^{d}$ be a given set (collection) of vectors where $i\in\{1,\dots,n\}$. Define the ...
- 1,421
0
votes
1
answer
228
views
Is it possible to numericaly solve functional equation
Given a functional equation of form $f(f(x))=T(x)$ is there any good ways to solve it numerically? If not then at least approximate in some small region $x\in(-a;a)$.
E.g. with the equation $f(f(x))=x+...
- 3
0
votes
0
answers
93
views
Number of vertices in a polyhedron
Consider polytopes
$$A_1[x_{1,1},\dots,x_{1,m_1},z_{1}]'\leq b_1$$
$$A_2[x_{2,1},\dots,x_{2,m_2},z_{2}]'\leq b_2$$
$$B[z_{1},z_{2},z]'\leq c$$
having vertex count $v_1,v_2$ and $v$ respectively.
We ...
- 13.9k
0
votes
0
answers
57
views
Numerically finding matrix approximation by lower-dimensional "pseudo-similar" matrix
Consider an $N\times N$ (real or complex) matrix $A$, and some $n<N$. Is there a good numerical algorithm that finds the set consisting of an $n\times n$ matrix $B$, an $n\times N$ matrix $I$, and ...
- 3,001
0
votes
0
answers
267
views
Can we improve the error bounds for spline interpolation if the interpolated function is smooth?
Let me first state the original problem I want to solve:
Given a closed curve $C:[a,b]\to\mathbb R^2$ that is smooth ($C^\infty$), a partition in the parameter space $a=t_0<t_1<\cdots<t_n=b$,...
- 283
0
votes
0
answers
68
views
Convex optimization under asymmetric loss in infinite dimensional space
The following problem is common in financial economics
$$ \min_{m \in L^2} \mathbb{E}[ \phi(y(\theta)-m)] \quad \text{s.t. } \mathbb{E}[ mx ]= q $$
That is, given a random variable $y(\theta)$ ($\...
- 45
0
votes
1
answer
516
views
How do I get an analytical solution to this nonlinear equation?
I posted this question over on Math Stack Exchange (link), but have not received a response. I'm wondering if it's too complicated for that audience, so I'm posting it here in the hopes that someone ...
- 109
0
votes
0
answers
44
views
Solving nonlinear equations involving expectations
Let $X$ be a random variable and $g(x,y)$ be a function of two variables. Consider the equation
$$
\mathbb{E}_Xg(X,y) = 0
$$
Are there any specialized techniques for solving such equations (...
- 11