Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

0
votes
0answers
6 views

Convergence analysis of gradient descent method

From the following: Convex Optimization (S. Boyd) p.467 Content: We will see that the gradient method does in fact require a large number of iterations when the Hessian of $f$, ...
0
votes
1answer
31 views

Is inequality $tr(A^{-1^T} B) tr(A^T B^{-1}) \leq constant$ correct?

I have the following optimization problem \begin{align} \min_{A} &tr(A^{-1^T} B)\cr \text{subject to} &x^T A x > 0 \cr & A_{ii}=1 \end{align} where $A$ and $B$ are some positive ...
5
votes
1answer
115 views

are elementary symmetric polynomials concave on probability distributions?

Let $S_{n,k}=\sum_{S\subset[n],|S|=k}\prod_{i\in S} x_i$ be the elementary symmetric polynomial of degree $k$ on $n$ variables. Consider this polynomial as a function, in particular a function on ...
1
vote
0answers
25 views

How to solve the following convex optimization problem?

$$\min \|X\|_{*}+u\|Ax-b\|_2^2+v\|Cx\|_2^2$$ where $x$ is vec($X$), $u,v$. is the scalar. Is there any software to do this? Can the software cvx solve it?
1
vote
0answers
19 views

Why is this function, related to SVM derivation, non-convex?

I'm working through a support vector machines tutorial. In eventually deriving the solvable objective function, the following objective function (to be maximized) was proposed, but dismissed as ...
0
votes
0answers
27 views

Is convex or non convex function?$J(u,c)=\int K(x).u.(f(x)-c)^2dx$

I have a function such as $$J(u,c)=\int K(x).u.(f(x)-c)^2dx$$ where $f(x):\Omega \to R$; c is constant; $0 \le u \le 1$; and K(.) is gaussian kernel. My question is that : Is J convex or non-convex ...
8
votes
2answers
4k views

How the dual LP solves the primal LP

When I heard someone discussing LP the other day, I heard him say, "Well, we could just solve the dual." I know that both the primal LP and its dual must have the same optimal objective value ...
1
vote
1answer
53 views

Is there any way to make the following function convex?

I need to find optimal lagrangian multiplier vectors for a quadratic programming problem subject to three quadratic equality constraints and several other linear inequality constraints. I would like ...
-1
votes
1answer
20 views

Inversion of a matrix in a system of linear inequalities

I would like to know if someone knows sufficient conditions on $A\in\mathbb{R}^{n\times n}$ and $b\in\mathbb{R}^{n}$ such that for all $x\in\mathbb{R}^{n}$: $$Ax\leq b \Rightarrow x\leq A^{-1}b \text{ ...
0
votes
0answers
11 views

I want to find a maximum of a function by Maple. How to restrict the variables to be integers? [on hold]

For example, I want to find the maximum of $x^2+y^2$ with $0\le x,y\le 10$ in Maple. I can type $$maximize(x^2+y^2,x=0..10,y=0..10).$$ But if I restrict $x$ and $y$ to be both integers, then how can ...
1
vote
0answers
26 views

How to understand a proposition of subgradient

The question is from the following: Convex Optimization Algorithm (p.512)----- Prof. Bertsekas Let $f: R^n \rightarrow (-\infty, \infty]$ be a proper convex function. For every $x \in ...
0
votes
1answer
28 views

Gradient in mirror descent

Mirror descent can be in general written as \begin{equation*} \nabla\Phi(x_{t+1})=\nabla\Phi(x_t)-\lambda_t\nabla f(x_t), \end{equation*} where $f$ is the objective function and $\Phi$ is a convex ...
2
votes
1answer
48 views

Calculating the distance function and projection

Let $\Omega=\{x\in\mathbb R^n\mid\langle a,x\rangle=b\}$. We define the distance function and projection as follows $$d(x;\Omega)=\inf\{||x-\omega||\mid\omega\in\Omega\}$$ ...
0
votes
1answer
21 views

Supporting lines of closed Jordan curve

Given a simple closed Jordan (i.e. continuous) curve $\gamma:[a,b]\to\mathbb{R}^2,\ \gamma([a,b])=C_\gamma$, how can I prove that $D_\gamma$ (the set of all interior points of $\gamma$ toghether with ...
1
vote
1answer
23 views

Dual residual for linearized ADMM

I am using linearized ADMM for a problem with a (non-smooth) convex loss function $f(x)$, and a hard constraint $x \in E$, where $E$ is an ellipsoid in $R^d$. I have encoded the hard constraint as $A ...
0
votes
0answers
18 views

A min-max problem and convex optimization problem.

Let $x^*$ a solution of the convex programming problem $$ \begin{array}{rl} \max & f_0(x)&\\ \mbox{s.t.} & g(x)\leq 0 \end{array} $$ where $f_0:\mathbb{R}^n\to \mathbb{R}$ and the ...
1
vote
1answer
44 views

Is $f(X) = \| Y - XX^T \|_F$ convex given fixed $Y$?

In the scene of nonnegative matrix factorization, $f(X_1, X_2) = \| Y - X_1 X_2 \|_F$ is not convex, but both $f(X_1)$ given fixed $X_2$ and $f(X_2)$ given fixed $X_1$ are convex, enabling us to ...
2
votes
0answers
19 views

On the solutions of a system of inequalities avoiding Helly's theorem

Let $a_1,b_1,\cdots,a_4,b_4\in\mathbb{R},r_1,\cdots,r_4\in(0,+\infty)$. Show that, if $\not\exists (x,y)\in\mathbb{R}^2$ such that $$ \begin{cases} (x-a_1)^2+(y-b_1)^2\le r_1\\ ...
0
votes
0answers
14 views

Is this floor function/problem quasiconvex?

I am trying to study an optimisation problem under constraints. The point is that all my constraints are linear as well as all terms of my objective function except one. This guy : $$ \alpha^{\lfloor ...
0
votes
0answers
10 views

Analysis of Optimizatiointechniques: Regret Analysis vs. Direct convergence? [on hold]

When it comes to convergence rate analysis of optimization algorithms (like gradient descent and its family), there seems to be to be two main: Direct analysis, i.e. bound on $$ |f(x_t) - f(x^*)| ...
0
votes
1answer
11 views

Concave-Convex Decomposition of a continuous function

In this paper http://www.stat.ucla.edu/~yuille/pubs/optimize_papers/cccp_nips01.pdf they have a theorem that says that a twice continuous differentiable function (an energy function, they say) with ...
1
vote
1answer
127 views

proving that $\text{ri rge}\,A=\text{ri conv rge}\,A$

In Proposition 6.4.1 we want to prove that if $A:\mathbb R^n\rightrightarrows\mathbb R^n$ is maximal monotone, then $\text{cl rge}\,A$ and $\text{ri rge}\,A$ are convex. In proof we arrive to the ...
1
vote
2answers
56 views

proving that $(\text{aff}\,C-\text{aff}\,C)\subset\text{aff}(C-C)$

In proof of Theorem 6.4.1, the author assumes that $\text{rge}\,A\subset\text{aff}\,C$ and for $\epsilon>0$ claims that $\epsilon^{-1}(C-\text{rge}\,A)\subset\text{aff}\,(C-C)$, that I can't verify ...
0
votes
1answer
51 views

Algorithms For Large-Scale $\ell_{\infty}$ Minimization

The general problem I want to solve is well studied: $$ \min_x \Vert Ax\Vert_\infty \;\;\; \mathrm{s.t.} \;\;\; Bx=c, $$ which is equivalent to the following linear program: $$ \min_{t,x} \, t ...
1
vote
2answers
46 views

Is it convex function?

I have a function and I don't know it is whether convex or non-convex: $$J(c,\alpha)=\int_\Omega ( \alpha c-I(x))^2u \, dx+ \|\alpha\|^2$$ where $0 \le u \le 1$, $I(x): \Omega \to R$, $c$ is constant ...
0
votes
1answer
37 views

MATLAB: minimize function using x value from previous iteration

I'm trying to develop an algorithm for a proximal point method defined as: $$ \underset{x \in \rm I\!R^n}{\arg\min} f(x) + \lambda g(x) $$ where f(x) is a convex and coercive function and also ...
1
vote
1answer
28 views

any good way to approximate this non-convex function with convex function?

There is a non-convex constraint in my optimization problem, which is given by $\displaystyle -xy\log\left(1+\frac{z}{xy}\right)$. Obviously, it is neither convex or concave. Is there any good convex ...
0
votes
1answer
400 views

relation between size of matrix and condition number

I have a matrix A of size NxM. Is there any relationship between size of a matrix A with the condition number ? I am computing the pseudo inverse (pinv in matlab ) ...
0
votes
0answers
15 views

Help required in solving the lagrangian dual?

I'm trying to write the Lagrangian dual to the following problem \begin{align*} (P) \quad \min\;&\text{Trace}(CG)\\ \text{s.t.}\;&G \succcurlyeq 0\\ & G_{i,i}=I_d (i=1,..,M+1)\end{align*} ...
-3
votes
0answers
10 views

How to get attribute weights from a tradeoff? [closed]

Assume that we are getting oranges and apples from a fruit basket, getting apples is seen more important than oranges, and the outcome of x=(0 apple, 25 oranges) is equally preferred as x=(10 apples,0 ...
0
votes
2answers
49 views

How to compute primal variable based on dual variables and their multipliers

I edited this question based on information I got from comments. Assume we have an optimization problem (primal problem). we solve it's dual using some kind of primal-dual interior point solver. So, ...
-1
votes
1answer
15 views

How can I show that any local minima of a concave function is at extremal point? [closed]

I would like to know some formal proof. I think this is intuitive but I cannot prove it for the general case... Thanks in advance...
0
votes
0answers
42 views
5
votes
2answers
78 views

Proving $x^4$ is strictly convex

I'm not sure how to prove $f(x) = x^4$ is strictly convex using just the definition of strict convexity: $$f((1-t)x+ty) < (1-t)f(x)+tf(y)$$ for $0<t<1$. Is this just an algebra slog? If so, I ...
0
votes
3answers
50 views

Prove $||\lambda x_1 + (1-\lambda) x_2 - y|| \leq ||x_1 - y||$

Assume we have have $3$ points $x_1, x_2$ and $y$ and $||x_1-y||=||x_2-y||$. How do we prove that the distance between $y$ and the convex combination of $x_1$ and $x_2$ is smaller than that between ...
0
votes
1answer
15 views

Analysis of iterative optimization methods using lyapunov analysis

In analysis of iterative methods, is it possible that we have to use two time-lagged version of the time-varying system to analyze its convergence? (that is, we construct the evolution of x^k, ...
1
vote
2answers
415 views

Convex Optimization of quadratic function with inequality constraints

How would I solve the following problem? $$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$ where A is positive semidefinite and symmetric. Is it possible to ...
0
votes
1answer
435 views

Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
0
votes
1answer
12 views

Gradient of squared distance to a convex set

I have the following problem: Let $f:\mathbb{R}^n \rightarrow \mathbb{R}$, $f(x)=(\operatorname{dist}(x,D))^2$ where $D$ is a convex, close set in $\mathbb{R}^n$. Prove that $f$ is convex and ...
1
vote
0answers
30 views

tangent cone to the set

I'm supposed to solve this problem: Let us consider the set $M=\{(x, \sin{x}):x\in\mathbb{R}\}\cup\{\big(\cos(x)-1,x\big):x\in\mathbb{R}\}$ The question is to find the tangent cone to the set $M$ in ...
0
votes
0answers
25 views

Karush-Kuhn-Tucker conditions for non-linear optimalization

I have the following problem: solve the local conditions (KKT) and find ALL optimal solutions: $$\min f(x,y)$$ subject to $$g(x,y)\le 0$$ $$x\geq0, y\in\mathbb{R}$$ I have some questions to this ...
1
vote
0answers
49 views

Proof that equation is non-convex function

I have a objective function as following $$E(\phi)=\int_{\Omega}(I(x)-m_1)^2H(\phi(x))dx+\int_{\Omega}(I(x)-m_2)^2(1-H(\phi(x)))dx+\int_{\Omega}|\nabla H(\phi(x)|dx$$ where $I$ is an image; $I: \Omega ...
1
vote
1answer
48 views

How to project gradient vector to subspace defined by linear constraints

I have the following set of linear constraints: $$\begin {align}\textbf{y}^T\textbf {x} &= 0 \\ \textbf {0} &\leq\textbf {x} \leq C\cdot\textbf {1},\end {align}$$ where $\textbf {y} \in ...
0
votes
1answer
13 views

Under what hypotheses is a solution to the Lagrangian multiplier equations automatically a global minimum?

Suppose we are minimizing a function $f(x_1,...,x_n)$ under the conditions $g_1(x_1,...,x_n) = g_2(x_1,...,x_n) = 0$. Under what hypotheses is a solution to the Lagrangian multiplier equations ...
1
vote
1answer
429 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
0
votes
0answers
29 views

Intuition between convex function and convex set

In my text (Luenberger), there is a proposition about convex set Prop: let $f$ be convex function on convex set $\Omega$. The set $\Gamma_c = \{{x: x\in \Omega, f(x) \leq c}\}$ is convex ...
1
vote
0answers
35 views

Optimization of sum of logs

I have an optimization problem of the form $$\operatorname*{argmax}_{\mathbf{w}} \sum_i \log(1 + \mathbf{w} \cdot \mathbf{k_i})$$ given some set of vectors, $\mathbf{ \{k_i\} }$. I have tried both ...
0
votes
1answer
21 views

Is the normalized duality mapping symmetric?

In the area of functional analysis, nonlinear operator theory, the normalized duality mapping on a Banach space $X$ is a set valued map from $J:X\rightarrow 2^{X^*}$ given by \begin{align} ...
0
votes
0answers
20 views

Product of linear and convex function

More specific, how many maxima are there for product of these two functions: $ f(x) = ax + b $, and $ a > 0 $ $ g(x) $ is (strongly) decreasing convex function, $ \lim_{x\rightarrow\infty} g(x) = ...
0
votes
1answer
37 views

A maximization problem within the simplex

Let $\lambda_i$ be an ordered list of $N$ positive numbers, $\lambda_1<\lambda_2<\dots<\lambda_N$. I'm looking for the extrema of the function $$ f=\left(\sum_{i=1}^N p_i \lambda_i ...