Questions tagged [numerical-optimization]
Numerical methods for continuous optimization.
1,224
questions
1
vote
0answers
9 views
Minimizing the trace of a SPD-matrix subject to two trace equality constraints
I've encountered a problem where I need to check many (approximately $10^4$-$10^5$) minimum trace solutions subject to two trace inequality constraints. I've written this problem as an SDP and my gut ...
0
votes
0answers
5 views
Simulated annealing when the objective function is noisy?
Is there a variant of simulated annealing suitable for when the objective function is noisy? That is, we want to optimize $f(x)$, but we have available only $f(x) + \epsilon$ where $\epsilon \sim N(0,...
0
votes
0answers
51 views
+50
An Unconstrained Quadratic Optimization problem
Let $\mathbf{A}_n,~ n=1,\ldots,N$ be a set of $N$ known $M\times M$ complex matrices and $\alpha_n,~ n=1,\ldots,N$ be a set of $N$ real numbers. What is the solution of the following optimization ...
1
vote
0answers
15 views
Interpolation Error Problem.
Problem
Let $p_{n-1}$ be a polynomial of degree $\leq(n-1)$ that interpolates the function $f(x)=e^{x}$ at any set of $n$ nodes in the interval $[-1,1]$. Prove that the error obeys this inequality on $...
0
votes
0answers
23 views
Maximum Likelihood Estimation via Numerical Optimization
I am reviewing the maximum likelihood estimation where we derive the likelihood of the sample data parametrized by the unknown underlying distribution parameters and we maximize the likelihood with ...
0
votes
0answers
30 views
Optimizing $\arg\min_{U}||R-UMU^\dagger|| $
Consider the optimization problem
$$\arg\min_{U}||R-UMU^\dagger|| $$
with R and M hermitian matrix and U unitary and ||.|| is the Frobenius norm.
Are there known numerical method to solve it ?
I ...
1
vote
0answers
8 views
What is the computational complexity (in flops) of nonnegative least square optimization?
Suppose I have a vector $x\in \mathbb{R}^D$ and a matrix $U\in\mathbb{R}^{m\times D}$. I would like to solve the following nonnegative least squares optimization problem:
$a = \text{argmin}_{y\in \...
1
vote
0answers
21 views
Find Pareto front of a two-objective function of a two-dimensional variable of different dimmension.
I need to find Pareto front of two objective functions $J_g(g,h)$ and $J_h(g,h)$ where $g$ is a matrix (image) and $h$ is a small convolution (blur) matrix
\begin{equation}
J_{g}(g, h)=\frac{1}{2}\|h *...
0
votes
1answer
52 views
How can I solve this optimization problem - what concrete math algorithm should I use?
I need to run the following optimization problem in mobile phones. Therefore:
Need to run within 0.1 seconds using mobile phone's CPU (you know, kind of weak cpu)
Need the installation file to be ...
0
votes
1answer
44 views
Enforcing the standard deviation constraint in convex optimization
My optimization problem needs to have a constraint that I am not sure can be expressed in convex functions.
The vector I want to optimize is $x$ with size $m\approx 10$ . I have a tall $n \times m$ ...
0
votes
0answers
27 views
Numerical derivative of a function $f(x)$ by another function $g(x)$
Consider the following function derivative:
\begin{eqnarray}
\frac{\partial f(x)}{\partial y},
\end{eqnarray}
where $f(x)$ is a function and $y$ is also a function of $x$ as:
\begin{eqnarray}
y = g(x)....
0
votes
0answers
20 views
Create an equation from input data recorded of the system to match the output
I'm trying to formulate a general equation from a set of data recorded from a nonlinear system. The equation takes input values from multiple sensors and must be equal to the output sensor value. The ...
1
vote
0answers
20 views
Having a Problem Proving Halley's Method
I've been looking through the derivation of Halley's theorem presented here, and attempting to replicate it myself (as well as generalising it to higher orders). Unfortunately, partway through this ...
1
vote
0answers
49 views
Proving that $g(x) = \frac{L}{2} x^Tx -f(x)$ is a convex function
Suppose we have a function $f\in {C^1_L}$ such that ${\lVert \nabla f(x) - \nabla f(y)\rVert}_2$ $\geqslant$ $L{\lVert x - y\rVert}_2$ for some $L>0$.
We take a function $g(x) = \frac{L}{2} x^Tx -...
0
votes
0answers
18 views
gas network optimal design (using pyomo): Which optimization textbook?
I am currently working on the optimal design of a gas network (actually hydrogen) and particularly trying to optimally size pipelines' diameters (using pyomo python package) for a given graph. The ...
1
vote
0answers
63 views
Quadratic Approximation Method to find the maximum of $f(x)$.
This is a quadratic approximation method to find the maximum of a function $f(x)$.
The algorithm is as follows:
Choose three points $x_0, x_1, x_2$ such that $f(x)$ is unimodal function on interval $[...
4
votes
0answers
72 views
Questions about Lemma 7.3.2, Trust Region Conn's Book
I am reading Section 7.3.3 from [1]. A preview of the book can be found here. In this section, Newton's method is applied to solve the secular equation
$$\phi(\lambda) = \frac{1}{||s(\lambda)||_2} - \...
0
votes
0answers
12 views
Can we approximate the linear sum assignment solution with bistochastic matrices?
This question was concerned with random bistochastic matrices and the answer pointed out an algorithm, that can "bistochastize" a starting matrix $\boldsymbol{X}$ (with positive elements ...
0
votes
1answer
46 views
Optimizing product of $L^1$ norms of a function and its second derivative
Let $\eta : \mathbb{R} \to \mathbb{R}_0^+$ be a function of class $C_0^2$ such that $\eta(t) \geq 1$ for $|t| \leq 1/2$. Here $\mathbb{R}_0^+$ denotes the set of all positive real numbers including ...
2
votes
1answer
76 views
I want help in formulating a mixed integer linear problem formulation.
I want the following help in linear fashion:
I have a vector: $P(n) = [1, 2, 3, 4, 5,...,n]$
I have binary variables with length of $P:y(1),y(2).....y(n)$. These variables, y(i) can only take $0$ or $...
1
vote
1answer
52 views
How to show applying gradient descent on a differentiable convex function generates a non-increasing sequence?
Let $f:\mathbb{R}\to\mathbb{R}^n$ be a differentiable convex function, i.e., $f(y)\geq f(x)+\langle \nabla f(x), y-x\rangle\,\,\forall x,y\in \mathbb{R}^n$.
We do not assume that the gradient is ...
1
vote
0answers
18 views
Upper bound for optimal parameter in Tikhonov regularization
For ill-posed equation
$$Ax=b$$
where $A\in \mathbb{R}^{m\times n}$ and $b=b_{ex}+e$ is perturbed by noisy vector $e$ with unknown exact data $b_{ex}=Ax_{ex}$, I want to use the Tikhonov ...
1
vote
1answer
37 views
Modification of Linear Least Square
We are given a matrix $A$ and vectors $b,d$ of appropriate size and we want to solve
$$\begin{cases}\min_x ||Ax-b||_2 \\ \text{s.t.}\\ 0\leq x\leq 2d\end{cases}$$ where the inequality has to be ...
0
votes
1answer
42 views
Question on Hessian Matrix and Gradient Descent Step
Some context before my question
I'm trying to make some object tracking software where the tracking is achieved by minimizing an energy function. The energy is a function of the pose parameters of the ...
0
votes
0answers
14 views
Who has implemented the M2SPSA optimizer?
I ran across this paper, which is an update to the second-order simultaneous perturbation stochastic approximation (SPSA) black-box optimizer. Has anyone seen it implemented and/or is there a code ...
3
votes
2answers
132 views
Select five vectors that upon undergoing elementwise multiplication are most similar to another vector
I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows.
$$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
2
votes
1answer
77 views
Is this property a theorem somewhere?
Apologies if the question is trivial.
Consider the following statement.
Let $f(\mathbf{\theta})$ be a convex, smooth and differentiable function of parameters $\mathbf{\theta}\in \Re^p$. So, $arg \...
0
votes
0answers
72 views
Time complexity of conjugate gradients applied to normal equations
Consider a least squares problem $\min_x \|Ax-b\|^2$ with a rectangular matrix $A$. One way to solve it is to use the conjugate gradients method applied to the normal equations $A^\top A x = A^\top b$,...
6
votes
1answer
49 views
Sparse PCA vs Orthogonal Matching Pursuit
Can't wrap my head around the difference between Sparse PCA and OMP.
Both try to find a sparse linear combination.
Of course, the optimization criteria is different.
In Sparse PCA we have:
\begin{...
0
votes
0answers
37 views
What criteria guarantee that gradient descent tends to a local minimum?
Is there a set of criteria that a function $f$ can have so as to ensure that the gradient descent algorithm leads us to a local minimum?
If so, why do such criteria ensure reaching a minimum?
1
vote
0answers
49 views
$k^{-k}$ converges superlinearly but not quadratically.
A sequence $(x_k)$ converges to 0 superlinearly if $||x_{k+1}/x_k||\to0$ as $k\to\infty$.
A sequence $(x_k)$ converges to 0 quadratically if there exist $N,M>0$ such that $||x_{k+1}/x_k^2||<M$ ...
0
votes
0answers
31 views
How to minimize this function of two variables
I'm trying to minimize this function of $s$ over some bounds of $x$ and $y$.
The function is
$$\frac{s x y + 1}{a b s^{3} x y + a s^{2} \left(b + x\right) + s x y + 1}$$
$a$ and $b$ are constants, and ...
0
votes
1answer
48 views
$f(x) = \frac{1}{2}x^TQx+q^Tx$ has a unique minimum if and only if Q is positive definite.
I am trying to prove the above result. I can show one direction but am having trouble with the direction "unique minimum implies positive definite".
Edit: I have seen related questions such ...
3
votes
1answer
57 views
Derivation of Gradient Descent Update Rule
I am trying to understand the interpretation of Gradient Descent provided in Ryan Tibshirani's 2019 Convex Optimization course scribed notes:
http://www.stat.cmu.edu/~ryantibs/convexopt-S15/scribes/05-...
0
votes
0answers
46 views
Numerically dense but dynamically sparse optimization problems
From the Ceres Solver's documentation on nonlinear least-squares:
ellipse_approximation.cc fits points randomly distributed on an ellipse with an approximate line ...
3
votes
0answers
72 views
Obtaining $h_i$ by evaluating $f(s)=\sum_{i=1}^n \exp(-h_i s)h_i$
Suppose I'm able to obtain values of $f(0),f(1),f(2),\ldots,f(m)$ with $f$ defined as follows:
$$f(s)=\sum_{i=1}^n \exp(-h_i s)h_i$$
Is there a numerical procedure to obtain $h_1,\ldots,h_n$? We know ...
0
votes
0answers
33 views
Optimization on $X^TX$ with all positive entries
Suppose I have an algorithm $\mathit{A}$ that can solve the optimization problem over certain functions $g: Sym(n) \to \mathbb{R}$. Now given $g$, let $f: \mathbb{R}^{k ,n} \to \mathbb{R}$ be another ...
0
votes
1answer
63 views
How to solve linearly constrained quadratic program with many variables?
Suppose I have the following quadratic program
$$\begin{array}{ll} \underset{v_1, v_2, \dots, v_m \in \mathbb{R}^n}{\text{minimize}} & \displaystyle\sum_i v_i^T a_i + \displaystyle\sum_{i,j} \...
0
votes
0answers
29 views
The projection onto the intersection of the set of unitary matrices and the set of matrices with entries $\{0, \pm 1\}$
The title really says it all.
I am looking to solve the following problem:
$$ \underset{U}{\text{minimize}} \; || \mathbf{A} - \mathbf{U}||_{F} $$
$$ \text{subject to} \; \; [\mathbf{U}]_{i,j} \in \{-...
3
votes
1answer
248 views
Intuition behind Newton's Forward and Backward Interpolation
I was studying Newton's Forward Interpolation and backward interpolation in a computer science course and the form that I got them in, is as follows-
Forward Interpolation
$$f(x)=y=y_0+\binom u1 \...
1
vote
0answers
37 views
Krylov Subspace and Conjugate Gradient
On each iteration we will compute a diagonal preconditioning matrix $\mathbf{D}$ (we omit the subscript $n$ ). $\mathbf{D}$ is expected to be a rough approximation to the Hessian. In our experiments, ...
1
vote
1answer
77 views
Conjugate Gradient and Krylov Subspace Method
In HF, on each iteration the CG algorithm is used to approximately compute
$$
\mathbf{d}=-(\mathbf{H}+\lambda \mathbf{I})^{-1} \mathbf{g}
$$
where $\mathrm{d}$ is the step direction, and $\mathrm{g}$ ...
0
votes
0answers
13 views
Is finding a point lying inside a convex set but outside another a convex problem?
Consider two convex volumes, $V_1\subset \mathbb{R}^n$ and $V_2\subset \mathbb{R}^n$. It is easy to find a point inside either of them, or their intersection $V_1 \cap V_2$, as the problem of finding ...
4
votes
1answer
54 views
Algorithms for Stochastic Continuous Optimization
Question
I have a continuous optimization problem of the form $$ \max_{x \in \mathbb R^n} f(x), $$ where $f:\mathbb R^n \rightarrow \mathbb R$ is mostly smooth and bounded above. The standard ...
0
votes
1answer
60 views
Numerical Model Predictive Control: Optimize states or Optimize control input?
I have read a number of different sources on numerical model predictive control. Something that comes up is if you optimize over states or optimize over controls. I have seen videos where people talk ...
1
vote
1answer
69 views
What are good curve fitting methods for highly non linear functions in the interval $[0, 1]$
I have two sets of experimental data X and Y. The data in both sets are related by $y = f(x),\hspace{0.2cm} x \in X,\hspace{0.2cm}y \in Y$ the function $f(x)$ is unknown. The data is in the interval $...
1
vote
1answer
52 views
Finding the relationship between Gradient and Hessian to improve convergence rate
I ask for help from optimization experts:
Article Finite-Time Convergence in Continuous-Time Optimization - http://proceedings.mlr.press/v119/romero20b/romero20b.pdf contains section 4. Second-Order ...
0
votes
0answers
9 views
Constraints dependent on feasiblity of points with other constraints.
Does some theory exists for optimization problem where a certain constraint can only be computed when all other constraints are satisfied. Let us assume that there are two sets of constraints, set-A ...
1
vote
1answer
83 views
Finite Differences Metods for the Laplace's Equation.
My question is not about content, but I would like to ask for references to a topic I have never studied. I need to do research on the following topic:
"Finite Difference Methods for the One-...
0
votes
0answers
19 views
optimization with nonconvex constraint
I am working on a min-max optimization problem that I have converted to the following form:
$\displaystyle\min_{\textbf{x,y}} z$
$f_i(x_i,y_i,z)=\frac{x_i}{y_i-a_ix_i}+\frac{x_i}{b_i-c_ix_i}-z\leq0, \...
