Questions tagged [optimization]
This tag is intended for questions on methods for the (constrained or unconstrained) minimization or maximization of functions.
1,000
questions
3
votes
2
answers
402
views
Poor test functions for optimization
I have been looking in detail into one of the many "meta-heuristic" optimization algorithms and became suspicious at how well it appeared to perform (compared to other methods like Nelder-...
1
vote
1
answer
70
views
How does the slack variable work in the problem formulation?
Recently I am reading a paper. In it, after they achieve eq(15), which is
$$ \operatorname{Tr}(\boldsymbol{Q})-\sqrt{2 \ln (1 / \rho)} \sqrt{\|\boldsymbol{Q}\|_F^2+2\|\boldsymbol{r}\|^2}+\ln (\rho) \...
2
votes
2
answers
107
views
Gradient descent for solving polynomial equations while encouraging variables to be nonzero
I would like to use gradient descent to "randomly sample" solutions to a set of homogeneous polynomial equations. Because the equations are homogeneous, setting all variables to 0 is a valid ...
0
votes
1
answer
68
views
Why using large bound to supplement inifinity in interior point method can be bad
Here in the documentation of mosek (https://docs.mosek.com/latest/pythonfusion/debugging-numerical.html)
we see:
Never use a very large number as replacement for infinity
. Instead define the ...
0
votes
2
answers
92
views
BFGS Constrained Optimization Failure Due to Precision Loss
I am trying to optimize the following objective function according to some constraints. However, the optimization fails at the first iteration with the message that the desired error was not ...
1
vote
2
answers
404
views
optimizing piecewise linear objective functions (perhaps non convex) with equality constraints
When I do my project, I need to optimize piecewise linear objective functions (perhaps non convex) with equality constraints.
The piecewise linear objective function may be not convex like this in the ...
2
votes
1
answer
189
views
Speeding up 3 body problem acceleration calculation
I want to find optimizations to my code for the 3BP, and more specifically computing accelerations. I'm using a data-driven approach, so I have a bodies structure ...
0
votes
0
answers
23
views
Loop Bounds vs. Iteration Domain in Polyhedral optimization
Context:
I was reading a tutorial on polyhedral optimization. But got confused while trying to translate the iteration domain (i.e. loop bound) to set builder notation.
Problem Description:
A code ...
0
votes
1
answer
50
views
MIP - Large Piecewise Linear Constraints Over Continuous Intervals
I'm currently trying to run a MIP (have access to both Gurobi and CBC) with a piecewise linear function having ~200 intervals for each of the ~30 x values I have. I am using the standard decomposition ...
1
vote
0
answers
28
views
1-dimensional nonlinear global minimization of kepler distance problem
I want to solve the problem to determine the next intersection of a Keplerian orbit with the Sphere of Influence of a celestial body to find the next intersection within one future period of the ...
0
votes
0
answers
22
views
dual svm square hinge loss
Let $x_1,\dots,x_n\in \mathbb{R}^n$, $y_1,\dots,y_n\in \{-1,1\}$, $\lambda \ge 0$
and $K$ be the invertible Gram matrix $K=(x_i\cdot x_j)_{ij}$.
Consider
$$
(P) \qquad \qquad \min_{a\in \mathbb{R}^n} \...
0
votes
0
answers
59
views
Help with inferring Network topology from Spectral templates
I am trying to use matlab and YALMIP to solve a graph learning problem of recovering eigenvalues from the eigenvectors of the covariance of sampled graph signal data. This is to implement the ...
0
votes
0
answers
38
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
94
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
87
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
106
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
57
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
115
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
108
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
155
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
59
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
43
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
51
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
415
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
65
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
111
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
12
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
58
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
59
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
192
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
61
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
62
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
119
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
98
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
209
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
40
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). ...
1
vote
0
answers
47
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
48
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
239
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
98
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
54
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
62
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
80
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
301
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 ...