Tag Info

New answers tagged

3

Hint: Your problem is addressed in functional analysis and is a constrained calculus of variations problem. I would form the Lagrangian and get rid of the constraint, and then would try to derive the Lagrange-Euler formula for the problem.


0

Not sure about the half-space representation. Can't you just calculate that yourself from the returned points? >> lookfor hull convhull - Convex hull of a set of points in 2D/3D space convhulln - N-D Convex hull. qhull - Copyright information for Qhull. bwconvhull ...


0

As pointed out in the above by user "1015" (who keeps changing his username ^_^ ), the set of all invertible matrices is not convex. Therefore your question does not make sense. However, $\operatorname{tr}\left((X^TX)\right)^{-1}$ is locally convex at every invertible matrix $X$ and this can be proved using the trick demonstrated in another thread by Robert ...


1

The two problem formulations are equivalent for some choice of $\lambda$, at least if $g(x)$ is non-negative; the problem is that in general there's no way to figure out which $\lambda$ will give you the solution corresponding to $g(x) \leq t$.


1

It has already be mentioned in the comments above that the maximum doesn't exist. Note that $$ \{-1-x : x\in (0, 1]\} = [-2, -1) $$ and this set does not have a maximum. Remember that the maximum is an upper bound that is itself a member of the set. As also mentioned in the comment above, this set does have a supremum which is the least upper bound. You ...


0

The equation you want to use is this: $$||\mathbf x -\mathbf y - \theta(\mathbf z - \mathbf y)||^2 - ||\mathbf x - \mathbf y||^2 \geq 0$$ Remember the reason this is true is that $\mathbf y + \theta(\mathbf z - \mathbf y) \in C$ for all $\theta \in [0,1]$. To make things a little easier, first show that if $$||\mathbf a - \theta \mathbf b||^2 - ||\mathbf ...


1

If $f(x)$ has no critical points, then it's derivative is continuous and either positive definite or negative definite (over the domain $M$). To be either convex or concave, the second derivative would have to, likewise, by either positive definite or negative definite. A simple sketch will show that the derivative can be positive definite and yet the ...


2

If $f(x) = 2x+\sin(x), x\in \mathbb{R}$, then $f^\prime(x) = 2+\cos(x)$ is nowhere $=0$, hence there is no critical point. However, $f^{\prime\prime}(x)=-\sin(x)$ changes sign, so $f$ is neither convex nor concave. By scaling you can do that on any interval, as small as you like.


2

In general, the answer is no to both questions. Of course, you could always try a finite number of test points, including $x=0$, $x=c$, to see if they happen to satisfy $Ax=b$; and you can try the minimum-norm solution $x=A^T(AA^T)^{-1}b$, to see if it happens to satisfy $0\preceq x\preceq c$. If any of these tests hold, then you've found a closed form ...


0

Your problem is not convex even if $L=1$, for two reasons: for one, you would be maximizing a convex function; and two, your constraint set is non-convex. We can fix the second problem by relaxing the constraint to $\|x\|\leq 1$. Alt suggested this, but what he did not make clear is that you can guarantee equivalence in this case. To see why, suppose we ...


0

For (a), because the objective function is continuos and the constraints set is compact, therefore, there always exists a solution (Existence). For (b), you want to prove uniqueness, you should prove the objective function is strictly convex. In your case, because l2 norm is strictly convex, so we have uniqueness. BTW, if C is a subspace, then based on ...


0

For (a), the set $C$ may not be bounded so you need to do a little more work. I make the additional assumption that $C$ is nonempty. Let $z_0\in C$. If $\|x-z\|_2<\|x-z_0\|$ then $z\in \overline{B_{\|x-z_0\|}(z_0)}\cap C$, which is closed and bounded. Hence $\|z-x\|$ has a minimum in $\overline{B_{\|x-z_0\|}(z_0)}\cap C$, which must be the minimum in $C$. ...


2

Hint:The probably your objective is either log-convex or log-quasi convex. My suggestion is to take $\log$ and then solve it. Note, that even by doing so your problem is non-convex because of $\|x\|=1$ (especially if $\|x\|=\|x\|_2$, then you can either relax the problem by converting the constraint $\|x\|=1$ to $\|x\|\leq 1$. If the relaxation is not ...


0

The condition $\nabla f(x^\star) + \lambda \nabla g(x^\star) = 0$ tells us that $x^\star$ is a minimizer of $f(x) + \lambda g(x)$. If $x \in C$, then \begin{align*} f(x) & \geq f(x) + \lambda g(x) \\ & \geq f(x^\star) + \lambda g(x^\star) \\ &= f(x^\star). \end{align*} (In the first step, I used the fact that $\lambda g(x) \leq 0$, which follows ...


1

The fact that dual to dual norm is equal to the original norm in case of finite-dimensional spaces is equivalent to the fact that the corresponding Banach space is reflexive. By James' theorem, a Banach space $B$ is reflexive if and only if every continuous linear functional on $B$ attains its maximum on the closed unit ball in $B$. That is surely true for ...


0

I think I got the answer (thanks S.B. for the comments) but not sure so I'm placing it as a community wiki feel free to edit: The minimum occurs at $\left(\underbrace{\frac{1-\frac 1k}{N-1},\ldots,\frac{1-\frac 1k}{N-1}}_{k\text{ times}},\underbrace{\frac 1{N-1},\ldots,\frac 1{N-1}}_{N-k\text{ times}}\right)$ for some $k$. First show the minimum must have ...


0

This is late but in case you need it in the future. Lemma 2.1 (Chandra) states that if $f(x)$ is non-negative concave and $g(x)$ is strictly positive convex, then $h(x)$ is strong pseudoconcave. http://www.new1.dli.ernet.in/data1/upload/insa/INSA_2/20005a7f_278.pdf


1

The difference is that one condition is algebraic and one is geometric. both are needed to develop intuition of both kinds. The correct geometric condition, by the way, is that the epigraph of $f$ be convex, not the range. Consider, e.g. $f(x) = -|x|$ with a perfectly convex range $(-\infty,0]$ (but the function, of course, is concave, not convex). EDIT As ...


1

I'm sure the link @AC_MOSEK offers here will give you the instructions you need. I'm also fond of Optimization by Vector Space Methods by David Luenberger. It's a bit dated in some respects, but its treatment of Lagrange multipliers is particularly well suited for conic and semidefinite programming, in my view. But what the heck, I'll do it for you right ...


0

As a reference, the classical Ben-Tal, Aharon, and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Vol. 2. Siam, 2001. usually works for me. Or you can take a look to the modeling manual here: http://mosek.com/resources/doc/


0

The key to your formula is $$\|x\| = \sup_{\|u\|_2\le1} u^\top x.$$ This should help showing the equality above.


1

The problem is affine, so we might as well assume the $T_i$ are the standard basis vectors: $T_i=e_i$. Then: \begin{align*} C(S) &= \left\{\lambda_0\cdot 0 + \sum_{i=1}^n\lambda_i e_i\;\colon\; \text{all $\lambda_i\ge 0$ and } \sum_{i=0}^n \lambda_i = 1 \right\} \\ &= \left\{\sum_{i=1}^n\lambda_i e_i \;\colon\; \text{all $\lambda_i\ge 0$ and } ...


1

I'm going to use the notation where a $t$ or $w$ subscript represents partial differentiation on that variable; e.g., $x_{tw}\triangleq \partial^2 x(t,w) / \partial t\partial w$. In order for $t$ to be the local minimum for fixed $w$, you must have $$2(x-c_x)x_t+2(y-c_y)y_t=0$$ This equation is satisfied for all $t_0(w)$. Differentiating implicitly I get ...


1

The proof looks good. You do not need any assumption on the interior as you are separating a point from a convex set. You would need a non-emptyness condition on the interior if you would like to separate two convex sets in infinite-dimensional spaces.


1

For general convex sets, the sorts of simple relationships you're suggesting don't exist. I find it helps to draw two dimensional pictures to see why. (Even if the space is dimension higher than 2, we could restrict the problems to the plane spanned by $x_1,x_2,x$ and none of the answers to your questions would change.) Here's an example of what can happen ...


2

I'm not an expert, but maybe there is some thing related to distributions in the dual space. If there is such a thing then that would help.


0

$F_1$: the graph Laplacian is positive semidefinite, hence the second derivative $F_1''$ is a positive semidefinite matrix, and $F_1$ is convex. $F_2,F_3$: are sums of convex functions. The function $|\cdot|$ is convex (it is a norm), $\max(\cdot,\cdot)$ is a convex function, too.


1

I'd say a projected gradient method is likely going to work well for a simple problem like that. That is, alternate between gradient steps $$X_+ = X - \alpha \nabla f(X)$$ and projection steps: $$X_{++} = \mathop{\text{arg}\,\text{min}}_{X\succeq 0} \|X-X_+\|_F$$ The projection is relatively simple: given a Schur decomposition $X_+=U\Sigma U^T$, then ...


0

I am a beginner in optimization theory, So wait for someone to confirm this. My idea is to start with finding the standard form of an SDP, witch is : $$\begin{array}{rll} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n} & \\ \text{subject to} & \langle A_i, X \rangle_{\mathbb{S}^n} = b_i, \quad i = 1,\ldots,m & ...


0

I would say $x^*\in\mathop{\text{arg}\,\text{min}} f$, because it might be possible for other points $x$ to achieve $f(x)=0$. But otherwise, yes, the statement is true. If $f(x^*)=0$, but $x\not\in\mathop{\text{arg}\,\text{min}} f$, then there must be some $x$ satisfying $f(x)<0$. But if that were the case, $f(\alpha x)\rightarrow-\infty$ as ...


0

I'm going to get you part of the way there in one direction. First, write it as follows: $$\begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to} & \sum_i F_i x_i - \bar{X} = - F_0 \\ & \bar{X} \succeq 0 \end{array}$$ Split each free variable into the difference of nonnegatives: $$x_i=x_{+,i}-x_{-,i} \quad x_{+,i},x_{-,i}\succeq 0 \quad ...


2

No. The KKT point is $(x^*,\lambda^*)=(0,1)$. $\lambda=0$ is not dual feasible. The Lagrangian is $L(x,\lambda)=x-\lambda x$, and the dual problem is $$\begin{array}{ll} \text{maximize} & 0 \\ \text{subject to} & \lambda = 1 \\ & \lambda \geq 0 \end{array}$$ So clearly, $\lambda^*=1$ is the optimal dual point. It's actually not difficult to ...


0

Assume $P$ symmetric positive definit. Then your problem is equivalent to $$ \min 0 $$ subject to $$ P\Delta u + q = 0. $$


1

Example 3.10 of Boyd is already presenting you with a proof! Ok, let us revisit: what is eigenvalue of $X$? Given a vector $y$, if $$Xy = \lambda y \ldots (1)$$ then $\lambda$ is called the eigenvalue of X. Multiplying (1) by $y^{\top}$ we get, $$y^{\top}Xy = \lambda y^{\top}y = \lambda \|y\|^2$$ So, if we restrict ourselves to all $y$'s of norm $1$, then ...


2

Let us enter in the Karush–Kuhn–Tucker framework, with $$ f(x,y) = -\max(x,y);\\ g_1(x,y) = 2x+y-1;\\ g_2(x,y) = x+3y-1. $$ The Lagrangian is $$ L(x,y,\lambda) = -\max(x,y) + \lambda\cdot g(x,y) $$ and the solution is, in the region $x\neq y$ (where $L$ is smooth): $$ \begin{cases} 0&=&-1_{x>y} + 2\lambda_1 + \lambda_2 \\ ...


1

The statement is clearly false: just think about a vertex of a square! By the way, you guys got it wrong: by definition the empty set and a single point are convex set. The latter is indeed an affine set of dimension 0. A set $S$ is convex iff $$ \forall x,y \in S \Rightarrow \theta x + (1-\theta)y \in S, \quad \forall \theta \in [0,1]$$ an it doesn't ...


0

No, take $A=(-1,1)$, $f(x)=x^4$. Then $x_0=0$ is the unique critical point of $f$, $f''$ is positive semi-definite, but $f''(x_0)=0$.


1

You don't even need $S$ convex: just take $y_1 = y_2 = y$.


-1

$$\left\{ \sum_{i=1}^m a_ip_i\; \mid\; a_i \geq 0, \sum_{i=1}^ma_i=1\right\}$$


1

Some stuff can be said about the case $g(X,Z)=Z^TX=∑_iZ_iX_i$ where $AX\le b$. For a given value of $X$, if $\min_Z Z^TX$ is bounded, then the minimizing value of $Z$ will be one of the vertices of the simplex/polyhedron $AZ\le b$. The number of vertices is at most $K-1$, where $K$ is the number of constraints in $AZ\le b$. Thus in $(Z^*)^TX$, where $Z^* = ...


1

You can find such notation and how it relates with the one you are used to in the classic book Ben-Tal, Aharon, and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Vol. 2. Siam, 2001. or more in brief in http://docs.mosek.com/generic/modeling-a4.pdf You basically introduce variables so that ...


0

Minimizing continuous functions over compact level-sets is a nice problem. Boundedness of level-sets alone is not enough. The function $$ f(x) = \begin{cases} 1-x^2 & |x|<1\\ x^2 & |x|\ge 1 \end{cases} $$ has bounded level sets, but there exists no global minimizer. The function $f(x)=e^x$ has star-shaped, connected level-sets, but no minimizer ...



Top 50 recent answers are included