Questions tagged [optimization]
This tag is intended for questions on methods for the (constrained or unconstrained) minimization or maximization of functions.
0
votes
0answers
9 views
What kind of standard deviation must be used in optimization algorithms?
I would like to ask about the standard deviation of objective function value.
There are two types of standard deviations
° Population standard deviation
° Sample standard deviation
In ...
1
vote
0answers
22 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....
3
votes
1answer
32 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 ...
-1
votes
0answers
13 views
Nevergrad not assessing bounds properly
I'm using Nevergrad by Facebook in Python and am observing some strange behaviour relating to bounds.
Let's find the minimum of a standard simple function:
...
4
votes
0answers
50 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 ...
1
vote
0answers
45 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
72 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
75 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
59 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
107 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 ...
0
votes
0answers
27 views
Inverse kinematics BFGS divergence
I am trying to implement inverse kinematics solver using BFGS as stated in the paper Xia2017.
In the test experiment, i created 4 objects in 3-dimensional space: Node, Node1, Node2, Node3. Each Node ...
0
votes
0answers
28 views
Parameter estimation using fmincon
This is a follow up to my previous question posted here.
I am solving an optimization problem using fmincon in MATLAB. There are no equality constraints in my model....
0
votes
0answers
41 views
Parameter estimation using shooting method
I want to do the following,
I have a set of 20 first order differential equations and I want to estimate some of the parameters.
I've got the following initial and boundary conditions.
The initial ...
0
votes
0answers
22 views
state of art resources for transportation logistics
By transportation logistics, I mean the application of theoretical tools like traveling salesman problem, routing problem etc. So what are these applications? Well, stuff like how to schedule a fleet ...
3
votes
0answers
54 views
Solve ODE with non-negative and maximization constraints
My task is to solve $$\eta_k\frac{d^2C_k}{dz}(z)=-e_k, k = 1,2,3$$
$$C_k\ge0$$
$$C_1(0)=0, C_2(0)=A, C_3(0)=0$$
$$C_1(L)=B, \frac{dC_2}{dz}(L)=0, \frac{dC_3}{dz}(L)=0$$
with $$e_1 = -\beta_1-\beta_3$...
1
vote
1answer
76 views
Is there a name for this integer linear optimization problem?
I have an integer linear programming problem of the form:
$$\DeclareMathOperator{\tr}{tr} \min \tr WX$$ subject to:
$$\begin{align}
\sum_j X_{ij} < c_i && \forall i \\
\sum_i X_{ij} = 1 &...
1
vote
1answer
123 views
How do I solve the matrix equality constrained optimization problem using Lagrangian multipliers?
Solve the following minimization problem in $\mathbf{X} \in \mathbb{R}^{m \times n}$
$$\begin{array}{ll} \text{minimize} & \frac 12 \| \mathbf{X}\mathbf{X}^T -\mathbf{A} \|^2_\mathcal{F}\\ \text{...
2
votes
1answer
86 views
Formulation of the least-squares parameter estimation problem
I have a system of 10 ordinary differential equations of the form,
$$\frac{dy_1}{dt} = f1(V1,k1,y1,y2)\\
\vdots \\
\frac{dy_{10}}{dt} = f_{10}(V_{10},k_{10},y_{9},y_{10})
$$
I want to estimate the ...
0
votes
0answers
19 views
Scipy basinhopping custom step update and constrained looping
I am searching for the global minimum of a certain function and trying to use its gradient (here same as Jacobin) to guide the step counter. However, my x is fix ...
0
votes
0answers
11 views
Finding Maximum Value of CST Parameterization over an interval
I have a CST parameterization for a shape over an interval (0,1), so I have y as a function of x like so $$y = C(x)*s(x)$$ where $$C(x) = x^{n1}*(1-x)^{n2}$$ and $$S(x) = \sum_{i = 0}^{n} A_i(x)^i(1-x)...
0
votes
0answers
20 views
convex atomic function reformulation to meet concave dcp rule requirements
I have an atomic constraint of the form
abs(w - w_prev) >= some_threshold
It is supposed to get every value equal to or above my threshold.
I am working on a ...
1
vote
0answers
36 views
Biconvex problem whose objective function depends on only one variable
I am solving the following biconvex problem:
$$\min_{x,y} f(y)$$
$$s.t. ~~ g(x) \leq 0$$
$$~~~~~h(x,y) = 0$$
$$x \in X, y \in Y$$
where $X$ and $Y$ are compact convex sets, $g(x)$ and $f(y)$ are ...
4
votes
1answer
78 views
Examples of problems that cannot be formulated as optimization problems
An optimization problem has 3 main components: decision variables, constraints and an objective function. Such a problem can be mathematically modelled and solved using an optimization solver. For ...
0
votes
1answer
59 views
Solve multi-dimensional optimization problem using basinhopping
I am searching for an optimization solution, which is a 8d vector representing 4 complex elements, where each element is within the complex circle with maximal radius 1.2.
The objective function is:
...
3
votes
2answers
90 views
Optimization techniques for expensive multi-variable functions
I'm working with a finite element model in which I'm interested to minimize the average temperature at a surface. I have 15 independent variables in my model, including geometry, materials, flows, ...
3
votes
3answers
130 views
Find a solution of large system of inequalities
I have a large system of homogenous inequalities involving 33 real unknowns of the form
$$
\vec{F}(z_i)^T \cdot \vec{X}>0\,
$$
where $\vec{X} = \left(x_1,...,x_{24}\right)^T$ are the unknowns and ...
2
votes
0answers
43 views
Non-parametric models as solutions to Partial Differential Equations
In the realm of scientific computing, there are a plethora of techniques developed to solve Partial Differential Equations (PDEs). Many of the popular methods are variants of common techniques such as ...
5
votes
1answer
63 views
What is the name for this type of constraint?
I have what would be a straightforward mixed-integer linear programming problem, except for the fact that some of the constraints are of the form $f(x_1,x_2,x_3,\ldots,x_n) < c$, where $f$ is 'take ...
0
votes
0answers
12 views
Cost functions to judge time/memory/accuracy tradeoffs
I am working on an interesting algorithm: Its absolute error is exponential in a parameter $j \in \mathbb{N}$, and for a given $j$, I have complete freedom to choose between an $\mathcal{O}(1)$ time-...
0
votes
1answer
17 views
Minimize squared error of linear function
Let $M$ be a $m \times n$ matrix, $x$ a $n$-vector, $y$ a $m$-vector, and $\|\cdot\|_2$ represent the $L_2$ norm (i.e., Euclidean norm). Given $M,y$, the goal is to find $x$ that minimizes the ...
0
votes
0answers
28 views
Minimizing the ratio of two specific non negative quadratic convex functions
$F$ is $m\times m$ diagonal, with real non negative elements
$D$ is $n \times m$ complex
$P$ is $n \times 1$ complex
$A$ is $m \times 1$ complex.
Minimize $\Gamma(A)$, with respect to $A$.
$$\...
2
votes
1answer
83 views
Is there an optimization scheme/algorithm that converges, for this non-convex scenario but with some special properties
I have a smooth function $f(x) = \frac{g(x)}{h(x)}$ that is the ratio of two smooth convex functions $g(x)$ and $h(x)$. It is known that $f(x)$ has a global minimum, achieved at the unique point $x_0$....
0
votes
0answers
49 views
Simplification of an optimization objective
Let $G(V,E)$ is a weighted simple graph, where $V$ and $E$ are the set of vertices and Edges. The graph is undirected. Let $A \in \{0,1\}^{n\times n}$ and $W \in R_+^{n\times n}$ be the adjacency ...
0
votes
1answer
36 views
Vehicle Route assignment with capacity constraint
Problem Background
I'm trying to find a solution/model to the following problem:
Let's consider a cellular network (mobile network, ie., hexagonal cells) denoted $N$ composed of $|N|$ cells. Each ...
7
votes
1answer
196 views
Lack of quadratic convergence in Newton's method
It is well-known that Newton's method can converge quadratically, if initial guess is close enough and if the arising linear systems are solved accurately.
I am applying Newton's method to highly ill-...
3
votes
1answer
81 views
Minimize a function with sparse Hessian
The problem I am trying to solve involves minimising a function with respect to a large number (probably 10,000+) of parameters. I can cheaply compute both its Jacobian and its Hessian. The Hessian is ...
0
votes
0answers
33 views
In-exact line search
In my class notes, the author says:
"If $f:\mathbb{R}^n \to \mathbb{R}$ is bounded below and $p_k$ is a descent direction and the $\alpha-\beta$ also known as Armijo-Goldstein condition is met then ...
0
votes
0answers
32 views
Is this a form of stochastic gradient descent?
I want to minimize the following with respect to parameters $B$.
$$\sum_{k = 1}^{K} f(A_{k}, B)$$
where $A_k$ are $K$ different data-sets and $B$ is a matrix of parameters.
Can I do this by a ...
0
votes
1answer
23 views
Gradient ascent method with a constant step size?
I'm trying to use the gradient ascent method on a convex function like the multivariate-Normal density function with respect to its parameters (the original is a bit more complicated), something ...
-3
votes
1answer
68 views
4
votes
3answers
247 views
Best software to do big number calculations quickly
I am trying to do some work on some math conjecture. I am testing the conjecture numbers using very large math numbers (100+ digits ). I am currently using python to test these numbers.
In the ...
2
votes
1answer
51 views
Question about strange outputs from the CVXPY solver
I am familiarizing myself with CVXPY, and encountered a strange problem. I have the following simple toy optimization problem:
...
3
votes
0answers
58 views
Given a list of intervals, find region that is contained by the largest number of those intervals
Start with 1d case. Say I have lots of 1d intervals $[s_i, e_i]$ and I want to find an interval $[s^*, e^*]$ to maximise the count of interval $i$ such that $[s_i, e_i]\supseteq [s^*, e^*]$.
1d case ...
3
votes
0answers
73 views
Nonlinear least squares and regularization
Consider the nonlinear least-squares minimization of a vector of $n$ residuals $\mathbf{f}$ in $p$ parameters $\mathbf{x}$:
$$
\min_{\mathbf{x}} || \mathbf{f}(\mathbf{x}) ||^2
$$
This can be done with ...
0
votes
1answer
79 views
Is this a knapsack problem?
I have a set of $K$ keywords. Each of this keywords can have set of bids from $1\$,\dots,N\$$. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and Cost ...
0
votes
1answer
67 views
Minimize cost with Levenberg-Marquart method
I want to minimize a cost function of the form,
$$
\min_{q,t}\left(q^T\left(\mathcal A + \mathcal B\right)q + t^T\mathcal C t+\delta t+\varepsilon Q(q)^TW(q)t+\lambda\left(1-q^Tq\right)^2\right)
$$
...
1
vote
1answer
68 views
sum of absolute difference constraint in optimization problem
I am writing a model for an optimization problem. I need to write the following constraint:
$$\sum^{N - 1}_i \lvert (a_i - a_{i+1}) \rvert \leq 2\, .$$
How to write this constraint (or linearize)?
...
1
vote
2answers
115 views
Method to find PDE equation coefficient satisfying mean solution?
What is the best approach to go about solving a PDE problem of the type
\begin{equation}
k^3\Delta u - k(\mathbf{1}\cdot\nabla u) = 0\, ,\\
u=g\; \text{on}\; \Gamma_D\, ,\\
mean(u) = u_\text{...
1
vote
1answer
60 views
Nature of stationary points of a Lagrangian fuction
I would like to extremize a certain function $f$ with respect to a parameter $x$, under constraints $g_1(x) = 0, ..., g_m(x)=0$. In order to achieve this, I consider the Lagrangian function $L(x, \...
-1
votes
1answer
74 views
Compute affine transformation between two sets of points
Consider two sets of points $P = (P_1, ...,P_n), \ Q = (Q_1, ..., Q_m) $ included in $\mathbb{R}^3$.
I'm looking to compute an optimal affine transformation that "maps" $Q$ to $P$, although the sets ...
