# Tagged Questions

The tag has no usage guidance.

17k 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 ...
2k views

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

Why are optimization problems often called programs? linear programming geometric programming convex programming Integer programming ...
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 ...
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 ...
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 ...
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 ...
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 ...
381 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 ...
303 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 ...
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 ...
670 views

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

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

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

### Two fold optimization: is there an established approach for this kind of problem?

I have a list of thousands of linear expressions, with less than 100 total variables. Each expression is associated with a positive point value. I want to make as many of the expressions greater than ...
87 views

### Optimization of a function of a positive definite matrix and its inverse

This question is a little ill-posed, but I've been playing with some equations and am just wondering if this resembles any known problems that have been solved. Suppose I have two real, positive ...
76 views

I have a function $F$ which is defined as follows: $$F(x) = \sum_{i=1}^N f(z_i^T x)$$ where ${z_i}$ are known $m \times 1$ vectors, $x$ is an $m \times 1$ vector, and for $t\in \mathbb{R}$, $f(t) = \... 2answers 2k 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 ... 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 ... 0answers 211 views ### maximize non-convex composite function I want to maximize a composite function over a convex set \begin{aligned} & \underset{\mathbf{p}}{\text{maximize}} & & f(\mathbf{p})-g(\mathbf{p})\\ & \text{subject to}... 2answers 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 ... 2answers 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 ... 2answers 745 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 ... 1answer 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? 2answers 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 + ... 1answer 587 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 ... 1answer 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 ... 1answer 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 ... 1answer 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 ... 0answers 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 ... 0answers 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 ... 2answers 197 views ### Maximal minimum for a sum of two (or more) cosines Please prove (or disprove, and give the correct answer):$$2 =\mathrm{argmax}_{r\geq 1}\min_{x\in \mathbb{R}}\left[\cos\left(x\right)+\cos\left(rx\right)\right] $$In other words, find r \geq 1, ... 4answers 512 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:... 2answers 2k 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) & ... 3answers 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 \;\; \...
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 ...