Questions tagged [optimization]

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

Filter by
Sorted by
Tagged with
3
votes
1answer
30 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 ...
5
votes
0answers
62 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
1answer
345 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 ...
2
votes
2answers
41 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
57 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
48 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
39 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
76 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 \...
2
votes
1answer
98 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(...
3
votes
0answers
103 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
71 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
9 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
44 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 ...
2
votes
1answer
66 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 ...
2
votes
1answer
50 views

Ordering of eigenvectors to maximise trace of diagonalising matrix

I asked a similar question on the Mathematics stack exchange here without much success, so I thought I'd ask it with a more practical bent here. Suppose we have a Hermitian matrix $H$ with (for the ...
1
vote
0answers
58 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
1answer
49 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 ...
1
vote
0answers
37 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
71 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
116 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
47 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 ...
5
votes
2answers
2k views

Relation and difference between combinatorial optimization, discrete optimization and integer programming

I wonder what relation and difference are between combinatorial optimization and discrete optimization? Thanks! Originally by reading Wikipedia, I thought discrete optimization consists of ...
5
votes
4answers
2k views

Simulated Annealing proof of convergence

I implemented downhill simplex simulated annealing algorithm. Algorithm is very hard to tune, w.r.t. parameters including cooling schedule, starting temperature... My first question is about ...
5
votes
2answers
754 views

What is the most appropriate derivative free optimization algorithm

We can use random optimization/ derivative free/ direct search to find the minimum of some black box function $f$. If I have some 2D black box function, $f(x,y)$ - which I know to be convex - what ...
2
votes
1answer
129 views

What is the name of the optimization algorithm that uses random sampling?

I am generating random weight as per e.g. below. The I generate a set of 3 values say 100, 250, 300 and I multiple them with the weights below Initial population. ...
2
votes
0answers
39 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
101 views

ill-conditioning

I am struggling with the following exercise from the book of Nocedal, Numerical optimization, chapter 2, exercise 2.12: Suppose that a function $f$ of two variables is poorly scaled at the solution $...
1
vote
2answers
137 views

Solving a system of polynomial equations with multiple variables

I have a system of equations of the form: $$ l_i^T l_j \cdot m_i^T m_j - m_i^T R l_j \cdot l_i R^T m_j = 0$$ where $R \in \mathbb{R}^{3\times3}$ is an unknown rotation matrix. $l_i, l_j, m_i, m_j \in ...
1
vote
2answers
122 views

Factoring a quadratic function

I have a quadratic binary optimization problem of the form \begin{align} &\max x^TQx \cr &\text{subject to }x\in\mathcal{X}\subseteq\{0,1\}^n, \end{align} where $\mathcal{X}$ is the feasible ...
3
votes
1answer
60 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 ...
0
votes
0answers
44 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
58 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) ...
4
votes
2answers
1k views

LP feasibility checking

I have a linear programming problem. I want to know if this LP is feasible. What is the best known algorithm for checking feasibility of an LP or a linear system of equations?
7
votes
2answers
706 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 ...
3
votes
0answers
44 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
66 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
308 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
2answers
64 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
238 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
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....
1
vote
1answer
61 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
89 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
31 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
43 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 ...
3
votes
1answer
343 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
86 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
60 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 ...