All Questions
Tagged with convexity nonlinear-optimization
18 questions
8
votes
0
answers
210
views
Concavity of product and ratio of sums
Apologies if this question is not appropriate for MathOverflow. I have asked at Math.StackExchange without success.
Consider the function $f:\mathbb{R}^n\rightarrow \mathbb{R}$ defined as
$$
f(x)=\...
- 389
6
votes
2
answers
718
views
Can we decompose a polynomial into difference of convex polynomials?
Given a multivariate polynomial $p(x_1, ..., x_n)$ on $\mathbb{R}^n$, can we always decompose it into the difference of two convex polynomials? i.e., is there a pair of convex polynomials $f$ and $g$, ...
- 81
6
votes
0
answers
255
views
Concavity of a function implicitly defined by a polynomial
Consider the following system of $n$ equations:
\begin{equation}f_j^2 = x_j^2\sum_{i=1}^n A_{ij} f_i
\tag{$\star$}
\end{equation}
where $A_{ij}\geq 0$ are known constants and where $x_j>0$ for ...
- 389
4
votes
2
answers
981
views
Convex Sets and Nearest Neighbors
For a set $S \subseteq \mathbb{R}^n$ and a point $x \in \mathbb{R}^n$, let $c_S(x)$ be the point $s \in S$ that minimizes $\|x-s\|$ if such a point exists and is unique. It is known that $c(x) = s$ ...
- 177
4
votes
3
answers
2k
views
Zero lambda, zero constraint in the complementary slackness condition of the Kuhn-Tucker problem
Complementary slackness condition in the KKT theorem states that:
$\lambda_i^*\geq0; \lambda_i^*h_i(x^*)=0 $
The usual reasoning goes like this: either constraint is clack $h_i(x^*)>0$ and then ...
- 71
3
votes
2
answers
266
views
Fixed point iteration on symmetric biconvex function
Suppose $X\subseteq\mathbb{R}^n$ is a convex set and that a function $g(x,y):X\times X\rightarrow\mathbb{R}_+$ is smooth, "strictly biconvex" (strictly convex in $x$ and $y$ independently but not ...
- 705
3
votes
1
answer
261
views
When is the optimum of an optimization problem affine in the constraint parameter?
While working on a variational problem I have reached to the following question:
Let $f:(0,\infty) \to [0,\infty)$ be a $C^1$ function satisfying $f(1)=0$. Suppose that $f(x)$ is strictly increasing ...
- 6,741
3
votes
1
answer
2k
views
Global minimum of nonlinear least square
We have a continuous and differentiable function $f(\cdot)$ that maps from $R^n$ to $R^n$. We are trying to solve a nonlinear least square problem:
Minimize $J(x)=\Vert f(x)-z\Vert^2$
subject to box ...
- 33
2
votes
1
answer
212
views
Checking concavity of a highly non linear function
I have a highly non linear profit function which depends on four independent variables (decision variables) E,W,T and p. I want to check concavity of profit function with respect to these four ...
- 49
2
votes
1
answer
154
views
Is the optimum of this problem convex in the constraint parameter?
Let $f:\mathbb R^+ \to \mathbb R$ be a smooth function, satisfying $f(1)=0$, and suppose that
$|f|$ grows with the distance from $1$: $|f(x)|$ is strictly increasing when $x \ge 1$, and strictly ...
- 6,741
2
votes
0
answers
101
views
Sparse signal recovery (nonlinear case)
Let $K \subset \mathbb{R}^n$, it may be that $K$ is "very thin" (e.g. $K$ is a $k$-dimensional affine subset of $\mathbb{R}^n$, with $k \ll n$). I'm interested in the case where $K$ is ...
- 981
1
vote
2
answers
1k
views
How to find the necessary and sufficient conditions for a non-convex function to be locally convex?
Let $f(X)\geq 0$ be a nonconvex $C^\infty$ function: $\mathbb R^3\to \mathbb R$.
Give any fixed $X_0$ such that $f(X_0)=\epsilon^+$, and the level set:
${L}=\{X\in \mathbb R^3:f(X)\leq \epsilon^+\}$ ...
- 197
1
vote
1
answer
1k
views
Is a Lipschitz continuous gradient equivalent to this condition?
I know if a function $f: \mathbb{R}^n \to \mathbb{R}$ is $L$-smooth, i.e. its gradient $\nabla f$ is $L$-Lipschitz continuous, then it satisfies the following inequality for any $x, x_0 \in \mathbb{R}^...
- 163
1
vote
0
answers
149
views
Coordinate descent conditions
The following is quoted from "Bertsekas, D. P. (1999). Nonlinear programming (p. 794). Belmont: Athena scientific".
Convergence of Coordinate Descent: Suppose a function $f$ is continuously ...
- 133
1
vote
0
answers
232
views
Semi-convex problem and almost convex problem
I have a target function, I've computed its Hessian to check convexity, it has a positive-definite sub-matrix and small negative-definite sub-matrix and a kernel. Sometimes it is even better -- the ...
- 355
1
vote
0
answers
150
views
Hessian matrix positive definiteness (concavity test) [closed]
I have a rather simple scenario based optimization problem:
Maximize
$$
Q_1{_s}(A_1{_s}-Q_1{_s}-bQ_2{_s})+ Q_2{_s}(A_2{_s}-Q_2{_s}-bQ_1{_s})-[(Q_1{_s}-K_1)^+ + (Q_2{_s}-K_2)^+]c
$$
subject to $Q_1{...
- 11
1
vote
0
answers
100
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 ...
- 33
0
votes
0
answers
73
views
Number of local minima of a particular non-convex composite function
I am interested in proving that the following equation on the interval $x \in [c,1]$ is minimized either at the endpoints or where $x=\sqrt{c}$:
$f(x)=\frac{-1}{\log(1-x)}+\frac{-1}{\log(1-\frac{c}{x}...
