The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

493 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
0answers
113 views

Is this algorithm for solving an inverse problem similar to any known algorithms?

The short version of my question is: I designed this algorithm for finding a solution for an inverse problem. Based on my research it is a new algorithm, does anyone know a similar algorithm? My ...
1
vote
0answers
194 views

Prove the steepest descent algorithm for solving $Ax = b$

Prove that the steepest descent algorithm for solving $Ax = b$, where $A$ is symmetric and positive definite, can be rewritten as follows: Compute the residual at the $k^{\text{th}}$ step: $r_k = b − ...
1
vote
0answers
56 views

Can this nonconvex optimization problem be tranformed into a convex problem?

I’m trying to solve the following optimization problem. Minimize M subject to $0=t_{1,1}\prec t_{1,2}=t_{2,1}\prec t_{1,3}\prec t_{2,2}=t_{3,1}\prec t_{3,2}\prec t_{2,3}\prec t_{3,3}=M$, $t_{j,k}=...
1
vote
1answer
164 views

Element-wise upper bound by rank-1 matrix

I would like to solve the following optimization problem for vectors $\mathbf{u} \in \mathbb{R}^m$ and $\mathbf{v} \in \mathbb{R}^n$, given a matrix $\mathbf{h} \in \mathbb{R}_{\geq 0}^{m \times n}$ ...
1
vote
0answers
464 views

Convergence of gradient descent method with non Lipschitz gradient

I would like to study the convergence of the gradient descent method applied to the function $$f(x)=|x-1|^3$$ In order to do that, I was thinking about using the following theorem: Assume that $...
1
vote
0answers
103 views

Numeric solution to summation with Hadamard product of vectors

I need to solve: $$\vec a_i\circ \vec b_i=\sum_{j}^n\alpha_{ij}\vec c_j\circ(\vec d_j-2\pi\tau_{ij})$$ For $\vec d_j$ and $\tau_{ij}$ when $\circ$ denotes the Hadamard product and $\vec a_i,\vec b_i,\...
1
vote
0answers
38 views

Optimisation problem: connectors

Suppose there are $n$ distinct points in the $\mathbb{R}^3$ space, namely $P_1,P_2,\ldots,P_n$. Define the distance matrix $M:=(d_{ij})_{n\times n}$, where $d_{ij}$ denotes the distance of line ...
1
vote
0answers
72 views

Finding zero of a matrix function via trust region subproblem

I have an issue with some steps carried out in a paper (https://arxiv.org/abs/1508.07497 sec 9.2.2) In order to perform a gradient descent step, we need to solve the following equation for the square ...
1
vote
0answers
102 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
335 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
477 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
75 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
91 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
338 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
52 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
689 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
999 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
198 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
46 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
152 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
96 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
45 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
178 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
497 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
54 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
182 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
208 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
236 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
107 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
213 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
55 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
106 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
97 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
100 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
453 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
172 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 ...