Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

501 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
0answers
55 views

Convergence Rate of Projected Gradient Descent with Simplex Constraints

I'm trying to study the convergence rate, which is defined as $$ \lim_{k \to \infty} \frac{f(x_{k+1}) - f(x_*)}{(f(x_k) - f(x_*))^p} = R$$ (where $x_k$ is the $k$-th iterate while $x_*$ is the ...
0
votes
0answers
25 views

Proof of the convergence of a convex function with newton method

I need to prove the following: Assuming that $f$ is convex, under the assumption that $f$ is convex and $x^{(0)} \geq x_\star$, the algorithm always delivers a converging sequence: Theorem: Let's ...
0
votes
1answer
14 views

Initial feasible solution for barrier method

From this example page 9 It said set initial feasible solution at 2 here's barrier function: $$T(x)=\frac{100}{x}+\frac{1}{r}(\frac{-1}{x-5})$$ after derivative: $$\frac{\delta T}{\delta x}=\frac{1}{...
0
votes
0answers
18 views

Stochastic Optimization with Piecewise Function

I have a stochastic optimization problem where my objective is a piecewise function: $$ \underset{x}{\text{min}} \: \sum_{i=1}^{N} E(g(Y, x_{i})) $$ where $Y \sim N(\mu, \sigma^2)$ is a random ...
0
votes
0answers
53 views

Comparisons of Solving Speed of QP & SOCP

For two same scale optimization problem, quadratic programming (QP) and second-order cone programming (SOCP), which one is faster to solve? As far as I know, the computational complexity of QP and ...
0
votes
0answers
15 views

Specific number of Halton Points

I'm starting to study many article about numerical calculus and I see the definition of Halton Points (HP). But in this article sometimes one author use 289 HP, and sometimes another author use 1089 ...
0
votes
0answers
53 views

What is the arithmetic cost (computational complexity) of an SDP with nonlinear matrix inequality constraint

In the book ''Interior-Point Polynomial Algorithms in Convex Programming'' (Nesterov and Nemirovskii) section 6.4, there is a computational complexity result for the general positive semi-definite ...
0
votes
0answers
32 views

Can we always find a proper step size?

In convex optimization, if we know the gradient of a function $f(x)$, then is it true that we could always find a way to determine a proper step size in the gradient descent method? When I say "proper"...
0
votes
0answers
19 views

Optimizing a system of equations to minimize purchasing cost

I am new to this (posting on stack exchange and higher level math in general) so please correct me where I am in error. I am trying to minimize the cost to my company for purchasing a certain product. ...
0
votes
1answer
40 views

Why is this inequality true in the proof of the convergence of Newton's method?

From Convex Optimization by Boyd & Vandenberghe: Let $f$ be a twice continuously differentiable convex function that is strongly convex with constant $m$, i.e., $\nabla^2 f(x) \succeq m I$ for $...
0
votes
0answers
16 views

multi-objective optimization test function explanation

i took this image from a paper that describes a multi-objective optimization algorithm where UF1 is a multi-objective function to optimize. can you explain to me what J1, J2 variables and the second ...
0
votes
0answers
59 views

Block Separability in ADMM

I am reading Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, where Boyd claimed that ADMM is an algorithm that is intended to blend the ...
0
votes
0answers
27 views

Estimiate Fourier transform coefficients of optimial $L1$ function?

Let there be a loss function $h$ that takes an $L1$ function as input. Assume that $h$ has a finite global minima reached by a single $L1$ function $f^\ast$. In other words... $$f^\ast = \...
0
votes
0answers
82 views

Computation of function with sup

I am trying to compute the value of the following function $R:\mathbb{R}^m\mapsto\mathbb{R}$ $$R_n(\theta)=\sup_{\lambda\in\mathbb{R}^m}\left\{-\frac{1}{n}\sum_{i=1}^{n}\sup_{x\in\mathbb{R}^m}\lbrace ...
0
votes
0answers
107 views

Computational complexity of solving an SDP in CVX

I have solved an SDP by the MOSEK solver of the CVX toolbox. I need to calculate the computational complexity of my algorithm. Can you help me in this regard? I would appreciate it if you can give me ...
0
votes
0answers
26 views

constraint optimization using penalty function

Let say you have following constraint optimization problem and you want to optimize it using penalty function method: $$ \min f(\mathbf{x}), \mathbf{x} \in R^{2} \\ s.t. \mathbf{a(x) = 0}, \\ \mathbf{...
0
votes
0answers
35 views

Active set method for a simple problem

In my computetional methods course we recently had an algorithm for solving $(P)$ : $\min_{x \in \mathbb{R}^n} f(x) = \frac{1}{2}x^THx + c^Tx $ subject to $a_i \leq x_i \leq b_i$ for $i \in \...
0
votes
0answers
20 views

How can I prove $\lambda_k^* = \frac{-g_k^T u_k}{u^T_k A u_k}$ in the conjugate gradient method?

To break down the formula, This only applies to quadratic functions, $q(x) = \frac12 x^TAx+bx+c$ $g_k$ is the first derivative at the point $x_k$ $A$ is found from the quadratic function, or, I think,...
0
votes
0answers
54 views

Online Non-convex optimization

Can stochastic gradient descent be used for online non-convex optimization? If not, what are the suitable algorithms?
0
votes
0answers
20 views

What is the advantage of using KKT-CQ over LI-CQ for first-order KKT necessary condition

In the notes I follow, the author uses the KKT-CQ for the first-order necessary KKT conditions, then impose an additional constraint qualification which is the LICQ for the second-order conditions. ...
0
votes
0answers
31 views

What is the fault with Fritz John necessary condition for finding a local minimum for a general NLPP

The author says: It is also possible that, at some feasible point $x$, the FJ conditions are satisfied with Lagrange multiplier associated with the objective function $u_0 = 0$. In those ...
0
votes
0answers
49 views

Linear Program is Surprisngly Infeasible - Trying to Write the Dual

I need to solve the following linear program: $$\displaystyle{\min_{\bar{X},t}} \hspace{0.1in}t$$ such that: $$A\bar{X}=\tilde{x} + td$$ where $A$ is $N\times N$ and known, $t$ is scalar, $\tilde{...
0
votes
0answers
37 views

Difference between augmented Lagrangian and penalty method

1.what is an auxiliary variable? 2.when should we use the augmented Lagrangian (AL) instead of Lagrangian multiplier? 3.when should we use the penalty function instead of augmented Lagrangian (AL) ? ...
0
votes
0answers
43 views

Algorithm to find minimum of a multivariate function

Problem: Find (numerically) minimum of a function $f=f(x_1,...,x_M)$, where $M \in \mathbb{N}$ - a fixed number (often large), and $x_i \in [a,b],\forall i$. Function $f$ is complicated, and to ...
0
votes
1answer
43 views

What point will ADMM converge to ? A feasible point or a stationary point or local optima or global optima?

In Boyd's great ADMM paper Section 3.2.1, ''Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers'', it says that as iteration index $k\to \infty$, ...
0
votes
0answers
37 views

Globalized Newton method for minimizing a specific functional: Convergence?

I'm currently working on a generalized p-Laplace equation: \begin{align} \label{DP} \begin{cases} \text{div} (\sigma |\nabla u|^{p-2} \nabla u) = f &\quad \text{in } \Omega\\ u = g &\quad \...
0
votes
0answers
23 views

Estimating rate of decay of residual norms in gradient descent

I am using gradient descent to solve the linear system $Ax=b$, where matrix $A$ is symmetric and positive definite. More precisely, I am attempting to solve the following quadratic program $$\text{...
0
votes
0answers
10 views

Reference on one iteration convergence of gradient projection algorithm (Bound constrained optimization)?

So for a bound constrained optimization problem of minimizing a continuously differential function f(x) with $x^*$ which is a non degenerate solution, I was interested in showing that if all bound ...
0
votes
0answers
37 views

Characterizing class of functions from their gradient descent trajectory

Let $f : \mathbb R^d \to \mathbb R$ be a function with at least one minimum. Suppose that $f$ has the property that the gradient descent trajectory from any point of the function is a straight line to ...
0
votes
0answers
15 views

Superimpose an item of the chaotic sequence on vector

In the article "Improved Chaotic Gravitational Search Algorithms for Global Optimization" on page 1223, in step 6 of the pseudo-code "Chaotic Local Search Algorithm", the phrase "Superimpose an item ...
0
votes
0answers
27 views

Is there efficient Surface Walking method for optimization problems with equality constraint?

To my best knowledge, if we want to find the minimum of a function $f$ defined on a $d$-dimension manifold $M$ in $\mathbb{R}^n$, a.k.a an optimization problem with equality constraint, the most ...
0
votes
0answers
12 views

Roots of a n-variable non linear function with numerical methods

Currently I am working with finding the solutions for the following problem: I have a unit sphere in which I have n points defined by their polar and azimuthal angles: $\theta_n , \phi_n$. I then do ...
0
votes
1answer
20 views

Prove that $\xi_{k+1} = (-1)^{k+1}(\alpha_0 \times \alpha_1 \times \dots \times \alpha_k)$ is the (k+1) coefficient of $p_k$

I was given the following question as part of a homework assignment. Any help would be greatly appreciated! The following image shows the steps of a preliminary version of the conjugate gradient ...
0
votes
0answers
28 views

Optimization with difference equation constraint

I'm working on a problem where I have a (vector) linear recurrence relation of the form $$ a_{n+1} = \lambda \circ a_n+b_n $$ I need to solve the following optimization problem: $$ \min\limits_{b_n}...
0
votes
0answers
36 views

Confused about Nesterov momentum gradient descent algorithm

I've found a variety of variations of writing Nesterov but I cannot understand why they cannot simply be expanded into a one liner. Here is one I found that can just be re-arranged, can someone ...
0
votes
0answers
29 views

General Chebyshev approximation

I am having trouble understanding it, first of all, what is x? Are x's coefficients of this polynomial we are looking for? This would mean that the polynomial is of degree $n-1$ because it has n ...
0
votes
0answers
13 views

Minimize Error for Expansion of $1/(1-x)$ with fewer terms

Suppose you want to expand $f(x) = \frac{1}{(1-x)}$ around some point $x_0$ for $0<x<1$ Call the expansion of $f$ around $x_0$ as $Exp_{x_0}f$. I want to compare the performance of $Expf$ vs $...
0
votes
0answers
47 views

Zoutendijk's Lemma Using Goldstein Conditions

I am reading Numerical Optimization by Wright and Nocedal and in page 39, it says that a similar result to Zoutendijk's lemma (Theorem 3.2) can be proven using the Goldstein conditions instead of the ...
0
votes
0answers
35 views

I am trying to find the maximum learning rate or stepping rate of steepest descent algorithm in 2 dimensions

Let $f(x,y) = (x-y)^4+2x^2+y^2-x+2y$. I am trying to numerically find the miniumum of $f$. We define a fixed-point iteration scheme \begin{align*} g(x, y) = \vec{x}_{n+1} = \vec{x}_{n} - a\nabla f \...
0
votes
0answers
19 views

Quadratic programming terms

Help me to understand the terms of this quadratic programming problem? $$ P{\left(U,Z,W\right)} = \sum_{p=1}^{k} \sum_{i=1}^{n} \sum_{j=1}^{m} U_{ip} W_{pj} ( X_{ij} - Z_{pj} )^{2} +{1 \over{2}}a \...
0
votes
0answers
27 views

Manifold Optimization in Human understandable language

I am coming across a project that involves with "manifold optimization". I don't know what that is. After Googling for a bit, my understanding is that we use a low dimensional surface to approximate ...
0
votes
0answers
40 views

Are step sizes in quadratic programming solvers analytically exact?

In this paper (DOI link), Goldfarb and Idnani describe an algorithm for solving a certain subset of quadratic programs. This algorithm (or a very similar one) is implemented in the quadprogpp package ...
0
votes
0answers
76 views

Do BFGS and L-BFGS methods converge when the matrix $H=B^{-1}$ is ill-conditioned?

I am using BFGS and L-BFGS to solve an unconstrained optimization problem. The objective function is the Mean Euclidean Error. The output is given by an Artificial Neural Network. The line search ...
0
votes
0answers
23 views

Minimum path distance from a source

Suppose I have a path-connected subset $I$ of $\mathbb{R}^n$ (not convex, but can be contained in a product of finite-measure closed intervals), and I define a "source point" $a \in \mathbb{R}^n$. ...
0
votes
0answers
16 views

Transform the problem to EQ constrained problem with simple bounds

\begin{align} min && x_1^2 + x_2^2\\ s.t. && (x_1 -3)^2+1 \leq x_2\\ &&x_1-2x_2+2=0\\ &&x_2 \geq0.5 \end{align} SOLUTION. \begin{align} min && x_1^2 + x_2^2\\ ...
0
votes
0answers
56 views

Motive of Conjugate Gradient method.

It is known that the solution to the linear system $Ax=b$ where $A$ is symmetric and positive definite is the minimizer of the quadratic function $f(x)= \frac{1}{2} x^T A x - x^T b$ We can solve it ...
0
votes
0answers
29 views

Concerning the idea of Trust Region methods

As far as I understood is that the idea of TR methods is that at the current iterate $x_k$ we build a model "usually quadratic", of the objective function $f$ to be optimized, $m_k(s)$ of $f(x_k +s)$ ...
0
votes
0answers
27 views

In-exact line search

In my class notes, the author says: "If $f:\mathbb{R}^n \to \mathbb{R}$ is bounded below and $p_k$ is a descent direction and the $\alpha-\beta$ also known as Armijo-Goldstein condition is met then ...
0
votes
0answers
301 views

Advantages and disadvantages of the Golden-section search method

As I understand that the golden-section search is a zero-order line search method so it is a global method so in comparison with Newton's and the secant's method this is an advantage. But it has a ...
0
votes
0answers
136 views

How to take derivative of log loss function in gradient descent?

I know the gradient descent about $z=wx+b$. But how to implement the derivative values of $w$ and $b$ in Python? I see some example like ...