Questions tagged [numerical-optimization]
Numerical methods for continuous optimization.
0
votes
0answers
9 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 ...
1
vote
0answers
13 views
Show convergence of an algorithm within $m$ steps
I am trying to show that the following algorithm with will converge within $m$ steps.
Assumptions $A$ is symmetric positive definite with $m$ distinct Eigen values
then
\begin{align}
\text{for } &...
0
votes
0answers
24 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 ...
-3
votes
0answers
18 views
how to prove equation 3.19 in page 40 of “numerical optimization” second edition, Jorge Nocedal [on hold]
how to prove equation 3.19 in page 40 of "numerical optimization" second edition, Jorge Nocedal
enter image description here
2
votes
0answers
10 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
0answers
36 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
0answers
22 views
Is it possible to specify optimization algorithm in CVX? [closed]
I am using CVX as a bench mark to debug my MATLAB code for gradient descent algorithm. Although CVX gives me a good reference point, I was wondering if it is possible to ask cvx to solve optimization ...
0
votes
1answer
22 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
14 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
3answers
92 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 ...
1
vote
0answers
43 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
24 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
11 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
11 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
21 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
40 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
21 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 ...
2
votes
2answers
84 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 = \...
1
vote
1answer
36 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
55 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
53 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
15 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
0answers
85 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
1answer
37 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
11 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
23 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
36 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^...
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
33 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, ...
1
vote
0answers
28 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'...
0
votes
1answer
69 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
30 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))$$ ...
0
votes
1answer
35 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 ...
0
votes
0answers
17 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
\...
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+...
3
votes
1answer
117 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\...
0
votes
0answers
23 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
19 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
20 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 ...
0
votes
1answer
39 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
34 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
33 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 ...
0
votes
1answer
33 views
How to solve a minimize problem with maximize a subproblem
I have a minimization problem
$$\min_{x, y} \{f(x, y) + \max_{y} g(y)\}$$
which has a max subproblem inside it.
How to solve it? Will alternating optimizing converge to the optimum?
0
votes
0answers
38 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
1answer
17 views
What is a nontrivial minimizer?
I came across a statement that x is a nontrivial minimizer of some function, but couldn't find a definition of "nontrivial minimizer" on the Internet. Can anyone help point out some references for ...
3
votes
1answer
56 views
How can I check for the accuracy of numerical result to optimization problem?
How can I check for the accuracy of numerical result to optimization problem?
Or when is this possible?
Intuitively it could be possible at least to some extent, when one knows how to find analytic ...
1
vote
0answers
48 views
Reference request. Rigorous numerical optimization
I am looking for texts on Numerical optimization that are closer to Analysis definition-theorem-proof style texts.
EDIT: This is my first acquaintance with numerical optimization. My institution ...
2
votes
0answers
56 views
How to solve a large scale convex optimization problem?
Consider the following convex optimization problem in vectors $x$ and $y$
$$\begin{array}{ll} \text{minimize} & f(x,y)\\ \text{subject to} & g_1 (x)\le 0\\ & g_2 (y)\le 0\end{array}$$
...
0
votes
0answers
18 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
21 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$. ...
