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
1answer
67 views

Doubt regarding stopping criterion for Newton method

I am solving an unconstrained convex optimization problem, which can easily have a million variables. I am trying to get a working system with a toy problem of around 200 variables. I am noticing that ...
0
votes
1answer
57 views

Unconstrained minimization of unbounded function with SciPy

It seems that scipy.minimize can find the minimum of an unbounded function. ...
0
votes
0answers
39 views

stochastic optimization with unknown distribution

I have a stochastic optimization problem in which I have expectation in constraints. we do not have any any information about distribution function of the random variable a prior. I know in cases you ...
4
votes
2answers
110 views

Nearest positive semidefinite matrix to a symmetric matrix in the spectral norm

So I have a symmetric matrix $A$ and I would like to solve the optimization problem: $$\text{Minimize}\;\; ||A-S||_2$$ $$\hspace{-5mm}\text{Subject to}\;\; S\geq0$$ $A$ is given and $S$ is the ...
1
vote
2answers
48 views

Optimization: Providing gradients by autodifferentiation e.g PyAutoDiff

What is the difference (in terms of e.g robustness and speed) between proving a gradient obtained by an AD package (like PyAutoDiff) and let the solver (e.g BSGS) calculate the gradient ? It seems so ...
2
votes
1answer
89 views

optimization (using python) how to find the most suitable solver?

I have a fitting routine set up. It works, but pretty slow. I was wondering if there is a better method to use. I checked my (forward) code against some literature data and at least I do have no bugs ...
0
votes
0answers
32 views

Dynamic programming as final value problem?

I refer to the note "Stochastic systems" by Geering, Dondi, Herzog, Keel (freely available as a pdf ); We consider a stochastic optimal control problem, i.e. given a dynamical system with state ...
2
votes
1answer
70 views

Generalized linear-fractional program [closed]

Given the generalized linear-fractional program: $$\text{Minimize}\;\; \max_{i}\Big|\frac{c_i^Tx+d_i}{e_i^Tx+f_i}\Big|$$ $$\hspace{-5mm}\text{Subject to}\;\; e_i^Tx+f_i>0$$ I convert this into the ...
0
votes
0answers
65 views

Help with the definition of constraints for a joint optimization problem

A trajectory is piecewise defined by the following polynomial form: $$ f(t) = a + bt+ct^{2}+dt^{3}+et^{4}+ft^{5}+gt^{6}+ht^{7}+it^{8}+jt^{9} $$ for every single segment composing the trajectory (the ...
2
votes
2answers
92 views

Find $\min x^TAy$ subject to $1^Tx=1^Ty=1,x\ge 0,y\ge 0$

In the following problem, $A$ is a given $\mathbb{R}^{m\times n}$ matrix: \begin{align} \mbox{minimize}\quad & x^TAy \\ \mbox{subject to}\quad & 1^Tx=1^Ty=1, \\ & x\ge 0,y\ge 0. ...
3
votes
1answer
109 views

Converting quadratic constraint to linear matrix inequality

So I have the quadratic programming problem: (x is the variable) $$\text{Minimize}\;\; x^T\Sigma x$$ $$\hspace{15mm}\text{Subject to}\;\; p^Tx = \frac{1}{n}p^T\boldsymbol{1}$$ ...
2
votes
1answer
49 views

Piecewise linear optimization with resource allocation constraints

I have this problem: \begin{align} \min_{\mathbf{w}} & \sum_{i=1}^N c_i P_i(w_i)\\ s.t & \notag\\ & \sum_{i =1 }^N w_i = w \\ & 0 \leq w_i \leq w_{max},~~\forall i \in 1, ..., N ...
1
vote
0answers
62 views

Search Direction in Conjugate Gradient

Could you help me with a Conjugate Gradient question? In using CG to solve Ax=b, why is the search direction $p_{k+1}$ in CG chosen as a linear combination of the residual $r_k$ and previous direction ...
5
votes
0answers
61 views

Reference request for numerical variational method

I have a variational problem where the unknown function is a periodic path $\gamma:[0,1)\to\mathbb{R}^2$, and the functional is $$ \int_0^1\left( \tfrac12\|\dot\gamma(s)\|^2 + ...
1
vote
0answers
59 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?
-1
votes
3answers
106 views

optimization non linear problem with java code

Is there some packages in java that can be included to eclipse in order to solve a non linear problem? I have used ipopt but when running, there is a notification which say "NOTE: You are using Ipopt ...
1
vote
1answer
71 views

Minimization of The Blind Deconvolution Functional

I want to minimize the functional of teh Blind Deconvolution model as given in: Total Variation Blind Deconvolution by Chan and Wong. Their model is given by: $$ z = h \ast u + \eta $$ Where $ \ast ...
0
votes
0answers
121 views

How to solve this problem using Particle Swarm Optimization?

I'm currently revising my optimization algorithm for a specific part of a problem. I have trouble in wrapping my head around a new approach and my mind is having this tunnel-vision of ideas. I could ...
0
votes
1answer
68 views

Largest Cylinder inside Polyhedron

Imagine you have a piece of wood and from that piece you want to get the largest cylinder possible. How do you determine the position and orientation of the cylinders axis, to maximize its radius? ...
0
votes
0answers
75 views

Solving 10000, Non-Linear, Simultaneous Equations

Could anyone let me know if there is any optimization solver that I can use to solve about 10,000 simultaneous equations (most of which are non-linear) using Python? Please also advise if it is ...
0
votes
0answers
47 views

Coding a convex problem in CVX

I am new to CVX and am trying to simulate this convex problem I found in a paper. $$\min_{\gamma,\mathbf{mu},\mathbf{G},\mathbf{\Omega},t} \text{Tr}(\mathbf{G}\mathbf{C}\mathbf{G}^H)+t \\ s.t. ...
0
votes
2answers
55 views

MILP formulation and optimization

For $i=1, \dotsc, K$, we have $n_i$ ordered real numbers: $$ x_i(1) \leq x_i(2) \leq \dotsc \leq x_i(n_i) $$ I want to solve the following optimization problem: \begin{align} \mathrm{maximize} \; ...
1
vote
1answer
65 views

Global optimization methods in computational chemistry

I'm looking for a current and comprehensive overview (like a review article) of global optimization methods and their application in computational chemistry. Mostly I'm interested in geometry ...
1
vote
0answers
78 views

Optimizing rank computation for very large sparse matrices

I have a sparse matrix such as ...
1
vote
1answer
65 views

Discrete optimization on a cartesian product with component-wise increasing objective function

The set-up is the following: We have $K$ finite sets of real numbers, i.e. sets $G_i, i=1 \dotsc, K$ and $|G_i| = n_i < \infty$. Furthermore, assume that we have a function $$ h: \mathbb R^K ...
0
votes
1answer
112 views

Disciplined convex programming error: Only scalar quadratic forms can be specified in MATLAB's CVX

I want to minimize $$W\, \text{tr}\left([A-Y_{pie}][A-Y_{pie}]^T\right) + \lambda\Vert A\Vert\, \enspace ,$$ however, I encounter the following problem: ...
0
votes
1answer
66 views

Deflation for generalized eigenvalue problem

We know that principle component analysis (PCA) is a eigenvalue problem. Let $A$ be the covariance matrix of $X$, PCA aims to find the eigenvalue of $A$: $\max v'Av$, subject to $v'v=1$ Multiple ...
7
votes
1answer
135 views

Performance of adding eight numbers sequentially vs. in a tree

The simplest way to add 8 numbers would be something like this, sum = one + two + three + four + five + six + seven + eight; This (in C) would add ...
5
votes
1answer
131 views

Intuition behind Alternating Direction Method of Multipliers

I've been reading a lot of papers on ADMM lately, and also tried to solve several problems using it, in all of which it was very effective. In contrast to other optimization methods, I can't get a ...
2
votes
1answer
63 views

fitting a non-linear curve

I have an equation: $\ddot{x}+(\delta+\epsilon\cos{t})x=0$ known as the Mathieu equation.The $\delta-\epsilon$ parameter space of this equation looks something like The red lines in this diagram ...
0
votes
0answers
17 views

MAX-SAT for infinite system

Is there a generalization of maximal satisfaction (MAX-SAT) based on infinitely many variables? One natural occurrence of such problem is the general Ising model in material science.
1
vote
1answer
36 views

state of art MAX-SAT solver for ising spin glass

What is the best MAX-SAT solver problems for Ising spin glass? I tried Scip-Max-sat and open-wbo. While open-wbo cannot solve the instance with only 27 variable Scip-max-Sat fail to solve the one with ...
3
votes
2answers
37 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. ...
0
votes
2answers
110 views

Statistical analysis of optimization algorithms

If we optimize some parameter using 4 optimization algorithms, 2 of which are population based (say A and B) and 2 trajectory methods (single point search)(say C and D); what statistical test can be ...
2
votes
3answers
114 views

Beale's function and newton iteration

I am trying to find the minimum of the so called Beale’s function given by $f(x_1,x_2) = (1.5-x_1+x_1x_2)^2 + (2.25-x_1+x_1x_2^2)^2 + (2.625-x_1+x_1x_2^3)^2$ Using Newton iteration $x^{(k+1)} = ...
1
vote
1answer
58 views

Comparison of the time efficiency of an optimization problem formulated as a Network Flow model and Mixed Integer Programming

In combinatorial optimization, there are many problems that can be formulated as either Network Flow model or Mixed Integer Programming (MIP), e.g. supply chains, transportation, and graph-base ...
2
votes
0answers
59 views

Maximize sum of Rayleigh quotients

I want to maximize the sum of Rayleigh quotients: $$\max_x\sum_{i=1}^n\frac{x^\top A_i x}{x^\top B_i x}$$ where $A_i$ and $B_i$ is positive definite. I've found a similar question here: minimization ...
0
votes
0answers
16 views

Max weighted subset (max sum diversification)

Given a set of elements $V$, with known cost $\pi_S$ for each subset $S \subset V$ and a monotone increasing function on the subsets $f(S)$ . I'm wondering if there is a pseudo-polynomial algorithm ...
2
votes
1answer
31 views

Combinatorial optimization problem: choose a set of corrective factors to make a set of points most closely resemble a plane

Apologies in advance if this has already been asked before (I suspect it has, but I'm not experienced to know what to call it, or how to classify this problem). Given a set of $m$ points in space, ...
2
votes
2answers
141 views

How many generations does it typically take for a differential evolution method to reach a global optimum?

For differential evolution methods in optimization, how many generations does it typically take to reach a global optimum? How do we know if the values are never going to converge?
3
votes
2answers
241 views

Parallel optimization algorithms for a problem with very expensive objective function

I am optimizing a function of 10-20 variables. The bad news is that each function evaluation is expensive, approx 30 min of serial computation. The good news is that I have a cluster with a few dozen ...
1
vote
1answer
82 views

How does the number of iteration until optimization begins depends on the dimension of the problem?

I am optimizing a function of 10-20 variables by running algorithm such as BOBYQA and a few other derivative-free algorithms. The bad news is that each function evaluation is very expensive, approx 30 ...
1
vote
3answers
125 views

Minimize quadratic form with equality constraints

I want to minimize function: $f(x) = x^T \cdot A \cdot x + b \cdot x$ given constraints: $B \cdot x = 0$. Here: $x$ is a vector ($x \in \mathbb{R}^n$), $A$ is a matrix of size $n \times n$, $b$ ...
1
vote
2answers
67 views

Solving a minimization problem with “scaled” equality constraint

Given a symmetric positive semi-definite matrix $Q\in\mathbb{R}^{n\times n}$, a vector $v\in\mathbb{R}^n$, a matrix $A\in\mathbb{R}^{m\times n}$ and a vector $b\in \mathbb{R}^m$ I'd like to solve the ...
4
votes
1answer
116 views

Finding a global minimum of non-convex quasi-smooth function that is costly to evaluate

I have a bounded non-convex function in 10-dimensional space. The function is quasi-smooth, you can imagine a histogram, here is an illustration, it just shows the idea and not related to my ...
0
votes
0answers
32 views

Sequence optimization for multithreading

Given a list of object I must compute an expensive operation on any couple of object of the list. So I need to create a sequence of tasks. I want to find the sequence of tasks such that there is the ...
4
votes
1answer
55 views

Does the amount of correlation of model parameters matter for nonlinear optimizers?

I am using nonlinear optimizers such as BOBYQA to train a model with 10-20 parameters. It so happens that some of the parameters have high correlation. Roughly speaking, imagine that you are fitting ...
8
votes
2answers
112 views

Method to quantify geometric difference of two dissimilar meshes

I am looking for a method or algorithm to produce a value that describes how different two meshes are geometrically but that have different topologies. An example would be some CAD data that has had ...
2
votes
2answers
90 views

fastest and most efficent way to count all combinations in many sets and sum them together

I am a Java programmer who has reached the limits of brute computer power. My relational database (and non relational databases) is not producing results quick enough and I have hit a bottleneck in ...
3
votes
1answer
107 views

How to solve this optimization problem with abs object function?

Helo, every one. May I ask for help about how to solve this problem. $\begin{align} & \text{max}_{x_i} \quad |\sum_{i=1}^{4} a_i x_i | \\ & s.t. \quad \sum_{i=1}^4 x_i^2=1 \end{align} $ ...