The global-optimization tag has no wiki summary.

**1**

vote

**1**answer

437 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

503 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

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

**11**

votes

**3**answers

862 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

341 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

465 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

91 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

255 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

846 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

686 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

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

**1**answer

626 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

640 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

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

**3**

votes

**2**answers

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

**5**

votes

**0**answers

391 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

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

**10**

votes

**2**answers

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

**5**

votes

**1**answer

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

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

**3**

votes

**3**answers

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

**2**

votes

**1**answer

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

**0**

votes

**1**answer

295 views

### max length or size of a convex set

I want to maximize $||x-y||$ with $x$ and $y$ in $C$ where $C$ is the intersection of some discs. We assume the intersection is nonempty, and closed. I am thinking, how to formulate it as a ...

**13**

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

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

**19**

votes

**5**answers

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

**1**

vote

**2**answers

217 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$
...

**2**

votes

**0**answers

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