The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
0answers
109 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
1answer
571 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
98 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
1answer
261 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
1answer
353 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
1answer
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
votes
1answer
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
0answers
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
1answer
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
1answer
864 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
0answers
445 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
2answers
548 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
1answer
121 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
2answers
325 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
714 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 ...
10
votes
0answers
213 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
136 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
416 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) = ...
0
votes
0answers
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. ...
2
votes
1answer
182 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
0answers
804 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 ...
1
vote
2answers
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 ...
2
votes
2answers
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
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 \;\; ...
1
vote
1answer
147 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
1answer
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
0answers
191 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
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 ...
2
votes
3answers
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
0answers
360 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
1answer
740 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
2answers
574 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
0answers
215 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
3answers
887 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
2answers
380 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
1answer
614 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
0answers
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
1answer
300 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
2answers
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
3answers
942 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
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 ...
3
votes
1answer
665 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
1answer
942 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
4answers
501 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
2answers
724 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 ...
6
votes
0answers
545 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
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
2answers
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 ...
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 ...
4
votes
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 ...