Questions tagged [numerical-optimization]
Numerical methods for continuous optimization.
1,429
questions
0
votes
0
answers
12
views
Solving for a distribution function in Python
I am trying to solve the following equation for $f(E)$
$g(E)=\int_{E}^{E+a}f(E')dE'$
where $a$ is a constant, and $g(E)$ is known numerically. I used Leibniz's integral rule to solve for:
$\frac{dg(E)}...
2
votes
0
answers
88
views
How to calculate the upper bound of the gradient of a multi layer ReLu neural network?
Question
Layers: We shall denote in the following the layer number by the upper script $\ell$. We have $\ell=0$ for the input layer, $\ell=1$ for the first hidden layer, and $\ell=L$ for the output ...
- 21
0
votes
0
answers
11
views
How can I ensure that points do need stick to the boundary of a level set in this gradient descent application?
Hopefully this question makes sense: I'm minimizing a nonnegative function of the form $$E(x)=\int_{[0,\:1)^d}|f_x(y)-g(y)|\:{\rm d}y$$ using the gradient descent method. Here, $x\in([0,1)^d)^k$, $f_x$...
- 13.4k
1
vote
0
answers
12
views
Choose $x$ such that $\int_{[0,\:1)^2}|\frac1{\sigma^2(x)}\exp\left(-\left(r\frac{\|x-y\|}{\sigma(x)}\right)^2\right)-p(y)|\:{\rm d}y$ is minimized
Let $p:[0,1)^2\to\mathbb R$ be a Lebesgue integrable function. Define $\sigma(x):=p(x)^{-\frac12}$, if $p(x)>0$, and $\sigma(x):=\infty$, if $p(x)=0$, for $x\in[0,1)^2$. Moreover, let $\varphi(y):=...
- 13.4k
0
votes
1
answer
23
views
Cost Optimization Given Constraints
Balance = 1,360 USD
Cost = (0.0001% * Purchase Qty * Purchase Qty) + (1% * Purchase Qty)
Problem: Find maximum Purchase Qty while keeping Cost below Balance.
Is there a closed form solution to this?
- 115
1
vote
1
answer
55
views
Lagrangian Duality problem
Suppose that $\lambda, N_0 \in \mathbb{R}$, $\boldsymbol{X}_{0} = (X_2',...,X_{m+1}')' \in \mathbb{R}^{m \times n} , X_1 \in \mathbb{R}^n$ is fixed, $\iota \in \mathbb{R}^n$ is the vector of ones, ...
- 367
0
votes
0
answers
19
views
Choosing quadratic programming algorithm
I have a quadratic program of the following form with $m$ inequality constraints.
$$ \min_{x \in \mathbb{R}^n} \| F x - y \|_2 \quad \text{subject to} \quad Ax \leq b $$
where $n$ is around $100$ to $...
- 55
0
votes
1
answer
38
views
Finding the minimum of Rosenbrock's function numerically
As the introduction for a computing assignment on the Nelder Mead method, I need to do the following:
Find the minimum of Rosenbrock's function numerically.
I'm using the standard variant with $a=1$,...
0
votes
0
answers
40
views
Show sufficient decrease condition is hold using KKT conditions
We let $p_k$ be solution to:
$${\rm argmin}_p m_k(p)$$
where $m_k(p)=f(x_k)+\nabla f(x_k)^T p+ \frac{1}{2}p^T B_k p$
And I have an expression for finding minimum $m_k$ for trust-region in the ...
- 645
-2
votes
0
answers
25
views
Optimizing a cost function where the feasible set is given by a distribution
I was wondering if the following optimization problem has somewhat been studied somewhere.
Suppose you have a closed set $\Omega \subset \mathbb{R}^n$ and a cost function $f$ (say a positive convex ...
- 5,166
0
votes
0
answers
25
views
For quadratic function: show that pair the KKT conditions
I have following quadratic function with non-linear equality constraint:
$$min_x f(x)=\frac{1}{2}x^TQx+x^Tg \ \ st. ||x||^2 \leq \Delta^2$$
where Q is positive definite. Then for $x^* \in\mathbb{R}^n$...
- 645
2
votes
1
answer
25
views
Bound on truncation error for theta method
Let $x(t)$ be the solution to a differential equation:
$$
x'(t) = f(t, x(t))
$$
where $f:[t_0, T] \to \mathbb{R}^n$ is a $C^1$ function.
We consider the problem of approximating $x$ using a partition $...
- 71
0
votes
0
answers
71
views
What numerical integration method can solve a integral over a function that depends on a differential equation without an analytic solution?
Suppose we have a differential equation of the form $\frac{dy}{dx}=f_{p_x,p_y}(y,x)$. After solving this differential equation for particular values of $p_x$ and $p_y$, we obtain $y_{p_x,p_y}(x)$. ...
0
votes
0
answers
23
views
How to solve this optimization problem? If there is no close-form solution, an approximate numerical results also helps.
I am stuck in an optimization problem. I only know Lagrange multipliers. However, it looks useless for such a complicated problem.
$l, k, f$ are variables. Based on some domain knowledge, the range of ...
- 1
0
votes
0
answers
22
views
Physical interpretation of gradient descent with momentum
This is the Stochastic Gradient Descent with Momentum (SGD-M) equivalent question of the Batch Gradient Descent masterly answered here.
In most of the literature where SGD-M is treated, the physical ...
- 11
0
votes
0
answers
35
views
Perturbed gradient descent to escape the saddle point
I encountered the following problem:
Given the function $f:\mathbb{R}^2\rightarrow\mathbb{R}$ given by $f(x,y) = y^2-x^2y$, I will omit the calculation of the gradient and Hessian but one can see the ...
- 226
2
votes
0
answers
68
views
Minimizing a function $f$ of the form $f(x)=\prod_if(x_i)$, is it possible to ensure $x_1,\ldots,x_j$ minimizes $\prod_i^jf(x_i)$?
Let $\varphi:\mathbb R\to\mathbb R$ with $$\varphi(x)\xrightarrow{|x|\to\infty}0,$$ $d\in\mathbb N$ and $$f_d(h):=\prod_{i=1}^d\sum_{k\in\mathbb Z}\varphi(h_i-k)\;\;\;\text{for }x\in\mathbb R^d.$$ ...
- 13.4k
0
votes
0
answers
31
views
Minimize the variance of a nonnegative linear least-squares problem
My question is related to the Question: Minimize Variance of a Linear Function
But with an additional contraint.
Given a Matrix $A \in \mathbb{R}_{n\times m}$ and vector $\vec{b} \in \mathbb{R}_{m}$ .
...
- 211
0
votes
0
answers
37
views
Can one use quadratic programming to solve linear programs?
The quadratic programming objective function look like this:
$$\text{J}_{\text{min}} = \frac{1}{2}x^TQx + c^Tx$$
And the linear programming objective function look like this:
$$\text{J}_{\text{min}} = ...
- 2,732
1
vote
1
answer
35
views
Minimum distance between a disk and a circle in 3D: pair of closest points?
Let a disk $D$ in $\mathbb{R}^3$ be given by a center $O_d$, a radius $R_d > 0$, and a unit normal vector $N_d$ to the plane $\{X \in \mathbb{R}^3 \mid N_d \cdot (X-O_d) = 0\}$ containing the disk. ...
- 6,003
1
vote
1
answer
80
views
How to minimize the distance between the point $(-1,0)$ and the curve $y^2 - x^3 = 0$?
Given the equation of a curve : $y^2 - x^3 = 0$, it is demanded to find the shortest distance from the point $(-1,0)$ to this curve.
Here is what I tried:
solve the curve formula for $y$:
y²=x³
...
- 41
0
votes
0
answers
35
views
Quadratic programming with positive semidefinite matrix
Let us consider the following optimization problem
$$
\min \,\,\, (1/2)x^{T}Px + q^{T}x
$$
$$
\text{subject to} \quad Ax \in C
$$
where $C$ is a closed convex set.
Assume now that $p$ is positive ...
- 73
2
votes
0
answers
36
views
Efficiently approximating multidimensional function
I have a function $f:\mathbf{x} \mapsto \mathbf{y}$ where $\mathbf{x} \in \mathbb{R}^n$ and $\mathbf{y} \in \mathbb{R}^m$.
I can evaluate this function numerically, but it is relatively expensive (a ...
- 121
1
vote
1
answer
56
views
Polynomial optimization, how to solve numerically?
For context this problem is derivative from this problem regarding polynomial position estimation.
I have a problem where I have two vectors , $\bf v$ and $\bf w$.
Let us assume that they are linked ...
- 25k
1
vote
0
answers
37
views
Attainment of the maximum in the induced norm definition
I am not looking for an answer, but rather a hint for the following question:
The induced norm $||A||_{a,b}\,$ is defined as
$||A||_{a,b} = \max\{||Ax||_b : ||x||_a ≤ 1\}$.
Prove that there exists an $...
- 31
1
vote
0
answers
31
views
Multiplier updates for partially augmented lagrangian?
TLDR: I can't figure out whether the standard multiplier update works for the partially augmented lagrangian case, and if not, whether there's an update that's more appropriate. Many thanks in ...
1
vote
1
answer
68
views
Why are Bezier curves numerically less stable for a larger number of control points?
I think the question is quite straightforward. Why are Bezier curves with more control points numerically more unstable. Can someone give me clear substantiated reason(s)? And with this the notion of ...
- 33
0
votes
2
answers
60
views
Optimization problem of angles for classical mechanics problem
I come from civil engineering background but the problem I came across is more mathematical, so I seek your help here.
Imagine there is force to be supported using truss structure. Given is the ...
2
votes
2
answers
71
views
What is the least number of payments to settle the score?
Suppose $n$ guys go on holiday. Suppose their names are the numbers $1,\dots, n$.
Suppose that, at the end of the vacation, the guy $i$ has paid an amount of $a_i \geq 0$ for the entire group, which ...
- 2,844
0
votes
0
answers
189
views
Minimum distance between a line and a circle in 3D: bracketing triplet?
Let $L(t) = B + tM$ be the parametrization of a line in $\mathbb{R}^3$. Let a circle in $\mathbb{R}^3$ be given by a center $C$, a radius $R > 0$, and a unit normal vector $N$ to the plane $\{X \in ...
- 6,003
2
votes
0
answers
95
views
Interval quasi-Newton methods?
I am looking to find all zeroes of a smooth function $ f \colon [0,1]^2 \to \mathbb{R}^2, $
using interval arithmetic.
The standard way to do this seems to be to use the interval Newton method
$$ x_{n+...
- 1,960
0
votes
0
answers
27
views
Search for a unitary transformation using multi-parameter optimization
Given a set of functions $\{\psi_1(x), \psi_2(x), \psi_3(x), \cdots, \psi_n(x)\}$ and a set of "ideal" functions $\{\psi^{\star}_1(x), \psi^{\star}_2(x), \psi^{\star}_3(x), \cdots, \psi^{\...
- 39
2
votes
1
answer
52
views
Optimizing a nonlinear function with both equality and inequality contraints
I have the non-linear optimization problem
$$\min f(a,b,c,x)=\int_0^R\frac{y}{1+(2ay+b)^2}dy =\frac{\log(\frac{(2aR+b)^2+1}{b^2+1})-2b(\arctan(2aR+b)-\arctan(b))}{8a^2}$$
subject to the constraints
$$\...
- 33
5
votes
1
answer
134
views
Convex optimization using constraint projection matrices
I have a convex optimization of the form
$$
\min_x \frac{1}{2} x^TAx-x^Tb \\
\text{s.t.}\ (I-P)x=0
$$
where $A$ is a $n$ by $n$ positive definite matrix, and $P$ is a $n$ by $n$ projection matrix (it ...
- 149
1
vote
1
answer
37
views
Should projected gradient descent be used for solving convex optimization problem instead of interior point method?
It is widely known that interior point method has been used for convex optimization problem.
However, the intermediary step of interior point method is usually consist of the Newton method. This may ...
0
votes
1
answer
43
views
Non linear curve fitting of a cosine with multiple unknown parameters
I have an equation that I am able to solve with scipy curve fitting when I have good first guess values, however I was hoping to simplify this equation so that my answers are more reliable. The ...
1
vote
0
answers
27
views
Unclear point: how do we know gradient at time step $t+1$ in conjugate gradient descent$\,$?
Below is the conjugate gradient descent algorithm. At time step $t$, how do we know gradient at time step $\;t+1\;,\;g(t+1)$, in the conjugate gradient descent ?
Reference: page 7-35, enter as ...
- 153
0
votes
0
answers
21
views
Simulation based optimization with constraints
Consider the following constrained nonlinear optimization problem:
\begin{align*}
&\min f(x), x \in \mathbb{R}^n\\
&c_i(x) = 0, i \in E \\
&c_i(x) \ge 0, i \in I \\
&E: \text{Indices ...
0
votes
0
answers
25
views
How to implement Newton iteration in Navier stokes equation
Suppose the nonlinear Navier stokes equation
$$
\left\{\begin{array}{l}
(\mathbf{u} \cdot \nabla) \mathbf{u}-\nabla \cdot \mathbb{T}(\mathbf{u}, p)=\mathbf{f} \quad \text { in } \Omega \\
\nabla \cdot ...
- 149
0
votes
0
answers
24
views
Algorithm for a minimization problem of a function that is not differentiable under a constraint
I'm trying to understand an algorithm for a minimization problem but it is unclear. Here is the function we consider
$\lVert Y - X\beta\rVert_{2}^{2} + \lambda\lVert\beta\rVert_{1}$ where $Y\in\mathbb{...
- 888
0
votes
0
answers
14
views
Derivation of backwords SOR iterative method using matrices in numerical analysis
Cheers, while studying numerical analysis, I came across the following statement: SOR can be written as:
$x^{(k+1)} = (I - \omega L)^{-1}[(1-\omega)I + \omega U] x^{(k)} + \omega(I-\omega L) ^{-1} c$ ...
0
votes
0
answers
9
views
Is there a reason why you would build a non-separable problem from a separable one? i.e. Rastrigin function
I'm reading on the Rastrigin function and I read that this function is additively decomposable, my understanding of this is that I could optimize this function by adding up its n independent 1-D ...
- 75
3
votes
0
answers
86
views
Are there any ODEs like these?
I have been working on using automatic differentiation to compute the sensitivities of systems of ordinary differential equations of the form
\begin{equation}
\frac{d\mathbf{u}(t)}{dt} = F(\mathbf{u}(...
- 95
1
vote
0
answers
30
views
Constrained optimization: When are the Lagrange multipliers bounded?
In some texts I have seen arguments for the fact that the Lagrange multipliers of a constrained optimization problem remain bounded. Are there general conditions for that fact?
In particular,
Let a ...
- 185
0
votes
1
answer
50
views
Questions about the Picard–Lindelöf theorem for the ODE $y(0) = y_0 (1)$ $y'(x) = αy(x)$
Hi i have questions about an exercise that we have done in class:
We consider the following ODE for a given $y_0 ∈ \mathbb{R}$ and $α ∈ \mathbb{R}$
$$
\left.\begin{gathered}
y(0) = y_0
\\
y'(x) = αy(...
- 693
0
votes
0
answers
30
views
numerical methods on data analysis
I have some data and I want to do two things with it:
find its derivative at each point
predict a little bit for the future
My data are not always going up or down, its going up and down for certain ...
- 11
0
votes
0
answers
8
views
How can one represent the constraint "monotonically increasing" in an approximation of a function using numerical optimization?
Background:
We seek $f(t)$, a function which has properties
$f'(\pi n) = 0$
$f$ monotonic on $[n\pi/2,(n+1)\pi/2]$
Approximates $\sin(t)$ so that $$\left(\int_{-\pi}^{\pi} |f(t)-\sin(t)|^k dt\right)^{...
- 25k
0
votes
0
answers
10
views
Correlation metric when response is piecewise
A series of measurement on $y$ is performed at different $x$ where noise is not negligible. How would I be able to tell the goodness of fit of the measurements to the model
$$y = \left\{ \begin{...
- 2,749
0
votes
0
answers
19
views
update numerical solution of an optimization problem
The problem might sound a bit vague. The general setup is an optimization problem in the following form
$$\min f(x) \ \ \text{ s.t. } x \in S,$$
where $f$ is our target function, the values $x$ could ...
- 77
2
votes
0
answers
52
views
How to exploit QR factorization implicitly
I meet a problem when I try to develop an iterative method for discrete inverse problem
$$Ax+e=b$$
where $A\in\mathbb{R}^{m\times n}$ and $e$ is a noise. I want to approximate the true solution $x_{...
- 47