Questions tagged [numerical-optimization]
Numerical methods for continuous optimization.
1,344
questions
0
votes
0
answers
7
views
Can a method for a quadratically constrained quadratic programming be applied to a quadratic optimization function with linear constraints?
I want to find a time complexity for solving
$$\min_x \|Ax-b\|^2_2 \quad \text{s.t.} \quad 0 \leq x \leq 1$$
In section 10.2 of Interior Point Polynomial Time Methods In Convex Programming [PDF] (...
- 578
1
vote
1
answer
31
views
Comparison of Wolfe conditions to other "weaker" conditions or facts about optimization techniques for conceptual understanding
So in the book, it states that the first wolfe condition is the following,
$\begin{equation}p^Tg_k\leq-\eta_0|||p|||g_k||\end{equation}$, where $g_k=\nabla F(x_k)$.
Here it states that this is a ...
- 355
1
vote
0
answers
18
views
Approximate first-order loss function with piecewise-linear functions in python
I'm trying to approximate the first-order loss function $$\mathbb{E}[max(d-y,0)]=\sigma \cdot (\phi(\frac{d-\mu}{\sigma})- \frac{d-\mu}{\sigma} \cdot (1- \Phi (\frac{d-\mu}{\sigma})),$$
where $d\in \...
- 33
0
votes
0
answers
22
views
Flux that can be represented by low and high resolution schemes.
In the wiki page of Flux limiter, it writes:
If these edge fluxes can be represented by low and high resolution schemes, then a flux limiter can switch between these schemes depending upon the ...
- 732
2
votes
0
answers
11
views
A question on the projection step of Generic Adaptive Method: $x_{t+1} = \Pi_{\mathcal{F},\sqrt{V_t}} (\hat{x}_{t+1}).$
I am reading the paper "ON THE CONVERGENCE OF ADAM AND BEYOND". In this paper, they proposed the following framework of adaptive methods.
I was confused on the last step: $x_{t+1} = \Pi_{\...
- 601
1
vote
0
answers
13
views
BFGS computational complexity derivation
The update for the Hessian using BFGS is given by:
$$H_{k+1}=(I-\rho_ks_ky_k^T)H_k(I-\rho_k y_ks_k^T)+\rho_ks_k s_k^T$$
where $\rho_k=\dfrac{1}{y_k^Ts_k}$.
Nocedal and Wright, Numerical Optimization ...
- 576
1
vote
0
answers
35
views
How do you represent the number of iterations in the formulation of an optimization problem?
Let's say I want to minimize some function for f(x), with respect to x, in the minimum number of iterations. How would I represent the number of iterations in the formulation of this optimization ...
- 133
0
votes
1
answer
38
views
Algorithm to minimize $(x_1+\dots+x_n)^2 + \frac{c}{2}\sum_{i=1}^n x_i^2 + \sum_{i=1}^n (\lambda_i - cz_i)x_i $ subject to $x_i\geq 0$
I am trying to minimize $(x_1+\dots+x_n)^2 + \frac{c}{2}\sum_{i=1}^n x_i^2 + \sum_{i=1}^n (\lambda_i - cz_i)x_i $ subject to $x_i\geq 0$ where $c\geq 1$ is a constant (that I can push arbitrarily ...
- 1,731
0
votes
1
answer
35
views
Fail to get convergence on point iteration method
I have the following formula:
$$\lambda = \lambda(1-F(S-2)) + \frac{r}{c}p$$, where $S, p, r$ and $c$ are constants and $F(.)$ is the CDF function of a random (Poisson distributed) variable, so $F(S-2)...
- 1,259
1
vote
0
answers
83
views
For which starting points for $f(x) := \sqrt{1+x^2}$ does Newtons Method converge?
I am stuck at the following exercise:
For which starting points for $f(x) := \sqrt{1+x^2}$ does Newtons Method converge?
I recently learned about Newton's Method in class and the real theorem ...
- 2,452
1
vote
1
answer
59
views
Maximize $\displaystyle\sum_{i=1}^4\frac{A_i(1-e^{-k_it_i})}{t_i}$ subject to $t_1 + t_2 + t_3 + t_4 = T$
I'm working on a personal project and I have the function $$ P(t_1,t_2,t_3,t_4) = \cfrac{A_1(1-e^{-k_1t_1})}{t_1} + \cfrac{A_2(1-e^{-k_2t_2})}{t_2} + \dots +\cfrac{A_4(1-e^{-k_4t_4})}{t_4} $$
where $ ...
- 61
0
votes
0
answers
24
views
Running time of box-constrained least-squares
I want to find the time needed to solve the box-constrained least-squares problem $$\begin{array}{ll} \underset{x}{\text{minimize}} & \|Ax-b\|_2^2\\ \text{subject to} & v \leq x \leq u\end{...
- 578
0
votes
0
answers
39
views
What is the computational cost of the alternating direction method of multipliers
I am solving the following proximal problem:
$min_x f(x) + g(z)$,
$x^{k+1} = \arg\min_x (f(x) + (\rho/2) \Vert x - z^k + (1/\rho) y^k \Vert_2^2)$,
$z^{k+1} = \arg\min_z (g(z) + (\rho/2) \Vert x^{k+1} -...
- 109
0
votes
0
answers
37
views
Question about a convex optimization using gradient descent
Recently I have read a paper, but I was confused about the optimized method of this article. In the following I will try to abstract the problem in the text. Supposed that we have six variables $\bf{\...
1
vote
0
answers
26
views
Constant step lengths in subgradient method
I was reading these notes (if the previous link doesn't work, use this) on the subgradient method, it says that the choice for step sizes (or step lengths) are determined before the algorithm is run, ...
- 109
1
vote
0
answers
35
views
Minimizing $b^Tb$ subject to $Ax=b, x\geq 0, x\leq 1$
I have the following quadratic program: Minimize $b^Tb$ subject to $Ax=b$ where $A$ is a $n\times m$ matrix ($n\leq m$) of rank $n-1$. I also want $0\leq x\leq 1$.
For my choice of $A$, I can prove ...
- 1,731
0
votes
0
answers
23
views
When is the product of a function with a positive linear one convex?
Let $f: Y \subset \mathbb{R}^n \to \mathbb{R}^m$ be a non-constant function and $g: \mathbb{R}^m_+ \times Y \to \mathbb{R}$ be defined as follows:
$$g(\mathbf{x},\mathbf{y}) = \mathbf{x}^T f(\mathbf{...
- 49
0
votes
0
answers
47
views
Chebyshev Nodes Interpolation
I am a bit confused as to what role the Chebyshev nodes play in the optimization of Langrage Polynomial Interpolation.
Reading online for what I understand that the Chebyshev nodes gives us the ...
0
votes
0
answers
8
views
Numerically approximating projection onto an infinite-dimensional Hilbert-space
We have the following problem that we want to model numerically. We would be glad for any references, since we could not find much useful information on these kind of problems and since we do not come ...
0
votes
0
answers
20
views
How to combine fix-point methods with linear equation systems for solving non-linear matrix equations?
A few days ago I revisited an old favorite problem of mine :
How to find "fractional" discrete integration operators?
My approach was that of a damped fixed point method
$$M_{i+1} = (1-\...
- 24k
0
votes
0
answers
71
views
How to use barrier method for constraints like $X \succ 0$?
When reading about interior-point methods in Stephen Boyd & Lieven Vandenberghe's Convex Optimization, a question arose about how to use barrier method for the constraint $X$ is positive definite, ...
- 31
1
vote
1
answer
47
views
Can optimization algorithms "bounce around" forever?
I have the following question on the convergence of numerical optimization algorithms. When it comes to convex functions, it can be shown that algorithms like gradient descent converge after an ...
- 1,692
0
votes
0
answers
31
views
Solving a nonlinear optimization problem
I'm trying to solve the following problem:
Let $\varphi_i: \mathbb{R}^n \to \mathbb{R}$ be continuously differentiable and
$\varphi_i( {\bf 0} ) = 0$ for all $i=1,\dots,r$. Assume that $x^*$
is a ...
0
votes
0
answers
43
views
Why does the pure Newton method use step size $\alpha = 1$?
We know that pure Newton method is derived from the Taylor second order expansion. Its step size equals to $1$. Also there exists Newton method with step search. Here are my questions.
Does the ...
- 1
0
votes
0
answers
14
views
L-BFGS, two loop recursion algorithm to compute the product between B_k and a direction
Let $B_k$ be the approximated Hessian computed with the L-BFGS method.
I know it is possible to compute $(B_k)^{-1}d$ with the two loop recursion algorithm.
I would like to know is there is such an ...
1
vote
0
answers
32
views
Calculus of variations: Lagrange multiplyers
I have a system of coupled PDEs which I solve numerically. I wish to optimise a particular objective function using gradient ascent, where the system of PDEs feature as constraints. I can't get the ...
- 11
0
votes
1
answer
41
views
Feasible descent
Consider a NLP $\min\{f(x): g(x) \le 0\}$. There are no equality constraints. The problem is feasible for small steps $t > 0$. I have to prove that $g(x + td) \le 0$ if $g(x) < 0$, where $t$ is ...
- 3
0
votes
0
answers
5
views
Optimization Algorithm for efficient stochastic evaluation of blocks
Are there stochastic optimization algorithms that benefit from evaluating the target function at multiple, predefined values at the same time?
Say I have a one-dimensional, smooth, and bounded ...
- 123
1
vote
0
answers
28
views
Optimality condition of proximal gradient
Given a convex $L$-smooth function $g: \mathbb{R}^d \rightarrow \mathbb{R}$ and a differentiable convex function $h: \mathbb{R}^d \rightarrow \mathbb{R}$
I want to find the optimality condition of the ...
- 85
0
votes
0
answers
19
views
What would be a good loss function for this problem?
The problem is as follows, you have an implicit function $f:\mathbb{R}^2 \rightarrow \mathbb{R}$.
You have a square region that overlaps with the boundary of the surface described by the iso line $f(x,...
- 2,269
1
vote
1
answer
33
views
Is there an 'inner product wrt a matrix' version of gradient descent?
Gradient descent generally starts with a first order Taylor approximation motivation. If we have a function $f:\mathbb{R}^p\rightarrow\mathbb{R}^p$, and we start at a point $x\in \mathbb{R}^p$, then ...
- 551
0
votes
1
answer
41
views
Gradient descent inside the expectation-maximization (EM) algorithm
I am feeling super uncertain about how much I can play around with the EM algorithm. Here is my question:
In the EM algorithm, during the M-step, one attempts to find a parameter value, $\theta$, that ...
1
vote
0
answers
26
views
Numerical low-rank approximation of sample covariance matrix
I could use some help with a matrix optimization problem. I have a $M \times M$ sample covariance matrix $\hat{\mathbf{C}}$ that I'd like to approximate using the decomposition $\hat{\mathbf{C}} = \...
- 11
1
vote
1
answer
64
views
Proximal Gradient Descent
I am trying to solve the below optimization problem using proximal gradient descent on a dataset in python:
$f(\theta) = \arg\min_{\theta \in R^d}\frac{1}{m}\sum_{i=1}^m\Big [log(1+exp(x_i\theta))-...
- 15
1
vote
1
answer
39
views
Lagrange Multipliers and Hard Margin SVMs
With hard margin support vector machines (SVMs), it suffices to find the critical points of the Lagrangian $L = \frac{1}{2}||\theta||^2 - \sum_{n=1}^{N} \alpha_n (y^{(n)} (\vec{\theta}^T\vec{x}^{(n)} +...
- 186
0
votes
1
answer
37
views
Gradient descent algorithm explanation
How do I get from the derivative in the second last line to get xj in the last line?
- 17
1
vote
0
answers
32
views
Approximating an integral with the value at some uniformly distributed points
Let $f(x)$ defined on $[0, 1]$ be a smooth function with sufficiently many derivatives. $x_i = ih$, where $h =\frac{1}{N}$ and $i = 0,1,\cdots,N$ are uniformly distributed points in $[0, 1]$. What is ...
- 732
0
votes
0
answers
18
views
Small mesh size implies a monotone polynomial approximation
We consider a piecewise smooth function
$$f(x) =
\begin{cases}
f_1(x), & x\le0 \\
f_2(x),& x>0
\end{cases}
$$
where $f_1(x) $ is a $C^\infty$ function on $(-\infty,0]$ and $f_2(x)$ is a $C^...
- 732
1
vote
0
answers
31
views
A Bi-Level Optimization Problem
I have a problem in which I need to maximize a function over a vector of $X:\mathbb{R}^{N}_{++},Y:\mathbb{R}^{N}_{++}$. The maximization problem looks like this,
$$ \max_{X} \left( \sum_{n=1}^{N} f_{n}...
- 67
1
vote
0
answers
57
views
What is this optimization method called?
I am using a technique to do numerical optimization of a system but I don't know what it's called. I would like to be able to look it up in literature or books, but can't without knowing what I'm ...
- 11
1
vote
1
answer
45
views
Merit Function Line Search in Interior Point Methods - Penalty Parameter Updates
I gues the TL;DR is summarized as follows:
Why do the step length and penalty parameter calculations not consider the steadily decreasing step length (in a backtracking line search) when calculating ...
- 108
0
votes
0
answers
27
views
Q-Convergence Explanation
I've been reading about convergence rates, in particular Q-convergence. But I'm struggling to understand it. I know that a sequence will converge Q-linearly to a number $L$ if there exist some $\mu \...
- 31
1
vote
1
answer
31
views
Which is better for optimization, tight inequality constraint or equality constraint?
I have a constrained optimization problem,
$$
\min_x f(x) \quad\mathrm{s.t.}\quad g(x)\leq0.
$$
The feasible region of this optimization problem is a convex set. I can prove that the optimal solution ...
- 48
0
votes
0
answers
35
views
Show the Hessian is locally Lipschitz continuous
The function $f: \mathbb{R}^2 \rightarrow \mathbb{R}$
$f(x,y) = (y-\cos x)^2 + (y-x)^2$
Has the following Hessian
$\nabla ^2 f = \begin{pmatrix}
2(\sin^{2}x + (y-\cos x)\cos x + 1) && 2(\...
- 31
0
votes
1
answer
24
views
What's the difference between a value of a dual and a solution of a dual?
In this video on total dual integrality: https://youtu.be/l8YdPRxqlXo?list=PLXsmhnDvpjORcTRFMVF3aUgyYlHsxfhNL&t=798
If the dual has an integral solution, not just an integral value ...
The ...
- 157
1
vote
0
answers
19
views
Optimization algorithm for a semi-factorizable function
(sorry for the terrible title, I don't know if there is a proper name for a function like that)
I have a function of several (n~100) real variables $f(x_1, x_2, \ldots, x_n)$ and I want to find the ...
- 201
0
votes
1
answer
38
views
Numerical solutions to the 3D wave equation
I am doing a research to explore the existing numerical schemes that are used to solve the $3$D wave equation.
The standard form of the problem in $3$ dimensional setting is : $$\Delta u= \frac{1}{c^2}...
- 650
1
vote
1
answer
74
views
Derivation of Gauss-Newton method for underdetermined inverse problems
I would like to derive the Gauss-Newton method for solving underdetermined inverse problems, i.e., where the parameter space is larger than the number of constraints. Although my final solution works, ...
- 13
0
votes
0
answers
22
views
Can a nonlinear system give same solution with distinct set of parameters?
This question comes after experimenting with learning the parameters of a nonlinear system $\dot{\mathbf{x}} = f(\mathbf{x}), f: \mathbb{R}^n \rightarrow \mathbb{R}^n$. If I take a system that has $f =...
- 26
1
vote
4
answers
71
views
Question About Gradient Descent
Gradient descent is numerical optimization method for finding local/global minimum of function. It is given by following formula: $$ x_{n+1} = x_n - \alpha \nabla f(x_n) $$
For sake of simplicity let ...
- 119