Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

475 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
0answers
97 views

Closed form solution to the Digamma recurrence relation?

The difference between two digamma function can be written using the following recurrence relation: $\psi(n+z) - \psi(z) = \sum_{i=0}^{n} \frac{1}{i + z}$ My question is, is there a closed form ...
1
vote
0answers
37 views

Expectation of Value Function

I am not sure whether this is the right place to ask this. I have solved a standard Bellman equation problem. The Value Function $V$ depends on 3 state variables: $K_t$, $X_t$, $Z_t$. The variables ...
1
vote
1answer
319 views

Why does Frobenius norm make BFGS scale-invariant?

On slide 11 here it is claimed that the weighted Frobenius norm leads to a scale-invariant optimization method. Similar claims about this norm can be found throughout the literature see 1,2,3. In ...
1
vote
0answers
467 views

Steepest descent method - proof in Nocedal and Wright

In Numerical Optimization by Nocedal and Wright, Chapter 2 on Unconstrained Optimization, (http://home.agh.edu.pl/~pba/pdfdoc/Numerical_Optimization.pdf) beginning on page 20, they verify that the ...
1
vote
0answers
73 views

Effect of Scale of Data and Objective Function in the Convergence of Gradient Descent

One way to tune step size in gradient descent is via backtracking line search. backtracking line search (with parameters α ∈ (0, 1/2), β ∈ (0, 1)) starting at $t = 1$, repeat $t := \beta t$ ...
1
vote
0answers
28 views

Numerical Method for fitting parameters of an explicit integration to actual data

I have a heat transfer system described by, $$\{\dot{T}\} = [C^{-1}]\left([K]\{T\} + \{F\} \right)$$ where ${T}$ is a vector of the nodal temperatures of the system. From initial conditions I am able ...
1
vote
1answer
84 views

Can someone help me understand using the Jacobian matrix with Newton's Method for finding zeros?

I'm struggling to understand approximating solutions to non linear equations using a Jacobian matrix. I understand intermediate steps, but I'm unsure how everything comes together. I want to use ...
1
vote
0answers
335 views

Computational complexity of conjugate gradient method for a positive semidefinite Hermitian matrix

Let us assume that we want to solve the linear system: $$\mathbf{A}\mathbf{x} = \mathbf{b}$$ with the conjugate gradient method. $\mathbf{A}$ is a positive semi-definite Hermitian matrix. The ...
1
vote
1answer
51 views

Calculating block diagonalization / canonical bases with linear optimization?

Edit Even though I have started answering my own question I am still eager to hear any feedback and new ideas. So feel free to tell me if you come to think of anything. In Linear Algebra there are ...
1
vote
0answers
61 views

Find the “optimal” placement of $n$ points in a polygon

I was hoping someone could help me with a question I've been pondering the past few days. I searched the usual places (google, journals, texts, etc) but couldn't find anything that fit the bill, but ...
1
vote
0answers
51 views

Numerical stability of computational results

Let z be a function of a finite number of variables i.e. z=f(a,b,c,...). If we have the mathematical formula connecting z and the variables, we can determine how the value of z varies with a change ...
1
vote
0answers
681 views

How does one rigorously prove that gradient descent indeed decreases the function in question locally i.e. show $f(x^{(t+1)}) \leq f(x^{(t)})$?

How does one prove that gradient descent indeed decreases the function in question locally? In other words if we take a step in the negative of the gradient as in: $$ x^{(t+1)} = x^{(t)} - \eta \...
1
vote
0answers
42 views

Minimize/Maximze a function against its approximation.

Let $f \in C^{\infty}[1,2]$ be a function we would like to approximate, let be $g$ such approximation, you can assume $g$ is a spline function (at least quadratic). In literature I have seen that a ...
1
vote
0answers
957 views

Exact line Search in Steepest descent

I wanted to clarify the idea of the exact line search in steepest descent method. An exact line search involves starting with a relatively large step size ($\alpha$) for movement along the search ...
1
vote
0answers
183 views

Scaled gradient descent

Consider the unconstrained minimization \begin{align*} \min_{x\in\mathbb{R}^n}f(x) \end{align*} One iterative approach to obtaining a solution is to use the gradient descent algorithm. This algorithm ...
1
vote
0answers
25 views

Minimizing a non-linear function

I am trying to minimize the following equation $$ C(\rho) = \| I-\sqrt\rho \nabla. \frac{1}{\rho} \nabla \sqrt\rho\|$$ where $I(x,y)$ and $\rho(x,y)$ are functions of x and y. I found solution for ...
1
vote
0answers
44 views

Find global minima of nonlinear, scalar, positive function numerically?

Let us consider a real, smooth vector function $g(x): \mathbb{R}^n\rightarrow \mathbb{R}$ which is globally increasing, e.g. $\exists r > 0$ for which $g(x)$ with $||x|| > r$ is monotonically ...
1
vote
0answers
148 views

Efficiency of quasiconvex optimization

Summary: Could we minimize quasiconvex objectives in polynomial time? Whenever an objective function of an optimization problem can be formed as a convex function, this is considered as victory. ...
1
vote
0answers
91 views

Relation between error of estimate and rate of convergence

How is an exact bound on estimated error of an iterative algorithm related to rate of convergence? Referring to references is appreciated. Edit: Now I am not talking about any bound. I am only ...
1
vote
0answers
42 views

Quantization threshold selection

I have the $256$-bin histogram representing a distribution of the values taken by a certain descriptor element. This descriptor element takes the values in $0-255$ range, hence $256$ bins. I want to ...
1
vote
0answers
161 views

Find max min with linear programming

I need to solve $$ \max_x \min_y x^T M y $$ subject to $$ \sum_{i=1}^n y_i = 1, \sum_{j=1}^m x_j = 1,\\ x \geq 0, y \geq 0 $$ where $ M \in \mathbb{R}^{m\times n} $, $ x \in \mathbb{...
1
vote
1answer
486 views

How to solve a system of nonlinear Hamilton-Jacobi PDE's numerically in MATLAB/Maple/other?

I've been trying recently to solve the following system of Hamilton-Jacobi PDE's, which are of the hyperbolic, first-order type: $ V_1,_t - 0.5 V_1,_x^2 + V_1,_x(0.1x^2+0.03x+.0.01)+0.02(x-0.5)^2-V_1,...
1
vote
0answers
52 views

Choosing a non-convex global optimization algorithm based on the number of permitted steps

Can anyone comment on the most suitable approach for the following optimization problem: We are given finite bounds for a set of $n$ real-valued parameters of an unknown deterministic function. The ...
1
vote
0answers
52 views

Computational methods to minimizing the norm of a matrix monomial.

Linear optimization solves the problem $$\min_{\bf x}\{\|{\bf Ax - b}\|_2^2\}$$ Edit: Some clarification Doing the derivation of the optimum, first expand the norm: $$\|{\bf Ax - b}\|_2^2 = ({\bf Ax-...
1
vote
1answer
90 views

Maximization of a nasty Gaussian likelihood

I have a Gaussian likelihood function, $$p(y|x) = \mathcal{N}(y; Ax, (x^\top V x + \lambda) \otimes I)$$ where $A,V,\lambda$ is known, and $\otimes$ is the Kronecker product. (the notation indicates ...
1
vote
0answers
119 views

Nonsmooth Gauss-Seidel minimization (coordinate descent)

I have attempted to implement the coordinate descent algorithm for a separably convex problem of the form $$\min \sum f_i(x_i) \\ \text{s.t.} \ Ax = b $$ using the augmented Lagrangian $$L(x,\lambda)...
1
vote
0answers
40 views

Numerical method for wave equation with nonlinear forcing in 1+1 D

I am looking for numerical method to solve the equation $$ \square \phi = \frac{\partial^2 \phi}{\partial x^2} - \frac{\partial^2 \phi}{\partial t^2} = \lambda \phi^3 \, $$ for real $\phi = \phi(x,t)$...
1
vote
1answer
173 views

Gradient descent with linear perturbation

Given a convex, differentiable function $f$ (from a Hilbert space to $\mathbb{R}$) with a minimum (say $x^*$), I know you can find $x^*$ using gradient descent. Suppose now that you apply gradient ...
1
vote
0answers
205 views

Convergence results for block coordinate descent methods

I am trying to solve the problem minimize $f(x)$ subject to $x_1 \in C_1, x_2\in C_2, ... x_m\in C_m$ where $x_1, ..., x_m$ are block subvectors of $x$, and $C_i$ are each closed convex sets (not ...
1
vote
0answers
229 views

Integrating over particular grids to obtain Spherical Harmonic coefficients

Theoretically the spherical harmonic expansion coefficients of a function $f$ should be calculated via a continuous integration: $$F_{lm} = \int_{0}^{2\pi}\int_{0}^{\pi} f(\theta,\phi)Y_{lm}^*(\theta,\...
1
vote
1answer
38 views

In an ODE dynamic system, is there a convient way or algorithms for estimating the parameters which make the ODE solution satisfing some constraint?

I have construct a ODE dynamic system like this $$molA(t)==sa$$ $$molB'(t)=sb-db\;molB(t)+\frac{kab\;molA(t)\;molB(t)}{molB(t)+Jab}-\frac{kgb\;molG(t)\;molB(t)}{molB(t)+Jgb} $$ $ molC'(t)=sc-dc\ ...
1
vote
0answers
99 views

Do quasi-Newton methods check the second-order optimality condition?

I have a practical question about quasi-Newton methods. In quasi-Newton methods, Hessian matrix is approximated. It seems to be impossible for them to check the second optimality condition. In ...
1
vote
0answers
211 views

Global and local maxima in a weighted sum of logarithms of linear functionals?

Is is possible to describe, and locate efficiently, the maxima of the function below in the parameters $\mathbf{x}$ $$\sum_{i} p_i \log( N + \sum_j x_j[B_j +(A_j-B_j)\delta_{ij} + min(A_j,B_j) ]) \...
1
vote
0answers
70 views

Powell vs Levmar

I'm learning about the application of numerical optimization, and noticed that in one of the programs that I'm using it uses Powell's method to get parameters of a piece-wise function, and Levmar if ...
1
vote
0answers
54 views

Levenberg-Marquardt - What is preferable (A + mu.I) or (A + mu.diag[A])?

The step size is computed by solving (A + mu I) h = -g I could find in some literature that one can compute the step size by solving (A + mu A') h = -g where, A' = diagonal(A) It is said that ...
1
vote
0answers
103 views

Numerical optimization in function space

I'm new to calculus of variations. I'm curious about how to apply simple numerical optimization techniques in function space. Consider the classical problem: finding the shortest path between two ...
1
vote
0answers
58 views

Efficient method for refining parameters in nonlinear curve fitting

I have time-series electrical current data $i(t)$ with transient steps in it which are convoluted with the hardware filter used in data acquisition. As a result, the real steps in current, which would ...
1
vote
0answers
96 views

integration rule for singular function

It is well known that for sufficiently smooth function $f(t)$, error bounds for midpoint are $$ \int_{t_i}^{t_{i+1}} f(s)ds=hf(t_{i+1/2})+\frac{h^3}{24}\frac{d^2 f(s)}{ds^2}|_{s=t_i} +O(h^5). $$ where ...
1
vote
0answers
98 views

saddle point versus local extermum

Suppose a function $f$ from $\mathbb{R}^n \to \mathbb{R}$, is differentiable. We know that $c$ is a critical point of $f$, i.e. $\nabla f(c) = 0$. Our goal is to find out if $c$ is a local extremum, ...
1
vote
0answers
284 views

Solution of equations involving determinant and matrix inverse

$x$ and $y$ are two scalar unknowns. The two equations are $$|\mathbf{I}+x\mathbf{h}_1\mathbf{h}'_1+y\mathbf{h}_2\mathbf{h}'_2|=R$$ and $$\mathbf{h}'_1\left(\mathbf{I}+x\mathbf{h}_1\mathbf{h}'_1+...
1
vote
1answer
435 views

Gradient descent for periodic function

Problem: minimize E=$\sum_{t=0}^T [ Y(t)-\sum_{k=0}^K(X(t+k)*cos(k*F+PHI)) ]^2$ where F, PHI - has to be optimized; Y(t), X(t) 1D arrays are given; t=0...T; T=1000; k=0..K; K=10; I can use FFT ...
1
vote
0answers
167 views

Equivalent optimization problems?

I am wondering if the set of optimizers of the problem $$ \min_{x \in X} \ f(x) \quad \text{subject to: } g(x) \leq 0, \ h(x) = 1 $$ is the same of the one of $$ \min_{x \in X} \ f(x) + h(x) \quad ...
1
vote
0answers
290 views

Optimal numerial method for optimization of “Rosenbrock Banana”-like function

Which numerical methods would be optimal to find an extremum of a function with an almost flat "valley" (but a single minimum in the middle of the valley)? In this context optimal means the least ...
1
vote
1answer
179 views

Optimization problem with a minimization sub-problem as a constraint

I have a problem, for predefined $x_0,z\in\mathbb{R}$, which looks like $$\min_{\alpha,x} \sum_{i=1}^n \alpha_i f_i(x_i,z) $$ subject to \begin{align} \sum_{i=1}^n \alpha_i &= 1 \\ \sum_{i=1}^n \...
1
vote
0answers
143 views

Simultaneous iteration of Symmetric Matrices

Given a Matrix $A$ we can use Simultaneous iteration(Using power iteration on all columns simultaneously) to compute the d biggest eigenvalues. Now this method will give you the biggest eigenvalues, ...
1
vote
1answer
276 views

Linear Programming, Optimal Solutions

I posted the whole question to give some context, but my problem lies with (iv). I think you're meant to use a formula for the generalization of the optimal solution, but I'm not really sure what this ...
1
vote
0answers
242 views

using lsqcurvefit to fit piece-wise linear

I would like to use this function to fit piece-wise linearly to a set of data. Namely, I want to fit them with several linear segments. Including other requirements, I would not want the segments ...
1
vote
1answer
51 views

How to know all errors in Optimization process?

I am using fminsearch in MATLAB to iteratively find the answer of a function. But it seems like the fminsearch cannot fulfill my expectation. So I ask this question whether there is any way to do what ...
1
vote
0answers
70 views

Effect of approximating a non-differentiable function on optimisation of minimisation

I am looking at a problem of constrained minimization, where the function to be minimized contains the Heaviside function, and as such is not twice continuously differentiable. My question is what ...
1
vote
0answers
160 views

bad convergence of steepest descent

Under which circumstances does the steepest descent method converge badly? I know if the search direction is approximately perpendicular to the descent direction the steepest descent method converges ...