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
2
votes
0answers
42 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[\...
10
votes
0answers
3k views

Optimized open source BLAS / LAPACK package

I was wondering what is a more optimized open source BLAS/LAPACK package with respect to modern multi-core processors (Haswell and beyond). Is there any distribution that can attain performance close ...
1
vote
1answer
46 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 ...
0
votes
1answer
101 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
303 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 ...
3
votes
0answers
31 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 ...
2
votes
1answer
23 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
36 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 ...
0
votes
0answers
33 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 ...
6
votes
1answer
88 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
74 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
367 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
61 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
67 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
50 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
40 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
86 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
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
72 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
45 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
67 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
52 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
39 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
76 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
118 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
3k 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
804 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
130 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
102 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
59 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
709 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
46 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
68 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
309 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
239 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....