Questions tagged [numerical-optimization]
Numerical methods for continuous optimization.
0
votes
0answers
10 views
Quadratic programming terms
Help me to understand the terms of this quadratic programming problem?
$Z$ and $U$, $x$ and $α$ are fixed. We have to minimize $w$. I would like to put it into terms of cvxopt to solve it.
1
vote
1answer
33 views
Approximate $f''(x)$ given $f(x),f(x+h),f(x+3h),f(x-5h)$
Given $f(x),f(x+h),f(x+3h),f(x-5h)$, approximate $f''(x)$.
Book's solution: From Taylor' series,
$$
\\ f(x+h)=f(x)+f'(x)h+0.5f''(x)h^2+{1\over6}f'''(x)h^3+O(h^4)
\\ f(x+3h)=f(x)+3f'(x)h+4.5f''(x)h^2+...
3
votes
1answer
74 views
Linear Least-Squares Problem with Inequality Constraints on Residual
I have an over-determined linear least-squares problem
$$\min_{\vec{x}}\Vert\mathbf{A}\vec{x}-\vec{b}\Vert_2^2,$$
where $\mathbf{A}\in\mathbb{R}^{n\times m}$, $\vec{x}\in\mathbb{R}^m$, $\vec{b}\in\...
0
votes
0answers
19 views
Manifold Optimization in Human understandable language
I am coming across a project that involves with "manifold optimization". I don't know what that is. After Googling for a bit, my understanding is that we use a low dimensional surface to approximate ...
0
votes
0answers
17 views
Computing the element-wise logarithm of a matrix exponential more efficiently?
Is there any known way to compute the element-wise logarithm of a matrix exponential more efficiently?
Motivation:
I am trying to an optimization problem (basically finding a specific Markov ...
0
votes
0answers
31 views
Question about the steepest descent method for minimization
Let $f : \mathbb R^n \to \mathbb R$ be defined by
$$f(x) = \frac{1}{2} x \cdot (Ax) - x^T v + \alpha$$
where $A$ is an $n \times n$ symmetric and positive definite matrix, $v \in \mathbb{R}^n$ and $...
0
votes
1answer
15 views
Operational cost of vector and matrix multiplications
Find the computational cost of a column vector $x$ multiplied by a row
vector $v$
I computed n multiplication operations and n - 1 addition operations, so would that make for $n(n-1)$ operations ...
0
votes
1answer
32 views
Inequality constraints and the max function
Let $g_i(x):\mathbb{R}^{n} \to \mathbb{R}$, for $i=1,\ldots,n$, be continuous convex functions. Define $g_{\rm max}$ as $g_{\rm max}(x) \triangleq \mbox{max}_{i=1,\ldots,n}\{g_i(x)\}$. Define also the ...
0
votes
1answer
29 views
$ \sum_{i = 1}^{m}\lambda_i v_i v_i^T$ for $v_1,v_2, \ldots,v_m \in \mathbb{R}^n$ linearly independent has rank $m$ $(\lambda_i \neq 0)$
I often see this formula used in the rank 1 or rank 2 cases for Quasi-Newton methods, but I am wondering how this can be proven in the general rank $m$ case. As a linear algebra problem, I would like ...
3
votes
0answers
30 views
Optimizing intervals in piecewise function
I am not sure what the relevant tags are (or how to best described the problem).
I have a piecewise function where for a particular interval element there is a known functional form (e.g. for ...
0
votes
1answer
28 views
How to solve a minimize problem with maximize a subproblem
I have a minimization problem
$$\min_{x, y} \{f(x, y) + \max_{y} g(y)\}$$
which has a max subproblem inside it.
How to solve it? Will alternating optimizing converge to the optimum?
0
votes
0answers
37 views
Are step sizes in quadratic programming solvers analytically exact?
In this paper (DOI link), Goldfarb and Idnani describe an algorithm for solving a certain subset of quadratic programs. This algorithm (or a very similar one) is implemented in the quadprogpp package ...
0
votes
1answer
16 views
What is a nontrivial minimizer?
I came across a statement that x is a nontrivial minimizer of some function, but couldn't find a definition of "nontrivial minimizer" on the Internet. Can anyone help point out some references for ...
3
votes
1answer
52 views
How can I check for the accuracy of numerical result to optimization problem?
How can I check for the accuracy of numerical result to optimization problem?
Or when is this possible?
Intuitively it could be possible at least to some extent, when one knows how to find analytic ...
0
votes
0answers
36 views
Reference request. Rigorous numerical optimization
I am looking for texts on Numerical optimization that are closer to Analysis definition-theorem-proof style texts.
EDIT: This is my first acquaintance with numerical optimization. My institution ...
2
votes
0answers
48 views
How to solve a large scale convex optimization problem?
Consider the following convex optimization problem in vectors $x$ and $y$
$$\begin{array}{ll} \text{minimize} & f(x,y)\\ \text{subject to} & g_1 (x)\le 0\\ & g_2 (y)\le 0\end{array}$$
...
0
votes
0answers
13 views
Do BFGS and L-BFGS methods converge when the matrix $H=B^{-1}$ is ill-conditioned?
I am using BFGS and L-BFGS to solve an unconstrained optimization problem. The objective function is the Mean Euclidean Error. The output is given by an Artificial Neural Network. The line search ...
0
votes
0answers
21 views
Minimum path distance from a source
Suppose I have a path-connected subset $I$ of $\mathbb{R}^n$ (not convex, but can be contained in a product of finite-measure closed intervals), and I define a "source point" $a \in \mathbb{R}^n$. ...
2
votes
0answers
33 views
Non-convex numerical optimization
I am looking for a way how to prove/show that one problem is easier to optimize(more robust to starting guesses) than another.
Suppose I have two non-convex functions from $L_1,L_2:\mathbb{R_+}^8\...
2
votes
0answers
15 views
Gradient of function with index operation
First of all, please let me know if anything is off with my notation. I am a computer scientist and as such I am not that strict about notation.
In my problem I want to optimize an objective function ...
1
vote
3answers
54 views
Slow convergence of gradient descent for a strictly convex quadratic
Let $0 < \lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n$ and let $f: \mathbb{R}^n \to \mathbb{R}$ define by
$$ f(x) = \frac{1}{2}x^TMx $$
where M is \begin{bmatrix}
\lambda_1 & 0 &...
1
vote
2answers
55 views
Linear approximation to xln(x)
Suppose we need to approximate $f(8.4)$ where $f(x) = \mathbb{xln(x)}$ by using a linear polynomial . We have the following points as nodes : $x_0=8.1 , x_1 = 8.3 , x_2 = 8.6 , x_3 = 8.7$ .
I ...
2
votes
0answers
12 views
How to show convergence of Frank-Wolfe algorithm ( or conditional gradient method)?
Let $g(w)$ be a differentiable convex function. Frank-Wolfe algorithm over a convex set $C \in \mathbb{R}^n$ is defined so as to find the local minimum of the function:
$$
s_{t+1}=\arg\min_{s \in C} ...
-1
votes
0answers
29 views
Using numerical method of integration !!
I have got raw accelerometer data along all three axis. And I want to calculate velocity from this raw accelerometer data. So velocity is basically integration of acceleration. But since it's discrete ...
1
vote
2answers
52 views
Is modified Newton's Raphson method redundant?
I have been recently taught Newton's method for finding roots of non-linear equations. I was told in class that if the multiplicity of the root is more than 1, then the order of convergence is not ...
3
votes
1answer
58 views
Solve $\min_{x} \frac{1}{N}\sum_{i=1}^{N} f_i(x_i) + g(x)$ $\ {\rm s.t.} Ax = b$; $x = [x_1,\ldots,x_N]^T$ and $A \in \mathbb{R}^{M \times N}$.
An optimization problem:
\begin{equation*}
\begin{aligned}
& \underset{ x \in \mathbb{R}^N }{\text{minimize}}
& & \frac{1}{N} \sum_{i=1}^{N} f_i\left(x_i\right) + g(x) \\
& \text{...
1
vote
0answers
40 views
Nonlinear optimization with parametric constraint
Is there any way of reformulating the following problem so that it can be solved by means of e.g. Matlab's fmincon?
$\min f(x_1,\dots,x_n)$ subject to $c(x_1,\dots,...
0
votes
0answers
16 views
Transform the problem to EQ constrained problem with simple bounds
\begin{align}
min && x_1^2 + x_2^2\\
s.t. && (x_1 -3)^2+1 \leq x_2\\
&&x_1-2x_2+2=0\\
&&x_2 \geq0.5
\end{align}
SOLUTION.
\begin{align}
min && x_1^2 + x_2^2\\
...
0
votes
0answers
35 views
Motive of Conjugate Gradient method.
It is known that the solution to the linear system $Ax=b$ where $A$ is symmetric and positive definite is the minimizer of the quadratic function
$f(x)= \frac{1}{2} x^T A x - x^T b$
We can solve it ...
0
votes
0answers
16 views
Concerning the idea of Trust Region methods
As far as I understood is that the idea of TR methods is that at the current iterate $x_k$ we build a model "usually quadratic", of the objective function $f$ to be optimized, $m_k(s)$ of $f(x_k +s)$ ...
0
votes
0answers
22 views
In-exact line search
In my class notes, the author says:
"If $f:\mathbb{R}^n \to \mathbb{R}$ is bounded below and $p_k$ is a descent direction and the $\alpha-\beta$ also known as Armijo-Goldstein condition is met then ...
0
votes
0answers
28 views
Advantages and disadvantages of the Golden-section search method
As I understand that the golden-section search is a zero-order line search method so it is a global method so in comparison with Newton's and the secant's method this is an advantage. But it has a ...
1
vote
1answer
33 views
How to write Frank-Wolfe algorithm in two steps optimization problems?
Let $g(w)$ be a differentiable convex function. Frank-Wolfe algorithm over a convex set $C \in \mathbb{R}^n$ is defined so as to find the local minimum of the function:
$$
s_{t+1}=\arg\min_{s \in C} ...
0
votes
0answers
28 views
How to take derivative of log loss function in gradient descent?
I know the gradient descent about $z=wx+b$. But how to implement the derivative values of $w$ and $b$ in Python? I see some example like
...
0
votes
0answers
25 views
Soft Question: Optimization
Let $N$ be the number of locations for hotspots. Each has its cost and achievable rate. I want to find the optimal combinations of $n \leq N$ locations such the cost is minimized. How can I do so ...
0
votes
0answers
16 views
On the idea of the penalty methods of constrained minimization
I'm studying constrained optimization. For instance, consider the EQ constrained optimization problem of the form
\begin{align}
min_{x \in X} && f(x)\\
s.t && h_i(x)=0 && i=...
1
vote
0answers
20 views
Projected Conjugate Gradient or BFGS for bound constrained optimization
We know how projected gradient descent works for bound constrained optimization (https://neos-guide.org/content/gradient-projection-methods). It is basically steepest descent with an additional ...
0
votes
0answers
24 views
SOCP constraint vs Quadratic constraint - trust region methods
I'm implementing code for performing sequential convex optimization based on trust regions, but I have some doubts because I haven't found a unique approach.
Suppose we want to minimize a convex ...
2
votes
1answer
43 views
Is compressive sensing a type of interpolation? [closed]
In what ways is compressive sensing different from traditional numerical interpolation of sampled points from a given signal?
0
votes
0answers
36 views
Search for projection on a special matrix space with regard to Frobenius norm(computer vision background)
Background
Define essential space as
$$\varepsilon=\{E \in \mathbb R^{3\times3}|E=\hat{T}R\}$$
$$\hat{T}\in\{S\in \mathbb R^{3\times3}|S^T=-S\}$$
$$R\in\{A\in\mathbb R^{3\times3}|A^TA=I,\det(A)=1\}$$...
1
vote
0answers
20 views
The constrained optimization problem
I would like to find the minimum value $F(x)=x^{T}Ax$ and $\|x\|_{2}=1$, where $A$ is symmetric and positive-definite. I know
that the minimum value is the smallest eigenvalue problem of the
matrix $...
0
votes
1answer
38 views
Linearly constrained quadratic program
I have the following quadratic program
$$\min_x x^TAx \qquad \text{s.t} \quad Ax \in [a,b]^m$$
where matrix $A$ is positive semidefinite, and is similar both the objective function and in the ...
1
vote
0answers
77 views
Solving 2nd order ODE with variable coefficients
ODE:
$$X''(t)+A(t)X'(t)+B(t)X(t)=F(t),$$
IC's: $$X(0)=U_1, $$
$$X'(0)=U_2$$
where
$X(t)=[X_1 X_2...X_n]^T$ and $U_1, U_2,F(t)$ are $n\times1$ matrices,
$A(t), B(t)$ are $n\times n$ matrices.
...
0
votes
1answer
32 views
Does ADMM work for nonconvex optimization problems?
I need to solve the following nonconvex optimization problem:
\begin{equation}
\begin{split}
\min_{x,y}\quad &f(x)+g(y)\\
\mathrm{s.t.}\quad &Ax+By=b
\end{split}
\end{equation}
where $f$ is ...
1
vote
1answer
40 views
Numerical solution of non-linear first order partial differential equation (HJB)
I am trying to solve a simple optimal control problem using the Hamilton-Jacobi-Bellman equation, numerically in Python. This is proving to be rather difficult as I end up having to solve the ...
1
vote
1answer
49 views
Find the maximum value without computing matrix
I have a optimization problem, which is to find a certain $h^*$ that:$$h^* = argmax(h'\alpha-\frac{\kappa}{2}h'\Sigma h)$$
where $\alpha$ is a $(n \times 1)$ vector and $\Sigma$ is a $(n\times n)$ ...
0
votes
1answer
22 views
Optimization problem: Computing the gradient [closed]
I need help with the following exercise:
Solve $\min_{x\in\mathbb{R}^d} f(x)$, where $f:\mathbb{R}^d\to\mathbb{R}$. We define the inner product $(v,w)_A:= v^TAw$, induced by a positive definite and ...
0
votes
0answers
14 views
Tychonoff Regularization by calling an Optimization Routine
Question : Set $ X = [−1,1]$ let $u_c(x)=sin(\pi x) $ be a clean signal. Add noise $n(x)$ which is mean zero with variance $σ^2=0.1^2$ and let $u_n=u+n$. Let, $ 0 = x_1,......,x_n = 1$ be an equally ...
1
vote
0answers
13 views
An alternate for Householder QR linear equation solving for fixed-layout sparse matrix
This concerns sparse matrices where the sparsity pattern is known beforehand, and where the size is between 5 and up to 50, as the linear solver for a Newton Raphson non linear solver.
For smaller ...
0
votes
0answers
25 views
Roots of a real exponential sum
Suppose I had some exponential sum $\ f(x)\ $ of the form:
$$f(x) = \sum_{i=1}^{N} \left( c_i \ e^{a_i x} \right)$$
where:
$$c_i, a_i \in R$$
$$a_i \leq 0$$
Is there a quick way to find the roots, $\ \...
