Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

7
votes
4answers
184 views

Finding minimum $\frac{x+y}{z}+\frac{x+z}{y}+\frac{y+z}{x}$

I would appreciate if somebody could help me with the following problem Q. Finding maximum minimum $$\frac{x+y}{z}+\frac{x+z}{y}+\frac{y+z}{x}(\text{where} ~~x,y,z>0)$$
7
votes
1answer
8k views

How to compute the Pareto Frontier, intuitively speaking?

I'm working on a multi-objective optimization problem and we have 'alternatives' that are quantified on two dimensions - value and cost. Now the question is 'how does one compute a pareto frontier'? ...
6
votes
3answers
127 views

Determine the minimum of $a^2 + b^2$ if $a,b\in\mathbb{R}$ are such that $x^4 + ax^3 + bx^2 + ax + 1 = 0$ has at least one real solution

I just wanted the solution, a hint or a start to the following question. Determine the minimum of $a^2 + b^2$ if $a$ and $b$ are real numbers for which the equation $$x^4 + ax^3 + bx^2 + ax + 1 = 0$$ ...
5
votes
1answer
149 views

dual problem of a Semidefinite programming in a non-standard forme

I have a problem with calculating the dual problem of : $$ \mbox{Minimize } tr(Y) + \frac{1}{\eta} tr(Z) $$ $$ \begin{pmatrix} Y & X \\ X & Z+\varepsilon I \end{pmatrix} \succeq 0 ...
5
votes
1answer
55 views

Fundamental Optimization question consisting of two parts.

A) Find all extrema of $$f(x)=\sum_{k=1}^{n} x_{k}^{2} $$ subject to the constraint $\sum_{k=1}^{n}\vert x_k\vert^p=1$ B) prove that $$\frac{1}{n^{(2-p)/(2p)}}(\sum \vert x_k\vert^p)^{(1/p)}\le (\sum ...
5
votes
2answers
534 views

Generalizing Lagrange multipliers to use the subdifferential?

Background: This is a followup to this question: Lagrange multipliers with non-smooth constraints Lagrange multipliers can be used for constrained optimization problems of the form $\min_{\vec x} ...
4
votes
3answers
840 views

Monotonicity of $\ell_p$ norm

Consider a $n$ dimensional space, it is known (Wikipedia) that for $p>r>0$, we have $$ \|x\|_p\leq\|x\|_r\leq n^{(1/r-1/p)}\|x\|_p. $$ I have two questions about the above inequality. $(\bf ...
4
votes
0answers
899 views

Convergence of Gauss-Newton method for piecewise linear functions

Notation for Gauss-Newton method Non-linear least squares problems are often solved by the Levenberg-Marquardt algorithm, which can be viewed as a Gauss–Newton method using a trust region approach. ...
3
votes
1answer
113 views

Newton's method vs. gradient descent with exact line search

tl;dr: When is gradient descent with exact line search preferred over Newton's method? I simply don't understand why exact line search is ever useful, and here's my reasoning. Let's say I have a ...
3
votes
3answers
129 views

Find out minimize volume (V) of tetrahedral

I have this problem: On space $ (Oxyz)$ given point $M(1,2,3)$. Plane ($\alpha$) contain point $M$ and ($\alpha$) cross $Ox$ at $A(a,0,0)$; $Oy$ at $B(0,b,0)$; $C(0,0,c)$. Where a,b,c>0 Write the ...
3
votes
3answers
119 views

Mminimize the integral and obtaining the constants $a$ and $b$

Determine the constants $a$ and $b$ for the integral $$ \int\limits _{0}^{1}(ax+b-f(x))^{2} dx$$ take the smallest possible value if $f(x)=(x^{2}+1)^{-1}$ thanks
3
votes
2answers
98 views

Is this “theorem” true in Optimization Theory?

If I have a function $f(x,y)$ subjected to a region $D$ on the xy-plane, then the extreme values of $f(x,y)$ occurs at the extreme "corners" points of $D$? I remember waaaaaaay back in calculus, if ...
2
votes
1answer
54 views

linear approximation with respect to L1 norm

I am trying to solve this problem: Find the best $L^1$ linear approximation of $e^x$ on [0,1] i.e. minimize $\int_0^1|e^x-\alpha-\beta x| dx$ any hints how to proceed
2
votes
3answers
132 views

Is this optimization problem solvable?

I have the following optimization problem: $$ \min_\mathbf{x}\|\mathbf{a+Bx}\|^2 ~~\text{s.t}~~ \|\mathbf{y+Ax}\|_\infty \leq \beta\|\mathbf{y}\|_\infty ~~,~~ \|\mathbf{x}\|^2 \leq \alpha^2$$ where ...
2
votes
2answers
97 views

Gradient and Swiftest Ascent

I want to understand intuitively why it is that the gradient gives the direction of steepest ascent. (I will consider the case of $f:\mathbb{R}^2\to\mathbb{R}$) The standard proof is to note that the ...
2
votes
1answer
141 views

Set convergence and lim inf and lim sup

I'm a bit confused with the general concept of convergence of a sequence of sets. I'm well aware that the limit of a sequence $\{C^{\nu}\}$ exists iff $$\liminf_{\nu \rightarrow \infty} C^{\nu} = ...
2
votes
3answers
108 views

Maximal area of a triangle

What would be the most elementary proof of the following: A triangle has been drawn inside the circle with radius $r$ and its area is as large as possible. Prove that the triangle is equilateral. I ...
2
votes
1answer
231 views

Does the uniqueness of solutions to convex optimization with linear constraints hold in n>3 dimensions?

This is a repost of an earlier question, where I think I was not clear enough in what I was asking: I am examining the following optimization problem, for which I would like to know if, when a ...
2
votes
2answers
179 views

Shortest ternary string containing all ternary strings of length 3?

How can we find/construct the shortest ternary string that contains all ternary strings of length 3? For instance, $120011$ contains $120$, $200$, $001$, and $011$. (The shortest such a string could ...
2
votes
1answer
189 views

minimum lines, maximum points

There are $P$ points in the 2-dimensional plane. Through each point, we draw two orthogonal lines: one horizontal (parallel to x axis), one vertical (parallel to y axis). Obviously, some of these ...
2
votes
1answer
476 views

Preconditioning for an LBFGS

I am working on a high dimensional (N ~ 1000-60000) optimization problem which is currently solved with an LBFGS algorithm. I have experimented with different diagonal preconditioners as I know that ...
2
votes
1answer
139 views

Control on Conformal map

Let $\Omega$ be smooth simply connected open set of $\mathbb{R}^2$ such that $\overline{\Omega}$ is compact. We know that there exists a conformal diffeomorphism $\psi$ from $\mathbb{D}$ to $\Omega$. ...
2
votes
2answers
227 views

$\beta_k$ for Conjugate Gradient Method

I followed the derivation for the Conjugate Gradient method from the documents shared below http://en.wikipedia.org/wiki/Conjugate_gradient_method ...
1
vote
2answers
61 views

Theorem 6.4.1 Auslender Asymptotic cones and functions in optimization and variational inequalities

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 ...
1
vote
1answer
34 views

how to find the solution of this cost function?

I have the following cost function. $J = \sum_{i=1}^N a\, Trace(W^TX_iW) - b\, Trace(W^TY_iW)$ Where $X_i$ and $Y_i$ are symmetric matrices, $a$ and $b$ are scalars. How can I find W?
1
vote
2answers
92 views

Local optimality of a KKT point.

Consider the problem \begin{equation} \min_x f(x)~~~{\rm s.t.}~~~ g_i(x)\leq 0,~~i=1,\dots,I, \end{equation} where $x$ is the optimization parameter vector, $f(x)$ is the objective function and ...
1
vote
1answer
154 views

Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
1
vote
2answers
65 views

Confounding Lagrange multiplier problem

Optimize $f(x,y,z) = 4x^2 + 3y^2 + 5z^2$ over $g(x,y,z) = xy + 2yz + 3xz = 6$ According to the theorem the gradients must be parallell, $\nabla f = \lambda \nabla g$, so their cross product must ...
1
vote
2answers
174 views

Clarification on optimization problem

While reading a combinatorics paper about packing densities in compositions, I encountered the following optimization problem. Maximize $$f(\alpha_1, \dots, \alpha_5) = \sum_{1 \le i < j ...
1
vote
2answers
145 views

Calculus of variations, what is a functional

I'm reading a bit about the calculus of variations, and I've encountered this bit: Suppose the given function $F(.,.,.)$ is twice continuously differentiable with respect to all of its arguments. ...
1
vote
1answer
1k views

“Box With No Top” Optimization

I am having some trouble with this problem, A box with no top is to be constructed from a piece of cardboard of dimensions $A$ by $B$ by cutting out squares of length $h$ from the corners and ...
1
vote
0answers
116 views

Why these two problems lead to same answers?

Suppose these two problems: Problem 1: $$\min_{X,P} \quad\max_{1\leq l\leq L-1} \quad {|\sum_{1\leq i\leq N_p}^{N_p}x_ie^{\frac{2\pi l}{N}p_i}| \over {\sum_{i=1}^{N_p} x_i^2}} \quad \equiv \quad ...
1
vote
3answers
740 views

How to find maximum and minimum volumes

I would appreciate if somebody could help me with the following problem: Q: Let $S$ be the region bounded by the curves $y=\sin x \ (0 \leq x \leq \pi)$ and $y=0$. Let $V(c)$ be the volume of the ...
1
vote
0answers
81 views

KKT: Explain visually the optimality condition $F_0\cap G_0\cap H_0=\emptyset$

I am trying to understand visually what this condition actually mean. It is the optimality condition in KKT. It means something like that constraint -set, objective -set and hyperplane -set has no ...
1
vote
2answers
267 views

How can I infer a result using primal feasibility, dual feasibility, and complementary slackness?

I am trying to find the minimum of $-x_1$ with restrictions $\bar g\leq\bar 0$ so that $$\bar g=\begin{pmatrix} (x_1+2)^2+(x_2-4)^2-20\\ (x_1+2)^2+x_2^2-20\\ -x_1\end{pmatrix}\leq ...
1
vote
1answer
724 views

Need help with Lagrange Multipliers

I need to maximize $U = BM$ with constraits: $6B +3M = 60$, $B>0$ and $M>0$. The Lagrange function is $L=U + \lambda (6B+3M-60) + KB + HM$. So $$\partial_{\lambda}L= 6B+3M-60=0$$ ...
0
votes
1answer
58 views

Distribute small number of points on a disc

Firstly I strongly know how many similar questions there are here. It's about sets of evenly distributed points inside a circle. If we need a big set of such points, good solutions are: Isocell ...
0
votes
0answers
104 views

Ternary balance with unknown weight

Main references: Ternary (Wolfram MathWorld) Balanced ternary (Wikipedia) Weighing scale: Balance (Wikipedia) <quote> Balanced ternary has other applications besides computing. For example, a ...
0
votes
4answers
189 views

Maximizing the Magnitude of the Resultant Vector

Given a set of $n$ two-dimensional unit vectors: $\left\{ \mathbf{v}_1, \dots, \mathbf{v}_n \right\}$, I want to find the coefficients $\left\{ \alpha_1, \dots, \alpha_n \right\}$, $0 \leq \alpha_i ...
0
votes
2answers
93 views

Help finding local extrema of $f(x)=\frac{x}{\sqrt{2}}-3\sin\frac{x}{2}$

Find the local extrema of $f(x)=\dfrac{x}{\sqrt{2}}-3\sin\dfrac{x}{2}$ on the interval $0 \leq x \leq 2\pi$ $f^{\prime}=\dfrac{1}{\sqrt{2}}-3\cos \left(\dfrac{x}{2}\right) \left ( ...
0
votes
1answer
126 views

Explain Complementary Slackness $\mu_i g_i(x^*)=0\forall i$

Wikipedia here explains it like this: I understand it so that either $\mu_i=0$ or $g_i=0$ but this answer here: "If μ1≠0 and μ2≠0, then x is one of the two points at the intersection of the two ...
-2
votes
2answers
3k views

Minimum ladder over wall optimization

A fence 6 feet tall runs parallel to a tall building at a distance of 2 feet from the building. We want to find the the length of the shortest ladder that will reach from the ground over the fence to ...
7
votes
2answers
4k views

Taking derivative of $L_0$-norm, $L_1$-norm, $L_2$-norm

I am a little confused about taking derivatives w.r.t. the norms. $L_0$-norm: $L_0$ means number of non-zero elements in a vector. Say, I am interested in an $x_i$. ...
6
votes
0answers
193 views

Optimization of relative entropy

Wondering if my following question is an application of information theory: Lets say we have a factory and ship boxes of stuff outside. If a competitor stands outside my factory, observes the stream ...
5
votes
1answer
146 views

What is the minimal isoperimetric ratio of a polyhedron with $5$ vertices?

I'm asking and answering this question to provide a partial answer to this question and a comment on this answer at MO. The isoperimetric ratio $\mu$ of a solid is the ratio $A^3/V^2$, where $A$ is ...
5
votes
1answer
470 views

Optimizing a functional with a differential equation as a constraint

I am working on solving the following optimization problem. I think it is well-poised but, if not, please give me some pointers that could make the question make more sense. We have a parametric ...
5
votes
1answer
370 views

Find extremes of function $f(x,y,z) = x^2y + y^2z + x - z$

I am preparing for an exam tuesday morning and I would like to ask you, if someone could please review my solution for the following excercise. I don't have the correct answer so I am unable to check ...
5
votes
2answers
1k views

Minimize a matrix function with constraints

Let $A, X\in\mathbb{R}^{n\times n}$. The scalar objective function is $$J=\mathrm{tr}(AX)$$ If no constraints, let the derivative of $J$ with respect to $X$ be zeros, then we have $$A=0$$ Suppose $A$ ...
5
votes
1answer
535 views

Find minimum in a constrained three-variable equation

After my last question I have worked through the math quite a bit and now I'm stuck again. This time my question is less wordy. I have two equations for $t$, one with respect to each $a_{x}$ and ...
4
votes
1answer
171 views

Minimize Frobenius norm with unitary constraint

I am trying to find a unitary tramsformation, $M$, that minimizes $\Vert MA-B \Vert_F^2$ where $A$ and $B$ are $N\times L,\;L\ge N$. I know how to solve it without the unitary constraint. I thought ...