Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

Filter by
Sorted by
Tagged with
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] (...
user avatar
  • 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 ...
user avatar
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 \...
user avatar
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 ...
user avatar
  • 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_{\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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)...
user avatar
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 ...
user avatar
  • 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 $ ...
user avatar
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{...
user avatar
  • 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} -...
user avatar
  • 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{\...
user avatar
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, ...
user avatar
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 ...
user avatar
  • 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{...
user avatar
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 ...
user avatar
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 ...
user avatar
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-\...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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,...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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}} = \...
user avatar
  • 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))-...
user avatar
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)} +...
user avatar
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?
user avatar
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 ...
user avatar
  • 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^...
user avatar
  • 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}...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 \...
user avatar
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 ...
user avatar
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(\...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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}...
user avatar
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, ...
user avatar
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 =...
user avatar
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 ...
user avatar

1
2 3 4 5
27