Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [optimization]

This tag is intended for questions on methods for the (constrained or unconstrained) minimization or maximization of functions.

7
votes
2answers
689 views

Bin-packing: Maximise number of bins / “Fukubukuro” problem?

I recently encountered a problem that looks like a variation of bin packing or knapsack problem, but with the objective to maximise the number of bins/knapsacks: Consider there is a list of M items ...
0
votes
0answers
13 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 BFGS algorithm. But I want to change the following implementation, so that: 1) Wolfe-Powell step-size control is ...
3
votes
0answers
32 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
57 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 \...
3
votes
1answer
286 views

Using the Nelder-Mead algorithm to find a maximum

In the Nelder-Mead algorithm, the simplex looks for the minimum of the function. If I multiply all the function values times -1, would I trick the simplex into searching for the maximum?
3
votes
1answer
57 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 ...
3
votes
2answers
63 views

What is a good way to select a small subset (say 50) of items from a large pool of items (say 5 million) while minimizing an objective function?

I have 5 million items that have 10 features (all continuous and not categorical) each and would like to select a small subset of these items. Ideally, I want to manually specify 10 features of my own ...
1
vote
3answers
233 views

Traveling Salesman Problem

First off some context. The Traveling Salesman Problem(TSP) is to find the most efficient route passing through a series of points only once. However, there is no perfect function to solve for this in ...
5
votes
0answers
93 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....
-1
votes
0answers
24 views

How to perform improved euler integration for a 3D vertex model (network minimization)?

I am a PhD student who is struggling to implement a 3D vertex model. Vertex model are commonly used by physicists in biology to understand how biological cells in a tissue coordinate together. In the ...
1
vote
1answer
52 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
1answer
88 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) $$ ...
0
votes
1answer
30 views

R function or package for carrying out maximum likelihood techniques in random effect models

I am applying optim() function in R to obtain maximum likelihood estimates of the fixed effects and random effects in a model with bivariate random effects. The ...
1
vote
0answers
37 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 ...
-1
votes
0answers
41 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 ...
3
votes
1answer
304 views

Optimization of a blackbox function with an equality constraint?

I believe this would be an interesting problem. I have a blackbox function which can take 2-60 input variables $(X_1,X_2,...X_n)$ which are to be optimized. I'm calling this objective function as a ...
4
votes
1answer
83 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 ...
4
votes
0answers
56 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
74 views

Find a vector B that minimizes |W-A*B|

I want to find a candidate vector $B$ that $$\min|(W - A_i * B_i)|$$ $$ a_i > 0,\ A_i=\{a_0,...,a_i\},\ B_i=\{-1,0,1\}^i$$ For example, given $$W = 0.6,\quad A_4 = [0.1, 0.2, 0.4, 0.7] $$ one ...
4
votes
1answer
36 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
23 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
1answer
159 views

zero terminal value of the adjoint based optimal control

I have been pondering about this issue for some time... Say, I want to minimize a costfunctional $$ \tilde J(u) = J(v(u),u) = \frac 12 \int_0^T (v-v_0)^2 + \alpha u^2 dt $$ subject to $$ \dot v = v^2 ...
0
votes
2answers
159 views

Solving a quadratic pseudo-boolean optimization problem where the integral constraints are relaxed

Quadratic Pseudo-Boolean Optimization (QPBO) problem: Problem 1. Minimize $\sum_i a_ix_i + \sum_{i<j} a_{ij}x_i x_j$ subject to $x_i\in\{0,1\}\forall i$. Consider the following problem, where the ...
1
vote
0answers
51 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 ...
0
votes
1answer
80 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
0answers
28 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 ...
3
votes
1answer
76 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 ...
6
votes
2answers
174 views

Unknown domain in optimization problem

I have a similar question compared to this post. I am trying to maximize a function, which is a black-box to me. I have tools of gradient-free methods; in fact, this problem is reasonably smooth that ...
4
votes
3answers
252 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
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
62 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} \...
0
votes
1answer
291 views

Nonlinear integer program with linear constraints

I'm trying to perform inference over a subset of the latent variables of a hierarchical hidden Markov model I built. I've derived the relevant optimization problem, but it's a pretty nasty piece of ...
5
votes
2answers
108 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 ...
2
votes
1answer
88 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
29 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
42 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 ...
3
votes
0answers
55 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
78 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
93 views

Some proof that linear translations and rotations of a bound-constrained function are equivalent

For example, I have a function to optimize: $$f_1(x,y) = x^2+y^2, \quad x_{lb}\le x\le x_{ub},\quad y_{lb}\le y\le y_{ub}$$ Then I apply rotation by $\theta$ plus translation by $x_0$ and $y_0$: $$f_2(...
4
votes
4answers
217 views

Find representatives of vector-space in set of vectors?

Suppose I have a multi-dimensional vector space $X$, and a collection of $n$ vectors $\{x_i\}_{i=1}^n \subset X$, which are not evenly "spaced-out" in $X$. I am searching for $m<<n$ of these $...
0
votes
0answers
22 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 ...
6
votes
3answers
6k views

Python solvers for mixed-integer nonlinear constrained optimization

I want to minimize a black box function $f(x)$, which takes a 8$\times$3 matrix of non-negative integers as input. Each row specifies a variable, whereas each column specifies a certain time period so ...
0
votes
0answers
13 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
22 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 ...
2
votes
0answers
37 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 ...
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 ...
3
votes
2answers
92 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, ...
0
votes
1answer
61 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: ...
2
votes
3answers
132 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 ...