Nonlinear objectives, nonlinear constraints, non-convex objective, non-convex feasible region.

learn more… | top users | synonyms

5
votes
1answer
171 views

How to solve such an optimization problem

I encounter the following optimization problem, but I can't solve it. Given $N$ variables satisfying $0 \leq x_1 < x_2 < x_3 < ... < x_N \leq 1$ and an integer $K$ no large than $N$, find ...
6
votes
0answers
59 views

Bounding volume of cell in complement of zero set

I am given an integer polynomial $f \in \mathbb{Z}[X_1, \ldots, X_n]$ of bounded degree and bounded coefficient size. The polynomial's zero set partitions $\mathbb{R}^n$ into cells. What I am looking ...
4
votes
0answers
137 views

Optimization problem involving Multivariate Normal

I use $\phi(t)$ to describe the standard normal distribution density and $\Phi(t)$ as the normal distribution CDF and would like to prove that for all $n\geq3$, the function: ...
2
votes
0answers
77 views

Techniques for proving that a set of constraints over the integers are inconsistent

I have a problem which boils down to showing that a set of constraints has no solutions. A simplified version of this constraint system would be the following system: $$ \left\{ \begin{array}{l} ...
2
votes
0answers
151 views

Subtour Elimination in Travelling Salesman Problem using MTZ

I am trying to formulation a problem similar to a Traveling Salesman with Time Window constraints. To eliminate subtours, I need to use some constraint similar to a generalization of MTZ constraints ...
2
votes
0answers
140 views

An intuition for three different types of subgradients (proximal, regular, limiting)

I'm having a bit of difficulty getting my head around the different types of subgradients we're currently covering in a nonsmooth optimisation class I'm taking. These subgradients are (assume $x \in$ ...
2
votes
0answers
136 views

Quadratic optimization with parameter in constraint

Disclaimer: I posted the same question on math.stackexchange. However, the FAQ suggests to post research-level questions in this forum. Question: Given a function $q: \mathbb R^{N\times N}\mapsto ...
1
vote
0answers
20 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 ...
1
vote
0answers
61 views

Estimation of part of parameters from an ODE

Suppose, we have an ODE $$ \frac{dy}{dt}= f(t,y;p',a)$$ or alternatively $$ \frac{dy}{dt}= f(t,y;p)$$ where the set of all parameters $p = (p',a)$. We only need to estimate part of parameter set ...
1
vote
0answers
128 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 ...
1
vote
0answers
118 views

Recovering a partition from spectral properties of the graph Laplacian

Let $G$ be a weighted graph with vertices $V$. Let $W$ be its real-valued, non-negative, $|V|\times|V|$ adjacency/affinity matrix. Let $L = \mathrm{diag}(W\mathbf1)-W$ be the (unnormalized) graph ...
0
votes
0answers
18 views

Maximizing the “uniformity” of a probability measure, with constraints, via path length minimization

I want to find a probability measure for a continuous random variable, subject to moment constraints, that is maximally "uniform", as defined below: Definition: Maximally Uniform Probability ...
0
votes
0answers
32 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 ...
0
votes
0answers
7 views

Recursively calculate Tikhonov regularizer in b-spline objective function

I'm trying to write a program to calculate cubic b-spline based on set of inputs. But I can't figure out how to calculate value of Tikhonov regularizer. My b-spline function is this: I have ...
0
votes
0answers
41 views

Finding gradient of an optimization

I am trying to find the gradient of the following optimization problem and then add to objective, but I got some trouble in computing. Could you please help me? Assume that we have an optimization ...
0
votes
0answers
46 views

Solution of a nonlinear system of two equations

Given the matrix $A_{M,N}$ with $N\gt M$, the vector $y$, I have to find the vectors $x$ and $u$, satisfying the following equations: $$D(x)x=A^Tu$$ $$y=Ax$$ where: $$D(x) = \left| \begin{array}{ccc} ...
0
votes
0answers
33 views

A Optimization problem using co-ordinates of joint numerical range.

Let $\mathbf{A}_1,\dots,\mathbf{A}_L$ be $N\times N$ hermitian matrices. Define the mapping from the $N-$dimensional unit sphere to $\mathbb{R}^L$ as \begin{align} ...
0
votes
0answers
77 views

Complexity of turning a d-degree polynomial to 2-degree polynomial

For a very simple example, $(1+x)^4=x^4+4x^3+6x^2+4x+1$ is a 4 degree polynomial, and I want to change it to a 2-degree polynomial by add more variables, for this example, we can simply let $y=x^2$, ...
0
votes
0answers
62 views

No Strong Duality In Spite of Slater's Condition

I was reading some course notes here. On Page 8, it says: Note that strong duality holds here (Slater's condition), but the optimal value of the last problem is not necessarily the optimal ...
0
votes
0answers
49 views

What is the best way to optimize this matrix equation

What is the best way to optimize this Procrustes like formulation: $\min\quad\|AX-B\|^2_{\rm F} + \|X^Tc\|^2,$ s.t. $X^TX = I$ Here A and B are $n \times p$ matrices and $c$ is a $p \times 1$ ...
0
votes
0answers
21 views

weakly Complementary slackness

Suppose we have a general pair of primal-dual semidefinite programming and strong duality holds. What does mean the term "weakly Complementary slackness condition" in optimality?
0
votes
0answers
100 views

Modifying a QP to incorporate more constraints

Consider the following problem: $$\min \sum_{i=1}^n (Y_i - Z^{(i)})^2 \\ \text{subjected to}~ \epsilon_k^{\top}(X_j-X_k) \leq Z^{(j)}-Z^{(k)} ~ \forall k,j = 1 \ldots n. $$ where $\epsilon_1, ...
0
votes
0answers
45 views

What is the sufficient condition for a “strict local optimal point” to be “isolated local optimal point”(or strong local optimal point)?

I encountered a case that seems obvious that the local optimal point are isolated, yet I can only prove the local optimal points are strict rather than isolated. I know under certain peculiar ...
0
votes
0answers
136 views

k-means type clustering of binary data, under capacity constraints per cluster. Proof of NP-hardness?

Suppose you are given a set of $I$ binary vectors in ${\mathbb R}^N$, a number of clusters $k$, and positive integers $\{ c_i \}_{i=1}^k$ where $\sum_{i=1}^k c_i = I$. I am interested in finding a ...
0
votes
0answers
62 views

Big eigenvalues of a special stochastic matrix

Given a matrix $M$ of size $n\times n,$ we write its different eigenvalues by $x_1,x_2,\ldots,x_m$ with $m\leq n$ such that $|x_1|>|x_2|>|x_3|>\cdots|x_m|,$ and call $x_2\doteq ...
0
votes
0answers
52 views

functional maximization

Define a functional space of functions of the form $F(t)=p_1 exp^{-\mu_1(\delta-t)}+p'_1 (1-exp^{-\mu_1(\delta-t)}))$. $p_1,p'_1,\delta,\mu$ are parameters in [0,1] and trivially, variation of these ...
0
votes
0answers
52 views

Minimizing inside a spherical uncertainty region

I am trying to figure out how to solve: $\min_U r_{p}$ where $r_{p}=\alpha^\intercal\omega$ and $U$ is a sphere centered at $\alpha$ with radius equal to $\chi|\alpha|$ . ( $\omega$ is a vector or ...