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

learn more… | top users | synonyms

0
votes
0answers
16 views

Elastic LP Programming

Say I have an LP that is unfeasible and that I want to find the solution that makes it feasible without strongly violating the current constraints. What is a principled way of solving this problem, ...
0
votes
0answers
25 views

How to measure the computational costs of solving CSPs and optimization problems?

I would like to define an abstract cost (machine and implementation independent measure) of the work needed to solve CSPs as a function of constraint and Jacobian evaluation counts. I am trying to ...
0
votes
2answers
119 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 by N Matrix). Someone marks some pixels as anchors. Now, you need to ...
3
votes
1answer
100 views

Recommendations on FEM software for implementing Nitsche's method on interfaces between matching meshes?

Suppose: I have two domains, $\Omega_{1} = [0, 1/2] \times [0, 1]$ and $\Omega_{2} = [1/2, 1] \times [0, 1]$. The domains share an interface $\Gamma = \{1/2\} \times [0, 1] = \partial\Omega_{1} \cap ...
3
votes
4answers
76 views

Plane constraints in R3

I have multiple plane constraints in $\mathbb{R}^3$ of the form: $$n_i \cdot x \ge \delta_i$$ Where $n_i$ is the $i$th plane normal (in form (x, y, z)), $x$ is a point in space, and $\delta_i$ is ...
0
votes
1answer
45 views

Effect of Initial guess B (approximate Hessian) on BFGS algorithm

I am trying to implement BFGS. The purpose is to approximate Hessian matrix only (not using the quasi-newton optimization steps), so i am using steepest ascent for optimization. What I observe is that ...
0
votes
1answer
50 views

How to model waterflow when only a couple of sample points available

Figure below depicts a cross section of a creek for which I am trying to measure the water flow for that section. What we have as inputs are a bunch of sample points on the river. For each sample ...
2
votes
1answer
70 views

Weighted Gauss-Seidel Algorithm

In Jacobi method's Wikipedia article there's a section that describes Weighted Jacobi method: http://en.wikipedia.org/wiki/Jacobi_method#Weighted_Jacobi_method. I need to implement the Weighted ...
3
votes
0answers
53 views

Why not use this simpler variant of Stepwise Regression?

In stepwise regression, you step predictor by predictor, each time selecting the one with the greatest correlation with the measurement, subtracting greedily to leave a residual with no correlation to ...
2
votes
1answer
43 views

Why do QM programs use redundant internal coordinates for geometry optimization?

Brief explanation of QM geometry optimization Quantum mechanics packages are often tasked with optimizing a chemical structure. The problem is essentially this: Given a set of points in 3D space and ...
1
vote
0answers
22 views

Optimal partition - variable number of parts

Suppose I have a box $D \subset \Bbb{R}^2$ (compact set). Denote $\mathcal{P}= \{ (\Omega_1,...,\Omega_n) : \bigcup_{i=1}^n \Omega_i = D,\ \Omega_i \cap \Omega_j =\emptyset\}$ the family of partitions ...
8
votes
1answer
152 views

Efficient Gravitational Field Implementation

I asked a similar question on physics.stackexchange, being ignorant about this website. I am basically looking for an efficient way to implement gravitational fields. I have a huge 2D space, with ...
0
votes
1answer
43 views

Finding maximum value in huge dataset

I am working on a project involving some pattern recognition. For this I need to find the maximum value in a huge multidimensional dataset. For example I have a discrete 5-dimensional space containing ...
0
votes
1answer
55 views

How does Abaqus calculate Hill's function for non-rectangular coordinate systems?

Within the manual, the effective/von Mises stress or Hill's potential for anisotropic bodies is calculated in Abaqus in cartesian rectangular coordinates as $\sigma_{eff}=\sqrt{I_{1}^{2}-3I_{2}} \\ ...
1
vote
0answers
33 views

Rank one constraint in optimization, which is nonconvex, but will we find the global maximum?

The objective function is $L = D(B)$, here $D$ is a function of $B$ and $D$ is a convex function. We have a prior information of $B$: it is rank one and we can write $B$ into $B = pq^T$. So we can ...
0
votes
0answers
35 views

What is a common approach to assess success rate of optimization?

Optimization approaches often differ in many aspects. E.g. their (guaranteed) convergence, the nature of their approach and the type of problems they can deal with. However, I find it difficult to ...
1
vote
0answers
64 views

BFGS Fails to Converge

The model I'm working on is a multinomial logit choice model. It's a very specific dataset so other existing MNLogit libraries don't fit with my data. So basically, it's a very complex function ...
2
votes
3answers
78 views

How to solve (continuous) quadratic programming problem with non-PSD matrix

In which problem category can I put a quadratic programming problem with only continuous values whereas the matrix A should be symmetric but needs not to be positive semi-definite? ...
0
votes
1answer
95 views

optimizing a discontinous function

I am trying to maximize the following function (variable:\theta, a vector ($\theta_1$,...,$\theta_K$). most likely K <=5 $F(\theta, c_0, c_1) = P_{\theta}(T_0 > c_0, \max T_i >c_1, \min T_i ...
4
votes
2answers
124 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, ...
7
votes
4answers
279 views

Linear programming with matrix constraints

I have an optimization problem that looks like the following $$ \begin{array}{rl} \min_{J,B} & \sum_{ij} |J_{ij}|\\ \textrm{s.t.} & MJ + BY =X \end{array} $$ Here, my variables are matrices ...
1
vote
1answer
54 views

Convex objective function of matrix with prescribed determinant and trace

I have real symmetric positive definite matrix $M = \left(\begin{matrix} a & b \\ b & c \end{matrix}\right)$ where $a,b,c \in R,\ a,c>0,\ \left|b\right|<2\sqrt{a c}$. I want to define ...
2
votes
1answer
79 views

Nonlinear optimization for minimizing matrix norm

Suppose that $A(x) \in \mathbb{R}^{m \times n}$ is a nonlinear matrix function of $x \in \mathbb{R}^d$. We may assume that $A(x)$ is continuously differentiable. Are there any good ways to estimate ...
5
votes
2answers
154 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,$ ...
3
votes
1answer
44 views

coefficient c2 for curvature condition of Wolfe Conditions for line search in non linear conjugate gradient

Can anyone point me in the direction of literature pertaining to the selection of the coefficient c2 in the curvature condition in the wolfe conditions when performing a line search? In Nocedal, he ...
5
votes
1answer
46 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 ...
2
votes
1answer
104 views

Question about extending Tikhonov regularization

I know that the Tikhonov regularization of a linear system has an analytical solution given by: \begin{equation} \hat{\mathbf{x}} = \mathrm{arg\;min}\left( \left| \mathbf{Ax} - \mathbf{b} \right|^{2} ...
1
vote
2answers
57 views

Minimizing a negative quadratic function with specified bounds

I have a quadratic programming problem: I want to minimize w.r.t. x: f(x) = (1/2) x^T * D * x + c^T * x subject to a constraint of the following form: ...
1
vote
2answers
283 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, ...
2
votes
2answers
76 views

Advice on the regularisation of a linear problem

I'm numerically inverting an integral transform using a method suggested by a scicomp user from an earlier question. The problem is as follows: I wish to estimate $f(x)$ for a given $F(y)$, both of ...
0
votes
0answers
44 views

Minimizing a quadratic form

I would like to minimize the following quadratic form: $$ f(\mathbf{\theta}) = (\mathbf{y} - \mathbf{\mu}(\mathbf{\theta}))^T \mathbf{\Sigma}({\mathbf{\theta}})^{-1} (\mathbf{y} - ...
0
votes
2answers
81 views

Nonconvex Optimization

Consider the following optimization problem: $\text{max}_{p} \quad ||p||^2 \\ s.t: x\geq 0\\ p\in D$ where $D$ is a convex set. Is this problem $\mathcal{NP}$-hard?
2
votes
2answers
50 views

Questions about Laplacian Surface Editing

I read the paper called Laplacian Surface Editing, but I'm confused about how does the author solve the formula (4). The paper says that 'Solving this quadratic minimization problem results in a ...
5
votes
2answers
158 views

Optimizing matrix-vector multiplication for many small matrices

I'm looking at speeding up matrix-vector products but everything I read is about how to do it for very large matrices. My case, the matrices are small but the number of times it must be done is very ...
2
votes
2answers
84 views

Workaround for BFGS with non simple constraints?

In one sentence (thanks to @Brian Borchers), I want to minimize the function f(x, y, ...), with gradient g(x, y, ...), subject to constraints that aren't given explicitly, but are defined by ...
3
votes
2answers
76 views

Affect of approximating a non-differentiable function on optimisation of minimisation

I am looking at a problem of constrained minimization, where the function to be minimized contains the Heaviside function, and as such is not twice continuously differentiable. My question is what ...
1
vote
1answer
50 views

If the global minimum value of a nonconvex $C^{\infty} f: R^n\to R$ is known,can it be easier to find the global minimizer?

If the analytical form global minimum value of a nonconvex $C^{\infty} f:R^n\to R$ is already known, will it be easier to find its global minimizer $x^*\in R^n$?
1
vote
1answer
88 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. ...
4
votes
1answer
118 views

constrained minimization in N dimensions

I am looking to create an algorithm to minimize an N dimensional problem. I am unsure how to write it in its generic form, so I will show it in 1, 2 and 3 dimensions Minimize $ \sum_{i} x_i\left [ ...
2
votes
1answer
73 views

Optimal algoritm of gcd with complexity

I want to know the best optimal algoritm of gcd with its complexity if you have a any useful source I will be glad to have a look at it.
0
votes
0answers
51 views

Quadratic programming problem involving permutation matrices

Does anyone know a good algorithm for quickly finding an approximate solution to the following problem? Given two square matrices $A$ and $B$, minimize $\| P A P^\top - B \|$ over all permutation ...
0
votes
1answer
55 views

Modeling a quadratic constraint with a linear expression

In a problem I am trying to model with a MIP program, the following scenario occurs: I am given binary variables $x_1,\ldots,x_n$ and $y_1,\ldots,y_n$ which can really be regarded as $n$-vectors. ...
0
votes
0answers
35 views

Optimisation using artificial neural network

Hello i have a set of 4 variables and for each variable there is 10 data points.now i also have a output data point with respect to each of these 10 data points of these 4 variables. Now i have to ...
3
votes
1answer
79 views

indirect method for least-squares with inequality constraints

I aim to find $x \in \mathbb{R}^n$ that $\min_x |D \cdot F \cdot x|^2$ subject to $x_i = X_i$ and $x_j \geq X_j$ , $i \in I, j \in J$ and I and J partition ${1\cdots N}$ into two sets. it is ...
0
votes
0answers
72 views

Help in developing a dynamic programming solution to this problem

I have asked this question on programmers.stackexchange but nobody was able to answer this question.I have asked for help on other forums but did not get much help.Since this is a part of my research ...
3
votes
2answers
159 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 ...
5
votes
2answers
145 views

Global maximization of expensive objective function

I am interested in globally maximizing a function of many ($\approx 30$) real parameters (a result of a complex simulation). However, the function in question is relatively expensive to evaluate, ...
0
votes
0answers
42 views

BFGS method with weights

Let me put the following question relating to the non-linear least squares $$\min_{x\in\mathbb{R}^{m}}\frac{1}{2}f^{T}(x)f(x).$$ Consider $J(m,n)$m, $m>n$, to be the Jacobian matrix and $W(m,m)$ ...
2
votes
1answer
125 views

How Matlab optimization works without Jacobian or Hessian

How does Matlab optimization tools works? It just gets the error function and doesn't need Jacobian (first derivatives) or Hessian (second derivatives)? How it is possible? If it is finite difference ...
4
votes
3answers
245 views

What's the fastest software(open source) to solve mixed integer programming problem

I have a mixed integer programming problem. And I am current using GLPK as my solver. But I found that GLPK is good for Linear Programming problem, but for Mixed Integer programming, it requires much ...