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

learn more… | top users | synonyms

1
vote
1answer
81 views

strict separation theorem?

Im learning and we have a theorem that says: Let $C$ be a non-empty, convex subset of $\mathbb R^d$ and let $p \in \mathbb R^d$ be a point which is not in the closure of $C$. Then there exists a ...
0
votes
0answers
16 views

Confusion related to a function used for optimization

I have a function $f(x)$, such that at point $x'$, it attains its minimum value, but the gradient at this point $x'$ is not equal to $0$. On the other hand the function $f(x)$ has slightly higher ...
0
votes
0answers
26 views

Confusion related to Newton's method for optimization

I am trying to use Newton's method for optimizing a certain function f. However, I am having some issues. I am using Armijo rule for finding the step size. So my iterations are like this $x_{t+1} = ...
1
vote
1answer
90 views

Prove that $ri (epi f)=\{(x, y): x\in ri (dom f), y >f(x)\}$

$f: R^n \to (-\infty, \infty]$ is a convex function. Prove that $ri (epi f)=\{(x, y): x\in ri (dom f), y >f(x)\}$ I have used definition of convex functions to prove that the right-side is ...
0
votes
0answers
33 views

How fast Interior Point method can be when solving Quadratic Programming problems?

Given the following Quadratic Programming problem: $\;\;\;\;\; \min x^TQx+c^Tx $ s.t. $Ax=b$ $\;\;\;\;\; x\ge0$ where $x\in \mathbb{R}^n$, $Q \in \mathbb{R}^{n \times n}$ is a positive ...
1
vote
2answers
138 views

What is a convex optimisation problem? Objective function convex, domain convex or codomain convex?

My teacher in the course Mat-2.3139 did not want to answer this question because it would take too much time. So what does a convex optimisation problem actually mean? Convex objective function? ...
0
votes
0answers
26 views

||w||=1 constraint in maximizing geometric margin of large-margin classifier.

In a video lecture regarding large-margin classifiers while deriving the primal and dual representations, the professor at the outset mentioned that given a geometric margin as follows: gamma = ...
0
votes
1answer
34 views

Help with a property of a convex function

I'm studying linear and nonlinear programming and on my book I bumped into the following statement: $$\lim_{\alpha \to 0} \displaystyle \frac{f(\textbf{x}+\alpha ...
0
votes
1answer
73 views

(pseudo-/quasi-)convexitiy of ratio between quadratic and affine function

Let $X\subseteq\mathbb{R}^n$. I have the following function $f:X\rightarrow\mathbb{R}$: $$ f({\bf x})= \frac{c_1 + \sum_{i=1}^n a_ix_i +\sum_{i=1}^n b_ix_i^2}{c_2+\sum_{i=1}^n d_i x_i}\enspace.$$ All ...
3
votes
2answers
91 views

why is argmin $\|w\|^2$ equivalent to $\operatorname{argmax} 1/\|w\|$

I was wondering why the maximization of $1/\|w\|$ is equivalent to minimizing the squared norm of $w$. Shouldn't it be equivalent to just minimizing the norm of $w$? This is a very basic optimization ...
2
votes
1answer
50 views

Minimization of norms

How do I minimize the following? $ min_{z>0} - zt + 1/2\ z\ ||\ Y + X_k\ /\ z\ ||_2^2 $ Also, $X_k^TX_k = 1 \ \ \forall k $ I am given that the answer should be : $ \sqrt{Y^T - 2t} + Y^TX$ ...
0
votes
1answer
34 views

Square of 2-norm

This might be silly but I am stuck with the following problem: $ || Y - Z_i/x||^2_2 $ = 2t How would I solve to get $x $ from this equation?
0
votes
1answer
159 views

KKT conditions on minimization problem

I am trying to get an explicit solution to the following problem with the help of KKT conditions. But I am stuck. The problem: $ min_x 1/2 ||y-x||^2_2 + \lambda||x||_1 $ This is what I have done ...
1
vote
0answers
64 views

Strong Duality and Duals of linear programming problem

I have the following problem: $ max_{x,y} \ x + y $ subject to $ 2x + y \leq 1 $ $ x + 3y \leq 3 $ $ x,y \geq 0 $ How to find the dual of this problem using the Lagrangian? I have done the ...
1
vote
1answer
80 views

Dual of this primal optimization problem?

How would one find the dual of the following problem? $min_x 1/2 ||y-x||_2^2 + \lambda||x||_1 $ Can someone please explain to me how to do this since there are no specific constraints?
1
vote
0answers
23 views

Issues related to positive definiteness in a convex optimization problem

I have some issues in a convex optimization problem. My f(X) is a convex function of X where X is a positive definite matrix. X is very sparse and has a handful of non zeros values. Now I only need to ...
0
votes
1answer
63 views

Is this function convex or concave?

I have a function, $f(x_{0},x_{1},......x_{n})=\sum^{n-1}_{i=0}A_{i}r^{-(x_{i}+x_{i+1})}-B$ $A_{i} >0$ for all $i$ and $B>0$ and $1 \leq r \leq 2$ so above function is convex or concave? ...
2
votes
0answers
79 views

Uniqueness of the solution

We know that 1) Minimise of a convex function the unique solution exists 2) Maximise of a concave function the unique solution exists How about 1) Minimise of a strictly convex function? 2) ...
5
votes
1answer
378 views

Dual to the dual norm is the original norm (?)

I have the following questions about dual norms : How do you prove that the dual of the dual norm is in fact the original norm? This is what I have so far: If I have $\|y\|_* $ as the norm dual of ...
0
votes
0answers
58 views

Matrix fractional minimization via SOCP

This is Exercise 4.27 in the book Convex Optimization. Express the following problem as an SOCP: $\text{minimize}\quad (Ax+b)^T(I+B\,\textbf{diag}(x)\,B^T)^{-1}(Ax+b)\\ \text{subject to} \quad ...
3
votes
1answer
71 views

What type of convex constraint is defined by SQRT?

Let $A$ be an $n \times n$ positive semidefinite matrix and $\forall k, x_k \in \mathbb{R}^n$. The distance with respect to this matrix is defined as $ \|x_i -x_j\|_A := ...
1
vote
0answers
21 views

Confusion related to interior point method

I was reading this wiki article related to interior point method. I didn't get when they say that it applied Newton's method to get an update for $(x,\lambda)$. How the expression at the end ...
0
votes
1answer
81 views

Maximize Trace with Lyapunov inequality as constraint

Let $C$ be a given symmetric matrix, $A$ be a given Hurwitz matrix and $X$ be a symmetric positive definite matrix. Is the following problem solvable to give unique, optimal $X$? max $tr (CX)$ ...
1
vote
0answers
59 views

Confusion related to fmincon function in matlab

I was reading this help section of matlab's fmincon function that uses interior point algorithm for solving an optimization problem. It says the following optimization problem is replaced by To ...
0
votes
0answers
260 views

Is a linear-fractional function convex?

For example a simple linear-fractional function $f(x) = \frac{a^Tx+b}{c^Tx+d}$ with the domain of $f$ being $\lbrace x|c^Tx+d > 0\rbrace$, where $a, c, x \in \mathbf{R}^n$ and $b,d \in \mathbf{R}$. ...
1
vote
0answers
52 views

Is the following problem convex , quasiconvex, or nonconvex?

I want to get the optimal matrix $W$. But I am not sure whether it can be resolved. Note that $W,\mu,\lambda_{1},\ldots,\lambda_{K} $ are variables, others are fixed. Is it convex or quasiconvex or ...
0
votes
1answer
305 views

How do I prove that the composition of an affine function preserves convexity?

What would be the formal proof that $ f(Ax + b) $ given $ f(x) $ is a convex function ? I got to the point where I expanded $$ f(\lambda(Ax+b) + (1- \lambda)(Ay+b)) = f(A(\lambda x + (1 - \lambda)y) + ...
1
vote
1answer
334 views

proximal operator of infinity norm

What is the proximal operator of $||x||_\infty $? I know we have to take the subgradient and compute it but I am a bit stuck. Can anyone show me steps?
2
votes
0answers
66 views

Maximizing the smallest eigenvalue of a linear combination of matrices

I have an engineering back ground. Due to work, I came across this problem \begin{align} &\max_{\lambda,y_i\in \mathbb{R}}~\lambda \\\ ...
3
votes
1answer
394 views

Solving optimization problems using derivatives and critical points

I have a homework question which I have completed 2/3 of; however I am stuck on the last part of the question. The question is: A drug used to treat cancer is effective at low doses with an ...
0
votes
1answer
188 views

Show convexity of the quadratic function

Can someone show this function is convex using the definition (without taking gradient)? $$F(x) = x^TAx + b^Tx + c$$ where $A$ is symmetric positive semi-definite.
0
votes
1answer
79 views

Confusion related to the calculation of gradient

I am having some confusion related to the calculation of gradient. My function $f(X) = g(X) + \lambda||X||_1$ where g(X) is convex and differentiable. I didn't get how the second expression when ...
0
votes
1answer
73 views

Proximal operator

What is a proximal operator and how would one derive it in general for a function? In particular, if I had a function: $ f(x) = x^TQx + b^Tx + c $ How would I get the proximal operator for this if Q ...
0
votes
1answer
56 views

Confusion over a proof that gradient is perpendicular to the level set

To prove that the vector $\nabla{f}(x_0)$ is orthogonal to the tangent vector to "an arbitrary smooth curve" passing through $x_0$ on the level set determined by $f(x)=f(x_0)$ the following proof is ...
0
votes
1answer
34 views

Confusion related to Armijo's rule

I am having confusion related to Armijo's rule used for line search. Can you give me some links to good tutorials. I want to get the geometric interpretation behind it. I found this one ...
2
votes
0answers
52 views

the objective function $\|F\|_F^2$ is quasiconvex in the optimization?why?

I have read a paper, but I can not understand one optimization thoroughly.Generally, Frobenius norm of one matrix, $\|F\|_F^2$, as the objective function is convex, so we can resolve it not using the ...
0
votes
1answer
83 views

Maximize Trace as standard semidefinite optimization

Let $A$ be a symmetric matrix and $X$ a symmetric positive definite matrix, then the following standard semidefinite optimization problem is convex: min $tr (AX)$ subject to $X>0$ Now I wonder ...
0
votes
1answer
116 views

How to get the closed form solution of a non-convex optimization problem?

I want to know if there is a closed form expression for the optimal objective function? How can I get it, if it does exist? Condition: $h,f\in \mathbb{C}^{N\times1}, \epsilon > 0 $. $\max \ \ ...
0
votes
1answer
483 views

Convex conjugate of $\ell_1$ and $\ell_2$ norm

Given a function $f$, we can define a function $f^{*}$, called the convex conjugate (also known as the Fenchel conjugate) of $f$ as follows: $$ f^*(\vec{z})= \sup_{\vec x \in \mathbb ...
0
votes
1answer
34 views

Proofs regarding convex sets

I need assistance with the following proofs. I am not sure how to prove that one set is contained in another set. Here are the things required to be proven: Let $S$, $S_1$ and $S_2$ be non–empty sets ...
1
vote
0answers
33 views

Is the optimizer of a strongly-convex cost function bounded?

Let f(x) be strongly-convex. Can its minimizer be unbounded? I suspect not. Can we obtain a bound on it in relation to the strong-convexity constant? I believe an equivalent formulation of this ...
3
votes
1answer
567 views

Pointwise infimum of affine functions is concave

So I was just starting on convex optimization and was having a slightly hard time visualizing the lagrangian being always concave because it is the pointwise infimum of a family of affine functions. ...
0
votes
1answer
33 views

convex set optimization problem

If I have a convex set $ \min f(x) $ $\sum_{i=1}^n x_{i} =1$ where $x\geq 0$. Will an $\overline x$ (a local minimizer), if $x_{i} >0$ be $ \dfrac{\partial{f(x)}}{\partial{x_{i}}} \geq ...
0
votes
1answer
37 views

Second-order Lagrange condition

I am not sure what the second-order Lagrange condition is and how it applies to this? Minimize $x^2 + y^2$ Subject to $x^2 - y - 4 \leq 0$ and $y - x - 2 \leq 0$. Please can someone assist me in ...
3
votes
2answers
1k views

Second derivative positive $\implies$ convex

In proof of the following theorem; If $f$ has a second derivative that is non-negative (positive) over an interval then $f$ is convex (strictly convex). $f$ is in real number space., the book I ...
3
votes
1answer
162 views

Attain minimum on boundary of a convex set?

It is well known that there exists a unique minimum norm vector over a closed convex set. Suppose we have a Banach space X (if it needs to be more concrete we can think of $L_2$, the space of square ...
1
vote
1answer
85 views

Computation Effort of Algorithms

Consider the strictly convex unconstrained optimization problem $\mathcal{O} := \min_{x \in \mathbb{R}^n} f(x).$ Let $x_\text{opt}$ denote its unique minima and $x_0$ be a given initial approximation ...
0
votes
1answer
140 views

How get the upper bound (maximum) of a convex function with inequality constraints?

Condition: $h,f\in \mathbb{C}^{N\times1}, \text{where}f =\hat{f} + e \text{ and } e^H e \leq 1,\ \ \ Q=h^Hff^Hh$. The function $ Q$ is convex. Now I want to get the maximum (not minimum), i.e., the ...
1
vote
1answer
103 views

Minimize Trace for non-symmetric matrix

Let $A$ be a given matrix and $X$ a symmetric positive definite matrix which shall be optimized: min $tr (AX)$ subject to $X>0$ This optimization problem is convex if $A$ is symmetric as it is ...
0
votes
0answers
60 views

References for maximizing a product under a sum equality constraint and individual variable inequality constraints

I am looking for references on the following optimization problem: maximize $\prod x_i$ under a sum constraint $\sum x_i = 1$ and individual variable constraints $0 \le x_i \le C_i$. I know the ...