The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
52 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 ...
0
votes
2answers
51 views

Analytic solution $\underset{n} {\mathrm{argmin}} \frac{a}{r + ns} + \sum_{i=0}^{n-1}\frac{b}{r + is}$ [closed]

Could anyone provide some hints for solving: $\underset{n} {\mathrm{argmin}} \frac{a}{r + ns} + \sum_{i=0}^{n-1}\frac{b}{r + is}$ for $n \in \{1,2,3,\ldots\}$ The problem is part of a coding ...
1
vote
2answers
225 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$ ...
0
votes
2answers
128 views

Uniqueness of solution of a nonconvex optimization problem

What conditions need to be hold for a nonconvex optimization problem to have a unique solution? Specifically, I have the following minimization problem that I'd like to know whether it has a unique ...
1
vote
0answers
28 views

Modified Orthonormal Procrustes Problem

In the general orthonormal Procrustes problem, we want to find an orthonormal matrix $C$ to minimize $\|Y-XC\|_F^2$, where $Y$ is a known $n\times q$ matrix, $X$ is a known $n \times m$ matrix, and ...
1
vote
2answers
145 views

iterative solution better than analytic solution? [closed]

My supervisor and I were discussing a specific optimisation problem this afternoon. To be simple: solve for $R$ in the equation $Rx=y$, where $x$, $y$ are made of samples in two difference ...
22
votes
6answers
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 ...
0
votes
0answers
28 views

numerical solver for stochastic optimal control problems

can any one recommend numerical solver (c/c++ library preferred) for stochastic optimal control problems? For deterministic optimal control I found something like that: ...
1
vote
1answer
134 views

maximizing a function involving factorial

Can someone suggest a way to calculate the maximum with respect to $x \ge 1$ of: $$f(x)=\frac{1}{x!} \frac{1}{1-c^{1/\binom{x+n-1}{n-1}}}.$$ The constants $c$ and $n$ are parameters such that $c \in ...
3
votes
2answers
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 ...
6
votes
1answer
240 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 ...
2
votes
2answers
160 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) & ...
0
votes
0answers
37 views

minimizing concave function

I am interested in using the algorithm of Harold Benson described in his 1991 paper: "A Branch and Bound-Outer Approximation Algorithm for Concave Minimization over a Convex Set". In the paper, he ...
1
vote
0answers
29 views

Changing a nonlinear equality constraint into some conic inequality plus rank constraint

If we have a constraint optimization problem in which one of our constraint is $\prod\limits_{k = 1}^N {\left( {x - {a_k}} \right) = 0} $ . How could this nonlinear equality condition be changed into ...
9
votes
4answers
261 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 ...
1
vote
1answer
49 views

Convergence rate of stochastic gradient decent with projections

Given a strong (not only strict) convex function $f: \mathbb{R}^n\to\mathbb{R}$. On such problems, stochastic gradient decent (SGD) has a convergence rate of $O(1/T)$, where $T$ is the number of ...
0
votes
0answers
52 views

Sufficient optimality condition for a non-smooth quasiconvex problem

The result of relaxing to an integer program is the following optimization problem: $$\min_{\textbf{x}} \sum_{i=1}^n \alpha_i h(x_i)\quad subject \; to \quad A\textbf{x} = \textbf{0}$$ where ...
2
votes
4answers
366 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 ...
1
vote
1answer
140 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} ...
1
vote
0answers
68 views

range of the difference-of-two-qubit-$4 \times 4$-density-matrix-determinants

The determinant of a two-qubit $4 \times 4$ density matrix--that is, a Hermitian, nonnegative definite matrix with unit trace--lies between $0$ and $(\frac{1}{2})^8$. (A "pure state" has determinant ...
2
votes
2answers
150 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 ...
0
votes
1answer
140 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 ...
5
votes
1answer
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 ...
1
vote
0answers
103 views

Maximizing an integral over a convex region

Let $C$ denote a compact, convex region in the plane containing the origin with unit area, and let $f$ be a probability distribution on $C$. Let $f^\ast$ denote the distribution that maximizes the ...
2
votes
1answer
103 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 ...
1
vote
0answers
133 views

Constructing an $\epsilon$-net for a Lipschitz subspace of $L^2$

Let $X$ be a subset of $L^2([0,1])$ which contains only Lipschitz function. Also, the member of $X$ are uniformly bounded $$ |x(t)| < M, \text{ for all $x \in X$ and $t \in [0,1]$}. $$ Let $F: X ...
20
votes
4answers
1k views

Why are optimization problems called “programming”?

Why are optimization problems often called programs? linear programming geometric programming convex programming Integer programming ...
2
votes
1answer
89 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
1answer
199 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 ...
1
vote
1answer
352 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}}{ ...
3
votes
2answers
223 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
1answer
368 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
0answers
82 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 ...
2
votes
1answer
285 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
1answer
88 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 ...
1
vote
1answer
130 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
votes
1answer
68 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
0answers
95 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
1answer
534 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 ...
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
0answers
357 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 ...
0
votes
1answer
103 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 ...
5
votes
2answers
513 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 ...
1
vote
2answers
283 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
1answer
388 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 ...
11
votes
3answers
863 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 ...
1
vote
2answers
185 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 ...
10
votes
0answers
198 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
0answers
126 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 ...
0
votes
0answers
525 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 ...