The global-optimization tag has no usage guidance.

**3**

votes

**1**answer

108 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?

**1**

vote

**1**answer

193 views

### Maximum Dispersion of a Connected Geometric Graph

Let $\left\{\mathbf{p}_1,\dots, \mathbf{p}_k\right\}$ be a set of points in $n$-dimensional Euclidean space, and let the second moment of these points be defined as:
$
U=\sum \limits_{i=1}^{k} ||\...

**3**

votes

**1**answer

260 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

**2**answers

266 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 + ...

**2**

votes

**1**answer

784 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 ...

**0**

votes

**0**answers

115 views

### The role of subgradient in programming with nonsmooth functions

It is obvious that there is similarity between subgradient and gradient. The subgradient of smooth functions is reduced to gradient. I have two questions.
The first is does there exist subgradient ...

**3**

votes

**1**answer

589 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 ...

**0**

votes

**1**answer

99 views

### Avoiding epsilon in mixed integer linear and quadratically constrained programs

I would like to represent the following constraint as MILP constraint where $x \in [a, b]$ with fixed $a, b \in \mathbb{R}$ and $y \in \lbrace 0, 1 \rbrace$.
$(x = 0 \wedge y = 1) \vee (x \neq 0 \...

**6**

votes

**1**answer

262 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 ...

**1**

vote

**1**answer

354 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}}{ x_i}\...

**1**

vote

**1**answer

142 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 2\sqrt{uv}xy\...

**2**

votes

**1**answer

72 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 ...

**1**

vote

**0**answers

101 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 ...

**0**

votes

**1**answer

149 views

### necessary and sufficient conditions for a function to be DC

Hi, Does anyone know the necessary and sufficient conditions for a function to be a DC-function?
Definition: A function is a DC-function if and only if it can be written as a differnece of 2 convex ...

**0**

votes

**1**answer

886 views

### Finding the lowest cost set of disjoint paths using all nodes in a directed graph?

I have a directed graph with edges connecting nodes representing costs.
I wish to find the set of paths which
-go from node 'start' to node 'end'
-are node-disjoint (except for the start and end ...

**3**

votes

**0**answers

449 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 ...

**5**

votes

**2**answers

550 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 ...

**0**

votes

**1**answer

125 views

### Is these two optimization problems share the same solution?

Hello all,
I am dealing with some SDP optimization, and I come across the following problem.
The optimization problem is given by
\begin{aligned}
&\operatorname*{min}_{t_1,\ldots,t_m,X}\ \sum ...

**1**

vote

**2**answers

336 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 ...

**2**

votes

**1**answer

730 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 $f_{...

**10**

votes

**0**answers

214 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 ...

**1**

vote

**0**answers

138 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

**1**answer

417 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) = \frac{(1-a)^2e^{(2x\cdot(x-1)a^2)}}{(1-a)(e^{(2x\cdot(2x-1)a^2)}+e^{((2x-1)\cdot(2x-2)a^2)})-2(1-2a)e^{(4x\cdot(x-...

**0**

votes

**0**answers

62 views

### equivalence between primitive and dual

Hi everyone! I have a problem about the duality gap of the primitive problem and the dual problem.
This problem comes from a probabilistic model named Lagrangian UVM.
http://www.freeimagehosting.net/...

**2**

votes

**1**answer

183 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}$ (...

**0**

votes

**0**answers

836 views

### optimization of a separable function

Hello everyone,
this is a optimization problem whose objective function is separable:
$$F(x)=\sum_{i=1}^n\frac{\theta_i^2}{4}\sum_{j=1}^m\left(1+\rho x_ik_j+\sqrt{(x_ik_j+\rho)^2+1-\rho^2}-\frac{2\...

**1**

vote

**2**answers

199 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 \log\left(a_{2,i}+\frac{b_{2,i}}{c_{2,i}+d_{2,i}x_i}\...

**2**

votes

**2**answers

2k 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

### 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
\;\;
\...

**1**

vote

**1**answer

148 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 ...

**2**

votes

**1**answer

167 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 ...

**3**

votes

**0**answers

193 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 ...

**3**

votes

**2**answers

1k 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 ...

**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 ...

**0**

votes

**0**answers

361 views

### Optimization of a matrix with an objective function (for ML)

Hi.
I need to do max. likelihood for an objective likelihood function L (minimize it), and the target is a matrix. ie:
$$min_KL(K)$$
For example:
K is, let's say, of size 3x3 and with initial ...

**1**

vote

**1**answer

769 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), ...

**5**

votes

**2**answers

580 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 ...

**1**

vote

**0**answers

217 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 R^{n,+}$,...

**11**

votes

**3**answers

888 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 ...

**2**

votes

**2**answers

381 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 ...

**3**

votes

**1**answer

633 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 ...

**0**

votes

**0**answers

94 views

### minimizing the integral of a function over square sets.

Hi!
I'm interested in some problems, but to be honest i'm not sure of the field they belong to.
Let $h(x,y)$ be a bivariate function on $X^2$, where $X$ is some nice topological space (for instance $...

**0**

votes

**1**answer

303 views

### Ranking algorithm [closed]

Hi!
I am interested in an algorithmic question. I'm not at all a specialist but I'm interested in this for very pragmatic reasons that you will understand. Maybe the problem is well known.
In a ...

**14**

votes

**2**answers

1k 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 ...

**2**

votes

**3**answers

967 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}$, $...

**3**

votes

**2**answers

4k 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

**1**answer

670 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 ...

**2**

votes

**1**answer

956 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

**4**answers

513 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 lines:...

**3**

votes

**2**answers

748 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 ...