Условия куна таккера в геометрической форме. Формулировка и доказательство теоремы куна-таккера. Более слабые условия

Существуют три основных системы координат, используемых в геометрии, теоретической механике, других разделах физики: декартова, полярная и сферическая. В этих системах координат вся точка имеет три координаты. Зная координаты 2-х точек, дозволено определить расстояние между этими двумя точками.

Вам понадобится

• Декартовы, полярные и сферические координаты концов отрезка

Инструкция

1. Разглядите для начала прямоугольную декартову систему координат. Расположение точки в пространстве в этой системе координат определяется координатами x,y и z. Из начала координат к точке проводится радиус-вектор. Проекции этого радиус-вектора на координатные оси и будут координатами этой точки.Пускай у вас сейчас есть две точки с координатами x1,y1,z1 и x2,y2 и z2 соответственно. Обозначьте за r1 и r2, соответственно, радиус-векторы первой и 2-й точки. Видимо, что расстояние между этими двумя точками будет равно модулю вектора r = r1-r2, где (r1-r2) – векторная разность.Координаты вектора r, видимо, будут следующими: x1-x2, y1-y2, z1-z2. Тогда модуль вектора r либо расстояние между двумя точками будет равно: r = sqrt(((x1-x2)^2)+((y1-y2)^2)+((z1-z2)^2)).

2. Разглядите сейчас полярную систему координат, в которой координата точки будет задаваться радиальной координатой r (радиус-вектор в плоскости XY), угловой координатой? (углом между вектором r и осью X) и координатой z, аналогичной координате z в декартовой системе.Полярные координаты точки дозволено перевести в декартовы дальнейшим образом: x = r*cos?, y = r*sin?, z = z. Тогда расстояние между двумя точками с координатами r1, ?1 ,z1 и r2, ?2, z2 будет равно R = sqrt(((r1*cos?1-r2*cos?2)^2)+((r1*sin?1-r2*sin?2)^2)+((z1-z2)^2)) = sqrt((r1^2)+(r2^2)-2r1*r2(cos?1*cos?2+sin?1*sin?2)+((z1-z2)^2))

3. Сейчас разглядите сферическую систему координат. В ней расположение точки задается тремя координатами r, ? и?. r – расстояние от начала координат до точки, ? и? – азимутальные и зенитный угол соответственно. Угол? аналогичен углу с таким же обозначением в полярной системе координат, а? – угол между радиус-вектором r и осью Z, причем 0<= ? <= pi.Переведем сферические координаты в декартовы: x = r*sin?*cos?, y = r*sin?*sin?*sin?, z = r*cos?. Расстояние между точками с координатами r1, ?1, ?1 и r2, ?2 и?2 будет равно R = sqrt(((r1*sin?1*cos?1-r2*sin?2*cos?2)^2)+((r1*sin?1*sin?1-r2*sin?2*sin?2)^2)+((r1*cos?1-r2*cos?2)^2)) = (((r1*sin?1)^2)+((r2*sin?2)^2)-2r1*r2*sin?1*sin?2*(cos?1*cos?2+sin?1*sin?2)+((r1*cos?1-r2*cos?2)^2))

Видео по теме

Длина, как уже отмечалось, обозначается знаком модуля.

Если даны две точки плоскости и , то длину отрезка можно вычислить по формуле

Если даны две точки пространства и , то длину отрезка можно вычислить по формуле

Примечание: Формулы останутся корректными, если переставить местами соответствующие координаты: и , но более стандартен первый вариант

Пример 3

Решение: по соответствующей формуле:

Ответ:

Для наглядности выполню чертёж

Отрезок – это не вектор , и перемещать его куда-либо, конечно, нельзя. Кроме того, если вы выполните чертеж в масштабе: 1 ед. = 1 см (две тетрадные клетки), то полученный ответ можно проверить обычной линейкой, непосредственно измерив длину отрезка.

Да, решение короткое, но в нём есть ещё пара важных моментов, которые хотелось бы пояснить:

Во-первых, в ответе ставим размерность: «единицы». В условии не сказано, ЧТО это, миллиметры, сантиметры, метры или километры. Поэтому математически грамотным решением будет общая формулировка: «единицы» – сокращенно «ед.».

Во-вторых, повторим школьный материал, который полезен не только для рассмотренной задачи:

Обратите внимание на важный технический приём – вынесение множителя из-под корня . В результате вычислений у нас получился результат и хороший математический стиль предполагает вынесение множителя из-под корня (если это возможно). Подробнее процесс выглядит так: . Конечно, оставить ответ в виде не будет ошибкой – но недочетом-то уж точно и весомым аргументом для придирки со стороны преподавателя.

Вот другие распространенные случаи:

Нередко под корнем получается достаточно большое число, например . Как быть в таких случаях? На калькуляторе проверяем, делится ли число на 4: . Да, разделилось нацело, таким образом: . А может быть, число ещё раз удастся разделить на 4? . Таким образом: . У числа последняя цифра нечетная, поэтому разделить в третий раз на 4 явно не удастся. Пробуем поделить на девять: . В результате:
Готово.

Вывод: если под корнем получается неизвлекаемое нацело число, то пытаемся вынести множитель из-под корня – на калькуляторе проверяем, делится ли число на: 4, 9, 16, 25, 36, 49 и т.д.

В ходе решения различных задач корни встречаются часто, всегда пытайтесь извлекать множители из-под корня во избежание более низкой оценки да ненужных заморочек с доработкой ваших решений по замечанию преподавателя.

Давайте заодно повторим возведение корней в квадрат и другие степени:

Правила действий со степенями в общем виде можно найти в школьном учебнике по алгебре, но, думаю, из приведённых примеров всё или почти всё уже ясно.

Задание для самостоятельного решения с отрезком в пространстве:

Пример 4

Даны точки и . Найти длину отрезка .

Решение и ответ в конце урока.

В статье ниже будут освещены вопросы нахождения координат середины отрезка при наличии в качестве исходных данных координат его крайних точек. Но, прежде чем приступить к изучению вопроса, введем ряд определений.

Yandex.RTB R-A-339285-1 Определение 1

Отрезок – прямая линия, соединяющая две произвольные точки, называемые концами отрезка. В качестве примера пусть это будут точки A и B и соответственно отрезок A B .

Если отрезок A B продолжить в обе стороны от точек A и B , мы получим прямую A B . Тогда отрезок A B – часть полученной прямой, ограниченный точками A и B . Отрезок A B объединяет точки A и B , являющиеся его концами, а также множество точек, лежащих между. Если, к примеру, взять любую произвольную точку K , лежащую между точками A и B , можно сказать, что точка K лежит на отрезке A B .

Определение 2

Длина отрезка – расстояние между концами отрезка при заданном масштабе (отрезке единичной длины). Длину отрезка A B обозначим следующим образом: A B .

Определение 3

Середина отрезка – точка, лежащая на отрезке и равноудаленная от его концов. Если середину отрезка A B обозначить точкой C , то верным будет равенство: A C = C B

Исходные данные: координатная прямая O x и несовпадающие точки на ней: A и B . Этим точкам соответствуют действительные числа x A и x B . Точка C – середина отрезка A B: необходимо определить координату x C .

Поскольку точка C является серединой отрезка А В, верным будет являться равенство: | А С | = | С В | . Расстояние между точками определяется модулем разницы их координат, т.е.

| А С | = | С В | ⇔ x C - x A = x B - x C

Тогда возможно два равенства: x C - x A = x B - x C и x C - x A = - (x B - x C)

Из первого равенства выведем формулу для координаты точки C: x C = x A + x B 2 (полусумма координат концов отрезка).

Из второго равенста получим: x A = x B , что невозможно, т.к. в исходных данных - несовпадающие точки. Таким образом, формула для определения координат середины отрезка A B с концами A (x A) и B (x B):

Полученная формула будет основой для определения координат середины отрезка на плоскости или в пространстве.

Исходные данные: прямоугольная система координат на плоскости О x y , две произвольные несовпадающие точки с заданными координатами A x A , y A и B x B , y B . Точка C – середина отрезка A B . Необходимо определить координаты x C и y C для точки C .

Возьмем для анализа случай, когда точки A и B не совпадают и не лежат на одной координатной прямой или прямой, перпендикулярной одной из осей. A x , A y ; B x , B y и C x , C y - проекции точек A , B и C на оси координат (прямые О х и О y).

Согласно построению прямые A A x , B B x , C C x параллельны; прямые также параллельны между собой. Совокупно с этим по теореме Фалеса из равенства А С = С В следуют равенства: А x С x = С x В x и А y С y = С y В y , и они в свою очередь свидетельствуют о том, что точка С x – середина отрезка А x В x , а С y – середина отрезка А y В y . И тогда, опираясь на полученную ранее формулу, получим:

x C = x A + x B 2 и y C = y A + y B 2

Этими же формулами можно воспользоваться в случае, когда точки A и B лежат на одной координатной прямой или прямой, перпендикулярной одной из осей. Проводить детальный анализ этого случая не будем, рассмотрим его лишь графически:

Резюмируя все выше сказанное, координаты середины отрезка A B на плоскости с координатами концов A (x A , y A) и B (x B , y B) определяются как :

(x A + x B 2 , y A + y B 2)

Исходные данные: система координат О x y z и две произвольные точки с заданными координатами A (x A , y A , z A) и B (x B , y B , z B) . Необходимо определить координаты точки C , являющейся серединой отрезка A B .

A x , A y , A z ; B x , B y , B z и C x , C y , C z - проекции всех заданных точек на оси системы координат.

Согласно теореме Фалеса верны равенства: A x C x = C x B x , A y C y = C y B y , A z C z = C z B z

Следовательно, точки C x , C y , C z являются серединами отрезков A x B x , A y B y , A z B z соответственно. Тогда, для определения координат середины отрезка в пространстве верны формулы:

x C = x A + x B 2 , y c = y A + y B 2 , z c = z A + Z B 2

Полученные формулы применимы также в случаях, когда точки A и B лежат на одной из координатных прямых; на прямой, перпендикулярной одной из осей; в одной координатной плоскости или плоскости, перпендикулярной одной из координатных плоскостей.

Определение координат середины отрезка через координаты радиус-векторов его концов

Формулу для нахождения координат середины отрезка также можно вывести согласно алгебраическому толкованию векторов.

Исходные данные: прямоугольная декартова система координат O x y , точки с заданными координатами A (x A , y A) и B (x B , x B) . Точка C – середина отрезка A B .

Согласно геометрическому определению действий над векторами верным будет равенство: O C → = 1 2 · O A → + O B → . Точка C в данном случае – точка пересечения диагоналей параллелограмма, построенного на основе векторов O A → и O B → , т.е. точка середины диагоналей.Координаты радиус-вектора точки равны координатам точки, тогда верны равенства: O A → = (x A , y A) , O B → = (x B , y B) . Выполним некоторые операции над векторами в координатах и получим:

O C → = 1 2 · O A → + O B → = x A + x B 2 , y A + y B 2

Следовательно, точка C имеет координаты:

x A + x B 2 , y A + y B 2

По аналогии определяется формула для нахождения координат середины отрезка в пространстве:

C (x A + x B 2 , y A + y B 2 , z A + z B 2)

Примеры решения задач на нахождение координат середины отрезка

Среди задач, предполагающих использование полученных выше формул, встречаются, как и те, в которых напрямую стоит вопрос рассчитать координаты середины отрезка, так и такие, что предполагают приведение заданных условий к этому вопросу: зачастую используется термин «медиана», ставится целью нахождение координат одного из концов отрезка, а также распространены задачи на симметрию, решение которых в общем также не должно вызывать затруднений после изучения настоящей темы. Рассмотрим характерные примеры.

Пример 1

Исходные данные: на плоскости – точки с заданными координатами А (- 7 , 3) и В (2 , 4) . Необходимо найти координаты середины отрезка А В.

Решение

Обозначим середину отрезка A B точкой C . Координаты ее буду определяться как полусумма координат концов отрезка, т.е. точек A и B .

x C = x A + x B 2 = - 7 + 2 2 = - 5 2 y C = y A + y B 2 = 3 + 4 2 = 7 2

Ответ : координаты середины отрезка А В - 5 2 , 7 2 .

Пример 2

Исходные данные: известны координаты треугольника А В С: А (- 1 , 0) , В (3 , 2) , С (9 , - 8) . Необходимо найти длину медианы А М.

Решение

1. По условию задачи A M – медиана, а значит M является точкой середины отрезка B C . В первую очередь найдем координаты середины отрезка B C , т.е. точки M:

x M = x B + x C 2 = 3 + 9 2 = 6 y M = y B + y C 2 = 2 + (- 8) 2 = - 3

1. Поскольку теперь нам известны координаты обоих концов медианы (точки A и М), можем воспользоваться формулой для определения расстояния между точками и посчитать длину медианы А М:

A M = (6 - (- 1)) 2 + (- 3 - 0) 2 = 58

Ответ: 58

Пример 3

Исходные данные: в прямоугольной системе координат трехмерного пространства задан параллелепипед A B C D A 1 B 1 C 1 D 1 . Заданы координаты точки C 1 (1 , 1 , 0) , а также определена точка M , являющаяся серединой диагонали B D 1 и имеющая координаты M (4 , 2 , - 4) . Необходимо рассчитать координаты точки А.

Решение

Диагонали параллелепипеда имеют пересечение в одной точке, которая при этом является серединой всех диагоналей. Исходя из этого утверждения, можно иметь в виду, что известная по условиям задачи точка М является серединой отрезка А С 1 . Опираясь на формулу для нахождения координат середины отрезка в пространстве, найдем координаты точки А: x M = x A + x C 1 2 ⇒ x A = 2 · x M - x C 1 = 2 · 4 - 1 + 7 y M = y A + y C 1 2 ⇒ y A = 2 · y M - y C 1 = 2 · 2 - 1 = 3 z M = z A + z C 1 2 ⇒ z A = 2 · z M - z C 1 = 2 · (- 4) - 0 = - 8

Ответ: координаты точки А (7 , 3 , - 8) .

Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter

Постановка задачи

Рассмотрим задачу нелинейной оптимизации. Пусть есть функции

При условиях .

Вильям Каруш в своей дипломной работе нашёл необходимые условия в общем случае, когда накладываемые условия могут содержать и уравнения, и неравенства. Независимо от него к тем же выводам пришли Гарольд Кун и Альберт Таккер.

Необходимые условия минимума функции

Если при наложенных ограничениях - решение задачи, то найдётся ненулевой вектор множителей Лагранжа такой, что для функции Лагранжа выполняются условия:

Достаточные условия минимума функции

Перечисленные необходимые условия минимума функции в общем случае не являются достаточными. Существует несколько вариантов дополнительных условий, которые делают их достаточными.

Простая формулировка

Если для допустимой точки выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также λ 1 > 0 , то .

Более слабые условия

Если для допустимой точки выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также (условие Слейтера ), то .

Wikimedia Foundation . 2010 .

Смотреть что такое "Условия Каруша - Куна - Таккера" в других словарях:

В теории оптимизации условия Каруша Куна Таккера (англ. Karush Kuhn Tucker conditions, KKT) необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые… … Википедия

В теории оптимизации условия Каруша Куна Таккера (англ. Karush Kuhn Tucker conditions, KKT) необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые условия регулярности.… … Википедия

Вильям Каруш William Karush Дата рождения: 1 марта 1917(1917 03 01) Место рождения: Чикаго, США Дата смерти … Википедия

У этого термина существуют и другие значения, см. Оптимизация. Оптимизация в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного … Википедия Википедия

Метод множителей Лагранжа, метод нахождения условного экстремума функции f(x), где, относительно m ограничений, i меняется от единицы до m. Содержание 1 Описание метода … Википедия

Теоремы Куна-Таккера - родовое название для утверждений, представляющих собой обобще-

ние теоремы Лагранжа на случай задач оптимизации с ограничениями в виде неравенств, т. е. задач

следующего типа:

gj(x) > 0, j = 1, .

M, (?)

x = (x1, . . . , xn) 2 X.

Здесь f: X 7! R - (в соответствие с установившейся терминологией) целевая функция, gr: X 7! R,

r = 1, . . . ,m, - функции ограничений, X _ Rn - открытое множество.

Теорема 196 (Теорема Джона в терминах седловой точки):

Пусть функции f( ), g1( ), . . . , gn( ) вогнуты и?x - решение задачи (?), такое что?x 2 intX.

Тогда существуют множители Лагранжа _j >

X является решением задачи

Мы приведем эти утверждения для случая, когда функции f, gr дифференцируемы (теоремы Ку-

на-Таккера в дифференциальной форме).

Напомним, что функция

L(x,_) = _0f(x) +

называется функцией Лагранжа (лагранжианом) этой задачи, а коэффициенты _j - множителями

Лагранжа.

Имеет место следующее утверждение.

Теорема 197 (Теорема Джона для дифференцируемых функций):

Пусть?x - решение задачи (?), такое что?x 2 intX и функции f( ), g1( ), . . . , gn( ) дифферен-

цируемы в точке?x.

Тогда существуют множители Лагранжа _j > 0, j = 0, . . . ,m, не все равные нулю, такие что

выполнены следующие соотношения (условия Куна-Таккера):

0, i = 1, . . . , n

J = 0 (условия дополняющей

нежесткости).

Отметим, что условия дополняющей нежесткости можно записать в виде

gj(?x)_j = 0, j = 1, . . . , m.

Из этих условий следует, что если множитель Лагранжа положителен (_j > 0), то соответствующее

ограничение в решении задачи (при x = ?x) выполняется как равенство (т. е. gj(?x) = 0). Другими

словами, это ограничение активно. С другой стороны, в случае, когда gj(?x) > 0, то соответствующий

множитель Лагранжа _j равен нулю.

Если в задаче (?) часть ограничений имеет вид ограничений на неотрицательность некоторых xi ,

то для них можно не вводить множители Лагранжа, записав такие ограничения отдельно:

gj(x) > 0, j = 1, . . . , m, (??)

xi > 0, i 2 P _ {1, . . . , n}. Во внутренней точке (в том смысле, что1 ?x 2 intX) условия первого порядка для i 2 P тогда

будут иметь следующий вид:

Для i /2 P здесь, как и в случае представления задачи в виде (?), производная функции Лагранжа

по той переменной будет иметь вид @L(?x,_)

Кроме того, выполнены также условия дополняющей нежесткости

Из второго из этих условий следует, что при?xi > 0 (i 2 P) выполнено

С другой стороны, если @L(?x,_)/@xi Другая модификация теоремы связана с наличием в задаче ограничений в виде равенств. Обозна-

чим множество соответствующих индексов через E. Задача принимает следующий вид:

gj(x) > 0, j 2 {1, . . . ,m}\E,

gj(x) = 0, j 2 E, (???)

xi > 0, i 2 P _ {1, . . . , n}.

При этом в теореме Джона снимается условие, что все множители Лагранжа неотрицательны -

множители Лагранжа _j при j 2 E могут иметь произвольный знак.

Теорема Джона не гарантирует, что множитель Лагранжа целевой функции, _0 , отличен от нуля.

Однако если _0 = 0, то условия Куна-Таккера характеризуют не решение рассматриваемой задачи, а

структуру множества ограничений в точке?x и теорема не имеет непосредственной связи с интересую-

щей нас задачей максимизации функции f( ), поскольку градиент самой функции f( ) .пропадает. из

условий Куна-Таккера.

Поэтому важно охарактеризовать условия, которые гарантируют, что _0 > 0.

Такие условия называются условиями регулярности.

В случае, когда рассматриваемая задача является выпуклой, одно из условий регулярности, -

так называемое условие Слейтера - имеет вид:

В случае, когда целевая функция и ограничения задачи являются дифференцируемыми, простей-

шее условие регулярности формулируется в терминах градиентов функций-ограничений и имеет вид:

градиенты активных ограничений в точке?x линейно независимы. (В число рассматриваемых ограни-

чений следует включать и ограничения на неотрицательность.)

Обозначим через A множество индексов тех ограничений, которые в точке оптимума?x активны

(в том числе, индексы всех ограничений в виде равенств), т. е.

gj(?x) = 0 , j 2 A.

Тогда если градиенты ограничений - векторы

линейно независимы2, то _0 > 0. Это условие называется условием регулярности Куна-Таккера.

Заметим, что если _0 > 0, то без потери общности можно считать _0 = 1, что обычно и делается.

Соответствующую теорему и называют собственно (прямой) теоремой Куна-Таккера. Теорема 198 (Прямая теорема Куна-Таккера, необходимое условие оптимальности):

Пусть функции f( ), g1( ), . . . , gn( ) дифференцируемы, и?x - решение задачи (?), такое что

X 2 intX и выполнено условие регулярности Куна-Таккера.

Тогда существуют множители Лагранжа _j > 0, j = 1, . . . ,m, такие что при _0 = 1 выполнены

следующие соотношения:

0, i = 1, . . . , n

Несложно переформулировать эту теорему для задач (??) и (???). Здесь требуются такие же мо-

дификации условий Куна-Таккера, как и в теореме Джона.

0, i = 1, . . . , n

можно переписать в виде:

Это соотношение показывает, что в точке оптимума градиент целевой функции является линейной ком-

бинацией антиградиентов ограничений, причем все коэффициенты этой линейной комбинации неотри-

цательны. Рис. 17.1 иллюстрирует это свойство. Интуитивно, идея этого свойства состоит в том, что

если бы какой-нибудь коэффициент линейной комбинации был отрицательным, то можно было бы

увеличить значение целевой функции, двигаясь вдоль этого ограничения. Один из вариантов обратной теорема Куна-Таккера утверждает, что при вогнутости функций

f( ), {gk( )} выполнение этих условий в допустимом решении?x (т. е. точке, удовлетворяющей огра-

ничениям) при некоторых множителях Лагранжа, удовлетворяющих требованиям прямой теоремы,

гарантирует, что?x является решением задачи.

Теорема 199 (Обратная теорема Куна-Таккера /достаточное условие оптимальности/):

Пусть f( ) - дифференцируемая вогнутая функция, g1( ), . . . , gn( ) - дифференцируемые

квазивогнутые функции, множество X выпукло и точка?x допустима в задаче (?), причем?x 2

Пусть, кроме того, существуют множители Лагранжа _j > 0, j = 1, . . . ,m, такие что при

0 = 1 выполнены следующие соотношения:

0, i = 1, . . . , n

Тогда?x - решение задачи (?).

Теорему можно очевидным образом переформулировать для задач (??) и (???). Для задачи (???)

ограничения в виде равенств могут быть только линейными (это связано с тем, что ограничение в виде

равенства, gj(x) = 0, следует представить с помощью двух ограничений в виде неравенств, gj(x) > 0

и?gj(x) > 0, каждое из которых задается квазивогнутой функцией; такое может быть только если

ограничение линейное).

В еще одном варианте достаточного условия оптимальности предположение о вогнутости целевой

функции заменяется на предположение о квазивогнутости с добавлением условия rf(?x) 6= 0.