Questions tagged [optimization]
This tag is intended for questions on methods for the (constrained or unconstrained) minimization or maximization of functions.
784
questions
-1
votes
0answers
19 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
58 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
45 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
47 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
70 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
27 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
91 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
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 ...
5
votes
0answers
75 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
66 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
76 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
51 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
88 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
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
46 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
40 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
124 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
48 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
0answers
51 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
60 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
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
69 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
70 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
39 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
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 ...
2
votes
1answer
69 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
93 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
76 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
71 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
109 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
41 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
34 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
45 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
64 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
79 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
141 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
97 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
52 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
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)...
