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
5
votes
4answers
139 views

Optimal solution to a table of numbers

I want to maximise the score of the following table, choosing one item from each column/row, so no two items are on the same row or column. Score to maximise is just adding all the choices together. $...
5
votes
2answers
1k views

Interpolation by Solving a Minimization Problem (Optimization)

I will try to give the motivation behind this problem and later the math formality. Given a grayscale image (1 Channel - $M \times N$ Matrix). Someone marks some pixels as anchors. Now, you need to ...
5
votes
2answers
111 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 ...
5
votes
5answers
3k views

Is there a convenient solver for linear programming with many summations?

How can I solve the following Linear Programming problem in the easiest way? How can the summation terms be modeled in there? From page 187 of Mathematical Programming Approaches by Charu Chandra ...
5
votes
2answers
206 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 ...
5
votes
2answers
1k views

Starting at a Given Basic Feasible Solution in the Simplex Method

I have a Simplex problem $ A y \ge b $, where some of the elements of $b$ are positive and some are negative, and thus setting $y = 0$ does not give a basic feasible solution (BFS). By previous work, ...
5
votes
2answers
2k views

Hill climbing and coordinate descent/ascent

From Wikipedia: In computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an ...
5
votes
1answer
3k views

Python: Multistart optimization using parallel programming

[I previously asked my question on StackOverflow but this site may be more appropriate] In Matlab, I am currently using the MultiStart as an optimization algo in a parallel setup for a computer ...
5
votes
2answers
213 views

Is there guaranteed global solver for such an eigenvalue problem?

The original nonlinear optimization problem I have is as follows: For constant symmetric matrices $A=A^T, B_i=B_i^T(\forall i\in\mathbb{N}) \in \mathbb{R}^{n\times n}, \text{rank}(A)=n,$ $$\arg\min\...
5
votes
2answers
287 views

Levenberg optimizer halts quickly when given more variables, or fewer constraints

I'm using the g2o C++ optimization library to refine a GPS trajectory using accelerometer data. The program uses a Levenberg-Marquardt optimizer over data points representing the position and ...
5
votes
2answers
3k 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
1answer
191 views

Linear Programming with constraints of the form $Cx \nless d$ where $C\in R^{m\times n}$

I have an optimization problem that has a linear objective function. The constraints are of the form: $(Ax \leq b) \wedge (Cx \nless d)$. In other words, I have: \begin{align} \min &f^T x \...
5
votes
1answer
204 views

Striking examples of success of local search algorithms

In N queens problem https://en.wikipedia.org/wiki/Eight_queens_puzzle, trying to find solution by backtracking encounters difficulties quite fast (even for SWI-Prolog, http://swish.swi-prolog.org/...
5
votes
1answer
979 views

Solving a system of nonlinear PDEs by minimization

I have two coupled nonlinear partial differential equations of the form: $ \begin{align} \dot{u} -f(u,u',u'',v,v',v'')=0 \\ \dot{v} -g(u,u',u'',v,v',v'')=0 \end{align} $ The boundary conditions are ...
5
votes
2answers
1k views

Scaling of optimisation function in non-linear least squares problem

Suppose I am minimizing the following function: $$g(\alpha)=\sum_{i=1}^n(y_i-f(x_i,\alpha))^2,$$ where $y_i$ and $x_i$ are data, $f$ is a known non-linear function and $\alpha$ parameter (of ...
5
votes
2answers
313 views

Approximating and visualizing basins of attraction

I am working on estimating the position and orientation (pose) of a model (rigid object) from its silhouette in an image. For this, I have constructed an error measure between the model in its pose ...
5
votes
1answer
76 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 ...
5
votes
1answer
136 views

Can Variational Inequalities handle non-symmetric matrices?

I am trying to enforce the discrete maximum principle (i.e., ensuring non-negative concentrations) for diffusion-type problems that have an anisotropic diffusivity tensor (e.g., tensor dispersion from ...
5
votes
1answer
620 views

Semidefinite Programming Using CVX in Matlab

I have the following optimization problem $$\begin{align} &\min_{ X_{1}, \dots,X_{k} } \max_{ \theta, \phi } \left|P_{d}(\theta,\phi) - \sum_{k=1}^K \operatorname{Tr}(a_{k}(\theta,\phi)a_{k}^{H}...
5
votes
2answers
938 views

minimization problem: sum of Rayleigh quotients

I would like to find $x$ which minimizes the following equation: $\frac{x^HAx}{x^HBx} + \frac{x^HCx}{x^HDx}$ where A, B, C, D are positive-definite. $x$ is not a very large vector (<1000 elements ...
5
votes
1answer
126 views

Using an approximation algorithm to adapt parameter values of a given algorithm

Problem: I have an incremental online clustering algorithm which need 4 parameters that should be specified by the user before execution. The algorithm will gives "good results" if "a good parameter ...
5
votes
1answer
50 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 ...
5
votes
1answer
344 views

Maximum Likelihood Estimation for State Space Models using BFGS

I have written some code that can do Kalman filtering (using a number of different Kalman-type filters [Information Filter et al.]) for Linear Gaussian State Space Analysis for an n-dimensional state ...
5
votes
1answer
137 views

Generate approximately semi-orthogonal tall matrix approximately satisfying constraints

I have a set of matrices $\{(A_i,D_i)\}$ for $i\in\{1,\ldots,n\}$, where: Each $D_j\in\mathbb{R}^{S\times S}$ is diagonal, and every entry on the main diagonal is non-negative. Each $A_j\in\mathbb{R}^...
5
votes
1answer
493 views

Solving a set of linear equations with block structure and weak coupling

I have a standard set of linear equations $Ax=b$ where the Hessian matrix $A$ has the special block structure as shown: $A= \begin{pmatrix} T & U\\ U^T & V \end{pmatrix}$, $x= \begin{...
5
votes
1answer
902 views

Fast projection onto semidefinite cone

Lots of algorithms for semidefinite programming make use of the Frobenius projection onto the cone of semidefinite matrices: $$\mathcal{P}(A) = \min_{X\succeq0} \|A-X\|_{\mathrm{Fro}}^2.$$ Let's ...
5
votes
1answer
73 views

Optimal partitioning of a graph

Consider a planar graph, where each node is associated with a weight. I would like to partition the graph such that the sum of the node weights in each group satisfy a minimum requirement. However, I ...
5
votes
1answer
419 views

scaling and preconditioning for trust region Newton methods

Geometrically, scaling and preconditioning seem to address similar challenges in optimization. However, these two concepts are implemented very differently. Take trust region Newton method, as an ...
5
votes
1answer
644 views

Is there a convergence proof for ADMM applied to biconvex/bilinear problems?

Ok, I've already asked this question in math.stackexchange, but I feel it is more appropriate to ask here (hopefully I am not violating any rules by repeating!). So here it is: I wonder if there is a ...
5
votes
2answers
225 views

What is a suitable algorithm for solving a large mixed-integer quadratic program?

I am interested in the solutions of a very large quadratic programming (QP) problem \begin{align} \min_{x \in \mathbb{R}^n} & x^T Q x\\ \mathrm{subject\ to} & A x = b\\ & x \in \{0,1\}^n \...
5
votes
1answer
116 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 ...
5
votes
1answer
148 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 \...
5
votes
1answer
534 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 ...
5
votes
1answer
92 views

$L_2$ projection with integer constraints and prescribed sum

Suppose I am given a vector $v^0\in\mathbb{R}^n$ and integers $k,\ell\in\mathbb{Z}$. Assuming $k$ is close to zero (e.g. $0\leq k\leq5$), is there an algorithm for solving the following integer ...
5
votes
1answer
263 views

What category is this problem?

My first question, please excuse me if its too basic. I have a matrix of evenly spaced geographical points; say 10 x 10, which I will call seed points. Each seed ...
5
votes
1answer
88 views

Exact recovery of large incomplete rank-one matrices?

Incomplete low-rank matrices can be exactly recovered in most cases, so long as the rank is low enough relative to the number of known entries. This result was famously proved by Candès and Recht in ...
5
votes
2answers
2k views

How to solve a Rayleigh-quotient-like minimization with inequality constraints

What I am trying to solve is the following Rayleigh-quotient-like minimization: \begin{eqnarray} \begin{split} (P_0)\quad\min_x \frac{\left( Ax - b\right)^\top \left( Ax - b\right)}{x^\top x}\\ s.t. \...
5
votes
0answers
103 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 ...
5
votes
0answers
238 views

conjugate gradient for Newton's method with non positive definite Hessian matrix

I want to minimize a non-linear function $f(x)$ using Newton's method. At each optimization step, I compute a descent direction $d$ to update $x$ using a second-order approximation of $f(x)$: $$ \...
5
votes
0answers
85 views

Minimize interesting objective function with knowledge of gradient nonlinearity?

I plan on using a Quasi-Newton method (L-BFGS) to minimize a non-linear objective function. $$ f: \mathbb{R}^n \rightarrow \mathbb{R}$$ The gradient is kind of interesting: as the values of the ...
5
votes
0answers
158 views

How to optimally choose points for multivariable Hermite interpolation?

I have a multi-variate, continuous function $f$ from $R^n$ to $R$, which I can query for its output for any input. I would like to create interpolation polynomial for it. In one-dimensional case ...
5
votes
0answers
351 views

Optimization on the manifold of stochastic matrices

So I have an optimization problem of the form $$\text{maximize}\hspace{3mm}f(A):{\bf R}^{K\times K}\rightarrow{\bf R}$$ $$\text{subject to}\hspace{19mm}A^T{\bf 1}=\bf{1}$$ $$\hspace{33mm}A\geq 0$$ ...
5
votes
0answers
506 views

Best way to add a positivity constraint to Newton's Method

So given an objective function $f({\bf x})$, I would like to include a positivity constraint when I perform the fixed point iteration: $${\bf x}^{(t+1)}={\bf x}^{(t)} - \text{H}_f^{-1}\nabla f({\bf x}^...
4
votes
2answers
8k views

Tikhonov regularization in the non-negative least square - NNLS (python:scipy)

I am working on a project that I need to add a regularization into the NNLS algorithm. Is there a way to add the Tikhonov regularization into the NNLS implementation of scipy [1]? [2] talks about it, ...
4
votes
2answers
219 views

Looking for name of optimization problem in form $\min \mathrm x^T \mathrm A \mathrm x$ subject to $\|\mathrm x\| = 1$

I'm sorry for this silly question. Several times I faced with optimization problems which can be expressed as $$\begin{array}{ll} \text{minimize} & \mathrm x^T \mathrm A \mathrm x\\ \text{subject ...
4
votes
2answers
153 views

Simplifying some operations on Gram matrices

Suppose two Gram matrices are given $A, B\in\mathbb{R}^{n\times n}$, such that $$A=XX^T,~~~~~~~~~~~~~B=YY^T,$$ for some $X, Y\in\mathbb{R}^{n\times k}$, $k\ll n$. Also, suppose a Gram matrix based on ...
4
votes
3answers
213 views

Objective function scaling in an Inverse Problem

I am trying to solve a large scale inverse problem using the Bayesian formulation. To estimate the Maximum a Posteriori Estimation (MAP) solution I will have to minimize the following objective ...
4
votes
2answers
364 views

Can the Levenberg-Marquardt algorithm be used for minimization and not fitting

Can the Levenberg-Marquardt algorithm be used for minimization and not fitting? Usually we input the derivative of the function we want to fit in the minimizer. Now if I assume I have an objective ...
4
votes
2answers
1k views

Line search for Newton method

If we want to solve nonlinear minimization problem $$\min_{x} f(x),$$ making least-squares assumption and using Gauss-Newton method so that at k$th$ iteration we have: $$J_k^T J_k p_k = - J_k^T ...
4
votes
3answers
4k views

Beating typical BLAS libraries matrix multiplication performance

A dull matrix multiplication algorithm where we use the formula $$C_{ij}=\sum_{k}A_{ik}B_{kj}$$ By literally following this in 3 loops we'll get a very slow program, because we don't utilize ...

1 2 3
4
5
17