The global-optimization tag has no wiki summary.
18
votes
5answers
8k 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 ...
14
votes
2answers
677 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 ...
13
votes
1answer
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 ...
11
votes
3answers
818 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
2answers
1k 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
0answers
174 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 ...
6
votes
4answers
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 ...
5
votes
2answers
462 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
0answers
323 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
1answer
662 views
Non-negative quadratic maximization
For a given symmetric, positive semidefinite, $n \times n$ matrix $A$, we want to solve the problem $$\max_{||x|| = 1, \;\;x >= 0} x^T A x.$$
Here, $x >= 0$ indicates that $x$ must be ...
4
votes
2answers
430 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 ...
4
votes
1answer
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
2answers
448 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
3answers
530 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 ...
3
votes
1answer
2k 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
2answers
169 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
2answers
403 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
2answers
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 ...
3
votes
1answer
351 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
1answer
554 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
0answers
129 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 ...
3
votes
0answers
231 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 ...
2
votes
3answers
272 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
3answers
343 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
1answer
109 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
3answers
463 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
1answer
166 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
2answers
489 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
2answers
306 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
1answer
257 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
1answer
135 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 ...
2
votes
1answer
129 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
1answer
62 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
1answer
214 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
2answers
560 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
0answers
150 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
0answers
148 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. ...
1
vote
1answer
108 views
Nonlinearly constrained optimization (quadratic)
Hi all -- what would be good methods (and/or software packages) to try for solving a problem minimizing a quadratic function $f(x) = \sum_{i=1}^N{(x_i - y_i)^2}$, where some constraints are non-linear ...
1
vote
2answers
170 views
what method can I employ to solve this optimization problem which involves \min?
The optimization problem is:
maximize $$\min(\sum\limits_{i=1}^N \log\left(a_{1,i}+\frac{b_{1,i}}{c_{1,i}+d_{1,i}x_i}\right),\sum\limits_{i=1}^N ...
1
vote
1answer
126 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 ...
1
vote
1answer
119 views
What kind is this optimization problem
I come across a problem like
$\max {\frac{1+v}{1-u}}$
$s.t.~$ $ux^2+vy^2-xy\ge0$ $\forall x,y\in\mathbb{R}$
I do not know much of optimization.
What I have done is that $ux^2+vy^2\ge ...
1
vote
2answers
206 views
how to estimate a polyhedron(convex hull) classifier from data sample
Given a set of points $X\in\Re^D$, they have labels $Y\in${$-1,+1$}. I would like to separate the data labeled +1 and the data labeled -1 by a polyhedron.
$min_w \sum_i \xi_i + \frac{1}{2}\|w\|_2^2$
...
1
vote
1answer
348 views
for what arguments the function reaches maximum?
Hi,
What is the maximum of the following function?:
$f(x_i,w_i)=\frac { \sum w_i}{ \sum \frac {w_i}{x_i} } - \frac{ 1 - \prod \left ( 1 - w_{i}\right )}{ 1 - \prod \left ( 1 - \frac{w_{i}}{ ...
1
vote
2answers
247 views
non convex optimization
Hi there,
In my studies I come up with this nonconvex optimization problem
argmin |Ax|_2+lamda*|x|_1 subject to x'x=1
where cost function is nonsmooth but convex and the constrant in nonconvex.
I ...
1
vote
1answer
309 views
Can one efficiently optimize over the inverse of matrix?
Hello,
I have the following problem:
Find a non-negative matrix $L$ (i.e. $L_{i,j} \geq 0$ for all $i,j$), $L \neq I$ so that $A(I-L)^{-1}y \geq 0$ (the inequality must hold for each component), ...
1
vote
1answer
485 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 ...
1
vote
0answers
91 views
Trying to get an idea of the maths I could use for this optimization problem
Firstly, apologies if some of the notation or terminology is odd, or if I am defining functions that have standard notation associated with them already - I am not familiar with the concepts in this ...
1
vote
0answers
117 views
An $L^{\infty} Version of Principal Component Analysis?
I have a $k$ by $n$ matrix $A$, with $k \ll n$. In case it helps, the $k$ rows are orthonormal.
I'm interested in finding a $k$ by $k$ orthogonal matrix $M$ so as to maximize the $L^{\infty}$ norms ...
1
vote
1answer
404 views
Global maximization of a particular function
Hello!
I want to prove that $x = 0.5$ is the global maximum of the function
$f(x) = ...
1
vote
0answers
144 views
On the convergence of a special fixed point iteration
The problem is actually a quadratically constrained quadratic program. And the formulation is:
$max: \frac{1}{2}x^TQx + d^Tx$
$s.t. x\in R^{n,+} ,\sum_{i\in I_p}x_i^2=1, p=1..k$
where $d\in ...