All Questions
1,732 questions
0
votes
1
answer
214
views
Hamilton equations-Symplectic scheme [closed]
We know that $\dot{q} = \frac{\partial H}{\partial p}$ and $\dot{p} = -\frac{\partial H}{\partial q}$, and we also know the values $Q$ and $P$ respectively of $q$ and $p$ at a later time step $\Delta ...
- 111
0
votes
1
answer
76
views
A question on graph partitioning
Given a connected un-directed simple graph $G=(V,E)$, is there a polynomial time algorithm to find the smallest subset $S$ of $V$ such that each node in $V \setminus S$ has at least 50% of its ...
- 1,216
0
votes
1
answer
113
views
How do I solve this integer programming problem with non convex constraints?
I am not sure if this is the right place to post this question, please point me to the correct forum if I posted in a wrong place.
I have an optimization problem like this
...
- 103
0
votes
1
answer
162
views
Clenshaw-Curtis integration without Fourier
The Clenshaw-Curtis quadrature rule approximates an integral $I=\int\limits_{-1}^{1} f(x) \, dx$ by $$I\approx I_n = \sum\limits_{j=1}^N f(x_j)w_j \, ,$$
where the $x_j$'s are the roots of the $N$-th ...
- 3,574
0
votes
1
answer
170
views
Numerical stable soliton solution
It is well known that the non-linear equation $f'' + 2f(1-f^2) = 0$ admits a soliton solution $f = \tanh(x)$.
Is it possible to solve this equation numerically?
For example on a finite interval $[-L,...
0
votes
1
answer
171
views
Distance of distributions of random variables, without PDF
Consider an interval $I$ with a smooth probability measure $d\mu (x) = c(x) dx$ and two known real measurable functions $f_1(x)$,$f_2(x)$. Both functions define a distribution on $X = {\rm Im} \, [f_1]...
- 3,574
0
votes
2
answers
120
views
Reference request: dependence on linear constraints
Excuse me if my question is stupid. I'm seeking the references on the dependence of the (linear) optimization problem on (linear) constraints. Namely, consdier the following optimization problem:
$$P(...
- 1,835
0
votes
1
answer
488
views
Efficient computation of matrix exponential of trace zero matrix [closed]
I am looking for identities that may help with numerical computation of the matrix exponential ${\rm exp}(A)$ where ${\rm tr}(A)=0$. I am already aware of general-purpose algorithms for computing the ...
- 561
0
votes
1
answer
2k
views
When to use non-negative-least square and least-square [closed]
What are the typical case we need to use Non-negative least squares NNLS
$$
||Ax - B||^2
$$
instead of least-square $$ Ax-B$$ (or vice versa)?
And is there any drawback in applying them on large $A$...
- 135
0
votes
1
answer
114
views
Fit a system of linear ODEs from several experiments
Assume we are given several initial vectors $x^{(1)},\ldots,x^{(r)} \in \mathbb{R}^n$, where the dimension $n=6$ (in any event a number below 10) , and the number of initial vectors $r$ is in the ...
- 749
0
votes
1
answer
726
views
Generating random variables from the Cantor Distribution [closed]
I am looking for a method (exact, if possible, but at least asymptotically correct) for generating random variates from a Cantor Distribution? It seems like its abstract definition prevents this. In ...
user42192
0
votes
1
answer
360
views
Estimating the vector potential
My question is, that given a vector field only numerically discrete in space, is there a way to estimate its vector potential?
Theoretically, I see this which requires the vector field over all of $\...
- 143
0
votes
2
answers
581
views
Does an implicit Runge Kutta scheme applied on a nonlinear ODE give a nonlinear set of equations to solve in each step?
We want to approximately solve an ODE
$$\frac{dy}{dt} = f(y,t)$$
with the Runge Kutta method
$$y_{n+1} = y_n + h \sum_{i=1}^s b_i k_i$$
$$k_i = f\left(y_n + h \sum_{j=1}^s a_{ij} k_j,\,t_n + c_i h\...
- 21
0
votes
1
answer
243
views
Does this algorithm terminate in all scenarios?
Let $x \in \mathbb{R}^p$ denote a $p$-dimensional data point (a vector). I have two sets $A = \{x_1, \dots, x_n\}$ and $B = \{x_{n+1}, \dots, x_{n+m}\}$, so $|A| = n$, and $|B| = m$. Given $k \in \...
- 123
0
votes
2
answers
244
views
Rewrite optimization objective
Hi,
I wanted to ask, under which conditions can one rewrite the optimization objective
$\min_x f(x)\;\;\;s.t.\;\;\;g(x) \leq s$
as
$\min_x g(x)\;\;\;s.t.\;\;\;f(x) \leq t$
I have particular ...
- 409
0
votes
2
answers
340
views
positive semidefiniteness: a psd matrix substracted by another rank 1 psd matrix
Given that $A$ is a positive semidefinite matrix, $x$ is a vector, $\lambda_0 \in [0, +\infty) $ is a real non-negative number. I want to know the answer to the following optimization problem.
$$
\...
- 101
0
votes
1
answer
173
views
Avoiding epsilon in mixed integer linear and quadratically constrained programs
I would like to represent the following constraint as MILP constraint where $x \in [a, b]$ with fixed $a, b \in \mathbb{R}$ and $y \in \lbrace 0, 1 \rbrace$.
$(x = 0 \wedge y = 1) \vee (x \neq 0 \...
- 1
0
votes
1
answer
2k
views
Find edge weights that fit given node weights
Let $G = (V,E)$ be a connected simple graph (unweighted, undirected, no selfloops) on $n$ nodes.
Let $\mathbf{d} := (d_1, d_2, ..., d_n) \in \mathbb{R}_{>0}^n$ be a vector of arbitrary given node ...
- 340
0
votes
1
answer
2k
views
Global Error Analysis of Euler's Method
I know that the local error at each step of Euler's method is O(t^2), where t is the time step. And since there are (b-a)/t steps, the order of the global error is O(t).
However, I saw a derivation ...
- 101
0
votes
1
answer
353
views
Moore-Penrose bound question
Suppose that we are given an equation $Ax=b$. The minimum least-squares solution is of course $x_{m}=A^{\dagger}b$. What I want to know is whether there are known bounds on $||x-x_{m}||$. In the ...
- 6,962
0
votes
1
answer
456
views
Is the Simplex Method still polynomial when all inequalities are through the origin?
Hello,
I want to solve a linear program using the simplex method, and I know that all my inequalities will pass through the origin (therefore, either my initial solution of (0, ... , 0) is optimal, ...
- 693
0
votes
2
answers
1k
views
Is there a method to find (fit) a function with four (4) independent variables?
I have a system with 4 sensors (say $s_1..s_4$) which I want to combine into a single signal.
I have logged the 4 outputs as well as a "control" sensor ($s_c$) which has the desired ouput signal. ...
- 1
0
votes
2
answers
1k
views
Degenerate case of linear programming duality?
Let's say we have a maximization linear program that looks like this: maximize $\vec{c}\vec{x}$, subject to $\matrix{A}\vec{x} \leq 0$, $\vec{x} \geq 0$. If we take the dual, we have "minimize $0\vec{...
- 2,019
0
votes
1
answer
40
views
How to handle the evaluation of functions on staggered ghost nodes?
I have a convection-diffusion-reaction steady state PDE in the form
$$
\frac{\partial C}{\partial x} = \frac{1}{u_0(x)}\left(\frac{\partial}{\partial z} \left( \mathcal{D}(z) \frac{\partial C}{\...
- 111
0
votes
2
answers
531
views
Any idea of solving an optimization problem with cubic constraints?
I have the following optimization problem with cubic constraints, which is hard to solve. Are there any ideas, or related references, of solving such a problem?
$$ \begin{array}{ll} \underset {y, z} {\...
- 21
0
votes
1
answer
103
views
Constrained linear optimization problem on $C^1$
I am dealing with a problem of the form ($a<b$)
$$
\displaystyle \max_{v \in C^1([a, b])} \int_a^b v(x)~\mathrm{d}x, \quad \mathrm{s.t.} \int^b_a \big(-o'(x)v(x)-v'(x)o(x)\big)f(x)~\mathrm{d}x \...
0
votes
1
answer
147
views
Is there a redundant constraint in linear programming? [closed]
From wikipedia:
But... Why do we need the $x\ge 0$ part? We can instead do $-x\le 0$, and thus saving a line in the definition (which is not a big deal but nevertheless nice).
(In order to do that, ...
- 3
0
votes
1
answer
143
views
$\mathrm{ILP}$-formulation for Minimum Maximal Matching (MMM) Problem
Despite some online searching I couldn't find examples of dedicated Integer Linear Programs ($\mathrm{ILP}$s) for determining smallest matchings, that are not contained in a larger one.
It seems that ...
- 13.2k
0
votes
1
answer
123
views
Explicit expression of Padé–Hermite approximant of type I
It is well known that the Padé approximants $(P,Q)$ of an analytic function in the neighborhood of $0$ can be expressed as a quotient of Hankel determinants built on the coefficients of the function $...
- 3,996
0
votes
1
answer
114
views
FEM based solution to parabolic problem
Consider the problem
$$
\begin{cases}
u_t - \Delta u = 0 &\text{ on } \Omega\times (0,T)\\u=0 &\text{ on } \partial \Omega\times (0,T) \\ u(x,0)=g(x) &\text{ on } \Omega
\end{cases}
$$
...
- 235
0
votes
1
answer
487
views
How to simulate Poisson point process
How to simulate a process $S_t=\sum_{0\leq s\leq t}\Delta_s,$ where $\Delta_s$ is a Poisson point process with values in $(0,\infty)$ and with characteristic measure $\Pi(dx)=\frac{\alpha}{\Gamma(1-\...
- 165
0
votes
1
answer
261
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 ...
- 2,442
0
votes
1
answer
220
views
Finding numerical solution for nonlinear Poisson-like equation using finite difference method
I am trying to use finite difference method to solve for $u(x,t)$ in the equation:
\begin{align}
\frac{\partial^2u}{\partial x^2} = \frac{au}{1+bu},
\end{align}
which is actually part of a system of ...
- 65
0
votes
1
answer
417
views
Gaussian quadrature, with no exact result over polynomial, but on inverse functions
Generally, a Gaussian quadrature of degree $n$ over an interval $I$ is defined so that it integrates exactly polynomials up to degree $2n - 1$. The main tool are the orthogonal polynomials.
When $I$ ...
- 97
0
votes
1
answer
230
views
Solution of complex linear system
In Brubeck, Nakatsukasa, and Trefethen - Vandermonde with Arnoldi (example 3) they solve the following linear system:
$$\operatorname{Re}\left(\begin{array}{ccc}1 & \cdots & z_{1}^{n} \\ 1 &...
- 45
0
votes
1
answer
275
views
Estimate for computing the $L^2$-norm of a function from its data
Let $f:\mathbb{T}^m \to \mathbb{R}$ is a function of bounded variation(BV). Let $D=\{\boldsymbol{p}_i,i=1,2,3\ldots\}$ be a countable dense subset of $(0,1)^m$. Let $E_n, n = 1,2,3\ldots$ be a ...
- 59
0
votes
1
answer
126
views
An otherwise linear matrix equation with the presence of a signum function : reference request
Consider the equation $$\pmb{c}+\text{sign}(G\pmb{c}) = L$$
$\pmb{c}$ is a $n\times1$ matrix.
$G$ is a $n\times n$ matrix which is also positive definite.
matrices $G$ and $c$ are real.
$L$ is a $n\...
- 698
0
votes
1
answer
488
views
Convergence of Chebyshev interpolation in L^1
Let $f\in C^0([-1,1])$ and $P_n(f)$ its interpolation polynomial at the Chebyshev nodes.
I would be interested to know about any existing results (positive or negative) about the convergence of $P_n(...
- 98
0
votes
1
answer
119
views
Convergence rate estimates of Monte-Carlo first-passage time estimates
Setup
Let $X_t$ be a $d$-dimensional diffusion process solving the Ito-stochastic differential equation
$$
X_t = x+ \int_0^t f(X_t,u_t)dt + \int_0^t \sigma dW_t,
$$
where $x \in \mathbb{R}^d$, $u_t$ ...
- 5,405
0
votes
1
answer
405
views
Computing discrete optimal transport
I am trying to find a combinatorial approach to solve the following optimization problem.
\begin{align}
&\max_{x_{ij}} C_{ij} x_{ij}, \\
&\text{such that},\\
&\sum_{j} x_{ij} \leq r_i~\...
- 133
0
votes
1
answer
99
views
Finding dual of a scheduling LP formulation
Suppose I have an LP formulation as such:
$\min\ \ \sum\limits_{i,j,t}\ w_{ij}x_{ijt} (\frac{t-r_j}{p_{ij}}+0.5)$
$\sum\limits_{i,t}\frac{x_{ijt}}{p_{ij}}=1\,\forall\ j$
$\sum\limits_{j}x_{ijt}\leq ...
- 103
0
votes
1
answer
138
views
What is the minimum number of stages $s$ required for a Runge-Kutta type numerical method of given order $p$?
These slides (slide 42) give a table (same as Table 1.6 given in Butcher's General Linear Methdos of the minimum number of stages $s$ for a Runge-Kutta type numerical method of order $p$ (the slides ...
0
votes
1
answer
61
views
Variant of the linear programming problem
Good afternoon, my experience in mathematical programming is low. I would like to know if there is any general method to address the following problem:
$$\text{Minimize }\sum_{i=1}^n d_i(x_j)$$
$$s.a....
- 193
0
votes
1
answer
568
views
Fast root finding algorithm for a special function
My question follows from
Fast root finding for strictly decreasing function
I am a bit surprised from the above page that there is even no efficient root finding algorithm (RFA) for a strictly ...
user128095
0
votes
1
answer
145
views
How to solve this optimization problem efficiently? [closed]
Let, $D\in\mathbb{C}^{1\times M}$ is a row vector with $M$ elements
$V\in\mathbb{C}^{3^M\times M}$ is a given matrix
$T$ is a scalar (real and $>1$)
$\textbf{The problem at hand is as follows:}$
...
- 111
0
votes
1
answer
212
views
Is an exact violated inequality constraint met as equal constraint in optimal solution?
We have a solution which does not satisfied exactly one inequality constraint in linear program. The corresponding dual solution is also feasible. Is it correct this constraint is in equal form in the ...
- 25
0
votes
1
answer
79
views
algorithms and tools available for a particular polytope computation
Let me define each half space i as:
$${H_i}:{c_i}{\bf{x}} \le {b_i}$$
The intersection of all such ${H_i}$ gives a polyhedron (bounded or not). Suppose I am interested in if ${H_i}$ is active (...
- 867
0
votes
1
answer
108
views
How to solve $y''+y'/x+f(x)y=0$ using B.C.s $y(0)=0$ and $y'(0)=1$ [closed]
The term $f(x)$ is available numerically. It was curve fitted to some function of $x$. I've used dsolve in Matlab. It reported that solution can't be found.
I tried solving the above equation using
...
0
votes
1
answer
201
views
Recursive linear programming on a linear subset of a simplex
The problem I am working on is:
Given an $n$ dimensional vector $r \in \mathcal{R}^n$, and a convex set $G=\{\mu \in \mathcal{R}^n | \mu_i \ge 0, ~ \mu^T \mathbf{1}=1, ~ A\mu =0 \}$ where $\mathbf{1}...
0
votes
1
answer
48
views
$C^\infty$ Periodic Pole-free Rational Interpolation
let $\quad-1=x_0 < x_1 <\ ...\ < x_n<1\quad$ be a set of abscissas
and $\quad(y_0, y_1,\ ...\,y_n)\quad$ a sequence of the corresponding ordinates.
Question:
what can be said ...
- 13.2k