The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
0answers
15 views

Converting a sum over squared norms to Quadratic Programming problem

I'm trying to minimize the following function which is a function of a set of vectors $\vec{x}_i \in \mathbb{R}^2$, and is parametrized by the fixed parameters $\alpha, \beta,\gamma_i,\vec{u}_i$ where ...
1
vote
0answers
21 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
0answers
20 views

Calculating block diagonalization / canonical bases with linear optimization?

In Linear Algebra there are many types of similarity transformations $${\bf A} = {\bf T}^{-1}{\bf DT}$$ Where $\bf D$ is (block-)diagonal. Famous examples include Eigenvalue decompositions, Jordan ...
1
vote
0answers
23 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 ...
0
votes
0answers
8 views

what is an efficient way to accomodate squares on an irregular big area?

I'm trying to use efficiently the space in this ship, there are 3x3 guns and 1x1 guns, the best guns are 3x3 so having more is better. Is there an algorithm or a program which help me find the best ...
-1
votes
0answers
21 views

Interpolation of random data

I have points $(t_1,x_1(t)),(t_2,x_2(t)), \cdots , (t_n,x_n(t))$ and I would like to estimate values of $x_k(t)$ where $1 < 2 < \cdots < k <\cdots <n$. How can I do this. I have read ...
0
votes
0answers
20 views

Parameter estimation with polynomial cost function

I am working on a model that can be written in its simplest form as $$ \mathbf{d_1}=a\,\mathbf{d_2}+b\,\mathbf{d_3}+ab\,\mathbf{d_4}, $$ where $\mathbf{d_i}$ are some data columns and $a,b$ are ...
0
votes
0answers
16 views

How to numerically evaluate a integral whose limits are functions of x (using Gauss quadrature rule)?

I am trying to numerically evaluate an integral $\int_q^1 \ln (\sum_i \alpha_ix_i) dq$, in which $\ln (\sum_i \alpha_i x_i)$ is related to $q$ via the following: $z_i=(1-q)\frac{\alpha_ix_i}{\ln ...
1
vote
0answers
26 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 ...
0
votes
0answers
13 views

Why is it that if a numeric method has quadratic rate of convergence then it can reach d digits of precision in logd iterations?

I was trying to understand why a method with quadratic convergence can get close to a good solution in $\log d$ iterations. Assume we have a method that has the property that the number of digits of ...
0
votes
1answer
16 views

Correct formulation of equality and non-negativity constrained non-linear minimization problem

I am trying to minimize a non-linear function with both equality and non-negativity constraints numerically (not analytically) using gradient based methods and without software packages. ...
1
vote
0answers
28 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
34 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 ...
0
votes
0answers
11 views

Quasi Newton updation matrix

How to prove that Quasi Newton updation matrix $B_{k}$ is positive definite for every iteration and it converges to $H^{*}$ ?
0
votes
0answers
6 views

Testing an SR1 update for approximate Hessian

I have written a function in MATLAB to run an SR1 update for an iteration of a Trust Region method to find a new approximate Hessian and its inverse, but I need to test it to check it works. Are ...
0
votes
0answers
12 views

Which are the alternative approaches to stochastic (online) gradient descend for online optimization?

I'm looking for some alternative approaches to online\stochastic gradient descent for online optimization such that 1) there exists some proof about the convergence of the parameters to some compact ...
0
votes
0answers
13 views

Equality constraints into inequalities constraints through elimination

I read here in Section 10.1.2 of this text that a way to eliminate linear equality constraints of the type $$Ax = b$$ in convex optimization problems is to parameterize the related affine space as a ...
0
votes
0answers
22 views

equality constraints and conic constraints in Sedumi (SOCP)

I´m starting playing with Sedumi. I want to solve a problem in the form $$ \min c_0' x $$ s.t. $$ A_1 x = b_1$$ $$ ||A_2 x + b_2|| <= c_2'x+d_2 $$ where $x \in R^n$, $ A_1 \in R^{m_1,n}$, $ ...
2
votes
0answers
41 views

Isotonic regression like

I have 2 ordered sets $$X=\{X_1<\dots<X_n\}$$ and $$Y=\{Y_1<\dots<Y_m\}$$ with $X_1<Y_1$ and and $X_n<Y_m$. I wish to approximate an increasing continuous function $g$ by piecewise ...
0
votes
0answers
17 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 ...
0
votes
0answers
12 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 ...
0
votes
0answers
15 views

Complexity of GMRES per iteration

I cannot find much about the complexity for GMRES. We're dealing with sparse matrices, I've been told that the time and space complexity grows with the number of iterations, thus is $\mathcal{O}(in)$, ...
1
vote
0answers
20 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 ...
0
votes
1answer
28 views

Solving nonconvex problem by iterating convex ones

I have a convex problem with the following properties: -The energy to be minimized is convex - it is basically a norm. -The domain is defined by a set of convex cone constraints inequalities. I am ...
0
votes
0answers
5 views

Minimizing percentiles of discrete distribution

I have a vector $\vec{v} \in \mathbb{R}^n$ and a matrix $A \in \mathbb{R}^{n \times m}$. For any $\vec{x} \in \mathbb{R}^m$, the vector $\vec{v} + A\vec{x} \in \mathbb{R}^n$ represents a discrete ...
0
votes
0answers
24 views

Two norm optimization with unit norm constraint

I am stuck with the following problem. Could someone give me some hints? Thanks a lot. Problem setting: Let $X\in R^{N\times k}$ and $\theta\in R^k$. Now we consider $\hat{\theta} = \arg\min ...
0
votes
3answers
84 views

Nonlinear Equation involving a matrix

I have a matrix $A$ whose entries are each a function of a variable $\epsilon$, with $\epsilon>0$. This matrix arises from Radial Basis Function (RBF) interpolation, and is symmetric ...
0
votes
0answers
27 views

Is $ \| \sum_{i \in [k]} \otimes^3 v_i - T \|_F^2 + \theta \| \sum_{i \in [k]} \otimes^3 v_i \|_F^2$ convex?

I am trying to find the minima of the following equation with respect to $v_i$, $i \in [k]$, to solve an optimization problem but I can't manage to make (stochastic or not stochastic, neither of them) ...
1
vote
1answer
45 views

trust region - choice of scaling matrix

According to many resources, TR algorithms often suffer from bad scaling. The simplest remedy is to use scaling matrix D in following way \begin{align} \min_d \ f + g'd + \frac{1}{2}*d'Bd \\ ...
0
votes
0answers
27 views

Get the global minimum with functions convex in a subset of the domain; numerical methods.

I have a $C^\infty$ function $f:\mathbb{R}^n\to \mathbb{R}$ that is positive and known to have a zero and a global minimum in an unknown point $x$. Furthermore, $f$ is convex in the set $$ S = ...
1
vote
1answer
13 views

How to derive the hard thresholding estimator?

The minimization problem is $$ \min_{\mu\in R^p} \sum_{i=1}^p (y_i-\mu_i)^2 + \lambda^2\sum_{i=1}^p \mathbb{1}(\mu_i\neq0) $$ for $y\in R^p$. This is also known as $l_0$ regularization. The solution ...
0
votes
0answers
20 views

Numerical Optimizer Matlab Calibration

I am trying to mimimize the following function in order to calibrate the Libor Market Model $$\sum_{i=1}^{n} \left(\sigma_i^{market}-\sigma_i^{Reb}\left(a,b,c,d,\beta\right)/\sqrt{T_i}\right)^2,$$ ...
0
votes
0answers
28 views

Convergence rate of steepest descent by newton's method

Help me to understand the proof that is given in the "Numerical Optimizaton" by Jorge Nocedal & Stephen J. Wright. The theorem says that at a near point $x_0$ then $\{x_k\}\to x^*$ by taking ...
0
votes
1answer
44 views

Minimal time trajectory optimization for body in 2D with waypoints

I am trying to control a spacecraft moving in 2D space through a number of waypoints as fast as possible. The spacecraft has directional acceleration (with an upper limit on its magnitude, and a limit ...
0
votes
2answers
49 views

Production optimization - what type of problem?

I want to make an algorithm that distributes orders $O_1,O_2,\dots$ to equipment $E^1,E^2,\dots$ so they can be processed in an optimal way. Different orders require different equipment for the ...
1
vote
0answers
34 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
1answer
37 views

Golden Section Search

I've been asked the following question: The golden section method is to be applied to a unimodal function to find the minimum in the domain $[0,2]$. Given we require the error not be greater than ...
0
votes
1answer
42 views

Find alternative shortest paths given extra properties

This is a follow-up question for a question I asked at here. The problem is mapped to a graph with say non-negative weights on edges (no preference if it can be directed or not). However, along with a ...
0
votes
0answers
12 views

matrix optimization problem techniques

I'm looking for some resources on learning techniques commonly used in matrix optimization. For example, minimization of the Frobenius/nuclear/weighted norm of a function of a matrix subject to ...
1
vote
0answers
29 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
35 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 ...
0
votes
0answers
15 views

what is the role of adding numerical dissipation to solve partial differential equations

I usually solve the partial differential equations (PDE), but I have never used the numerical dissipation to have a optimal results in terms on accuracy and stability of PDE's solution in generals. ...
0
votes
1answer
23 views

Conjugate gradient projection

Let $V$ be a collectino of the search direction for the conjugate gradient applied on a quadractic minimisation problem. As a proof of orthogonality in conjugate gradient: $$ V^T V = I $$ Now ...
0
votes
0answers
17 views

One-dimensional deblurring

I just begun studying image deblurring on my own, and I have a question. Most books I found say that I can see the images as arrays, and that I can "vectorize" the arrays of the images by stacking the ...
0
votes
2answers
38 views

Newton's method for optimization

I have been reading about Newton's method and know that you can use it for optimization problems. However, does Newton's method only guarantee convergence to a local minimum or maximum, or can it be ...
0
votes
0answers
10 views

Are there any optimization strategy suiting this framework?

For optimization problem: $min \quad f(x_1, x_2)$ Are there some strategies that are doing this sequentially, i.e. first solve $min_{x_1} \quad f(x_1, x_2^{k})$ to get $x_1^{k+1}$ then solve ...
1
vote
0answers
21 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
1answer
53 views

Do standard gradient descent methods work on complex variables

I am currently whishing to optimize a function numerically $f(z)$ where $z \in \mathbb{C} $ ($f(z) \in \mathbb{R}$) . I am doing this via numerical packages (specifically scipy in python) and I have ...
0
votes
0answers
23 views

Matrix approximation

How to solve numerically for non-negative full-rank matrices $P$ and $E$ with the following constraints? $Y$ is a known non-negative matrix with $G$ rows and $N$ columns, $G > N$ 1) ...
0
votes
0answers
28 views

Optimization on a grid

I worked a lot on defining the problem so I will be grateful to get input if i'm not clear enouth and I will fix the question. We have a grid made out of uniform points on $[x,y],$ $x,y\in[0,1],$ ...