Questions tagged [optimization]
This tag is intended for questions on methods for the (constrained or unconstrained) minimization or maximization of functions.
866
questions
3
votes
2answers
113 views
Which absolute and/or relative stopping criteria do use for Newton's method?
I saw many stopping criteria for Newton's method all around Web and books.
Some are defined from the residuals:
of either current iteration only:
$$
\|f(\mathbf{x}^{(k)})\| \leq \epsilon
$$
(https://...
0
votes
3answers
85 views
How can we solve the normal equations with limited memory?
I was asked this open ended question in an interview once:
How would you find a solution to the normal equations with limited memory?
Unlike Solving sparse least squares system with limited memory, ...
0
votes
0answers
25 views
similar function as fmincon in python?
I am trying to solve an optimization problem where I do not have the analytic form of the objective function. I am doing analysis by FEM to find a value for displacement in each iteration but I don't ...
0
votes
0answers
43 views
L2 norm optimization problem
I have an optimization problem where i need to find an image x, that is very close to x' such that:
monitor(x') is valid but monitor(x) is invalid. (output is valid
when the neural network output is ...
0
votes
1answer
89 views
Levenberg-Marquardt Algorithm for Black-box optimizations
I would like to create an optimization solution for black-box software calculations. Currently, I am using the Levenberg-Marquardt algorithm to update a vector of parameters, $\beta$, with residuals, $...
0
votes
1answer
40 views
How to generate neighbors for simulated annealing
I am learning about simulated annealing algorithm and want to create a general purpose one for optimizing continuous functions.
The problem I have is how to generate the neighbor points as candidates. ...
2
votes
0answers
78 views
Finding the extrema of a transition probability function for a quantum walker on a graph
The goal
Implement some Python code to find the extrema points of a function that is strongly oscillating.
The background
Let $G$ be a connected graph with $n$ points with Laplacian matrix $L(G)$. We ...
4
votes
1answer
61 views
SCP (Sequential Convex Programming) vs SQP (Sequential Quadratic Programming)
Can someone explain me at a high level the difference between an SCP and an SQP to solve a nonlinear (nonconvex) program?
Assume my problem is something like
$$\min\limits_x. \quad f(x)$$
$$s.t. \...
3
votes
0answers
49 views
What is this QR-factorization-based preconditioning called?
I have recently started to delve into someone else's code, and there is a part in there I don't quite understand. The authors of the code use some form of pre-conditioning to speed up the optimization....
2
votes
0answers
78 views
Black box optimization
I have a simulation which gives a scalar result depending on the choice of some continuous design variables. I am trying to minimize the output of the simulation. As a first step, I want to study the ...
1
vote
0answers
19 views
Minimize MAE for sum of powers
The model is
$$y_i=\beta\big(x_{i1}^\alpha+x_{i2}^\alpha+...+x_{im_i}^\alpha\big)+\epsilon_i\textrm{ for }i=1, 2, ..., n$$
I want to minimize the MAE, i.e.
$$\Sigma_{i=1}^n{\big|y_i-\beta\big(x_{i1}^\...
3
votes
1answer
50 views
Nonlinear root solving libraries which accept a Jacobian in band-storage
I'm in search for a library for solving large systems of non-linear equations, similar to MINPACK, but unlike MINPACK, can accept a Jacobian in band-storage.
My Jacobian is sometimes not invertible, ...
2
votes
0answers
130 views
Parametric nonlinear programming
I believe, I have a parametric nonlinear optimization problem.
The non-convex constraints depend on some parameters, and I seek a solution that satisfies these constraints for all parameters in a ...
0
votes
0answers
28 views
Compressed Sensing - CoSaMP algorithm
I'm trying to apply the compressed sensing theory (CoSaMP algorithm) to the DOA estimation in FMCW ULA (made of 48 elements). In the dechirped signals processing, I use a first FFT to solve the range ...
1
vote
1answer
70 views
How to best code a problem with scipy, cvxpy or Convex.jl with given generated data
I have a curve fitting problem of the form:
$$
\textbf{y} = f(\textbf{x}, a,b,c,d) + \varepsilon
$$
$$
f(x, a,b,c,d) = \frac{b}{e^{x\cdot a}+c}+d
$$
with the constraint
\begin{equation}
\begin{aligned}...
5
votes
0answers
77 views
Can automatic differentiation be used on the parameters of an optimization problem?
If I wanted to perform an optimization using a Newton-based solver where the Hessian and gradient of a function are known analytically, and then use a package such as Adept to compute a Jacobian ...
0
votes
1answer
161 views
How to compare 2D vector fields and minimize the difference?
I want to compare the field of two electrical currents and compare the resulting field to a magnetic dipol field and find magnetic momentum that minimizes the difference of the two fields.
My current ...
3
votes
1answer
109 views
A notion of resolution in inverse problems
Suppose I have a linear inverse problem of the form:
\begin{align}
Ax=b
\end{align}
I would like to reconstruct $x$ from the measurement $b$ via the objective
$$\min_x\{\vert\vert Ax-b\vert\vert^2_2+\...
1
vote
0answers
271 views
Minimax optimization with an oracle
I have an optimization problem of the following form: $$\min_y\left[\max_x f(x,y)\right].$$ It is fairly straightforward to minimize $f(x,y)$ over $y$ with $x$ fixed, and similarly to maximize $f(x,...
2
votes
0answers
81 views
How to derive the adjoint sensitivity equations for a least squares objective function gradient
The Problem
I would like to determine the gradient of a least squares objective function which depends on a vector of 40 parameters $p$, and the solution of a system of 32 differential equations. In ...
1
vote
1answer
93 views
Optimization on the multinomial manifolds of stochastic non-square matrices
Thanks for note! So I have an optimization problem with simple form but the decision variable is a large-scale matrix. My problem is similar to a existing problem here about multinomial manifolds and ...
0
votes
1answer
72 views
How can I deal with optimization problems that have a sum of functions of Z as a constraint when Z is the quantity to be minimized?
I have a problem where I have to minimize a certain quantity $Z$ subject to the following constraints:-
$w_1 + w_2 + w_3 = 1$
$\frac{f_1(w_1*Z) + f_2(w_2 * Z) + f_3(w_3 * Z)}{Z} >= k$
where $k$ ...
4
votes
0answers
63 views
Optimize linear equation using inner products and subject to L1 norm
I have a linear system of the form $A x = b$ where $A$ and $b$ are known, $A$ is "square", and $\lvert b \rvert_1 = \lvert x \rvert_1 = 1$. Unfortunately, I am working in a framework that ...
1
vote
1answer
51 views
Constraint programming problem with conditional constraints and some unknown indicator variables
I have an interesting little problem that I believe can be formulated in terms of optimization or constraint programming. I have a few dozen variables $a$, $b$, $c$ ... and a set of constraints that ...
2
votes
2answers
126 views
L1 least squares minimization with a sparse matrix
I have the following problem:
$$\min_{x\in \mathbb{R}^n}\|Ax-b\|_1$$
where the matrix $A$ is large and sparse. I am looking for methods/code that can minimize this efficiently. References are very ...
2
votes
0answers
28 views
Scaling tensor approximation by symmetric tensor decomposition with SciPy's L-BFGS-B
I am trying to approximate a symmetric tensor of which the values are in the range of [1e-7,1e-4], by a symmetric tensor decomposition of lower rank. For this I am using the L-BFGS-B method in SciPy's ...
5
votes
0answers
125 views
Inverse problem with uncertain forward operator
Suppose I want to solve a linear inverse problem. In this example we take a convolution with the kernel:
$$\frac{1}{(y^2+z^2)^{3/2}}$$
We only take a fixed $z$ for the computation and convolve with ...
2
votes
2answers
61 views
In a dynamical system, what might be a good reason why periodicity in an object's velocities is important?
I'm studying periodic motions in a dynamical system and, as a newbie, I narrowly think of an object's periodicity in its spatial x-y coordinates, but what might be a good reason why the existence of ...
0
votes
1answer
84 views
Interpreting multivariable root-finding results from Matlab's fsolve algorithm
Edit: So I was able to get the same value of r that's given, when coding up the sum of squares of function values directly in the script file, rather than on the Command Window. So, maybe there's a ...
2
votes
1answer
71 views
Reformulating a convex optimization problem with $x \mapsto \max(x,0)$ in the constraint
I am wondering if there is a well-known transformation allowing one to solve convex optimization problems of the form
$$\begin{array}{ll} \underset{x}{\text{maximize}} & r^T x\\ \text{subject to} &...
0
votes
0answers
67 views
Which algorithm is capable of solving a combinatorial optimization problem like this?
The problem I have at hand is a regression problem where each of $p$ inputs, $x_1, x_2, x_3, \cdots, x_p$, needs to undergo a variable transformation using one of $q$ basis functions from a set of ...
1
vote
0answers
87 views
N-dimensional optimization of moments of distribution function
Let's say I have a bag of marbles. Each marble has several attributes (color, diameter, surface roughness, weight).
I know that there is a statistical relationship between various marble attributes ...
1
vote
0answers
51 views
Quadratic optimization with nonlinear vector term
I wish to minimize the quantity $$W=1/2x^TAx-x^Tg(y)$$ with respect to $x$ and $y$, which are vectors of unknowns. $A$ is a sparse square symmetric positive definite matrix and $g(y)$ is a vector with ...
0
votes
0answers
70 views
Derivative-free ill-conditioned non-linear least squares
I am looking for a package which can solve (non-linear) least squares problems without the use of derivatives (because of an expensive model), but which also deals with ill-conditioning well (such as ...
1
vote
0answers
58 views
How to speed up the Mixed-Integer Quadratic Program process?
Currently, I am solving a problem in the format:
M is an integer as well. The problem that troubles me is that X is a vector in {0,1} with a size of 7000. I use the solver in https://github.com/...
1
vote
0answers
42 views
implementation of shell elements in a topology optimization algorithm
I am working on developing a topology optimization solver based on the finite element method and I want to add a triangular shell element in it. I used the classic finite element method but I didnāt ...
1
vote
0answers
35 views
What is the generalization of the resource allocation problem I'm dealing with here?
I'm dealing with a problem as follows:
I have a finite set of money š to spend over š different raffles, and I need to spend approximately to my budget, with the goal of maximizing my probability ...
7
votes
1answer
413 views
When and when not to use automatic differentiation
I am just learning (more) about automatic differentiation (AD) and at this stage it kind of seems like black magic to me. The second paragraph of its Wikipedia article makes it sound too good to be ...
4
votes
2answers
148 views
Solve two-player game - minimize the l-infinity norm of a matrix-vector product
I have a matrix $M$ with non-negative real entries, and I would like to minimize the objective function
$$\Phi(v) = \|Mv\|_\infty,$$
where $v$ is constrained to be a probability vector, i.e., $v_1+\...
1
vote
2answers
395 views
Jacobians with automatic differentiation
I have an objective function F: Nx1 -> Nx1, where N>30000. There are many sparse matrix/tensor multiplications in this function, so taking an analytic Jacobian by paper and pen is cumbersome.
...
2
votes
0answers
37 views
Convergence of Truncated Newton for non-convex Hessian
I was wondering if anyone could enlighten me about the convergence properties of the truncated newton method in case of a non-positive definite hessian $\nabla^2 f = H$. From the Book 'Numerical ...
3
votes
2answers
126 views
Optimization of expensive model with many parameters
I have a physical model which takes $\sim50$ parameters and gives $\sim2000$ outputs taking tens of minutes to run. I need to optimize these parameters to give outputs as close as possible to data. ...
0
votes
0answers
20 views
Benchmark instances for directed 3-Cycle cover
The directed 3-Cycle cover asks for a vertex-covering set of oriented cycles with at least three vertices per cycle such that every vertex is covered by exactly one cycle.
I have scrutinzed the ...
0
votes
0answers
34 views
Estimating the dimension of a solution space in nonlinear least squares
Suppose I have a nonlinear least squares problem,
$$
\min_{\mathbf{x}} || \mathbf{f}(\mathbf{x}) ||^2
$$
with $n$ residuals and $m$ parameters, so that $\mathbf{x} \in \mathbb{R}^m$, and $\mathbf{f} \...
2
votes
0answers
41 views
Non-negative Least Squares to perform Inverse Laplace with weights
I'm trying to perform the inverse Laplace transform of a (noisy) dataset $y_i$ using Tikhonov regularization:
$$\min \sum_{i=1}^{N} \left(\int_0^\infty e^{-s_i t} f(t) \, dt - y_i \right)^2 - \lambda^...
5
votes
0answers
22 views
Optimization for sampling multiple points of maximized minimum distance
I'm trying to find a way to sample new points that have maximum minimum-distance (maximin distance).
The current situation is where there are ns number of pre-existing sample points. I want N number ...
0
votes
1answer
133 views
Norm constraint in CVXPY
I'm trying to implement the algorithm outlined in https://arxiv.org/abs/1211.5608 on a small scale. I have a linear operator $\mathcal{A}$ which is defined as $$\text{trace}(A^*_l(hm^*))$$ where $$A_l ...
0
votes
1answer
31 views
How to check curvature of a vector valued function
In terms of numerical optimization, the newton-rapson method requires a pos. definite Hessian $\nabla^2f$ respectively pos. curvature for computing the next step $p_k$ by solving $$\nabla^2 f p_k = -\...
1
vote
1answer
41 views
Genetic algorithm: fitness proportionate selection using RMSD as fitness function?
I'm implementing a genetic algorithm to optimise $x$ so as to minimise the RMSD error $r(x)$ between my model and experimental data.
During the selection stage of recombination, I wish to select '...
1
vote
1answer
78 views
Making Hessian positive semidefinite
I have a large problem that I'm optimizing with Newton method. This involves a large sparse Hessian matrix.
For better convergence and not to get stuck prematurely, I'd like to make the Hessian ...
