Questions tagged [optimization]
This tag is intended for questions on methods for the (constrained or unconstrained) minimization or maximization of functions.
812
questions
2
votes
0answers
45 views
Does BFGS preserve the bandedness of the inverse hessian?
In the BFGS method we perform iterations by calculating an approximation $\boldsymbol{H}_k$ to the inverse Hessian $\boldsymbol{H}$ of the objective function. This method belongs to a family of ...
-1
votes
0answers
20 views
One to Many Assignment Problem where agents can't be assigned the same task if they share a trait
In the one to many assignment problem, many agents can be assigned to a task. In my problem, I want to assign many agents to a task, but for all of the agents assigned to that task, they must share a ...
-1
votes
0answers
48 views
What is going wrong in the way I set up constraints for optimization solver?
I have the following dynamical system,
Equation 1:
$\frac{d \phi}{dt} = -M^TDM\phi$
Equation 2:
$\frac{d \hat\phi}{dt} = -M^T\tilde{D}M\hat \phi$
Equation 1 represents the exact dynamics of a ...
-1
votes
1answer
38 views
Detecting degenerate triangles with very thin structures
Between the two ears in the following bunny images, there are some degenerate triangles I want to detect. It looks like a volume-less thin slits.
If the question is not clear, please let me know.
1
vote
0answers
35 views
Inverse Newton Method for optimization: is this the correct algorithm?
I am trying to implement the algorithm in this article. I have already asked a question before about it here, and I am trying to figure out what I am doing wrong. This time, it's this section of the ...
4
votes
2answers
54 views
MInimizing cost function using iterative search for a minimum method
I want to estimated the parameters $\ \hat{\theta} $ of a model using an iterative search for the minimum of a cost function. The cost function is defined as follows:
$$ V_N(\hat{\theta}) = \frac{1}{...
-1
votes
0answers
27 views
Pseudocode for implementing Tunneling Algorithm
I‘m searching for coding examples (Python, matlab, C++, ...) of the tunneling algorithm for finding global minimums in terms of Optimization. Even though some Users have claimed to implement the ...
4
votes
1answer
117 views
Which optimization method can be used to do the following?
I've the following system of equations for studying information flow in the below graph,
$$ \frac{d \phi}{dt} = -M^TDM\phi + \text{noise effects} \hspace{1cm} (1)$$
Here, M is the incidence ...
2
votes
2answers
85 views
What online optimisation algorithm can be used for a noisy cost function?
I am trying to optimise a function, but the function can be noisy and give varying results for the same parameters. Furthermore, it needs to be online, as the data from each new iteration happens ...
3
votes
2answers
165 views
log(det(X)) in Semidefinite Programming
I have been solving problems of the form $$max \ log(det(A)) \\ s.t. \ A = A^{T} \succeq 0, \\ p_{i}^{T}Ap_{i} \leq b_{i}$$ where $b_{i}$ and $p_{i}$ are input vectors (to be clear there is more than ...
4
votes
1answer
71 views
Arbitrary Precision Optimization Libraries?
Are there any well-known optimization libraries (ideally with Python bindings or even in Python) supporting (unconstrained) minimization (of $f:\mathbb{R}^n \to \mathbb{R}$ for $n$ for $n\sim 10^1,10^...
0
votes
0answers
33 views
exploding gradients in gradient descent procedure of multi-output ridge regression
Multi-output ridge regression:
$$W^{*}=\underset{W}{\arg \min } \frac{1}{\mathcal{N}}\|Y-WX\|_{F}^{2}+\lambda\|W\|_{F}^{2}$$
There are $Q$ outputs, $N$ samples, and $P$ covariates (features).
$\hat{...
4
votes
1answer
62 views
How to form the following constraint in cvx?
The optimization problem is
$$\min_{x\in K} \|h - x\|_2$$
where
$$K = \{v\in R^n : \exists \lambda \geq 0\ v_1=v_2=\ldots=v_k=\lambda \ \text{and} \ |v_i| \leq \lambda \ \text{for} \ i=k+1,\ldots,n \...
3
votes
1answer
86 views
What are the advantages of Level Set method in topology optimization?
I am studying the different topology optimization methods. There are numerous resources out there but when it comes to comparing different algorithms, in terms of strengths and weaknesses most of ...
0
votes
0answers
45 views
Are there unproblematic max constraints when modelling problems as Linear Programs?
Suppose we have a linear objective function that we want to maximize.
All variables are from the set of reals.
We have a constraint of the form:
$$\max(x_1,x_2) + \max(x_3,x_4)\leq c\,, \text{ with } ...
1
vote
0answers
15 views
SHREC 2010 Descriptors
I will appreciate if I may find someone how can clarify for me the part regarding the quality of feature descriptor, shown in the figure below:
and this screenshot is from the article: SHREC
All my ...
2
votes
0answers
83 views
Proving convexity of Frobenius norm and correlation function formulations of an optimization problem
I have been working on formulating my requirements in the form of an optimization problem in a multi-output regression setting.
Firstly, I would like to make the variables I used in the problem and ...
3
votes
1answer
57 views
Evaluate 3D Shape Descriptor
I'm trying to create my own 3d shape descriptor, the idea is that how I may evaluate how much my descriptor is well and good?
What I checked is that they evaluate descriptors through shape matching, ...
1
vote
0answers
59 views
Conjugacy in Non-linear Conjugate Gradient Descent
In linear conjugate gradient method, our goal is to solve the system of linear equations $$Ax = b$$ where A is a symmetric positive definite matrix, and that is equivalent to finding the minimizer of ...
0
votes
0answers
18 views
How to use the solution of a multistage stochastic program?
Given a multistage stochastic program, its solution (if it exists) consists of the first decision vector, as well as all the recourse decision vectors for all possible scenarios of an event tree. But ...
8
votes
1answer
198 views
When training a neural network, why choose Adam over L-BGFS for the optimizer?
More specifically, when training a neural network, what reasons are there for choosing an optimizer from the family consisting of stochastic gradient descent (SGD) and its extensions (RMSProp, Adam, ...
2
votes
1answer
50 views
Could the convex problem be tackled by CVX?
I want to solve the convex optimization as follows:
\begin{align}
\underset{X_1,X_2}{\min} &\ -\frac{1}{N}\sum_{i=1}^N\log\det\left(I+H_i^HX_2H_i\right)-\log\left[1+h^H(X_1+X_2)h\right]\\
&\...
2
votes
0answers
40 views
Fitting a plane with the Prewitt gradient operator
Prewitt gradient operator
Show that the Prewitt gradient operator can be obtained by fitting the least-squares plane through the 3 × 3 neighborhood of the intensity function.
Hint: Fit a plane to ...
4
votes
0answers
41 views
Nonlinear least squares optimized Jacobian calculation
I have a nonlinear least squares problem, in which I am trying to minimize residuals which can be divided into four classes:
$$
\min_x ||\epsilon(x)||^2 + ||\xi(x)||^2 + ||\delta(x)||^2 + ||s(x)||^2
$$...
1
vote
1answer
69 views
Prove that the set of maximizers are independent of parameter in the objective function
A maximization problem reads as
$$ J(y) = \sum_{k=1}^{K} \sigma_k(y)^q \mathop{\rightarrow}^{y} max$$
where $q \in [1,\infty]$ is a user-defined parameter and functions $\sigma_k, k=\{1,\dots,K\}$ ...
3
votes
0answers
51 views
Methods to approximate obective function gradients from point cloud
Problem statement:
Assume that I have an objective function $f(x)$ which takes as input a $D$-dimensional vector $x\in\mathbb{R}^D$, and that $f(x)$ is sufficiently smooth. Assume further that I ...
1
vote
0answers
66 views
How to approach geographic data interpolation by distance?
let's say I have a set of geographic locations (lat, lng) resulting from a query. Those locations have some kind of internal ranking, my set is sorted by this number in a descending order.
Now I'm ...
2
votes
1answer
56 views
How to obtain only the value of my variable using scipy.optimize.minimize
when I minimize a function using scipy.optimize.minimize I get a big list of things as a result, but I would like to only get the value of my variable, this is my code
:
...
2
votes
0answers
55 views
Multilevel minimization - boundary conditions
I am interested in minimizing
$$min_{x \in R^{n^l}} f^l(x),$$
where $f^l(x)$ is nonlinear objective function arising from discretization of PDE. I would like to use nonlinear multilevel minimization ...
3
votes
1answer
68 views
Calculate Transformation Matrix between two sensors
My question is if I can calculate the transformation matrix between two sensors.
Each sensor provides a $4\times 4$ matrix for every timestep recorded.
The sensors are moving and have some noise in ...
3
votes
2answers
54 views
Optimal line such that maximum points are between an upper and lower boundary
I have some 2D data and would like to find a line $y = mx + b$ such that a maximum number of points from the data is captured within the area between $y = mx + b + margin$ and $y = mx + b - margin$. ...
6
votes
2answers
136 views
How to solve calculus of variations problems numerically?
For example, how to solve the well-known isoperimetric problem (i.e., to enclose the largest area with a fixed-length curve)?
We can simplify things a bit and fix the two ends of the curve at $[a,0]$,...
0
votes
0answers
30 views
Method for implementing QP solver with matrix terms?
I am trying to implement (in code) a QP solver for the following equation:
$$\min_{u} u^{T} Wu$$
$$s.t. \; \beta u = \tau_{ref}$$
$$ Au \leq b $$
See this document, section 5.1 (Page 35)
$u$ is a ...
1
vote
0answers
66 views
Ramp least squares estimation
With some given $s$ value, let
\begin{equation}
\begin{aligned}
h(\beta)&=\min(\sum_{i=1}^n(Y_i - X_i\beta)^2, s)\\
&=\sum_{i=1}^n(Y_i - X_i\beta)^2-\max(0, \sum_{i=1}^n(Y_i - X_i\beta)...
2
votes
1answer
56 views
Python-accessible industry-standard for unconstrained minimization that converges to machine precision?
I have an unconstrained minimization problem of many variables for which I know the gradient exactly. I turned to the conjugate gradient method contained in ...
2
votes
0answers
46 views
Interesting maxmin mixed integer/real quadratic optimization problem
I have the following problem:
$
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\argmax_{\underset{\lambda_k\in \mathbb{R}}{\sigma_q^2(k)\in \mathbb{R}}}
\left[\...
1
vote
1answer
54 views
ADMM: why does method of multipliers lose decomposability
I am trying to understand intuition of ADMM (alternating direction methods of multipliers). It combines dual ascent and method of multipliers. Downside of method of multiplier is the loss of ...
5
votes
0answers
90 views
Minimum of quadratic assignment (QAP) with convex objective
Suppose $A,B\succeq0$ and $C\in\mathbb R^{n\times n}$. I am hoping to solve an instance of the following optimization problem:
$$
\min_{\textrm{permutation matrices }P}
\mathrm{tr}(BP^\top AP+C^\top ...
0
votes
0answers
46 views
Least square approximation of a polynomial with a constraint on the derivative in Python
I'm trying to fit a polynomial of the third degree through a number of points. This could be a very simple problem when not constraining the derivative. I found some promising solutions using CVXPY to ...
3
votes
1answer
89 views
Can I solve a model in GEKKO with Black Box, Simulated Annealing or GA solvers?
I'm trying to use my current GEKKO model with different solvers methodologies. I don't know if I can also use global optimisation solvers as GA, Simulated Annealing o Differential Evolution. I need ...
4
votes
1answer
40 views
Binary combinatorial optimization with hard to compute costs
I have a combinatorial problem regarding the optimal placement of sensors. I want to find the optimal placement of $N$ sensors, given $M$ possible locations, $N < M$. Right now I'm working with ...
6
votes
1answer
95 views
Optimization algorithm / approach for suggesting what goods to buy and sell in a marketplace?
A toy problem would probably be best to explain it this. Let's say we have 100 people, each with 4 unique types of items (to simplify things, let's say it's the same four types of items for each ...
3
votes
1answer
373 views
What's the terminology for this alternative minimization algorithm?
Say the model is $F(x_1)G(x_2)Z(x_3) = y \in \mathbb{R}^N$, with $F,G,Z$ explicitly known, we are given observation of $y$ as $y_b \in \mathbb{R}^N$ to find the value of $x_1$, $x_2$, $x_3$ for each ...
5
votes
1answer
99 views
Sensitivity of BFGS to the accuracy of the gradient
I am studying how to speed-up the BFGS method using quantum computing techniques.
I have used a method of speeding up the gradient of the function, but it sacrifices the precision value of the ...
3
votes
2answers
159 views
How to include penalty in a Objective Function with Python? GEKKO
I'm trying to include a "great M" penalty in my objective function.
I want use the entry x vector values as entry values in a function. A fixed maximum value is took initially for the returned value ...
4
votes
2answers
142 views
MINLP with GEKKO - Modeling discrete variables
I'm trying to define a MINLP optimization problem with GEKKO in Python, and I want to use some variables with fixed values.
For my first variable, x1, I need to define the following values (as would ...
3
votes
1answer
57 views
Optimizing for multiple objectives
Optimizing two models here, each model having its own set of parameters and an objective, but both models run on the same data which is difficult to compute, and which is computed based on both models'...
2
votes
0answers
43 views
Classification of multiobjective optimization algorithms
I am looking for a good (canonical?) overview paper(s)/book(s) on the classification of multiobjective optimization algorithms. I am focused on obtaining a representative set of Pareto optimal ...
4
votes
1answer
124 views
An optimization method for bounding the eigenvalues of a unknown non symmetric matrix
Given a positive objective function $f$ that acts on a real-valued matrix $A$, I am interested in the following problem
$$\underset{A \in \mathbb{R}^{n \times n}}{\text{minimize}} \quad f(A) \quad \...
3
votes
0answers
106 views
A maximization problem, with motivation in machine learning
Consider the minimization problem described this paper. Let $f_{\lambda}$ be the minimizer. As a part of extending my work, I am able to show the following facts
$$\lim_\limits{\lambda \to 0}\|f_{\...
