Questions tagged [optimization]
This tag is intended for questions on methods for the (constrained or unconstrained) minimization or maximization of functions.
990
questions
0
votes
0
answers
25
views
Methods for delaying the "break" in non-linear least squares optimisation when the step size gets too small?
I am using the Levenberg-Marquardt method for calibration purposes. Typically, the RMSE of my calibration looks like:
I want to break the algorithm when the algorithm step-updates start to slow down, ...
2
votes
1
answer
87
views
references for optimization in the context of parameter identification with finite elements
i am performing parameter identification for a non-linear partial differential equation (elasticity) that I solve with finite elements.
My optimization problem is a non-linear least squares data-...
5
votes
0
answers
81
views
optimization scaling techniques
Consider a convex QP of the form
$$
\min_x \bigl\{\tfrac12 x^\top Q x + q^\top x : Ax\leq b\bigr\}\tag{P}
$$
with dual
$$
\min_y \bigl\{\tfrac12 (A^\top y + q)^\top Q^{\dagger} (A^\top y+q) + b^\top y ...
0
votes
0
answers
60
views
Why researchers use MATLAB based YALMIP or CasADi for MPC?
I was looking at various research papers and most of the researchers use CasADi, YALMIP, MPCTools to implement MPC. My question is "Why researchers use MATLAB based YALMIP or CasADi for MPC ...
3
votes
1
answer
149
views
Role of rotation's pivot point in optimization?
In this paper, the authors describe how to use locally rigid transformations (sampled on nodes in space) to deform mesh vertices. In the paper, rotations are relative to the pivot point, which ...
0
votes
0
answers
47
views
PETSc non-linear solvers (SNES): specifying single Eval & Jacobian function
The PETSc documentation example of a non-linear solver call has the user provide separate functions for the Jacobian and function evaluations:
...
1
vote
1
answer
100
views
Improvement to naive gradient descent implementation for the Thomson problem
I have a Python program (available on github) that uses naive gradient descent to find approximate solutions to the Thomson Problem. It works surprisingly well, but I've been wondering if there's a ...
38
votes
10
answers
9k
views
stupid + stupid = brilliant in scientific computing
I'm interested in examples of very effective methods in scientific computing that are the sum or naive combination of very ineffective or bad ones.
2
votes
2
answers
101
views
Automatic Differentiation In the Presence of Jump Points
I have a complex monte-carlo cashflow model that traditionally uses the finite difference (FD) method to calculate its derivative at any given point. To improve model performance, I coded forward-mode ...
1
vote
2
answers
124
views
Are there good block sparse matrix solver libraries?
There are some great libraries with linear solvers for sparse matrices - SuiteSparse is the obvious one. The methods work on sparse matrices with scalar entries.
However, often in optimization ...
3
votes
0
answers
59
views
What 2nd-order optimization algorithms have convergence guarantees for strictly- but not strongly-convex problems?
A function $f$ is strictly convex if
$$f((1 - \lambda)x + \lambda y) \le (1 - \lambda)f(x) + \lambda f(y)$$
with equality if and only if $x$ and $y$ are equal.
This implies that the second derivative ...
1
vote
1
answer
57
views
Optimization: Find minimizer along linestring
Given some function f(x) and a set of points A representing a linestring (or polygonal chain), I am searching for the point on ...
1
vote
1
answer
40
views
Name this optimum-within-convex-hull algorithm: State is a convex combination of hull vertices; Nonnegativity ensured by reparameterization
I'm looking for the "official" name(s) for a procedure for optimizing a convex loss function over a convex subset. This seems to be a default/naïve algorithm that folks come up with before ...
1
vote
0
answers
50
views
Beyond the LP relaxation of binary least squares
I have a binary quadratic program with a convex objective function, of the form,
\begin{align}
\text{minimize}\;\;& x^tAx+b^tx\\
\text{subject to}\;\;& x_i\in\{0,1\}
\end{align}
where $A$ is ...
5
votes
3
answers
406
views
Packages suitable for numerical optimization of functions with discontinuous gradient at the point of minimum
Are there packages for numerical optimization in julia or python, or in any other system for scientific computing, capable of taking into account the discontinuity of gradient at the minimum point? ...
1
vote
0
answers
63
views
min(f(x)) is convex or concave based on type of f(x)
i have f(x) that is concave function. My question is g=min(f(x)) is concave or convex? And max(g) is concave or convex? there is a theorem for this?
1
vote
1
answer
90
views
Possible bug with scipy.optimize SHGO sobol: TypeError: <lambda>() takes 1 positional argument but 3 were given
I have been trying to perform some global optimization with SciPy optimizer SHGO
and I've had issues with the sampling method 'sobol'. Specifically, I get an error ...
0
votes
0
answers
54
views
Solving a minimization problem without flattening inputs?
I am reading this paper on improving time steps for solving simulation problems:
https://www.math.ucla.edu/~jteran/papers/GSSJT15.pdf
The authors developed this energy function:
$$E(x) = \frac{1}{2\...
0
votes
0
answers
11
views
Estimating/Tuning a Coefficient from a Quadratic Programming Objective Function so Optimal Solution Reflects Data
I am working on a problem that is a modified version of a two-knapsack knapsack problem. I am able to find the optimal choices by using Gurobi. However, I would like to estimate a coefficient that is ...
0
votes
0
answers
56
views
Rank-one updates for symmetric matrix eigen-system
Are there existing implementations for rank-one updating of symmetric matrices eigensystems?
This is the mathematical statement of the problem. Let $S=QDQ^T$
$$S + vv^T = QDQ^T +vv^T = Q_{new}D_{new}...
0
votes
1
answer
56
views
The row loss gradients
Suppose the original loss function is
$$\min_{\mathbf{V}}\frac{1}{2}\|\mathbf{V} - Q(\mathbf{V})\odot\mathbf{U}\mathbf{E} - \beta Q(\mathbf{V})\mathbf{V}\|_2^2$$
where $\odot$ denotes the element-wise ...
1
vote
1
answer
136
views
Python libraries for larges scale optimization/rootfinding
I have been dealing with the standard libraries of scipy.optimize for rootfinding and optimization problems, but the problems i want to solve are very large, which makes the standard solvers run out ...
1
vote
0
answers
58
views
Gradient based optimization involving a black box function where gradients (not the objective) are approximated using a surrogate model
Can we use gradients of surrogates of a black box function and the actual function evaluation for optimization involving an expensive black box simulation? Is there any merits to it?
1
vote
0
answers
41
views
Where to find datasets to research the optimal parameter search space for HPC systems? [closed]
I am a student researcher who is new to the HPC domain.
I have recently taken a project where I am working on optimizing the parameter search space (both application level and hardware level ...
3
votes
0
answers
51
views
When is it worth it to use the dual simplex method with warm starts?
Let's say I have a linear program that incurs a series of slight changes to it, so I want to warm-start it. I've read various things that recommend using the dual simplex algorithm over the primal ...
2
votes
0
answers
116
views
Is the Hessian of the strain energy of a hyperelastic material positive definite in general
Is the spatial second derivative of the strain energy of a hyperelastic material positive definite in general?
If this is not a general property of hyperelastic materials are there techniques for ...
2
votes
0
answers
97
views
Can we get the exact solution of large-scale quadratic programming problems (quadratic objective, linear inequality constraints) using KKT condition?
Crossposted at MathOverflow
Consider a quadratic programming problem with the following format:
$$
\text{min} Q(x) = c^Tx+\frac{1}{2}x^TDx \\
$$
$$
\text{s.t.} Ax\leq b, \\
x\geq 0
$$
where $D$ is a $...
5
votes
1
answer
206
views
How to optimize an approximated matrix multiplication?
[UPDATING]
The old one is a simplified version of the current one. Here is a solution based on the answer proposed by professor Bangerth down below. To describe what I am trying to do, first rewrite ...
1
vote
0
answers
38
views
step size cycling in semismooth newton for convex problem
I am using backtracking linesearch to globalize a (semismooth) newton solver to minimize a (strongly semismooth) strongly convex function , and I am observing something strange (which may be a bug). ...
0
votes
0
answers
47
views
Grid search for bi-level optimization
Apologies if this isn't the best place to ask this question, and further apologies for such a basic question (I am a secondary school graduate and have not learned very much yet). Please direct me to ...
0
votes
0
answers
27
views
Consering numerical implementation of gradient based method for control system
I'm trying to reproduce the results in Optimal consensus control of the Cucker-Smale model by Bailo et al. The system is the following,
the adjoint variables,
and the algorithm,
I tried to ...
1
vote
0
answers
46
views
Vehicle passenger assignment with capacity constraint
Problem Background
I'm trying to find a solution to the following passenger matching problem:
The network is represented by graph $G=(V,E)$. $V$ is the set of nodes/stations. $p_{ij}$ is the profit of ...
1
vote
0
answers
43
views
function optimization using reinforcement learning
I'm regular with optimization process, but this time, I would like to optimize a multiobjective function with reinforcement learning, using python.
Of course I already have some testing functions (...
4
votes
1
answer
233
views
Selecting most points from a set of points with distance constraint
I am looking for an algorithm to select the largest subset of $M$ points from a set of $N$ points ($M < N$) such that no point is within a certain minimal distance d to any other point in $M$? I ...
3
votes
0
answers
58
views
Adjoint method for imaging with an "analytical" forward model
I am working on tomographic image reconstruction (radar regime) of the dielectric properties of objects. As part of my work, I have programmed a ray tracer. This ray tracer is, in a way, purely "...
2
votes
0
answers
92
views
Parameter choice rules for L1 regularization?
I am solving an L1 regularized least squares of the form like:
$$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda {\left\| \boldsymbol{x} \...
0
votes
1
answer
53
views
Optimization of the log-absolute: reformulating to DCP-compliant on Julia
I am trying to reformulate this optimization problem in order to get a DCP-complaint expression on Julia (I am using the ...
0
votes
0
answers
59
views
Faster convergence for minimizing least squares of forward modelling problems
This specific question was raised from optimizing parameters of column experiments in the hydrogeological context. I want to optimize a parameter of interest (in this case $D$), based on experimental ...
1
vote
0
answers
76
views
Linear PDE solution with constraints
Consider the following linear PDE:
$$\nabla_q V(q) - M_d(q)M^{-1}(q)\nabla_q V_d(q) = 0,$$
where $V(q)$ and $M(q)$ are known and $M_d(q)$ is a grey box function (e.x., $M_d(q)$ is fitted using a ...
3
votes
1
answer
271
views
What problems does softmax() solve and when should I think of using it - in simple terms
I just for the first time saw the function softmax() in this SO answer to How do I use a minimization function in scipy with constraints and was intrigued.
Another way of weighting variables where ...
0
votes
0
answers
41
views
Optimizing multivariable without known function (only input & output), but it's a polynomial
I have multiple set of input (5 parameters) and output from an unknown function. But I know this is a polynomial function.
What method can I use to optimize to find the polynomial variable that can ...
1
vote
0
answers
27
views
Optimizing noisy but deterministic one-variable functions within an interval
I am looking for advice on what numerical methods to consider to solve optimization problems like the following, ideally with as few evaluations of the objective function as possible.
I am looking to ...
3
votes
1
answer
86
views
Reuse linear mapping that provides the solution to least squares problem using LAPACK
LAPACK.gglse allows me to solve
min x^T Q x
s.t. A x = y
(in my present use case, $Q$ is symmetric positive definite)
without having to think about the numerical ...
0
votes
0
answers
34
views
Difference between minimizing a function by gradient descent and by norm minimization?
I have working on 2 ways of training a neural network. The first method uses gradient descent updates the model with Adam optimizer. the second method minimizes the norm of the gradient of the ...
1
vote
0
answers
29
views
Non-Linear Distributed Delayed Kalman Filter
I have a system $\vec{x}_{i + 1} = \vec{x}_i + W_i$ where $W = N(\vec{\mu}, \Sigma)$. For some matrix $H_i$, let $y_i = H_i$ and let $z_i = y_i + R$. Where $R$ is some random variable. We are given $...
2
votes
1
answer
92
views
Min supporting line of a set of points
I am following along Rourke's book and I am trying to do the excercies mentioned in this SO post:
Min supporting line for a set of points
Design an algorithm to find a line 𝐿 that:
has all the ...
0
votes
2
answers
162
views
Minimize ||AX - Y|| for a matrix A that lies in a special orthogonal group
Let $X$ and $Y$ be two given $k\times n$ real matrices. If $A$ is a $k\times k$ real matrix then $AX - Y$ is a $k\times n$ real matrix. Applying the Frobenius norm $\| AX - Y \|$, we get a non-...
1
vote
0
answers
74
views
How to scale gradients in a gradient descent algorithm?
I am training a neural network with the multiobjective steepest gradient descent algorithm. The want to steer the direction of the gradient descent so that I land up at a point slightly above where I ...
1
vote
1
answer
286
views
Finding the parameters of a function via curve fit
I'm trying to estimate the parameters (v, n, k) defined in fit_func. I tried the default least squares fit but I couldn't find the parameters successfully.
...
-1
votes
1
answer
75
views
How to find armijo step length for a neural network?
The armijo step length formula states that
f(x+lr*descent_direction) <=f(x)+c*lr*f_gradient*descent_direction
In the above formula lris the learning rate and f ...