Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

Filter by
Sorted by
Tagged with
128
votes
4answers
72k views

Partial derivative in gradient descent for two variables

I've started taking an online machine learning class, and the first learning algorithm that we are going to be using is a form of linear regression using gradient descent. I don't have much of a ...
30
votes
4answers
21k views

Gradient descent with constraints

In order to find the local minima of a scalar function $p(x), x\in \mathbb{R}^3$, I know we can use the gradient descent method: $$x_{k+1}=x_k-\alpha_k \nabla_xp(x)$$ where $\alpha_k$ is the step size ...
25
votes
1answer
14k views

What is the difference between projected gradient descent and ordinary gradient descent?

I just read about projected gradient descent but I did not see the intuition to use Projected one instead of normal gradient descent. Would you tell me the reason and preferable situations of ...
10
votes
3answers
17k views

Optimal step size in gradient descent

Suppose a differentiable, convex function $F(x)$ exists. Then $b = a - \gamma\nabla F(a)$ implies that $F(b) \leq F(a)$ given $\gamma$ is chosen properly. The goal is to find the optimal $\gamma$ at ...
9
votes
3answers
9k views

What is the definition of a first order method?

The term "first order method" is often used to categorize a numerical optimization method for say constrained minimization, and similarly for a "second order method". I wonder what is the exact ...
9
votes
2answers
355 views

Gradient descent for differentiable convex functions

Suppose $f\colon\mathbb{R}^n\to\mathbb{R}$ is convex and differentiable, and assume that $f$ has a minimizer. If $(x_k)$ is the sequence generated by exact gradient descent, must it converge to a ...
9
votes
2answers
560 views

A numerical optimization problem with a convolution in the constraint

I have a problem of the following form: minimize $\|Dx\|_2$ subject to $\|x*x\|_2 = 1$ where $x\in\mathbb R^n$, $D$ is a given diagonal matrix of positive entries, and $*$ represents convolution, ...
8
votes
3answers
7k views

Why does gradient descent work?

On Wikipedia, this is the following description of gradient descent: Gradient descent is based on the observation that if the multivariable function $F(\mathbf{x})$ is defined and differentiable ...
8
votes
2answers
2k views

What Numerical Methods Are Known to Solve $ {L}_{1} $ Regularized Quadratic Programming Problems?

What numerical methods are suitable to solve the following problem $$\min_x \tfrac{1}{2}x^T A x + b^Tx + \lambda ||x||_1$$ where $x,b\in\mathbf{R}^n$, and $A\in \mathbf{R}^{n\times n}$ is positive ...
8
votes
1answer
677 views

Quasi-newton methods: Understanding DFP updating formula

In Nocedal/Wright Numerical Optimization book at pages 138-139 the approximate Hessian $B_k$ update for the quasi-Newton method: (DFP method) $$B_{k+1} = \left(I-\frac{y_ks_k^T}{y_k^Ts_k}\right)B_k\...
8
votes
4answers
1k views

Finding good approximation for $x^{1/2.4}$

I would like to a good (8 bits accuracy) approximation for $x^{1/2.4}$ in the range $[0, 1]$. This transform is used for converting linear intensities to SRGB compressed values, so it's important that ...
7
votes
2answers
786 views

How can I, as a future mathematician, contribute most to Smart Grid research?

After I've finished my Master's degree in mathematics, I too want to use my powers for good. One endeavour I consider good is the pursuit of the design and implementation of a Smart Grid which will, ...
7
votes
3answers
346 views

The Integral of Multiple Tangent Functions

I need help to find the numerical values to the precision at least $50$ digits (the closed forms if possible) for the following integrals \begin{equation} {\large\mathscr{F}}\left(\alpha,\beta,\mu\...
7
votes
1answer
2k views

How to decompose a matrix into the outer product of two vectors?

I have a matrix $M$ and I would like to find two vectors $u$ and $v$, that minimize $$ \sum_{i,j} (M_{i,j}-u_iv_j)^2 $$ How can I do this (numerically)? Actually this is very simplified compared ...
7
votes
1answer
5k views

What is the time complexity of conjugate gradient method?

I have been trying to figure out the time complexity of the conjugate gradient method. I have to solve a system of linear equations given by $$Ax=b$$ where $A$ is a sparse, symmetric, positive ...
7
votes
3answers
7k views

Gradient descent with inequality constraints

Suppose we are given a convex function $f(\cdot)$ on $[0,1]$. One wants to solve the following optimization problem: \begin{equation} \begin{aligned} & \text{minimize} && \sum_{i=1}^n \...
7
votes
1answer
213 views

Numerical optimisation in presence of fast algorithm for some axes

Suppose we're seeking $(x,y)$ to minimise $f(x,y)$ ($f$ continuous, differentiable, but not necessarily convex) where $x\in \mathbb{R}^m$ and $y\in \mathbb{R}^n$. We can use any number of standard ...
7
votes
3answers
4k views

How does one choose the step size for steepest descent?

Consider finding the minimal value for any function $g$ from $\mathbb{R}^n$ to $\mathbb{R}$. The method of steepest descent for finding a local minimum for an arbitrary function $g$ from from $\mathbb{...
7
votes
1answer
268 views

Bouncing ball optimization

There are many interesting methods of searching for a global minimum of a complicated function of many variables, based on physical/biological analogies. For example, particle swarm optimization and ...
7
votes
1answer
180 views

Singularity of a positive linear combination of rank one matrices

Given a set of rank one matrices $A_1,..,A_n$, we need to find out if there exists $x \in \mathbb R^n$ with $x\gg 0$ (i.e, positive) such that $$ \sum_{i=1}^n x_i A_i = x_1 A_1 + .... + x_n A_n $$ ...
7
votes
2answers
243 views

Non-convex optimization: $\min ||y-Ax||_p$ for very small $p$ given that $||x||_2=1$

I need to find $x$ that minimizes the cost function $\|y-Ax\|_p$ when $p$ is close to $0$, subject to the constraint $\|x\|_2=1$ where $x$ and $y$ are vectors in $\mathbb{R}^n$ and $A$ is an $n\times ...
7
votes
0answers
92 views

Recommendation for intro to geometric integrators?

Explicit Request Looking for book or lecture note recommendations on numerical optimization that (ideally) have the following: Emphasis on geometric and physical intuition Emphasis on symplectic ...
6
votes
2answers
5k views

What is the difference between interior point methods, active set methods, cutting plane methods and proximal methods?

Can you help me explain the basic difference between Interior Point Methods, Active Set Methods, Cutting Plane Methods and Proximal Methods. What is the best method and why? What are the pros and ...
6
votes
1answer
7k views

Linear Least Squares with Linear Inequality Constraints

I'm trying to follow this older paper, page 19. The goal is to solve: $\min \|Ax-b\|^2 s.t. Gx \ge h$ given $A, G, b, h$ By combining the equations into a single LCP of the form: $Mz + q = w$ s.t. $...
6
votes
3answers
137 views

Understanding Newton method when optimizing cost function depending on a triangle.

I have the following function defined from $\mathbb{R}^9 \to \mathbb{R}$ \begin{equation} f(x) = f(x_1,x_2,x_3) = \frac{1}{2}(\left\langle n,e_3 \right\rangle - \lVert n \rVert)^2 \end{equation} ...
6
votes
1answer
130 views

Existence of a positive semidefinite matrix that satisfies a set of equality constraints

Given vectors $a_1, b_2, a_2, b_2 \in \mathcal{R}^{n\times 1}$, I am interested in finding a positive semi-definite matrix $M \in \mathcal{R}^{n\times n}$, $M \succeq 0$, such that $M\cdot a_1 = b_1$, ...
6
votes
1answer
232 views

Convex optimization with $\ell_0$ “norm”

I have an optimization problem of the form $$\begin{align*}\text{minimize }\;&f(x)\\ \text{subject to }\;&||x||_0 \le t,\end{align*}$$ where $t$ is a given constant and $f:\mathbb{R}^d \to \...
6
votes
1answer
107 views

Minimizing the size of a cylinder sliding in a tube

Lets define a spine curve $\Gamma$ given in terms of its arc length parameter $s$, and a family of closed curves $\Omega = \Omega \left( s \right)$. Lets say $\Gamma$ has a finite length, from $s=0$ ...
6
votes
1answer
83 views

Simple Optimization Algorithm compared to Douglas-Rachford

The Douglas-Rachford optimization algorithm solves problems of the form $$\text{minimize} \hspace{8pt} f(x) + g(x)$$ where $f$ and $g$ are Closed Convex Proper (CCP). It is useful when both $f$ and $...
6
votes
2answers
2k views

Intuition for gradient descent with Nesterov momentum

A clear article on Nesterov’s Accelerated Gradient Descent (S. Bubeck, April 2013) says The intuition behind the algorithm is quite difficult to grasp, and unfortunately the analysis will not be ...
6
votes
1answer
1k views

Levenberg-Marquardt - Is forcing Hessian to be positive definite OK?

I am often doing parameter estimation using Levenberg-Marquard method which involves solving the following linear system at each step: $$(H+\lambda I)\delta=r_{i}$$ where $H$ is a square Hessian ...
6
votes
1answer
4k views

Jacobian of exponential mapping in SO3/SE3

Following this post Jacobian matrix of the Rodrigues' formula (exponential map) What if I really need the Jacobian of the exponential mapping function in $\omega \neq 0$? Basically, I want to ...
5
votes
2answers
829 views

Proving a contraction mapping is a Cauchy sequence

Let $\phi(x):[a,b]\rightarrow [a,b]$ be a continuous function. Show that if $\phi(x)$ is a contraction mapping on $[a,b]$ then the sequence $\{x^{(k)}\}$ defined by $x^{(k+1)} = \phi(x^{(k)})$ is a ...
5
votes
1answer
843 views

Motivation for Mirror-Descent

I am trying to wrap my head around why mirror descent is such a popular optimization algorithm. Based on my reading, it seems like the main reason is that it improves upon the convergence rate of ...
5
votes
1answer
1k views

Algorithm for solving sparse equality-constrained least squares

I have a diagonal, positive-definite inner product matrix $M$ and want to find a minimizer of $$\min_q \frac{1}{2} \|q-q_0\|_M^2\qquad \text{s.t.}\qquad C^Tq+c_0 = 0,$$ where $q_0, c_0$, and $C$ are ...
5
votes
3answers
4k views

High Dimensional Optimization Algorithm?

I have an optimization problem that at first sounds quite textbook. I have a convex objective function in $D$-dimensional space that is twice differentiable everywhere and has no local optima. ...
5
votes
2answers
2k views

Good Textbook in Numerical PDEs?

I am currently taking a course on Numerical PDE. The course covers the following topics listed below. Chapter 1: Solutions to Partial Dierential Equations: Chapter 2: Introduction to Finite ...
5
votes
1answer
3k views

Why does the standard BFGS update rule preserve positive definiteness?

My class has recently learnt the BFGS method for unconstrained optimisation. In this procedure, we have a rank-1 update to a positive definite matrix at each step. This is specified as: $H_{k+1} = ...
5
votes
2answers
1k views

Optimization benchmarks?

There are so many different optimization algorithms out there, and lots of research going on. However, I have difficulties to find good comparison between them, and all articles / books / papers seem ...
5
votes
1answer
151 views

Optimization based on partial derivative

I want to maximize $f(a,b,c)$ over the variables $a,b,c$, such that 1) $0\leq a\leq K$, 2) $0\leq b\leq K$, 3) $0\leq c \leq K$ where $K$ is a constant. The $f(a,b,c)$ is some rational ...
5
votes
1answer
606 views

Remez algorithm for best degree-0ne reduced polynomials with same endpoints

Given a function $f(x)$ on [-1,1], the Remez algorithm can find the degree (at most) $n$ polynomial $P_n(x)$ that minimizes the maximum error between $P_n(x)$ and $f(x)$ on that interval. It is an ...
5
votes
1answer
5k views

what are Smooth and Non Smooth Problem in optimization?

I am trying to understand the difference between the optimization problem types which are basically smooth and non smooth. I also found this question what does a smooth curve mean? I understand that ...
5
votes
1answer
161 views

Gradient estimates using a candidate

Suppose one has a differentiable function $f:\Bbb R^n\to\Bbb R$ that one can evaluate but for which one has no expression for the derivative. There exist several procedure for gaining an estimate for ...
5
votes
1answer
144 views

Calculating sin and cos based on combination of exponentiation and power series?

Taylor series for $\sin(x)$ and $\cos(x)$ around $0$ are well known and usually exercised in beginner calculus courses. However as we know Taylor series are very localized, ultimately fitting only one ...
5
votes
1answer
52 views

What is known about optimizing a function whose evaluation cost is variable?

Let's imagine I have a function $f(x)$ whose evaluation cost (monetary or in time) is not constant: for instance, evaluating $f(x)$ costs $c(x)\in\mathbb{R}$ for a known function $c$. I am not ...
4
votes
5answers
9k views

Difference between Gradient Descent method and Steepest Descent

What is the difference between Gradient Descent method and Steepest Descent methods? In this book, they have come under different sections: http://stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf ...
4
votes
3answers
382 views

Operation cost of a lower triangular matrix

I'm having a hard time understanding the cost of the operations. Take this for example: Considering the system $Tx=b$, with $T=(t_{ij})$ triangular lower matrix. \begin{cases} t_{11}x_1=b_1 \\ t_{21}...
4
votes
2answers
173 views

Can every semidefinite program be solved in polynomial time?

I am reading a book about semidefinite programming that states the following: Every semidefinite program can be solved in polynomial time, up to desired acuuracy $\epsilon$. Is this true? And how ...
4
votes
1answer
5k views

Gauss-Newton versus gradient descent

I would like to ask first if the second order gradient descent method is the same as the Gauss-Newton method. There is something I didn't understand. I read that with the Newton's method the step we ...
4
votes
1answer
389 views

What is the purpose of an oracle in optimization?

I am reading a textbook on convex optimization, and in it there was an extremely short discussion of so called "oracle model" on page 136, which has left me confused. Pardon my ignorance but why do ...