Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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, $\ \...