2
votes
0answers
14 views

Horn–Schunck method. Explanation of iterative solution

I am reading this paper (explanation of Horn-Shunck method for finding optical flow) and trying to understand it. My stumbling block is obtainig solution of system of linear equations I(x, y, t) ...
0
votes
1answer
29 views

Reference for gradient descent with unit norm constraint

I faced a non-convex optimization problem with unit norm constraint. I can solve the problem using the gradient descent method and the projection of the gradient onto the tangent plane as in @joriki ...
0
votes
0answers
39 views

Global optimization

Assume that I want to find the global minimum of a non-linear, non-convex, multidimensional function subject to several restrictions. Could you recommend me any deterministic strategy which can ...
0
votes
1answer
17 views

Quadratic Optimization Problem with Box Constraints

I want to solve a problem of form $$\min_x x'Ax + b'x \;\;\mbox{ s.t. } l\leq x \leq u$$ where $A$ is a positive semidefinite matrix, thus the function I'm optimizing should be convex. However the ...
0
votes
0answers
25 views

How to characterise this non-linear optimisation (linear objective function, non-linear constraints)

I was wondering if someone may be able to help me characterise this optimisation problem as I am struggling to find a numerical library that will solve it and I suspect it is because I am using the ...
0
votes
0answers
39 views

Finding minimum of a distance function using matlab

I have a function for that I want to find the minimum. The function calculates the distance between two sets where a set is defined as matix of row vectors $ D = [ d_1, d_2, ..., d_n]$, $d_n$ is a $m ...
0
votes
1answer
31 views

Why does the interpolation error go to zero if we increase the number of sampling points?

This question is motivated by polynomial interpolation. We know that for $f\in C^{n+1}[a,b]$ and $a=x_0<\dots<x_n=b$ holds $$\| f - p_n \|_\infty \leq \frac{1}{(n+1)!} \| f^{(n+1)} \|_\infty ...
1
vote
1answer
16 views

Numerically optimising a sequence of matrix multiplications

I am trying to set up an optimisation problem and solving it numerically. I am still formalizing it and unsure what is the best way to solve it. It seems like a common problem, and im sure people have ...
0
votes
1answer
47 views

A Simple Algorithm for Imposing Semi-definite Constraints

What is the simplest algorithm to implement, to impose semi-definite constraints? $\min_{X\succeq 0} f(X) $, where $X$ is an $n \times n$ symmetric matrix, and $f$ is a general smooth convex ...
1
vote
2answers
50 views

steepest descent with quadratic form converge in 1 iteration

Well I'm stuck on an exercise given: The steepest descent method is applied to the quadratic form $$Q(\mathbf{x}) = \tfrac{1}{2}\mathbf{x}^TA\mathbf{x} - \mathbf{b}^T\mathbf{x} + c$$ where $A$, ...
3
votes
0answers
38 views

Find closest vector to a given vector from a particular set of vector

Let $x=\left(x_t\right)_{t=1}^n$ be a vector such that $$ x_t = \prod_{i=1}^t u_i, \tag{1} $$ where each parameters $u_i$ can take any of two value $$ u_i \in \left\{a,b \right\} = \left\{ 1.3, 0.8 ...
0
votes
1answer
73 views

Minimax approximation of $\sqrt{x^2+1}$ on $[0,1]$

How do I find the linear minimax approximation of $\sqrt{x^2+1}$ on $[0,1]$? Should I choose points to check signs, which?
2
votes
1answer
58 views

Minimizing $\int_0^1\left\lvert -x + e^\varphi\right\rvert d\varphi$

Which value of $x$ minimizes the following integral? $$\int_0^1\left\lvert -x + e^\varphi\right\rvert d\varphi$$ Using computational mathematics software I've seen the value of $x$ should be in ...
1
vote
2answers
45 views

Minimizing a convex cost function

I'm reviewing basic techniques in optimization and I'm stuck on the following. We aim to minimize the cost function $$f(x_1,x_2) = \frac{1}{2n} \sum_{k=1}^n \left(\cos\left(\frac{\pi k}{n}\right) x_1 ...
0
votes
1answer
53 views

Can SVD help to solve (inequality) constrained least squares problem?

Consider the following minimization problem: $$ ||Q u - h^{o} ||^{2} \to min \;\;\; s.t. \; u \geq 0 $$ where $Q$ is $m \times n$ matrix and $u$ is $n$-dimensional vector and $h^{0}$ is ...
1
vote
1answer
42 views

How do you call the following iterative solving method

I have the following implicit equation $$ x= f(x) $$ which I solve by starting with some value for $x$, then setting $x$ to the new value $f(x)$ and so forth until convergence. How is that method ...
0
votes
0answers
24 views

Sparse coding with local sparseness of dictionary

The title is probably pretty unclear, I hope I am able to explain it better here. I am currently working on a problem in the field of sparse coding, that is Principal Component Analysis, Non-negative ...
0
votes
0answers
30 views

Linear least squares with sparse inequality constraints for support function estimation

The initial problem is the following: $$ ||h - h^{0}|| \to min \; \; s.t. Qh \leq 0 $$ where $h^{0} \in \mathbb{R}^{n}$ is known vector and $Q$ is a $m \times n$ matrix. The problem arises in specific ...
0
votes
0answers
40 views

Best optimizer in Matlab for this problem?

I need to do yield curve extraction for fixed income. I have 10 fixed income instruments for which I have values. The method is called Nelson-Siegel Method: ...
0
votes
2answers
139 views

Quadratic Function must be positive definite to have a unique minimum

I have attempted the following question multiple times and I am very confused about the proof please help me solve it. Let $V(x)=a+b^{T}x+\frac{1}{2}x^{T}Cx$ for some $a \in \mathbb{R}, b \in ...
0
votes
0answers
42 views

Approximation of largest eigenvalue

What is an approximation for the largest eigenvalue of a matrix $A $? I mean, I am looking for some expressions that can be used as approximation for largest eigenvalue
4
votes
1answer
100 views

Conjugate Gradient Method and Sparse Systems

What is it about conjugate gradient that makes it useful for attacking sparse linear systems. Why would steepest descent be significantly worse? Please keep in mind that I am still trying to fully ...
1
vote
0answers
30 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 ...
0
votes
0answers
34 views

constrained minimization in N dimensions

I am looking to create an algorithm to minimize an N dimensional problem. I am unsure how to write it in its generic form, so I will show it in 1, 2 and 3 dimensions Minimize $ \sum_{i} x_i\left [ ...
0
votes
0answers
60 views

What numerical methods could I use for this argmin problem?

I wish to solve the following using Numerical Methods: $$ \bar{m} = \underset{m \geq 0}{\text{argmin}} \left( \int_a^b \left( \frac{1}{\left(\sum_{i=1}^M \left(c_i^\alpha \cdot n^2 y^{-m-1} \cdot ...
0
votes
1answer
35 views

Compute $p \in P_2$ that minimizes $||x^{3}-p||$ in the '2'-norm

So far I've got an orthogonal base with: $\psi_0 = 1$, $\psi_1 = x$ $\psi_2 = x^{2}-\frac{2}{6}$ Am I supposed to calculate $p$ as: $\alpha_0\psi_0+\alpha_1\psi_1+\alpha_2\psi_2$ with: $\alpha_i ...
14
votes
1answer
252 views

Fastest curve from $p_0$ to $p_1$

I'm trying to solve a problem in path planning: Given points $p_0$ and $p_1$ and vectors $v_0$ and $v_1$, find a function $p(t)$ st. $p(0) = p_0$, $p(T) = p_1$, $p'(0) = v_0$ and $p'(T) = ...
0
votes
1answer
63 views

motivation for BFGS Hessian update rule

The BFGS method approximates Newton's method by replacing the Hessian of a function $f$ with an approximate Hessian $B_k$. At each iteration, the Hessian is improved using the formula in equation five ...
1
vote
1answer
149 views

Ideas on matrix factorizations and/or transformations for $\ell_1$ minimization

I am starting with a typical $\ell_1$ basis pursuit problem: $$ \min_{\mathbf{x}} \Vert \mathbf{x} \Vert_1 \quad \mathrm{s.t.} \quad \Vert \mathbf{ERx} - \mathbf{y} \Vert_2 \leq \epsilon, $$ where ...
0
votes
2answers
54 views

Numerical Methods

Assuming I am given a Program which can calculate the value of a continuous, infinitely differntiable (we cannot calculate these derivatives), real, positive function of two real variables which has ...
1
vote
0answers
97 views

Algorithm of projection

Suppose $S$ is a compact surface in $\mathbb{R}^{3}$ defined by a sufficiently smooth level set function $f$, that is, $S=\{s: f(s)=0\}.$ I am studying an algorithm that projects a point $x_{0}$on ...
0
votes
1answer
157 views

optimization of a non-differentiable, component-wise step function

I would like to estimate the (local) minimum of a function $c:R^N \mapsto R^+$ where: $c$ is only differentiable almost everywhere, there exists a component $j$, such that $\frac{\partial ...
1
vote
1answer
97 views

Looking for a window containing the solution of an equation

I need to solve billions of times equations $\,f(x)=0\,$ with $$f(x) := \sum_{i=1}^N \frac {z_i}{c_i + x}$$ All $z_i$ are positive and add to $1$. Among the $N$ coefficients $c_i$, $M$ are negative ...
2
votes
1answer
221 views

Optimizing trigonometric and nonlinear functions

First, Please, keep in mind that I'm a programmer not mathematician, and I have a fair mathematical background. I used optimization in Java to fit some observations to a trigonometric function, I ...
4
votes
2answers
82 views

What numerical optimization method to use for this function?

In order to solve this over-determined system of equations numerically: $$ f_l(\mathbf x) = \displaystyle \left \lvert \sum_{k=1}^Kx_k^2e^{-j\frac{2\pi}Np_kl} \right \rvert , \qquad P = ...
0
votes
1answer
58 views

Numerical Optimization methods?

What kind of functions are suitable for numerical optimization methods such as Newton, Gradient Descent, ... ? Any conditions?
0
votes
1answer
62 views

Convergence rate of an iterative scheme

Given an iteration scheme of the form : $x_{k+1}=x_k+t_kd_k$. It is also known that there are $\delta,C>0,D\geq 0$ such that if $x_k \in B_{\delta}(x_*)$ holds we have the following estimate: $ ...
0
votes
1answer
98 views

Condition or Proof: Minimizer of one function is maximizing another function

I have two real functions $f(X),g(X)$ where the argument $X$ is a real matrix. The solution $X^*$ for the problem of minimizing $f$ is ending up maximizing $g$ as well. I am looking for a way to prove ...
3
votes
1answer
317 views

How to show that the Hessian matrix of $G$ is positive definite?

Let $\{g_i:X\subset\mathbb{R}\rightarrow\mathbb{R};\;i=1,...,m\}$ be a linerly independet set of real functions. Given $n$ points $(x_1,y_1),...,(x_n,y_n)\in X$, consider the following function ...
2
votes
2answers
257 views

The Weierstrass Approximation Theorem Vs The Runge's Phenomenon

I am learning about different interpolation methods in my internship. Today as I was looking this article on Wikipedia to learn about the Runge's Phenomenon exhibited by Polynomial Interpolation. I ...
3
votes
0answers
50 views

Converting a linear program into standard form

In especially, I have a question about the demand that if I have $ Ax \leq b$, then I can convert this into $A'x'=b$ for some new $A'$ and $x'$. I have given the system of equations: $20x_1+30x_2 ...
1
vote
0answers
53 views

Optimize fill factor by move objects between areas

I have a optimization problem which is about several small rectangles inside one outer rectangle. We have, let say, three outer rectangles which are in following order (similar to weeks). Each ...
1
vote
0answers
83 views

Divergence of Gradient Method

Is there any example of a continuous differentiable function out there, in which the gradient method with Armijo's stepsize-rule doesn't converge? I found it pretty hard to create one myself because ...
0
votes
1answer
55 views

How to re-parametrize for quadratic minimization?

Given a real-rectangular matrix $S$ and inorder to solve this simple quadratic programming problem: Minimize $w'S'Sw = \|S w\|^2$ over $w$ subject to $e^Tw = 1$ and $w \geq 0$ using a solver I ...
0
votes
0answers
107 views

Simpson's rule characteristics

I just wanted to ask a quick question in regards to simpson's rule for integration. I have been reading up on the trapezoidal rule, and have found the notations and have an understanding such that: ...
0
votes
1answer
45 views

surface approximation using least squares

I am studying the following problem. Soppose you have two Bezièr patches with a common curve; suppose that the control points of the two patches are given by some initial guess (they are all known). ...
2
votes
1answer
98 views

Formulate optimization problem

My research area has "nothing to do with mathematics" but I still find it full of optimization problems. Therefore, I would like to learn to formulate and solve such problems, even though I am not ...
0
votes
1answer
185 views

Infeasible start Newton's method

I am implementing infeasible start Newton's method from the information in the slides (slide 11 of the link) posted here. It requires us to calculate primal and dual Newton steps, denoted by, $\Delta ...
0
votes
1answer
44 views

$(a - b \cot \theta) \cos^2 \theta = -\frac{b}{2} \cot \theta$ ,$\theta=$?

This question is a follow up question to this answer. In the equation: $$(a - b \cot \theta) \cos^2 \theta = -\frac{b}{2} \cot \theta.$$ $a$ and $b$ are given. What is the best way to solve for ...
0
votes
1answer
101 views

Solve: This System of equations for $X$ (does a real solution, exist?)

How can I solve $AX + diag(X)[I-c]=0$ for $X$? All matrices have real entries, $diag(X)$ is a diagonal matrix with the diagonal entries being the diagonal entries of $X$, and $c$ is a constant, real ...