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)

2
votes
1answer
813 views

When $\min \max = \max \min$?

Let $X \subset \mathbb{R}^n$ and $Y \subset \mathbb{R}^m$ be compact sets. Consider a continuous function $f : X \times Y \rightarrow \mathbb{R}$. Say under which condition we have $$ \min_{x \in ...
2
votes
1answer
800 views

Solution Technique to Optimize Sets of Constraint Functions with Objective Function that is Heaviside Step Function

I have the following constraint inequalities and equalities: $$Ax \leq b$$ $$A_{eq}x = b_{eq}$$ The problem is that the objective function, which I am asked to minimized, is defined as ...
1
vote
0answers
90 views

Constraint optimization with Calculus of Variations. How to handle positive function constraint?

the I am attempting to maximize the functional $F[f]$ with a constrain that $f$ has to be non-negative and some other integral constraints. More, specifically, \begin{align*} &\max F[f]\\ ...
1
vote
1answer
51 views

Maximisation problem

I am trying the following question: If$$a+b+c+d=0,\;a^2+b^2+c^2+d^2=1$$ Then what is the maximum value of $ab+bc+cd+da?$ By the rearrangement inequality I can get $ab+bc+cd+da\leq 1$ but I am ...
1
vote
1answer
111 views

A problem on positive semi-definite quadratic forms/matrices

Suppose $a+b+c=0$ and (without loss of generality) $a\leq b\leq 0\leq c$, $a^2+b^2+c^2=1$, is the following quadratic form positive semi-definite? Thank you very much. \begin{equation*} \begin{split} ...
1
vote
0answers
52 views

Sequence of solutions of approximated problem converging to stationary solution of the original problem

Let $I(x)$ be the indicator function defined as $$I(x) \triangleq \begin{cases} 1, & x \geq 0 \\ 0, & x < 0 \end{cases}$$ and let $L(x,\alpha) \in [0,1]$ be a smoothing function that ...
0
votes
1answer
58 views

Find minimal $\alpha_3$ such that $u\in H^3(\Omega)$ and $u(x,y,z)=x^\alpha(1-x)y(1-y)z(1-z)$

My instructor presented me the quiz below but forgot to define key terms such as minimality and $H^3$. Quiz Let $u(x,y,z)=x^\alpha(1-x)y(1-y)z(1-z)$. Find the minimal $\alpha_3$ such that $u\in ...
0
votes
2answers
528 views

How to prove equality from poincare inequality?

Let $$D = \{y \in C^1(0,1) : y(0) = y(1) = 0\}$$ Suppose there exists a $C_0$ such that $$\int_{0}^{1} y^2 \ dx \leq C_0 \int_{0}^{1} (y')^2 \ dx$$ for all $y \in D$, and for all $C < C_0$ ...
0
votes
1answer
136 views

Optimizing $x^2+y^2$ from two given equations? [duplicate]

What is the maximum value of $x^2+y^2$, where $(x,y)$ are solutions to: $$2x^2+5xy+3y^2=2$$ and $$6x^2+8xy+4y^2=3$$ Note: Calculus is not allowed. I tried everything I could but whenever I got for ...
16
votes
4answers
801 views

Gerrymandering/Optimization of electoral districts for one particular party

I'm asking this on behalf of Zach Weiner (actually it's my own initiative in order to promote this site). Original text is here, and is as follows: Hey-- This is Zach from SMBC, and I have a math ...
14
votes
1answer
267 views

Fastest curve from $p_0$ to $p_1$

I'm trying to solve a problem in path planning: Given points $p_0$ and $p_1$ and vectors $v_0$ and $v_1$, find a function $p(t)$ st. $p(0) = p_0$, $p(T) = p_1$, $p'(0) = v_0$ and $p'(T) = ...
8
votes
6answers
1k views

Optimization problem (in linear algebra course!)

Let $a_1, a_2, \ldots, a_n$ be real numbers such that $a_1 + \cdots + a_n = 0$ and $a_1^2 + \cdots +a_n^2 = 1$. What is the maximum value of $a_1a_2 + a_2a_3 + \cdots + a_{n - 1}a_n + a_na_1$? I'd ...
8
votes
1answer
2k views

On problems of coins totaling to a given amount

I don't know the proper terms to type into Google, so please pardon me for asking here first. While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
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
10k 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
143 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
163 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
56 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
553 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
922 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
1answer
437 views

Maximizing distance between points

I asked a similar question on SciComp, but it is a little out of the domain, so I thought I'd give it a try here as well. Give n points, I would like to place them in a periodic box (periodic such ...
4
votes
2answers
845 views

Change-making problem - counterexample for greedy algorithm

Let D be set of denominations and m the largest element of D. We say c is counterexample if greedy algorithm is giving answer different from optimal one. I found statement that if for given set ...
4
votes
0answers
931 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
0answers
72 views

If this problem is not unbounded, what's wrong in this dual derivation?

In a paper with 100 citation, Robust Support Vector Machine Training via Convex outlier Ablation, a convex relaxation is used. In this paper, a form of robust svm proposed: \begin{align} \min_{0\leq ...
3
votes
1answer
163 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
133 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
121 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
312 views

Minimize $x^TAx$, subject to $||x||=1$. Show that ${x^*}^TAx^*$ is the smallest eigenvalue of $A$ in magnitude.

I'm solving constrained optimization exercises for preparing my final exam. I got stuck at this question. $$ \begin{array}{ll} \text{min} & \mathbf{x}^T\mathbf{A}\mathbf{x} \\ \text{s.t.} & ...
3
votes
2answers
99 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
57 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
135 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
104 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
147 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
119 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
264 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
183 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
193 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
518 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
152 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
3answers
8k views

Optimization of the Area of a rectangle with regards to an Ellipse

The actual problem reads: Find the area of the largest rectangle that can be inscribed in the ellipse $$\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1$$ I got as far as coming up with the equation for the ...
2
votes
2answers
233 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
1answer
50 views

Find vector that maximizes $f(x) = 2x_1^2+2x_2^2-x_3^3+2x_1x_2$

Find the vector with $||x||^2=x^Tx=1$ that maximizes the following function. $f(x) = 2x_1^2+2x_2^2-x_3^3+2x_1x_2$ I have rewritten the quadratic form as $f(x) = \frac{1}{2}x^T \begin{bmatrix} ...
1
vote
2answers
56 views

Projection of a vector onto the null space of a matrix

I have the following optimization problem: $$ \text{minimize}_x \Vert z - x \Vert^2 \\ \text{subject to } Ax = 0, $$ where $x,z\in \mathbb{C}^N$, and $A\in\mathbb{C}^{M \times N}$. $A$ is a wide ...
1
vote
2answers
73 views

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

In proof of Theorem 6.4.1 of Auslender's book about asymptotic cones, the author assumes that $\text{rge}\,A\subset\text{aff}\,C$ and for $\epsilon>0$ claims that ...
1
vote
1answer
37 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
115 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
186 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
3answers
114 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
155 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. ...