Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

Filter by
Sorted by
Tagged with
2
votes
0answers
237 views

Stochastic optimization vs stochastic programming

How should I think about the differences between stochastic optimization (SO) and stochastic programming (SP)? From Wikipedia, it seems that SO is a framework that uses randomness to solve a pre-...
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{...
2
votes
2answers
54 views

Newton polynomial interpolation, which formula for the coefficients in rigth?

I'm studying Newton Polynomial interpolation, and there are formulas for the coefficients $c_i$ in the expansion $$P(x) = c_0 + c_1(x-x_0) + c_2 (x-x_0)(x-x_1)$$ On Wikipedia, the third coefficient ...
1
vote
1answer
67 views

Newton step for ${\min}_{x \in \mathbb{R}^n} \ \sum_{i=1}^n -\ln(1 + \eta_i x_i) \ $ s.t. $A x \leq b$; $-x \leq 0$ to be used in primal-dual

I have a following problem on hand. P1: \begin{align} \text{minimize}_{x \in \mathbb{R}^n} \quad & \sum_{i=1}^n -\ln(1 + \eta_i x_i) \equiv -e^T \ln(e + \eta \odot x) \\ \text{subject to }\quad &...
2
votes
4answers
112 views

Why do we need approximation methods when we have algorithms to find exact roots?

While I was studying numerical methods and optimizations recently, I observed that whenever we find a root to an equation or a system of linear equations, we always find approximate roots. However, we ...
4
votes
1answer
80 views

Show convergence of an algorithm within $m$ steps

I am trying to show that the following algorithm outputs the solution to the problem $Ax=b$. Assumptions $A$ is symmetric positive definite of size $n \times n$ with $m$ distinct eigenvalues. The ...
1
vote
0answers
31 views

Handling singular matrices in gradient-descent optimization.

Right now I am coding up optimization for a 70 dimension nonlinear optimization, where the analytical gradient is unavailable. I have some non-linear constraints that maps the structural parameters ...
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
36 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 ...
2
votes
0answers
11 views

Finding the domain shape, where the fundamental Helmholtz Eigenmode has certain properties at a boundary

The following is a problem about finding the shape of a domain such that the fundamental Helmholtz eigenmode has certain properties at the boundary of the domain. I search for an analytical or ...
1
vote
2answers
136 views

Minimization of Positive Quadratic Function Using Gradient Descent - At Most in $ n $ Steps

For minimization positive quadratic form $$f = \frac{1}{2}\left\langle Ax,x \right\rangle - \left\langle b,x\right\rangle \rightarrow \min_{x\in\mathbb{R}^n},$$ we use gradient descent $$x^{...
1
vote
0answers
41 views

Find minimizer of mean values

i'd like to know if there is an analytical method to solve the following optimisation problem : $\forall i=1,..,n$ find $\omega_i^{}$ and $\alpha_i^{}$ such that: $\dfrac{1}{n} \displaystyle \sum_{i=...
0
votes
1answer
24 views

How to work around a nonconvex constraint?

My objective function is \begin{align} \text{minimize}_{\mathbf{x} \in \mathbb{R}^3} \quad & \mathbf{x}^T\mathbf{M}\mathbf{x} \\ \text{subject to }\quad & x_1 = 1\\ & x_3=x_1x_2=x_2 \...
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 ...
1
vote
0answers
60 views

Optimisation under constraint of Wasserstein distance

Let $\mathcal P_n = \{P \in \mathbb R^n_{\geq 0}: P^T \mathbb I = 1 \}$, where $\mathbb I = (1,...,1)^T \in \mathbb R^n$ and $f: \mathcal P_n \to \mathbb R$ a convex and differentiable function (or ...
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
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 \...
2
votes
2answers
96 views

Optimal Value of a Cost Function as a Function of the Constraining variable

Consider the optimization problem : $ \textrm{min } f(\mathbf{x}) $ $ \textrm{subject to } \sum_i b_ix_i \leq a $ Using duality and numerical methods (with subgradient method) i.e. $d = \...
0
votes
0answers
25 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}...
1
vote
0answers
43 views

Use Conjugate Gradient to obtain the Eigenvalues

So I have been told that we can use CG to obtain an eigenvalue approximation to the true matrix. I am not sure how? (Connection to Lanczos) Furthermore I have been told that there is a deep ...
0
votes
0answers
32 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 ...
1
vote
1answer
41 views

Iterative algorithm for a simple linear optimization problem

Let $c_1,\dots,c_n$ be $n$ positive numbers and so be $a_1,\dots, a_n$. For some $r$ such that $1\leq r\leq n$, consider the optimization problem \begin{align} \max_{x_i\in\mathbb{R}}&~~\sum_{i=1}^...
2
votes
0answers
88 views

Using Coordinate Descent on Projected Space

My goal is to maximize an objective function using coordinate descent over a 3-dimensional vector. In the simple case the domain over which I am maximizing is defined as follows: $X \in \mathcal{X}$ ...
2
votes
0answers
66 views

How do I pack 2D objects into an arbitrary shape?

I've heard of packing problems in general, and I've seen a couple questions on this site that address specific cases (e.g. how to pack 45-45-90 triangles into an arbitrary shape), but after a search I ...
1
vote
2answers
55 views

Expanding $\frac{1}{1-x}$

Is there any kind of expansion of $f(x)=\frac{1}{1-x}$, possibly with polynomials, such that with only a few terms I can represent with an error smaller than $10\%$ the function over the interval $[0, ...
0
votes
0answers
20 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 ...
2
votes
1answer
41 views

Recovering a matrix from a linear ODE given observations

To make this simple, let's say we have $x: \mathbb{R} \rightarrow \mathbb{R}^2$ such that $$\frac{d}{dt}\vec{x}(t) = \begin{pmatrix} x_1'(t) \\ x_2'(t) \end{pmatrix} = A \vec{x}(t)$$ for some constant ...
0
votes
0answers
12 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
38 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
1answer
46 views

Getting to the gradient descent algorithm

I understand that gradient descent comes from the (quite natural) idea that we might want to choose our next weight vector ($w^{t+1}$) as $$w^{t+1} = \arg \min_w \frac{1}{2} \|w-w^t\|^{2} + \eta f(w^...
1
vote
2answers
784 views

A constrained gradient descent algorithm

I am looking for a way to find a solution to the constrained minimization problem using the gradient descent Algorithm. it follows ...
0
votes
0answers
34 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
1answer
36 views

Minimizer of a multivariable function and iteration through Newton's method

I got stuck on the following question. Find the minimizer for $$f (x_1,x_2) = \frac 12 (x_1^2 - x_2)^2 + \frac 12 (1-x_1)^2$$ and compute one iteration for minimizing $f$ from point $(2,2)$. Also, ...
0
votes
1answer
55 views

Applying a quasi newton (L-BFGS) method to a non differentiable cost function.

I'm reading through a paper which presents at some point an optimization step to a function of the form: $$ E = \sum_i \left|\alpha_i - \beta_i \right| $$ where $\alpha_i$ and $\beta_i$ are also ...
1
vote
0answers
33 views

What methods can solve SOCP problems?

What methods can solve SOCP problems? I need at least few different. By: https://en.wikipedia.org/wiki/Second-order_cone_programming it seems that the problem "reduces" to simpler problems, but I'...
2
votes
2answers
4k views

Stopping criteria for gradient method

For numerically solving a smooth convex optimization $\min\{f(x): x\in S\}$ where $S$ is a closed convex set, we can apply some different algorithms: gradient method, accelerated gradient, proximal ...
0
votes
1answer
78 views

Finding a global minimum

I seek the function $f$ which satisfies the 100 equations (i=1,2...100) $\sum_{j=1}^{2000} f(A_{ij},B_{ij},C_{ij})=Q_i$. Where $A,B,C$ are 100x2000 matrices and all entries are between 0 and 1. ...
1
vote
2answers
50 views

Differential equation: mixed boundary condition, how to solve numerically?

I have a differential equation (dot means derivative w.r.t time) $$(\dot x, \dot y) = f(x,y)$$ and I am given the initial condition for $x$, but a final condition for $y$: $$x(0),\qquad y(1)=g(x(1))$$ ...
3
votes
1answer
274 views

A good book on programming for numerical optimization

I was hoping someone could recommend a good book on programming for numerical optimization--including lots of code examples. I am reading Nocedal and Wright, which is great. One of the recommendations ...
3
votes
1answer
184 views

Linear Least-Squares Problem with Inequality Constraints on Residual

I have an over-determined linear least-squares problem $$\min_{\vec{x}}\Vert\mathbf{A}\vec{x}-\vec{b}\Vert_2^2,$$ where $\mathbf{A}\in\mathbb{R}^{n\times m}$, $\vec{x}\in\mathbb{R}^m$, $\vec{b}\in\...
1
vote
1answer
39 views

Approximate $f''(x)$ given $f(x),f(x+h),f(x+3h),f(x-5h)$

Given $f(x),f(x+h),f(x+3h),f(x-5h)$, approximate $f''(x)$. Book's solution: From Taylor' series, $$ \\ f(x+h)=f(x)+f'(x)h+0.5f''(x)h^2+{1\over6}f'''(x)h^3+O(h^4) \\ f(x+3h)=f(x)+3f'(x)h+4.5f''(x)h^2+...
4
votes
2answers
879 views

What's the intuition behind the conjugate gradient method?

I have been searching for an intuitive explanation of the conjugate gradient method (as it relates to gradient descent) for at least two years without luck. I even find articles like "An ...
0
votes
0answers
26 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
26 views

Computing the element-wise logarithm of a matrix exponential more efficiently?

Is there any known way to compute the element-wise logarithm of a matrix exponential more efficiently? Motivation: I am trying to an optimization problem (basically finding a specific Markov ...
0
votes
1answer
32 views

Operational cost of vector and matrix multiplications

Find the computational cost of a column vector $x$ multiplied by a row vector $v$ I computed n multiplication operations and n - 1 addition operations, so would that make for $n(n-1)$ operations ...
2
votes
1answer
310 views

Good convergence criterion for stochastic optimization?

This is a question that has bothered me quite long, as I have faced it many different optimization and equation solving problems. The basic idea is that one wishes to minimize $F(x)$ and has one ...
0
votes
1answer
46 views

Inequality constraints and the max function

Let $g_i(x):\mathbb{R}^{n} \to \mathbb{R}$, for $i=1,\ldots,n$, be continuous convex functions. Define $g_{\rm max}$ as $g_{\rm max}(x) \triangleq \mbox{max}_{i=1,\ldots,n}\{g_i(x)\}$. Define also the ...
0
votes
1answer
44 views

$ \sum_{i = 1}^{m}\lambda_i v_i v_i^T$ for $v_1,v_2, \ldots,v_m \in \mathbb{R}^n$ linearly independent has rank $m$ $(\lambda_i \neq 0)$

I often see this formula used in the rank 1 or rank 2 cases for Quasi-Newton methods, but I am wondering how this can be proven in the general rank $m$ case. As a linear algebra problem, I would like ...
3
votes
0answers
39 views

Optimizing intervals in piecewise function

I am not sure what the relevant tags are (or how to best described the problem). I have a piecewise function where for a particular interval element there is a known functional form (e.g. for ...