The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
0answers
18 views

Dennis More' Superlinear Convergence_refrences request

Why in the proof of superlinear convergence of restricted broyden class (for the unconstrained optimization) we need the bounded deterioration condition for the approximation of all the true hessian ...
3
votes
2answers
263 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 + ...
0
votes
0answers
58 views

Optimization with vectors

I am trying to solve the following optimization problem as a small part of a research project, and I do not know if there exists closed form solutions. My linear algebra is very rusty and I am looking ...
0
votes
0answers
175 views

A contractive mapping which I don't understand

Given a matrix $Y$ and a vector $c$ define the following iteration $\hat{c} = f(c)$, where each element of $\hat{c}$ is given by $$\hat{c}_{\ell} = \frac{\sum_k ...
0
votes
1answer
105 views

Convert general optimization problem to LP problem

I am trying to convert the following problem into a linear programming problem: There are $M\times N$ matrix $T$ of real numbers between 0 and 1 and $N\times 1$ vector $w$ of real numbers between 0 ...
0
votes
0answers
47 views

Separable Least squares - is there a notion of conjugate directions?

I have a general question. Suppose I have the following to optimize $$\|Y-A(\mathbf{x})B(\mathbf{y})\|^2$$ where $Y$ is a vector, $A(\mathbf{x})$ is a matrix that depends on a vector $\mathbf{x}$ in a ...
5
votes
1answer
82 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 ...
2
votes
2answers
194 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$, ...
-1
votes
2answers
91 views

Is finding a local minimizer of a NP-hard optimization problem is still NP-hard [closed]

I was wondering if for a NP-hard optimization problem, I only want to find its local minimizer, is it still NP-hard or NP-hard is only true when trying to find a global minimizer?
1
vote
0answers
17 views

Deterministic global solution to find the Optimal-knot placements for continuous piecewise linear functions to fit nonlinear data

I have been searching lately for a deterministic global technique to linearize a nonlinear function with continuous piecewise linear regions. I've a univariate nonlinear function y=f(x). where f(x) ...
1
vote
0answers
31 views

solution of an infinite horizon optimization problem

Give the following formulation: $\min_{\{x_s(t):\forall s,t\}} \sum_{s \in \mathcal{S}} \mathbf{1}\left(\lim_{T\rightarrow \infty} \frac{1}{T} \sum_{t=1}^T \frac{y_s(t)}{x_s(t)}\leq 1\right)$ $s.t. ...
2
votes
0answers
86 views

Solve non-linear Optimization Problem [closed]

I have to find $x$ that minimizes: $$ \sum_{k}(x^H\textbf A_kx - b_k)^2$$ where $A_k$ are 4 x 4 positive definite matrices ($A_1, A_2,...A_k$), $x$ is 4 x 1 vector and $b_k$ are scalars ...
5
votes
1answer
55 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 ...
0
votes
0answers
96 views

Optimization over space of probability measures

Consider an optimization problem as follows: $$ \min\mathbb E_w[f_0(w)] \mathrm{\,\,\,\,\,\ s.t.\,\,\,\,} E_w[f_i(w)]\leq 0 ,\,\,\, i=1,\dots, k $$ where the maximum is taken over $\mathscr M$, ...
4
votes
0answers
164 views

maximize non-convex composite function

I want to maximize a composite function over a convex set \begin{equation} \begin{aligned} & \underset{\mathbf{p}}{\text{maximize}} & & f(\mathbf{p})-g(\mathbf{p})\\ & \text{subject ...
5
votes
0answers
71 views

Basin of Attraction

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) = ...
0
votes
1answer
88 views

Why does optimization of a sum of two terms result in “neat” answers? [closed]

This is a somewhat vague and philosophical question. Consider the following three problems: Problem 1: Minimize over all real-valued $x,$ the function $f(x) = bx-ax^2$ where $a,b>0.$ ...
2
votes
1answer
56 views

Bounding the difference in the value of a strongly convex function at its integer minimum and other integer points

I am currently working on a problem where I have to minimize a $m$-strongly convex function $$f ~: ~\mathbb{R}^n \rightarrow \mathbb{R}^+$$ over a bounded integer lattice, $$L = \mathbb{Z}^n \cap ...
9
votes
3answers
372 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 ...
1
vote
1answer
74 views

arg min_X ||A X B - C||^2, with X diagonal [closed]

Let $A, B, C$ be known matrices, and let $X$ be an unknown matrix. Given that $C = AXB \Leftrightarrow \text{vec}(C) = K \text{vec}(X)$, where $\text{vec}(\cdot)$ denotes the vectorization of a ...
2
votes
1answer
185 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 ...
15
votes
1answer
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 ...
0
votes
1answer
261 views

Maximize a sum of log of sum

For a matrix $c (m\times n)$ of non-negative constants, find values of $\lambda_1, \lambda_2, \ldots, \lambda_n$ that satisfy $\sum_{k=1}^n \lambda_k = 1$, $\lambda_k \ge 0 \, \forall k$ and maximize ...
6
votes
3answers
668 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
1answer
156 views

Is there any algorithm can find local minima of nonconvex objective function in guaranteed polynomial time?

More precisely, The setting could be formulated as, $min. F_{\lambda}(p)$ over permutation matrices $P$ Here $F_{\lambda}(p)$=$\lambda *F_{0}(p)+(1-\lambda)F_{1}(p)$ where both $F_{0}(p)$ and ...
1
vote
0answers
110 views

Likelihood convexification

I am doing constrained vector optimization using a non-convex non-linear likelihood function. My problem is of the following form: $$\begin{align*}\hat Q &= \underset{\vec Q}{\arg\min} -\log ...
6
votes
0answers
117 views

A specific case of the $p$-center problem

Given a fixed positive integer $m$, let $\cal{S}$ be the subset from $\mathbb{R}^m$ defined as $\cal{S} = \{u \in \mathbb{R}^m \mid \forall i \in \{1, \dots, m\}, u(i) > 0$ and $\sum_{i=1}^m{u(i) = ...
2
votes
0answers
200 views

Solution of a linearly constrained quadratic programming problem [closed]

What is the solution of the following optimization problem: \begin{align} &\min{\mathbf{p}^\mathrm{T} \mathbf{B} \mathbf{p}}\\ &\text{subject to}: \mathbf{0}\leq{\mathbf{p}}\leq \mathbf{1}. ...
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
2answers
202 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 ...
0
votes
2answers
68 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
228 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$ ...
1
vote
0answers
48 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
164 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 ...
28
votes
6answers
16k 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
82 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
152 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
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 ...
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 ...
2
votes
2answers
1k 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) & ...
1
vote
0answers
47 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
302 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
422 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
71 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
495 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
187 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
107 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
310 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
148 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 ...