Questions tagged [optimization]
This tag is intended for questions on methods for the (constrained or unconstrained) minimization or maximization of functions.
793
questions
1
vote
0answers
34 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
37 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
60 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
47 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
52 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
0answers
19 views
How to check the feasibility of a set of linear inequality constraint?
(The image of the whole problem is also included)
Consider a set of linear inequalities constraint as:
Ax >= b,
0 <= x <= L,
where A(N,N), x(N,1), and b(N,1).
It is assumed that the ...
3
votes
1answer
62 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
53 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
126 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
29 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
62 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
50 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
50 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
77 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
35 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 ...
2
votes
1answer
47 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
38 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
370 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
0answers
78 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 ...
2
votes
2answers
91 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 ...
3
votes
2answers
96 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
52 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
42 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
0answers
89 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_{\...
2
votes
1answer
74 views
What is this discrete optimization problem called?
It feels like this problem should be commonplace, but I don't know what it's called:
Minimize
$$
\sum_{i=1}^{n}a^{(i)}_{k_i} + \sum_{i=1}^n\sum_{j=i+1}^n b^{(ij)}_{k_i k_j}
$$
with respect to ...
1
vote
0answers
11 views
Long AMPL model preparation time
We deal with a large-scale linear optimization problem (~50000 variables and ~4000000 constraints). We use AMPL Studio modeling environment for problem modeling and then calling linear solver (CPLEX, ...
5
votes
1answer
48 views
Term for an small optimisation algorithm used as a subroutine
Is there a term describing a specialised solver which is used as a subroutine or a different, larger solver?
For example, a gradient descent solver which, at each step, uses a line search to optimise ...
1
vote
0answers
59 views
How can I solve the matrix optimization problem where denominator and numerator are different?
I want to solve the following maximization problem in $\mathbf{X}\in {\mathbb{R}}^{{m} \times {n}}$
\begin{eqnarray}
\begin{split}
\quad\max_\mathbf{X} \frac{\mathbf{Tr}(\mathbf{X}^\top \mathbf{Q} \...
1
vote
0answers
42 views
least squared optimization
I want to decompose a list of 3D vectors $X_j$ as linear combination of five 3D verctors $C_k$
$$X_j= \sum_{i=1}^{5}{w_{ji}C_i}$$ both $X_j$ and $C_i$ are 3 components vectors
$$C= \begin{bmatrix} ...
1
vote
0answers
78 views
How to perform local sensitivity analysis for partial differential equations
I am looking for a way to do local sensitivity analysis for PDEs, preferably in Python.
I get the impression that discretizing the equation then treating it as an ODE could work; however, would that ...
2
votes
1answer
129 views
Simultaneously maximize and minimize
I am virtually new to optimization (saw it years ago in a very shallow course) and now I came across a problem that I believe would require from it. The problem is I don't know exactly how to proceed.
...
1
vote
0answers
49 views
Kinetic preconditioning
Publication arXiv:0804.2583 describes a method for doing self-consistent iteration without having to diagonalize the Hamiltonian operator at every step.
IX. PRECONDITIONING
As already ...
0
votes
1answer
105 views
Need an example Legendre-Gauss-Radau pseudospectral differentiation matrix or Matlab code
I'm trying to implement various kinds of pseudospectral methods for direct optimization in Matlab using IPOPT. I've got some working Legendre-Gauss-Lobatto code, but would like to use the flipped ...
3
votes
1answer
73 views
Geometric Programming - symbolic version
I am interested in finding minimizers of functionals of the type $\sum x^ay^bz^c$ where the exponents are 1, 0 or -1. I have codes to find such minimizers when they exist up to machine precision, ...
1
vote
0answers
63 views
How to use Wolfe-Powell step-size control in quasi-Newton method?
I'm trying to find the minimum of a function using the quasi-Newton method with the Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm.
But I want to change the following implementation, so that:
1) ...
3
votes
0answers
48 views
Constraint solver vs Bayesian optimizer for fast discontinuous processes
I have a complex domain-specific process that accepts inputs:
10-500 inputs, where each input is of type:
enum: choice between multiple string or numeric values
int: integers
float: floating point ...
1
vote
0answers
74 views
Best optimizer for unconnstrained non-convex nonlinear least-square optimization problem?
I am looking for a very good optimizer to the following problem:
$$\min_{P,\Theta}\lVert APD(\Theta)P^{-1} -B \rVert_F$$
where $A,B \in \mathbb{R}^{n\times m}$, $P \in \mathbb{R}^{m\times m}$, $D\in \...
1
vote
1answer
79 views
Pivoted Cholesky vs Modified Cholesky
I am solving nonlinear least squares problems with the normal equations approach, so on each iteration, I need to solve:
$$
J^T J \delta = -J^T f
$$
for the step $\delta$, where $J$ is a large (...
1
vote
0answers
44 views
Finite dimensional optimization problem over dynamical system
I am interested in solving numerically the following mathematical problem
Consider an ode of the form
$$
\dot q(t) = f(q(t),t_1,\ldots, t_N),\qquad t\in [0,T],
$$
where $q\in \mathbb{R}^n$ is the ...
5
votes
0answers
94 views
How to solve a 4th order nonnegative LASSO problem?
I need to solve the following 4th order nonnegative LASSO problem:
$$
\min_{x \geq 0} \quad || |Ax|^2 - b ||^2 + \lambda ||x||_1
$$
where $|\cdot|^2$ denotes element-wise squared. $A$ is small size (e....
4
votes
1answer
42 views
Single-variable multimodal derivative-free optimization (for a well-behaved function)
Are there well-established approaches to single-variable multimodal optimization?
Given $f:\mathbb{R}\rightarrow\mathbb{R}$ that:
has several local minima within a given range of interest $[a,b]$
is ...
4
votes
0answers
61 views
Fast approximate solver for vehicle routing problem
I need to solve capacitated asymmetrical vehicle routing problem with time windows on ~30k points. Time limits for calculations are 2 hours. I've tried using Clarke and Wright savings algorithm, it is ...
2
votes
1answer
72 views
User friendly scipy optimize wrapper package?
I'm creating too much throw away code for interfacing with the scipy optimize package in a user friendly way. (See code below for example of interruptible optimization that keeps last optimization ...
3
votes
1answer
99 views
Why would BFGS converge to a local minima of a non-convex function but maintain a large gradient?
I'm using BFGS to optimize a smooth but non-convex function $f$ that is computed by a simulation. The simulation also gives me a semi-analytical gradient $g$, which is verified by the numerical ...
2
votes
1answer
77 views
How to compute the determinant of Hessian of a multivariable function?
I have a function $F(\vec x)$ of many variables (let's say in the order of hundreds of thousands). I need to compute the determinant of the Hessian matrix at the point $x_0$.
Is there a way to ...
3
votes
2answers
89 views
Convexity of Sum of $k$-smallest Eigenvalue
If I have a real positive definite matrix $A\in\mathbb{R}^{n\times n}$, and denote its eigenvalues as $\lambda_1\leq \lambda_2 \leq ... \leq \lambda_n $.
Define the function as $f(A)=\sum_{i=1}^{k} \...
5
votes
2answers
110 views
Choose a subset of $m$ columns that maximize $|A^T A|$?
I have a set of $n$-dimensional vectors, and would like to choose $m$ of them to become the columns of an $n\times m$ matrix. I would like to choose the subset that maximizes $|A^T A|$, where $A^T$ is ...
