Questions tagged [numerical-optimization]

Numerical methods for continuous optimization.

Filter by
Sorted by
Tagged with
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, \...

1
2 3 4 5
25