The global-optimization tag has no usage guidance.

**25**

votes

**6**answers

12k views

### Is all non-convex optimization heuristic?

Convex Optimization is a mathematically rigorous and well-studied field. In linear programming a whole host of tractable methods give your global optimums in lightning fast times. Quadratic ...

**20**

votes

**4**answers

1k views

### Why are optimization problems called “programming”?

Why are optimization problems often called programs?
linear programming
geometric programming
convex programming
Integer programming
...

**15**

votes

**1**answer

2k views

### A circle packing conjecture

Consider $n$ circles with variable radii $r_1,\ldots, r_n$ that pack inside a fixed circle of unit radius. In other words, all $n$ variable-radius circles are contained in the unit radius circle and ...

**14**

votes

**2**answers

933 views

### Finding minimum (or maximum) element of a low rank matrix.

Let $A\in\mathbb{R}^{n\times n}$ and suppose that $A$ is of rank $m\leq n$. Moreover suppose we know $u_1,\ldots, u_m \in\mathbb{R}^{n\times 1}$ and $v_1,\ldots, v_m \in\mathbb{R}^{n\times 1}$ such ...

**11**

votes

**3**answers

874 views

### Greatest function satisfying some convexity requirements

Edit: Even though there is an accepted answer, the problem isn't solved. I only accepted the answer, because there was a bounty on the question so I had to accept an incomplete answer.
I was working ...

**10**

votes

**2**answers

2k views

### Maximizing the Smallest Eigenvalue of a Diagonally Dominant Matrix

Assume that we have a full-rank diagonally dominant matrix $A$, all the diagonal elements of which are positive, all the non-diagonal elements are negative, and the sum of the absolute values of the ...

**10**

votes

**0**answers

208 views

### “Small” maps from sphere to sphere

Start with a continuous map $f:S^{n+k} \rightarrow S^n$ (round unit spheres). The graph of $f$ lives in $S^{n+k}\times S^n$ and suppose it has a surface area (as a subspace of co-dimension $n$). Now ...

**9**

votes

**4**answers

282 views

### Software tools for medium-scale systems of polynomial equations

I am attempting to find all real solutions of a system of 12 polynomial equations in 12 unknowns. The equations each have total degree 6 and contain up to 1700 terms. I am only interested in real ...

**8**

votes

**3**answers

288 views

### “Most Similar Vector Problem” on an Integer Lattice?

I am currently working on problem that I think could be expressed as an integer lattice problem.
Given $u \in \mathbb{R}^n$ and a bounded integer lattice $L = \mathbb{Z}^n \cap [-M,M]^n$ I would like ...

**6**

votes

**3**answers

636 views

### Some questions about Invexity

Recently, I am looking into a non-convex optimization problem whose points satisfying KKT conditions can be obtained. Then the problem becomes how to decide whether the KKT conditions are sufficient ...

**6**

votes

**1**answer

248 views

### Generalization of the equilateral triangle?

I consider points in the two-dimensional plane.
An equilateral triangle is a set of three points in the plane which are equidistant.
Suppose now I have $n$ points $x_1,...,x_n$. What is the ...

**6**

votes

**4**answers

1k views

### Robust black box function minimization with extremely expensive cost function

There is an enormous amount of information about the common applied math problem of minimizing a function.. software packages, hundreds of books, research, etc.
But I still have not found a good ...

**6**

votes

**0**answers

98 views

### A specific case of the $p$-center problem

Given a fixed positive integer $m$, let $\cal{S}$ be the subset from $\mathbb{R}^m$ defined as $\cal{S} = \{u \in \mathbb{R}^m \mid \forall i \in \{1, \dots, m\}, u(i) > 0$ and $\sum_{i=1}^m{u(i) = ...

**5**

votes

**2**answers

535 views

### Gandhi's quote formalized [closed]

Hello,
I hope this question is appropriate for Mathoverflow. Gandhi said, "Be the change that you wish to see in the world". I don't understand anything in Game/optimization theory (I don't know ...

**5**

votes

**1**answer

1k views

### Non-negative quadratic maximization

For a given symmetric and positive semidefinite $n \times n$ matrix $A$, we want to solve the problem $$\max_{||x|| = 1, \ x\geq 0} x^T A x.$$
Here, $x\geq 0$ indicates that $x$ must be component-wise ...

**5**

votes

**2**answers

552 views

### Getting started: combinatorial optimization for computer scientists

I have a background in computer science and I am starting to work on some problems those are basically combinatorial optimization problems.
I have good knowleges of graphs, *-flow algorithms and so ...

**5**

votes

**0**answers

432 views

### Maximizing the matrix norm

Hi all,
I wish to find a 3x3 rotation (orthogonal) matrix $\mathbf{R}$ such that it maximizes the following matrix norm:
$||\mathbf{A} \mathbf{D}_r \mathbf{D}_b ||_2$
where $\mathbf{A}$ is a known ...

**4**

votes

**2**answers

1k views

### Optimal knot placement for fitting piecewise-continuous linear functions to a nonlinear function

I encountered this problem in my research and it is turning out to be a surprisingly difficult one(for me, at least).
Suppose we have a univariate nonlinear function $f(x)$ where $x \in [L,U]$. Our ...

**4**

votes

**1**answer

2k views

### Homogeneous system of polynomial equations

Hi all,
Previously I asked a question that currently has no satisfactory answer Least sum squares given constraints on subcomponents
It comes from an engineering problem. I was thinking to formulate ...

**3**

votes

**2**answers

867 views

### Computational complexity of unconstrained convex optimisation

What is known about the relationship between unconstrained convex optimisation and computational complexity? For example, for which optimisation problems and which gradient descent algorithms is one ...

**3**

votes

**2**answers

3k views

### Linear program to maximize the minimum absolute value of linear functions ?

I'd like to compute
$\max_{x,t} t$ such that $\forall i$, $t < a_i + |x - b_i|$.
where $a_i,\ldots, a_n$ and $b_1,\ldots,b_n$ are fixed and $x \in [0,1]$.
Can this be solved with a linear ...

**3**

votes

**2**answers

617 views

### Optimizing a quadratic restricted to the sphere

Let $A$ be $p\times p$ symmetric positive definite with distinct eigenvalues and $x_p\in \mathbb{R}^p$ and consider the problem
Minimize $x'Ax + b'x$
Subject to $x'x=1$
Most of the information I've ...

**3**

votes

**1**answer

95 views

### Compactness of a semi algebraic set

Suppose I have a polynomial $p\in R[x_1,\ldots,x_n]$ and I look at the set $S:=\{ x\in R^n : p(x)\geq 0\}$. Are there algebraic certificates on $p$ that will certify that $S$ is compact?

**3**

votes

**2**answers

229 views

### Uniqueness of fixed points for rational transformations

Background
Let $a,b,c,d$ be nonnegative constants and consider the map $T\colon [0,1]\times[0,1] \rightarrow [0,1]\times[0,1]$ defined by
$$
T(x,y) := \left( \frac{1}{1 + ax + by}, \frac{1}{1 + cx + ...

**3**

votes

**1**answer

531 views

### Java library for SDP [closed]

People who frequently code semi definite programs, is there any java library for solving sdps? I have tried my luck but all I can find is C/C++ libraries or matlab toolboxes. I can write wrappers to ...

**3**

votes

**1**answer

219 views

### Optimization problem - maximizing number of satisfied linear inequalities subject to a quadratic constraint

I am wondering what is known about optimization problems of the following type.
Our control x is a unit vector in $\mathbb{R}^n$. We are given a finite number of linear inequalities
$$Az≥b,$$
and we ...

**3**

votes

**1**answer

650 views

### maximization of a quadratic function with a quadratic constraint

I have the following quadratic maximization problem
$\max_{\mathbf X} \quad tr(\mathbf A\mathbf X\mathbf B\mathbf X^H)+tr(\mathbf C\mathbf X)+tr(\mathbf C^H\mathbf X^H)$
subject to the quadratic ...

**3**

votes

**0**answers

410 views

### Minimum weight bipartite graph clique covering

I was wondering if anyone here could give me any pointers as to how to solve the following problem.
Let $B=(L,R,E)$ be a bipartite graph, and $\forall u\in L\cup R$, let $c_u$ be a cost associated to ...

**3**

votes

**0**answers

186 views

### Could SVD be used to optimize the partial inner-products?

Suppose a set $N$ of $n$ distinct points in $m-$dimensional space is given in $X\in\mathbb{R}^{n\times m}$. Also, suppose a subset $L\subset N$, $|L|=l<m<n$, with
$m-$dimensional coordinates in ...

**2**

votes

**4**answers

414 views

### Efficient algorithm for finding the minima of a piecewise linear function

Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by
$f(x) = \max_i ( a_i + b_i x )$
We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two ...

**2**

votes

**3**answers

761 views

### Efficient Algorithm For Projection Onto A Convex Set

Given $\mathbf{x} \in \mathbb{R}^n$ and $\tau$ a scalar, I would like to solve the following Euclidean projection problem:
$\underset{\mathbf{p}}{\mathrm{argmin}} \; \|\mathbf{p}-\mathbf{x}\|_2
\;\;
...

**2**

votes

**1**answer

152 views

### Maximizing positive definite quadratic using the eigendecompoisition

Consider the problem:
$\textrm{max}\;\; x^T Q x$
subject to $||x||_\infty \leq 1$, where $Q$ is a positive definite matrix.
I believe this problem is NP-hard (although I have only found hardness ...

**2**

votes

**3**answers

834 views

### Maximizing the minimum of piecewise linear functions in high dimensional space

I'd like to compute
$\max_{x,t} t$ such that $\forall i$, $t < a_i + \|x - b_i\|_\infty$.
where $a_i,\ldots, a_n \in \mathbb R$ and $b_1,\ldots,b_n \in [0,1]^{21}$ are fixed, $x \in [0,1]^{21}$, ...

**2**

votes

**2**answers

401 views

### How to fit the parameters of differential equations with known data?

I have the following data from chemical kinetics research to fit the parameters of ordinary differential equations:
$$
\left[
\begin{array}{ccccccc}
\text{No.}& t & y_1(t)&y_2(t) & ...

**2**

votes

**2**answers

228 views

### Finding the maximum of a multivariate polynomial of degree one

I need to find the global maximum of the function
\begin{align}
f\left(x\right) & = p_1 \max\left(\sum a_{1i} x_{1i}, \sum b_{1i} x_{1i}\right) - \sum c_{1i} x_{1i} \\
&+\ldots \\
&+ p_n ...

**2**

votes

**1**answer

390 views

### lipschitz constant of a multivariate function

I have a function $f:\mathbb{R}^{50} \rightarrow \mathbb{R}$ and I need to compute the Lipschitz constant of $f$ to solve an optimization problem using a specific algorithm. Does any one have ...

**2**

votes

**1**answer

176 views

### A Function with Exactly $k$ Minima in a Bounded Space

Is it possible to have a function with the following properties?
(i) The function maps a bounded $n$-dimensional space $\mathcal{X}$ (say $\left[0,1\right]^n$) onto a bounded interval $\mathcal{Y}$ ...

**2**

votes

**1**answer

109 views

### Is there any algorithm can find local minima of nonconvex objective function in guaranteed polynomial time?

More precisely, The setting could be formulated as,
$min. F_{\lambda}(p)$ over permutation matrices $P$
Here $F_{\lambda}(p)$=$\lambda *F_{0}(p)+(1-\lambda)F_{1}(p)$
where both $F_{0}(p)$ and ...

**2**

votes

**2**answers

1k views

### Dual Norm For Sum of 2-Norms

What is the dual of a norm that is the sum of two-norms? Specifically, say we have the following norm for $\mathbf{x}\in \mathbb{R}^n$ and $\mathbf{A}_i \in \mathbb{R}^{m \times n}$
$\|\mathbf{x}\| = ...

**2**

votes

**3**answers

1k views

### Best algorithm/software for solving a planar transportation problem ?

I am looking for software (open-source or otherwise) or an implementable algorithm for solving a continuous transportation problem. The input consists of a pointset in a planar rectangle, and we need ...

**2**

votes

**2**answers

371 views

### Functional Minimization: When is this heuristic rigorous?

I'm trying to solve a functional minimization problem of the following form:
$$\arg\min_{f:\mathbb{R}\rightarrow [0,1]} h(f)$$
where $h$ is some expression in terms of several integrals over $f$.
I ...

**2**

votes

**1**answer

277 views

### Can subgradient infer convexity?

It is known that
If $f:U→ R$ is a real-valued convex function defined on a convex open set in the Euclidean space $R^n$, a vector v in that space is called a subgradient at a point $x_0$ in $U$ if for ...

**2**

votes

**1**answer

136 views

### Maximum of a mollified/convolution function

I have a function $f:{\mathbb R}\rightarrow {\mathbb R}_+$ which has a unique maximum at $x=0$. $f$ can be symmetric or asymmetric. I am interested on the mollified-f function
...

**2**

votes

**1**answer

111 views

### A Recursive Maximization Problem

Let $A\ge B>0$ be real constants. I say that a function $f:[0,1]\rightarrow[0,1]$ satisfies the $(A,B)$-condition if for all $p\in [0,1]$, the expression
$$q(A-Bp-Bf(q))$$
is maximized (not ...

**2**

votes

**1**answer

71 views

### Computing a point of refraction

Oddball question: say I want to travel from $(a, b)$ where $b > 0$ to $(c, d)$ where $d < 0$ using the shortest path, where I can travel at velocity $v_1$ in the upper half-plane and at velocity ...

**2**

votes

**1**answer

496 views

### Proving that a specific function is quasiconvex

Hello all,
Assume we have a sequence of quasiconcave functions (in $X$) denoted by $f_{i,j}(X)$ for $i,j = 1,\ldots,n$. Denote by $F(X)$ the $n\times n$ matrix whose $(i,j)$ entry is the function ...

**2**

votes

**1**answer

785 views

### Official name and complexity of k-way balanced set partitioning? What is the best heuristic?

As a lot of people know, graph partitioning is NP-Complete. In graph partitioning, you try to create k balanced (within some pre-specified epsilon) disjoint subsets of (possibly weighted) vertices ...

**2**

votes

**0**answers

140 views

### Solution of a linearly constrained quadratic programming problem [closed]

What is the solution of the following optimization problem:
\begin{align}
&\min{\mathbf{p}^\mathrm{T} \mathbf{B} \mathbf{p}}\\
&\text{subject to}: \mathbf{0}\leq{\mathbf{p}}\leq \mathbf{1}.
...

**2**

votes

**1**answer

528 views

### Maximizing supermodular functions

I have a real supermodular objective function which I want to maximize with constraint. The constraint is on the size, like |A|=k .
I am wondering if anyone can give me more information about a ...

**2**

votes

**0**answers

159 views

### modification of singlestart in global optimization

When minimizing a nonconvex function $f : \Omega \rightarrow \mathbb{R}$ that may have multiple minima, there are some very simple strategies to improve the odds of finding the global minimum point. ...